Earliest-Deadline-First Scheduling
EDF always runs the task with the nearest deadline; it achieves full processor utilization but at the cost of dynamic priorities and harder overload behavior.
The Rule
Earliest-deadline-first (EDF) is a dynamic-priority scheduling policy: at every scheduling decision, the processor is given to the ready task whose absolute deadline is nearest. Priorities are not fixed; they change as deadlines approach and as new jobs arrive.
Optimality and the Utilization Test
EDF is optimal for preemptive single-processor scheduling: if any algorithm can schedule a set of independent periodic tasks so all deadlines are met, EDF can too. For tasks with deadlines equal to periods, the schedulability test is simply that total utilization U <= 1.0. This is far more generous than the rate-monotonic bound of about 0.693, so EDF can use the processor fully.
The Trade-Offs
- Higher achievable utilization: up to 100 percent for the simple case
- Dynamic priorities cost more runtime bookkeeping to track deadlines
- Behavior under overload is worse: a domino effect can cascade missed deadlines unpredictably
- Blocking and shared resources need deadline-aware protocols
Overload Behavior
The main practical concern with EDF is what happens when demand briefly exceeds capacity. Under fixed-priority scheduling, overload sacrifices the lowest-priority tasks first, which is predictable. Under EDF an overload can cause a task that will miss its deadline to still consume the processor, causing others to miss too, so failures cascade. Systems using EDF add admission control or overload-management logic to contain this.
When to Choose EDF
EDF suits systems where high utilization matters and the task set is well characterized, such as multimedia and some soft real-time workloads. For hard safety-critical control, fixed-priority scheduling is often preferred because its overload behavior is easier to reason about and certify, even though it leaves some capacity unused. The choice is between squeezing out utilization and having simple, provable degradation.