multiprocessor scheduling

Question 1

explain and compare the multiprocessor scheduling technique

Answer 1

Global scheduling :
aims to find a general strategy to schedule job where jobs are allowed to migrate such that job starts its execution in processor one and finish it in processor 2

partitioned scheduling
aims to find a strategy to partition tasks among processors where job are not allowed to migrate

Question 2

why Partitioned and Global Scheduling are Incomparable

Answer 2

since there are tasks that Global scheduling can do, which partition scheduling can not do for example
U(t1) > 1
and vise versa

Question 3

Compare RM and EDF in the context of partitioning

Answer 3

For RM the bound is not tight enough U(𝜏) < n𝜋 (2 1/n𝜋 – 1) which leads to losing 50% of the platform capacity

For EDF it’s way more optimal where the condition of schedulability is limited to U(t) <1
the requirement FFDU are :
u(t) <=(m+1)/2 and Umax <=1

Question 4

what are the scheduling anomalies

Answer 4

is any intuitive positive change that may lead to jeopardizing the system schedulability,
intuitive positive change might be anything that leads to decreasing the utilization such that increasing the time factor or execution time ..etc

Question 5

what is the necessary condition for the schedulability of an implicit deadline system

Answer 5

Any Periodic Implicit-Deadline System is feasible iff U(𝜏) ≤ m and Umax(𝜏) ≤ 1

Question 6

Explain EDF^k

Answer 6

it is a modification of EDF to fit into smaller numbers of processors such that :
for I < K-1 jobs of tasks are given high priority
for I > K-1 jobs of taski are scheduled using pure EDF

Question 7

provide a sufficient condition for the schedulability of sporadic multi-p arbitrary deadline system

Answer 7

we can rely on the density;
density 𝜆i consists of Ci/ min(Ti, DI)
hence the schedulability test is
𝜆sum(𝜏) ≤ m and 𝜆max(𝜏) ≤ 1

Question 8

provide a sufficient condition for the schedulability of EDF^k

Answer 8

U(T) < m(m-1) Umax

however, for EDF this result is quite pessimistic since it requires a big number of processors

Question 9

explain the condition for the sporadic implicit-deadline system is schedulablbility on m processors
using edf(k)
i

Answer 9

Informally, EDF^k requires processors such that
T1 to P1 …..Tk-1 toPk-1 and then assigns the rest such that
Tk to PK …Tn to Pn