earliest-deadline-first scheduling
/ EDF /
Imagine a student juggling several assignments: the smart move is always to work on whichever one is due soonest, switching the moment a more urgent one appears. Earliest-deadline-first (EDF) scheduling is exactly that strategy for real-time tasks — at every instant, run the ready task whose deadline is closest, and re-evaluate whenever a new task arrives or a deadline shifts.
How it differs from rate-monotonic: EDF assigns priorities dynamically. There is no fixed ranking; the task with the nearest absolute deadline right now is the highest priority right now, and that can change from moment to moment as deadlines approach. It is preemptive — a newly arrived task with a sooner deadline immediately bumps the running one. EDF's headline property is that it is optimal for a single processor: if any scheduling algorithm can meet all the deadlines of a task set, EDF can too, and it can do so up to 100 percent CPU utilization (for tasks whose deadlines equal their periods), beating rate-monotonic's roughly 69 percent ceiling.
Why it matters and the trade-off: EDF squeezes the most out of the CPU while still meeting deadlines, which is why it is attractive for soft and some hard real-time systems. The costs are honest: tracking and re-sorting deadlines dynamically is more runtime overhead than fixed priorities, and its behavior under overload is dangerous — if the task set is ever infeasible, EDF can cascade into a domino of missed deadlines rather than failing gracefully, whereas a fixed-priority scheme tends to sacrifice the lowest-priority tasks first. Predictability under overload is the reason many hard real-time systems still prefer rate-monotonic.
At time 0, task X has deadline 30 and task Y has deadline 20. EDF runs Y first because 20 is sooner. If at time 10 a task Z arrives with deadline 15, EDF preempts and runs Z, then returns to Y, then X — always serving the nearest deadline.
EDF always runs the nearest-deadline task and can reach full CPU utilization — but degrades unpredictably under overload.
EDF is optimal and reaches 100 percent utilization in theory, but only when the system is NOT overloaded; push it past feasibility and it can miss many deadlines in a cascade, unlike fixed-priority schemes that degrade more gracefully.