EDF, Utilization Bounds, and Schedulability Tests

Rate-monotonic assigns priorities by period: the shortest period gets the highest priority. It is optimal among fixed-priority assignments, and its guarantee is conservative: a set of periodic tasks is schedulable if total utilization is at most n(2^(1/n) − 1), which approaches ln 2 ≈ 0.693 as n grows. That means a rate-monotonic system may reject a task set that would in fact meet all its deadlines, because the test is sufficient rather than necessary.

Earliest-deadline-first abandons fixed priorities. At every instant it runs the ready task with the nearest absolute deadline, so a task’s effective priority changes as time passes. On a single processor with preemption, EDF is optimal: if any scheduling algorithm can meet all deadlines for a task set, EDF can. The utilization bound rises from 0.693 to 1.0. The price is that the guarantee is fragile in ways the fixed-priority bound is not, and those fragilities are what a real implementation has to handle.

The optimality argument

The proof is an exchange argument, and it is worth following because it shows exactly which assumptions the optimality depends on.

Suppose a schedule meets all deadlines. Consider the first instant at which it differs from EDF: the schedule runs task A while EDF would run task B, and B’s deadline is earlier than A’s. Swap the two: run B now and A at the time B was going to run. B finishes earlier than before, so it still meets its deadline. A finishes at the time B would have finished, which is earlier than A’s original completion time, so A still meets its deadline. No other task is affected, because the interval is occupied by one task either way. The swapped schedule still meets all deadlines and agrees with EDF for one more instant. Repeating the exchange transforms any feasible schedule into the EDF schedule without violating any deadline.

The argument requires that preemption be free and that the swap not change any task’s release pattern. Both assumptions are approximations. Preemption has a cost, so an EDF schedule that preempts at every release is not the same as the idealised one; the exchange argument’s conclusion is that EDF is optimal among schedules that also pay the same preemption cost, which is a weaker statement. And a task whose next release depends on its completion time, as with a self-suspending or event-driven task, breaks the argument, because moving its execution moves its releases.

/* EDF pick over a set of periodic tasks. Absolute deadline is stored per
   activation; a heap keyed on it gives O(log n) insertion and extraction. */
struct task {
    uint64_t deadline;      /* absolute, in scheduler time units */
    uint64_t period, wcet;  /* relative, same units */
};

struct task *edf_next(struct heap *ready)
{
    struct task *t = heap_min(ready);
    if (t && t->deadline <= now())
        report_deadline_miss(t);   /* late already; policy choice follows */
    return t;
}

/* Called at each activation and each completion. */
void edf_advance(struct task *t)
{
    t->deadline += t->period;      /* absolute, not relative */
    heap_insert(ready, t);
}

The t->deadline += t->period line encodes a choice that matters: advancing the deadline from the previous deadline rather than from the current time keeps a late task from accumulating slack. If the deadline were recomputed as now() + period, a task that overran would silently shift its future deadlines and the system would drift out of phase with the analysis that proved it schedulable. Real implementations usually keep the absolute deadline sequence and treat a missed deadline as an event to report, not as a reason to re-base the schedule.

Utilization, density, and the difference

For a task with worst-case execution time C and period T, utilization is C/T and density is C/min(T, D) where D is the relative deadline. When deadlines equal periods the two coincide. When deadlines are shorter than periods, density exceeds utilization and the relevant test changes.

The utilization test, the sum of C/T ≤ 1, is necessary for any schedule to exist on one CPU, because no algorithm can execute more than one unit of work per unit of time. It is sufficient for EDF only when deadlines equal periods. With D < T, a set can have utilization well below 1 and still be unschedulable, because all the work of several tasks can land in the same short window. The density test, sum of C/min(T, D) ≤ 1, is the sufficient condition in that case, and it is strictly stronger.

The distinction matters in practice because the two tests fail for different reasons. Utilization is a property of the demand rates alone: if the sum of C/T exceeds one, no assignment of phases can help, because the work arrives faster than the processor can retire it. Density is a property of the demand within a window: with D < T the same average demand can pile up if several tasks release together, and the density test charges each task’s worst-case execution against its own deadline rather than against its period. The price of that pessimism is that density can exceed one while the average is comfortably below it, in which case the set may still be schedulable, since the exact test is the processor demand criterion over all intervals rather than a single ratio. Phase offsets are the usual remedy: spreading releases so that the short-deadline tasks do not all arrive at once reduces the demand in every window without changing any task’s parameters.

