SKEDSOFT

NONOPTIMALITY OF THE EDF AND THE LST ALGORITHMS
It is natural to ask here whether the EDF and the LST algorithms remain optimal if preemption is not allowed or there is more than one processor. Unfortunately, the answer is no. The fact that the EDF and the LST algorithms are optimal only when preemption is allowed is illustrated by the example in Figure 4–6. The system shown in this figure has three independent, nonpreemptable jobs J1, J2, and J3. Their release times are 0, 2 and 4, respectively, and are indicated by the arrows above the schedules. Their execution times are

3, 6, and 4; and their deadlines are 10, 14, and 12, respectively. Figure 4–6(a) shows the schedule produced by the EDF algorithm. In particular, 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 because preemption is not allowed. As a result, J3 misses its deadline. It is easy to see that the LST algorithm would produce the same infeasible schedule. The fact that these three jobs can meet their deadlines is demonstrated by the feasible schedule in Figure 4–6(b). At time 3 when J1 completes, the processor is left idle, even though J2 is ready for execution. Consequently, when J3 is released at 4, it can be scheduled ahead of J2, allowing both jobs to meet their deadlines.

We note that the schedule in Figure 4–6(b) cannot be produced by any priority-driven scheduling algorithm. By definition, a priority-driven algorithm never leaves a processor idle when there are jobs ready to use the processor. This example illustrates the fact that not only nonpreemptive EDF and LST algorithms are not optimal, but also no nonpreemptive prioritydriven algorithm is optimal when jobs have arbitrary release times, execution times, and deadlines. The example in Figure 4–7 shows that the EDF algorithm is not optimal for scheduling preemptable jobs on more than one processor. The system in this figure also contains three jobs, J1, J2, and J3. Their execution times are 1, 1, and 5 and their deadlines are 1, 2, and 5, respectively. The release times of all three jobs are 0. The system has two processors. According to the EDF algorithm, J1 and J2 are scheduled on the processors at time 0 because they have higher priorities. The result is the schedule in Figure 4–7(a), and J3 misses its deadline.

On the other hand, an algorithm which assigns a higher priority to J3 in this case can feasibly schedule the jobs. An example of such algorithms is the LST algorithm. The slacks of the J1, J2, and J3 in Figure 4–7 are 0, 1, and 0, respectively. Hence, this algorithm would

produce the feasible schedule in Figure 4–7(b). Unfortunately, the LST algorithm is also not optimal for scheduling jobs on more than one processor.