Deadline-aware scheduling

When can every deadline be met, and why does EDF collapse just past full utilization?

Earliest-deadline-first (EDF) always runs the task whose deadline is nearest. It is optimal in a strong sense: on a single preemptive resource, if any ordering meets all deadlines, EDF does.

Feasibility is even decidable by arithmetic. For periodic work (task i needs Cᵢ time units every Tᵢ time units), the set of tasks is schedulable if and only if

This is unusual and worth noticing: it is one of the few places in the whole stack where you can prove in advance that a commitment is keepable.

The catch is what happens at Σ > 1. EDF degrades by domino. It keeps chasing the nearest deadline, misses it, moves to the next one (already late), and misses that too, and so on. A policy that is optimal when feasible becomes worst-in-class when infeasible. So deadline scheduling is unusable without an admission gate in front of it: you must refuse work that would push the sum past 1. That is the thesis of this whole mechanism in miniature, and the reason admission control exists.

Boundary. Real-time theory assumes a known worst-case execution time. Pipeline run times are estimates, estimates are systematically optimistic, and the schedulability test inherits that bias. An SLA-aware orchestrator is doing EDF over numbers it made up.

EDF is optimal exactly up to utilization 1 and catastrophic immediately after. Deadlines need admission control as a matched pair.