18. Multi-Resource Scheduling

Question 1

Partitioned Multi-Processor Scheduling

Answer 1

• Consider parameters and assign priorities to tasks offline
• Apply single-core scheduling to each core independently

Question 2

First Fit on RM (RM-FF) and EDF (EDF-FF)

Answer 2

• Start with the first processor P_1 and use the schedulability test to check if P_1 is still schedulable after adding task tau_i
• If the test fails, repeat the assignment attempt on P_2

Question 3

RM-FF Schedulability Test

Answer 3

• A task set is schedulable on N processors under RM if the sum of the ratios of WCET / period <= N * (sqrt{2} - 1)

Question 4

EDF-FF Schedulability Test

Answer 4

• A task set is schedulable on N processers under EDF if the sum of the ratios of WCET / period <= (beta * N + 1) / (beta + 1)
• beta = floor(1 / max_k(C_k / T_k))

Question 5

Global Multi-Processor Scheduling

Answer 5

• Rank all of the tasks/jobs in the shared ready queue online
• Select top N to run on the N available processors

Question 6

Global EDF

Answer 6

• Invocation: at the completion or arrival of a job (preemptive)
• Policy: online, rank jobs by deadline and select the N tasks with the closest deadlines
• EDF is not optimal in the multi-processor case