Optimality Of Effective-deadline-first (Edf) And Least-slack-time-first (Lst) Algorithms

OPTIMALITY OF THE EDF AND LST ALGORITHMS: A way to assign priorities to jobs is on the basis of their deadlines. In particular, the earlier the deadline, the higher the priority. The priority-driven scheduling algorithm based on this priority assignment is called the Earliest-Deadline-First (EDF) algorithm. This algorithm is important because it is optimal when used to schedule jobs on a processor as long as preemption is allowed and jobs do not contend for resources. This fact is stated formally below.

THEOREM 1. When preemption is allowed and jobs do not contend for resources, the EDF algorithm can produce a feasible schedule of a set J of jobs with arbitrary release times and deadlines on a processor if and only if J has feasible schedules.

Proof. The proof is based on the following fact: Any feasible schedule of J can be systematically transformed into an EDF schedule (i.e., a schedule produced by the EDF algorithm). To see why, suppose that in a schedule, parts of Ji and Jk are scheduled in intervals I1 and I2, respectively. Furthermore, the deadline di of Ji is later than the deadline dk of Jk, but I1 is earlier than I2 as shown in Figure 4–4.

There are two cases. In the first case, the release time of Jk may be later than the end of I1. Jk cannot be scheduled in I1; the two jobs are already scheduled on the EDF basis in these intervals. Hence, we need to consider only the second case where the release time rk of Jk is before the end of I1; without loss of generality, we assume that rk is no later than the beginning of I1.

To transform the given schedule, we swap Ji and Jk . Specifically, if the interval I1 is shorter than I2, as shown in Figure 4–4, we move the portion of Jk that fits in I1 forward to I1 and move the entire portion of Ji scheduled in I1 backward to I2 and place it after Jk . The result is as shown in Figure 4–4(b). Clearly, this swap is always possible. We can do a similar swap if the interval I1 is longer than I2 :We move the entire portion of Jk scheduled in I2 to I1 and place it before Ji and move the portion of Ji that fits in I2 to the interval. The result of this swap is that these two jobs are now scheduled on the

EDF basis. We repeat this transformation for every pair of jobs that are not scheduled on the EDF basis according to the given non-EDF schedule until no such pair exists.

The schedule obtained after this transformation may still not be an EDF schedule if some interval is left idle while there are jobs ready for execution but are scheduled in a later interval (e.g., as in the schedule in Figure 4–4(b).) We can eliminate such an idle interval by moving one or more of these jobs forward into the idle interval and leave the interval where the jobs were scheduled idle. This is clearly always possible. We repeat this process if necessary until the processor never idles when there are jobs ready for execution as in Figure 4–4(c).

That the preemptive EDF algorithm can always produce a feasible schedule as long as feasible schedules exist follows straightforwardly from the fact that every feasible schedule can be transformed into a preemptive EDF schedule. If the EDF algorithm fails to produce a feasible schedule, then no feasible schedule exists. (If a feasible schedule were to exist, it could be transformed into an EDF schedule, which contradicts the statement that the EDF algorithm fails to produce a feasible schedule.)

When the goal of scheduling is to meet deadlines, there is no advantage to completing any job sooner than necessary. We may want to postpone the execution of hard real-time jobs for some reason (e.g., to enable soft real-time jobs, whose response times are important, to complete earlier). For this reason, we sometimes also use the latest release time (LRT) algorithm (or reverse EDF algorithm). This algorithm treats release times as deadlines and deadlines as release times and schedules the jobs backwards, starting from the latest deadline of all jobs, in “priority-driven” manner, to the current time. In particular, the “priorities” are based on the release times of jobs: the later the release time, the higher the “priority.” Because it may leave the processor idle when there are jobs ready for execution, the LRT algorithm is not a priority-driven algorithm.