Why EDF is fragile

The optimality of EDF is a statement about a static, known task set. Its behaviour under perturbation is worse than rate-monotonic’s, and the asymmetry is the main practical argument against it.

Consider a task set at utilization 0.95 that passes the EDF test. A single task overruns its worst-case execution time by a small amount. Under EDF, the overrun delays every task with a later deadline, which pushes their completions later, which in a system with periodic releases means the next activation arrives while the previous is still running, and the backlog compounds. The system does not degrade gracefully; it enters a state where deadlines are missed continuously and the queue of ready work grows without bound. This is the “domino effect”, and it is a consequence of EDF using all available slack by design: there is no reserve to absorb an overrun.

Rate-monotonic behaves differently. If a low-priority task overruns, the tasks above it are unaffected, because their priorities are fixed and the overrun only delays things below it. The system loses the low-priority task and keeps the high-priority ones. That is a partial failure rather than a total one, and for a system with a safety requirement, partial failure is often worth the lower utilization bound.

The standard mitigation for EDF is a server that isolates the overrunning task, charging it against a budget and throttling it when the budget is exhausted. A task that overruns then damages only its own execution, and the rest of the system continues on schedule. That is the mechanism described in Deadline Servers and Admission Control, and it converts EDF’s fragility from a system-wide property into a per-task one.

The second fragility is the deadline-miss response. When EDF cannot meet all deadlines it does not fail in a predictable order. The task that misses is whichever has the earliest deadline at the moment the processor falls behind, which can be any task, and the set of tasks that miss can change from period to period. A system that must shed load in a defined order, dropping low-value work first, needs the shedding to be explicit, because EDF’s implicit order is by deadline and deadlines are not values.

Multiprocessor EDF and the anomaly

On m identical processors, EDF is not optimal. The counterexample is the Dhall effect: a task set whose total utilization is only slightly above 1 can miss a deadline on m processors, because a single task with a very long period and a very large execution time — but a deadline earlier than its period — forces EDF to schedule it and delay all shorter-deadline tasks until their deadlines pass. The total work is far below the machine’s m processors of capacity, yet EDF fails where a partitioned or a priori fixed assignment would not. The intuitive reading is that a global scheduler offers no utilization bound that grows with m; the worst case degrades with the ratio of periods, and the only safe guarantee is to reserve capacity conservatively and treat the global analysis as an upper bound rather than a target.

The cause is the same domino effect multiplied across processors: a task delayed on one processor can be migrated, and the migration itself costs time, and the delay propagates. Partitioned EDF, which assigns each task permanently to one processor and runs EDF per processor, restores the single-processor analysis but reintroduces a bin-packing problem: deciding the assignment is NP-hard in general, and a bad assignment can leave one processor overloaded while another has slack that cannot be used because the tasks are pinned.

The practical resolution is admission control at a level that leaves margin, plus a server for isolation, plus a partitioning heuristic that is good rather than optimal. None of these restores the clean optimality of the single-processor case, which is why “EDF is optimal” is a statement that should always be qualified by the number of processors it applies to.

Where the model does not apply

The Liu and Layland model assumes periodic tasks, known worst-case execution times, independent tasks, and zero overhead. Each assumption has a known relaxation, and each relaxation costs bound.

Aperiodic work, a request that arrives at an unpredictable time, cannot be analysed by utilization at all, because there is no period to divide by. It must be handled by a server that reserves capacity for it, and the server’s behaviour determines the response time the aperiodic work can expect. A polling server gives a bound proportional to its period; a deferrable server can use its budget at any time within the period and gives a better bound; a sporadic server replenishes gradually and gives the best bound at the highest complexity.

Blocking due to shared resources adds a term to every task’s response time that is not captured by utilization. The bound is the longest critical section of any lower-priority task that can block the task in question, and with priority ceilings it is a single such section rather than a chain. The locking protocols that produce this bound are the subject of Priority Inversion and Inheritance, and they must be included in any analysis that claims a hard guarantee.

Worst-case execution time itself is the weakest assumption. It is measured or estimated, it varies with cache state and memory contention, and on a processor with shared caches and simultaneous multithreading the variation can be a large multiple of the mean. A schedulability proof built on a wcet that is wrong by a factor of two is not a proof, and the measurement techniques that produce defensible bounds are a substantial engineering problem in their own right, one that sits outside the scheduling policy and determines whether its guarantees mean anything.