Page 124 - DCAP608_REAL TIME SYSTEMS

Unit 12: Priority-driven Scheduling of Periodic Tasks

 When the first jobs J1, 1, J2, 1 and J3, 1 are rele3ased at time 0, their slacks are 1.2, 3.5 and 3.6 Notes
respectively.

 J1, 1 has the highest priority, and J3, 1 has the lowest.
 At time 0.8, J1, 1 completes and J2, 1 executes.
 When J1, 2 is released at time 2, its slack is 1.2, while the slacks of J2, 1 and J3, 1 become 2.7
and 1.6.

 Hence J1, 2 has the highest priority, but now J3, 1 has a higher priority than J2, 1.
 We can see that the EDF algorithm is a job-level fixed priority algorithms and LST is a job-
level-dynamic priority algorithms.

 In this version of LST, the scheduling decisions are made only at the times when jobs are
released or completed, thus we can call it non-strict LST.

 If the scheduler were to follow the LST rule strictly, it would have to monitor the slacks of
all ready jobs and compare them with the slack of the execution job.
 It would re-assign the priorities to jobs whenever their slacks change relative to each
other.
 J1, 1 has the highest priority, and J3, 1 has the lowest.
 At time 0.8, J1, 1 completes and J2, 1 executes.

 When J1, 2 is released at time 2, its slack is 1.2, while the slacks of J2, 1 and J3, 1 become 2.7
and 1.6.
 Hence J1, 2 has the highest priority, but now J3, 1 has a higher priority than J2, 1.

 We can see that the EDF algorithm is a job-level fixed priority algorithms and LST is a job-
level-dynamic priority algorithms.
 In this version of LST, the scheduling decisions are made only at the times when jobs are
released or completed, thus we can call it non-strict LST.
 If the scheduler were to follow the LST rule strictly, it would have to monitor the slacks of
all ready jobs and compare them with the slack of the execution job.

 It would re-assign the priorities to jobs whenever their slacks change relative to each
other.
 Consider the diagram below, the scheduler would find that at time 2.7, the slack of J2, 1
becomes (5-2.7-1.2) = 1.1, the same as that of J1, 2.
 It would schedule the two ready jobs in a round-robin manner until J1, 2 completes.
 The run-time overhead of the strict LST algorithms includes the time required to monitor
and compare the slacks of all ready jobs as time progresses.
 According to our classification, FIFO and LIFO algorithms are also dynamic priority
algorithms.
 Suppose we have three tasks T1 = (0, 3, 1, 3), T2 = (0.5, 4, 1, 1), T3 = (0.75, 7.5, 2, 7.5).
 If scheduled on FIFO basis J1, 1 has higher priority than J2, 1 which has higher priority
than J3, 1.
 Later J1, 4, J2, 3 and J3, 2 are released at times 9, 8.5 and 8.25, and T3 has the highest priority
and T1 lowest.

LOVELY PROFESSIONAL UNIVERSITY 119