Tutorial 2
Scheduling
Computational Foundation of Cyber Physical System 1
Real Time Scheduling: Rate Monotonic
Q. Verify the schedulability and construct the schedule according to the RM policy for the following
set of periodic tasks. Here Ci and Ti are the execution time and periods respectively.
Ans.
Utilization (U) = 2/6 + 2/8 + 2/12 = 0.75
Processor utilization upper bound Umax = n(21/n - 1) = 0.78
U < Umax The task set is RM schedulable
Computational Foundation of Cyber Physical System 2
Real Time Scheduling: Rate Monotonic
Q. Write down the RM schedule for the given task set.
Hyper-period = lcm (6,8,12) = 24
Task Set
RM Schedule
RM Schedule: Ƭ11 Ƭ21 Ƭ31 Ƭ12 Ƭ22 Ƭ13 Ƭ32 Ƭ23 Ƭ14
Computational Foundation of Cyber Physical System 3
Real Time Scheduling: Rate Monotonic
Consider the following set of tasks
Tasks Ci Ti
τ1 2 5
τ2 4 7
Utilization (U) = 2/5 + 4/7 = 0.97
Processor utilization upper bound Umax = n(21/n - 1) = 0.83
U > Umax The task set may not be RM schedulable
Lets check !!
Computational Foundation of Cyber Physical System 4
Real Time Scheduling: Earliest Deadline First (EDF)
Hyper-period = lcm (5, 7) = 35
Tasks Ci Ti
τ1 2 5
τ2 4 7
Computational Foundation of Cyber Physical System 5
Exercise - 1
Q. Check if the following task set is RM schedulable? If not, is it EDF
schedulable?
Tasks Execution Time Period
T1 20 100
T2 30 150
T3 90 200
Computational Foundation of Cyber Physical System 6
Real Time Scheduling
Q. Check if the following task set is RM schedulable?
Tasks Execution Time Period
T1 20 100
T2 30 150
T3 90 200
Ans.
Utilization (U) = 20/100 + 30/150 + 90/200 = 0.85
Processor utilization upper bound Umax = n(21/n - 1) = 0.78
U > Umax RM schedulable may not be feasible
Computational Foundation of Cyber Physical System 7
Real Time Scheduling
Hyper-period = LCM(100,150,200) = 600 Tasks Execution Period
Time
T1 T1 20 100
T2 30 150
T3 90 200
T2
T3
0 50 100 150 200 250 300 350 400 450 500 550 600
RM Schedule: T11 T21 T31 T12 T31 T22 T31 T13 T32 T14 T23 T32 T15 T33 T24 T33 T16 T33
Computational Foundation of Cyber Physical System 8
LDF Scheduling
Given the precedence graph in following figure and the following table of task execution times (Ci) and deadlines
(Di), determine a Latest Deadline First (LDF) schedule.
Schedule: J1 J2 J3 J5 J4 J6 J7 J8
Computational Foundation of Cyber Physical System 9
LDF Scheduling
Schedule: J1 J2 J3 J5 J4 J6 J7 J8
Computational Foundation of Cyber Physical System 10
EDF* Scheduling
All tasks arrive at t=0. They all have
deadline d=20. Their execution times are
A
given below. Determine the EDF* schedule.
C E
D F
Computational Foundation of Cyber Physical System 11
EDF* Scheduling
A
C E
d’E = 20
d’F = 20
B
d’G = 20
d’C = min(20, 20-2,20-5) =15
D F d’D = min(20, 20-5,20-1) =15
d’B = min(20, 15-4,15-3) =11
d’A = min(20, 15-4) =11
EDF* schedule: A,B,C,D,E,F,G
G
Computational Foundation of Cyber Physical System 12
Exercise – 2
Q. Consider two tasks to be scheduled periodically on a single processor using Rate
Monotonic (RM) scheduling policy. Task T1 has periodicity p1 = 4 and task T2 has periodicity
p2 = 6. If execution time of T1 is e1 = 1
a. what will the execution time of T2 to get a near maximum processor utilization?
Computational Foundation of Cyber Physical System 13
Exercise – 2
Q. Consider two tasks to be scheduled periodically on a single processor using Rate
Monotonic (RM) scheduling policy. Task T1 has periodicity p1 = 4 and task T2 has periodicity
p2 = 6. If execution time of T1 is e1 = 1
a. what will the execution time of T2 to get a near maximum processor utilization?
𝑒1 𝑒2 1 𝑒2
Sol. + ≤1⇒ + ≤ 1 ⇒ 𝑒2 ≤ 4.5
𝑝1 𝑝2 4 6
If e2 = 4.5 => Not RM schedulable (Check)
If e2 = 4 => RM schedulable
Computational Foundation of Cyber Physical System 14
Exercise – 2
Q. Consider two tasks to be scheduled periodically on a single processor using Rate
Monotonic (RM) scheduling policy. Task T1 has periodicity p1 = 4 and task T2 has periodicity
p2 = 6. If execution time of T1 is e1 = 1
a. What will the execution time of T2 to get a near maximum processor utilization?
b. Considering context switch overhead as 0.2 time units, comment on how it will affect
the schedule
Computational Foundation of Cyber Physical System 15
Exercise – 2
Q. Consider two tasks to be scheduled periodically on a single processor using Rate
Monotonic (RM) scheduling policy. Task T1 has periodicity p1 = 4 and task T2 has periodicity
p2 = 6. If execution time of T1 is e1 = 1
a. What will the execution time of T2 to get a near maximum processor utilization?
b. Considering context switch overhead as 0.2 time units, comment on how it will affect
the schedule
Sol. Not RM schedulable
Misses deadline (T2 finishes at 6.2)
T11 T21 T12 T21
0 2 4 6 8 10 12
Computational Foundation of Cyber Physical System 16
Exercise – 2
Q. Consider two tasks to be scheduled periodically on a single processor using Rate
Monotonic (RM) scheduling policy. Task T1 has periodicity p1 = 4 and task T2 has periodicity
p2 = 6. If execution time of T1 is e1 = 1
a. What will the execution time of T2 to get a near maximum processor utilization?
b. Considering context switch overhead as 0.2 time units, comment on how it will affect
the schedule
c. Had we used Earliest Deadline First (EDF) scheduling policy instead of RM with the same
set-up, how would context switch have affected the schedule?
Computational Foundation of Cyber Physical System 17
Exercise – 2
Q. Consider two tasks to be scheduled periodically on a single processor using Rate
Monotonic (RM) scheduling policy. Task T1 has periodicity p1 = 4 and task T2 has periodicity
p2 = 6. If execution time of T1 is e1 = 1
a. What will the execution time of T2 to get a near maximum processor utilization?
b. Considering context switch overhead as 0.2 time units, comment on how it will affect
the schedule
c. Had we used Earliest Deadline First (EDF) scheduling policy instead of RM with the same
set-up, how would context switch have affected the schedule?
Sol. EDF schedulable
T11 T21 T12 T22 T13
0 2 4 6 8 10 12
Computational Foundation of Cyber Physical System 18
