Earliest-Deadline-First and What Happens When the System Overloads

Fixed-priority scheduling decides once, at design time, who runs first, and the analysis then asks whether that order survives the worst case. Earliest-deadline-first decides at every release, ordering the ready set by absolute deadline. The dynamic order buys a tighter utilisation bound and a smooth overload behaviour, and it costs a run-time scheduling operation on every release plus an analysis that is less tolerant of the assumptions being wrong.

The optimality statement and its price

For preemptive scheduling of independent periodic tasks on a single processor with deadlines equal to periods, EDF is optimal: if any algorithm can meet all deadlines, EDF can. The utilisation bound is 100 percent, not the 69 percent of rate-monotonic, and the test is a simple sum: a task set with deadlines equal to periods is schedulable by EDF if and only if total utilisation is at most one.

That is a much stronger guarantee than fixed-priority gives, and it is achieved without any priority assignment step. The cost is entirely in the implementation. The kernel must maintain a ready set ordered by absolute deadline, insert new releases at the right position, and handle the case where a task’s deadline changes because its period changed. With a handful of tasks, a sorted list is fine; with many, the structure has to support O(log n) insertion, and the deadline of a task changes on every release, so the removal and insertion happen constantly.

Comparing the two on the same set shows where the flexibility comes from. A set with utilisation 0.9 is guaranteed under EDF and is not guaranteed under rate-monotonic, even though both are fixed on the same processor. The extra 20 points of utilisation are real capacity that rate-monotonic leaves unused because its priority order cannot adapt to the phasing of releases. Systems that need to pack periodic work tightly use EDF or one of its variants, and systems that need static, certifiable priorities stay with fixed priority and accept the wasted capacity.

The analysis: processor demand over an interval

EDF’s schedulability test is not the utilisation sum for every task set. When deadlines are less than periods, or when there are release jitters, the utilisation test is necessary but not sufficient, and the exact test is the processor demand criterion: for every interval [a, b] of length L, the work that must be released and completed inside that interval must not exceed L.

The demand in an interval of length L is the sum over tasks of the number of jobs whose release falls in the interval and whose deadline falls at or before the interval’s end, times the execution time. For a periodic task with execution time C, relative deadline D and period T, the number of jobs that contribute is bounded by floor((L - D)/T) + 1 when the deadline is at most the period, and the exact condition is that this sum is at most L for every L up to the largest interval that needs checking.

The largest interval that needs checking is bounded by the hyperperiod for periodic tasks, which can be enormous when periods are co-prime. The practical tests avoid scanning every interval by solving for the values of L where the demand function changes and checking only those; the demand is a step function that increases only at points of the form k*T + D. A set whose periods are in the tens of milliseconds can have a hyperperiod of hours, and the number of candidate points can be correspondingly large. This is why EDF’s analysis is more expensive than the response-time recurrence, which is per task and converges quickly.

Overload and the domination property

Fixed-priority scheduling has a useful property under overload: the highest-priority tasks keep meeting their deadlines and the low-priority ones take the damage. The damage is bounded — a task at the bottom of the order simply runs with whatever is left — and predictable, because the priority order is fixed. If the system is designed so that the tasks that must survive are at the top, an overload degrades gracefully.

EDF does not have this property in general. When utilisation exceeds one, EDF misses deadlines in a pattern that depends on the deadlines of the tasks that are late, and a task that misses can push others late in a cascade that is not confined to the bottom of any priority order. The classical result is that after the first deadline miss under EDF, the schedule can enter a state where every task misses, because the processor is busy with jobs whose deadlines have already passed and the new jobs inherit a backlog.

A task that always misses after the first miss is not a useful failure mode for a system that has to survive transient overload. The processor is doing work whose value is now zero while work with a future deadline waits, which is the definition of a bad schedule.

