Scheduling (RM and EDF)

Question 1

What is hyperperiod?

Answer 1

Is the minimum interval of time after which the schedule repeats itself.

Question 2

What is job response time?

Answer 2

It is the time (measured from the release time) at which the job is terminated.

Question 3

What is task response time?

Answer 3

It is the maximum response time among all the jobs.

Question 4

What is the processor utilization factor?

Answer 4

Ui = sum(i=1, i<n, Ci/Ti)

Question 5

How the rate monotonic (RM) scheduling algorithm works?

Answer 5

RM scheduling algorithm is a simple rule that assign priorities to tasks according to their request rates. Tasks with higher requests rates (shorter periods) will have higher priority. It is a fixed-priority assignment.

Question 6

What are the Liu and Layland assumptions?

Answer 6

1. Tasks are periodic with deadlines equal to period (Di=Ti)
2. Tasks do not suspend themselves
3. Tasks have bounded execution time (worst case execution time)
4. Tasks are independent
5. Scheduling overhead is negligible

Question 7

How the priorities are assigned by RM algorithm?

Answer 7

Shorter period means higher priority.

Question 8

What is the sufficient condition for scheduling in RM?

Answer 8

sum(i=1, i<= n * (2^[1/n] - 1)

Question 9

Is RM an optimal scheduling policy? Explain.

Answer 9

Among all static priority assignments, RM is an optimal scheduling policy. It means that if exist another static priority assignment that can make a task set schedulable, RM will schedule all tasks as well.

Question 10

How does the priority assignment on Earlier Deadline First work?

Answer 10

Priorities are dynamic, it means that tasks priority may change during execution time. Tasks with closer deadline receive a higher priority.

Question 11

How the EDF scheduling algorithm works?

Answer 11

The task in the ready queue with the higher priority (closer deadline) is executed. Sort priorities such that tasks with closer deadlines get higher priority at run-time.

Question 12

Which is the schedulability test in EDF when D=T? Is it necessary or sufficient condition?

Answer 12

sum(i=1, i<= 1

It is necessary and sufficient condition when D=T

Question 13

Under which condition does EDF is optimal?

Answer 13

EDF is optimal when utilization is below 1. It performs badly under overload.

Question 14

When is necessary to use exact analysis schedulability test?

Answer 14

When deadline is different from period (D<T)

Question 15

How to do the exact analysis (response time analysis)?

Answer 15

For the highest priority test, Ri = Ci (since it is not going to be preempted.

For all the other ones:
Ri = Ci + sum { ceiling[Ri/Tj] * Cj , for all j in hp(i)}

*hp(i) is the set of tasks with priority higher than task i
Formula is recursive until Ri is stable.

Question 16

Which is the schedulability test in EDF when D<T? Is it necessary or sufficient condition?

Answer 16

g(0,L) < L

G(0,L) = sum(i=1, i= sum (i=1, i<=n, { botton[ (L-Di) / Ti ] + 1 } * Ci )