Deadline Scheduling

Preeemptive Earliest-Deadline First (EDF) Scheduling

• a priority-based preemptive scheduling policy
• job with earliest (absolute) deadline has highest priority
• does not require knowledge of execution times
• is known to be an optimal policy for a single processor

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 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.

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

• another priority-based preemptive scheduling that makes use of deadlines
• job with least slack time has highest priority
• initial slack (or laxity) = relative deadline - total execution time
• dynamic slack (or laxity) = reamining time todeadline - remaining execution time
• requires knowledge of execution times
• needs interpretation of when scheduling decisions must be made
• can degenerate into time-slicing if jobs have equal slack

EDF vs. LST Scheduling

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

LST Scheduling Example

Latest Release Time Scheduling

• schedule is built from right to left (in reverse chronological order)
• deadline treated as release time
  release time treated as deadline
• delays each job long as possible and still make deadline
• requires accurate bounds on execution times
• not much good for on-line scheduling

LRT Scheduling Example

Optimal Scheduling Results

EDF, LRT, and LST are all optimal under the following assumptions:

• single processor
• processor preemption is allowed
• no contention for (non-preemptable) resources
• arbitrary release times
• arbitrary deadlines

What are the advantages of EDF over LRT and LST?