earliest-deadline-first scheduling (EDF)
Imagine a busy student with several assignments due at different times. The most natural strategy is simple: always work on whichever assignment is due SOONEST. You do not fix a permanent ranking among subjects; you just keep asking 'what is due next?' and do that. Earliest-deadline-first scheduling, or EDF, is exactly this strategy for a processor: at every moment, run the task whose deadline is closest in time.
The contrast with rate-monotonic scheduling is the heart of it. Rate-monotonic gives each task a FIXED priority based on its period, decided once. EDF uses a DYNAMIC priority: a task's urgency depends on how near its current deadline is, which changes over time, so the same task can be high priority now and low priority later. The scheduler is preemptive and always picks the ready task with the earliest absolute deadline; ties can be broken arbitrarily. The striking theoretical result is that EDF is OPTIMAL for scheduling independent periodic (or sporadic) tasks on a single processor: if any scheduling algorithm can meet all the deadlines, EDF can too. And its feasibility test is wonderfully simple — for periodic tasks with deadline equal to period, EDF meets all deadlines if and only if total utilization (the sum of Ci/Ti) is at most 1.0. In other words, EDF can use up to 100% of the CPU and still guarantee deadlines, where rate-monotonic guarantees only about 69%.
It matters because EDF squeezes the most schedulable work out of a processor while still guaranteeing deadlines, which is attractive when CPU time is precious. The honest trade-offs that keep RMS popular anyway: EDF needs dynamic priorities, so it has more run-time overhead (the scheduler must track and compare absolute deadlines), and its behavior under OVERLOAD is worse — if you push past 100% utilization, RMS degrades predictably (low-priority tasks miss first) while EDF can suffer a 'domino effect' where one missed deadline cascades into many. EDF is also harder to implement on simple fixed-priority RTOS kernels, which is one reason many real systems still use rate-monotonic despite its lower utilization bound. The 100% bound also assumes the idealized independent-task model, just like RMS's bound.
At t=0, three ready tasks with absolute deadlines: A: deadline at t=10 B: deadline at t= 4 <- earliest -> run B now C: deadline at t=20 EDF runs B first. If at t=2 a new task D arrives with deadline t=3, D's deadline is now earliest -> EDF preempts B and runs D. Feasibility: periodic tasks meet all deadlines iff sum(Ci/Ti) <= 1.0.
Always run the nearest deadline; priorities shift as deadlines approach. EDF can reach 100% utilization where RMS guarantees only ~69%.
EDF reaches 100% utilization but degrades badly under overload (a missed deadline can domino into many), and its dynamic priorities cost more overhead — which is why many fixed-priority RTOS kernels still favour rate-monotonic.