Figure 4–5 gives an example. In the precedence graph, the number next to the job name is the execution time of the job. Its feasible interval is given by the range of time next to its execution time. The latest deadline among all jobs is 8. Hence time starts at 8 and goes backwards to 0. At time 8, J2 is “ready” and is scheduled. At time 7, J3 is also “ready” to be scheduled, but because J2 has a later release time, it has a higher priority. Consequently, J2 is scheduled from 7 to 6. When J2 “completes” at time 6, J1 is “ready.” However, J3 has a higher priority and is, therefore, scheduled from 6 to 4. Finally J1 is scheduled from 4 to 1. The result is a feasible schedule.
The following corollary states that the LRT algorithm is also optimal under the same conditions that the EDF algorithm is optimal. Its proof follows straightforwardly from the proof of Theorem 1.
COROLLARY 2. When preemption is allowed and jobs do not contend for resources, the LRT 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 feasible schedules of J exist.
Another algorithm that is optimal for scheduling preemptive jobs on one processor is the Least-Slack-Time-First (LST) algorithm (also called the Minimum-Laxity-First (MLF) algorithm) [LeWh, Mok]. At any time t , the slack (or laxity) of a job with deadline at d is equal to d − t minus the time required to complete the remaining portion of the job. Take the job J1 in Figure 4–5 as an example. It is released at time 0, its deadline is 6, and its execution time is 3. Hence, its slack is equal to 3 at time 0. The job starts to execute at time 0. As long as it executes, its slack remains at 3, because at any time t before its completion, its slack is 6 − t − (3 − t). Now suppose that it is preempted at time 2 by J3, which executes from time 2 to 4. During this interval, the slack of J1 decreases from 3 to 1. (At time 4, the remaining execution time of J1 is 1, so its slack is 6 − 4 − 1 = 1.)
The LST algorithm assigns priorities to jobs based on their slacks: the smaller the slack, the higher the priority. The following theorem states that the LST algorithm is also optimal.
THEOREM 3. When preemption is allowed and jobs do not contend for resources, the LST (MLF) 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 feasible schedules of J exist.
While the EDF algorithm does not require any knowledge of the execution times of jobs, the LST algorithm does. This is a serious disadvantage. As discussed earlier, the actual execution times of jobs are often not known until the jobs complete. Obviously, it is impossible for us to calculate the actual amounts of slack under this circumstance.We typically calculate the slack of each job based on its maximum execution time ei when the range [ei−, ei ] of execution time ei of every job is relatively small. Furthermore, we require that the maximum (and sometimes even the actual) execution time of each sporadic or aperiodic job become known upon its arrival since this knowledge is needed for slack computation.
