Real Time Systems: Notes

Deadline Scheduling


Preeemptive Earliest-Deadline First (EDF) Scheduling

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.

Proof that EDF is Optimal

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 Tb that does not have the earliest deadline executes (shown in blue in the diagrams below). Let Tr be the job that should execute in this time interval according to EDF. Find the next block of time in which Tr (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.

Nonpreemptive EDF is not optimal

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.

Dual CPU EDF Anomaly

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.

Least Slack Time Scheduling

EDF vs. LST Scheduling

The schedule shown is EDF. What would the LST schedule be?

LST Scheduling Example

Latest Release Time Scheduling

In the figure above scheduling decisions are made only at job arrivals and completions. What would happen if the LST rule were applied continually. For example, what happens at the point where the red and blud lines cross, indicating equal slack?

LRT Scheduling Example

Optimal Scheduling Results

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$)