The practical fixes fall into three families. Deadline assignment can be tightened so that the effective utilisation is below one even when the nominal one is not, which buys margin at the cost of capacity. Admission control can refuse new work when the utilisation would exceed one, which requires the kernel to know the utilisation of every task and the application to handle refusal. And a hybrid can run the hard tasks under fixed priority and the soft tasks under EDF, so the degradation is confined to the soft class.

The variants used in practice

Several scheduling policies split the difference between fixed priority and pure EDF.

Earliest-deadline-first with a fixed-priority overlay runs the hard real-time tasks by fixed priority and the rest by deadline, which is one way to expose EDF inside a kernel whose scheduler is built around priority bands.

The constant-bandwidth server and its relatives give each task a reservation: a share of the processor, replenished on a period, that bounds the work the task can do. A task that exceeds its reservation is throttled rather than delaying the rest, which converts an unbounded overload into a bounded interference term and preserves the isolation that pure EDF lacks. The cost is a per-task accounting structure and a scheduler decision on every replenishment boundary.

The use of a deadline-monotonic order inside a fixed-priority kernel is the other common compromise: the priorities are static, so the analysis tools and the certification argument are the fixed-priority ones, but the assignment rule is by deadline rather than by period, which is the right rule when deadlines are shorter than periods. The mechanism is described in rate-monotonic priority assignment alongside the bound that makes it useful.

Implementation on a small kernel

A dynamic scheduler needs a priority queue keyed by deadline. On a microcontroller with a handful of tasks, a sorted array of task indices is adequate and keeps the code small; insertion is a linear scan, and the scan length is the task count, which is already bounded by the configuration.

typedef struct { uint64_t deadline; int task; } entry_t;

static entry_t ready[MAX_TASKS];
static unsigned ready_count;

static void insert_by_deadline(uint64_t d, int t)
{
    if (ready_count == MAX_TASKS)
        return;                         /* MAX_TASKS must cover every task */
    unsigned i = ready_count++;
    while (i > 0 && ready[i - 1].deadline > d) {
        ready[i] = ready[i - 1];        /* shift later deadlines up */
        i--;
    }
    ready[i].deadline = d;
    ready[i].task = t;
}

static int pop_earliest(void)
{
    if (ready_count == 0)
        return -1;
    int t = ready[0].task;
    for (unsigned i = 1; i < ready_count; i++)
        ready[i - 1] = ready[i];        /* O(n) per pop; a heap makes it O(log n) */
    return t;
}

The comparison is on 64-bit absolute deadlines, so the wrap problem of a 32-bit tick counter at a short tick period is real: a 1 kHz tick wraps a 32-bit counter in about 50 days, which is within the lifetime of a device that runs continuously. Widen the counter or use the half-range comparison rule.

The scheduler’s own cost, the insertion and removal, is part of every release and therefore part of every task’s response time. With ten tasks a linear insertion shifts at most ten entries, which is small next to the context switch that follows it. With a hundred tasks it is not, and the design has to move to a heap or a timing wheel, which brings its own data structures and their own worst cases.

Why EDF is rarer than it deserves to be

Theoretical optimality has not produced wide adoption in small embedded systems, for several reasons that are about engineering rather than about scheduling.

Priority is an integer in most kernels, and EDF needs a deadline and a comparison instead. The kernel’s data structures and its configuration tools are built around a priority table, and the change is not a local one. Certification arguments are built around static assignment, and a schedule that depends on run-time values is harder to argue for to an auditor.

The overload behaviour is the decisive one. A system that must survive an unexpected event burst is easier to reason about when the important tasks are pinned above the unimportant ones, and that is exactly what fixed priority provides and pure EDF does not. EDF’s 100 percent bound is a guarantee for the nominal load, and the guarantee is worthless in the first millisecond of an overload unless something bounds the damage.

The mixed approach — fixed priority for hard tasks, EDF or reservations for soft ones — captures most of the capacity benefit while keeping the failure mode of the hard class static. That split, and the priority-assignment problem for the hard class, connects to the blocking and interference terms in response-time analysis for fixed-priority sets.