Real Time Systems: Notes |
Optimal here means the algorithm finds a feasible schedule if-and-only-if a feasible schedule exists. It does not take into account other notions of merit, such as jitter and robustness.
The following pictures illustrate the basic idea of the proof that (preemptive) EDF scheduling is optimal.
We will show, later in this series of examples, that EDF scheduling is not optimal if we relax the restriction to there being a single processor or the restriction that scheduling is preemptive.
We will see later in the course that this is nearly the most general case where any kind of optimal scheduling is practical.
Suppose EDF is not optimal. In that case, there must be a non-EDF schedule in which there are no missed deadlines (i.e., the schedule is feasible), but the EDF schedule causes deadlines to be missed. Find the first place in the feasible schedule where it violates the EDF rule. That is, find the first interval of time in which a job T_{b} that does not have the earliest deadline executes (shown in blue in the diagrams below). Let T_{r} be the job that should execute in this time interval according to EDF. Find the next block of time in which T_{r} (shown in red) does execute. There are two possible cases, depending on whether the first interval or the second interval is shorter.
If the first interval is shorter, swap the work from the first interval into the second interval.
If the second interval is shorter, swap the work from the second interval into the first interval.
Either way, both jobs still complete before their deadlines.
The above example shows that nonpreemptive EDF scheduling is not optimal.
The arrows go from the deadlines back to the release times, with the head at the release time. That is, in the first schedule the red job arrives while the yellow job is running, and the blue job arrives while the red job is running.
To complete all three jobs within their deadlines, the processor must be kept idle to wait for the blue job.
The above example shows that EDF is not optimal for multiprocessor scheduling.
On the other hand, we will see later that it is not necessarily a bad choice, either.
Can you modify the non-preemptive scheduling example to also demonstrate an anomaly, for single-processor scheduling?
The following are some other well-inown deadline-based scheduling policies.
The schedule shown is EDF. What would the LST schedule be?
EDF, LRT, and LST are all optimal under the following assumptions:
What are the advantages of EDF over LRT and LST?
T. P. Baker. ($Id$) |