Page 79 - DCAP608_REAL TIME SYSTEMS

Real Time Systems

Notes
Figure 7.5: Non-optimality of the EDF and LST Algorithm

Source: ansari.szabist-isb.edu.pk/RTS/RTS0508.ppt
The system shown in the figure has three independent, non-preemptible jobs J1, J2 and J3. The
explanation of the figure is as follows:
 The release times are 0, 2 and 4 and execution times are 10, 14 and 12.
 (a) shows the schedule produced by the EDF algorithm
 When J1 completes at time 3, J2 has already been released but not J3. Hence J2 is scheduled.

 When J3 is released at time 4, J2 is executing.
 Even though J3 has an earlier deadline and hence a higher priority, it must wait until J2
completes s there is no preemption

 Thus J3 misses its deadline.
 (b) provides a feasible schedule.
 At time 3 when J1 completes, the processor is left idle, even though J2 is ready for execution.

 When J3 is released at 4, it can be scheduled ahead of J2, allowing both to meet deadline.
 (b) Can never be provided by a priority-driven scheduling algorithm as they never leave
a processor idle when jobs are ready.

 This figure shows that the EDF algorithm is not optimal for scheduling preemptible jobs
on more than one processor.
 J1, J2 and J3 have execution times 1, 1, 5 and deadlines 1, 2, 5 respectively and release
time 0.
 On two processors, J1 and J2 are scheduled on the processors at time 0 because of higher
priority so J3 misses deadline.

 An algorithm that could assign higher priority to J3 could do the job. (like LST)

74 LOVELY PROFESSIONAL UNIVERSITY