computer science//real-time computing//real-time scheduling//earliest deadline first
Earliest deadline first is a real-time scheduling policy that, at every moment, runs the ready task whose deadline is nearest, so priorities change at run time with the deadlines, and it is used where a processor must be loaded close to full while still meeting every deadline. A task is not urgent because of what it is but because of when it is due.
Earliest deadline first is a real-time scheduling policy that, at every moment, runs the ready task whose deadline is nearest, so priorities change at run time with the deadlines, and it is used where a processor must be loaded close to full while still meeting every deadline. A task is not urgent because of what it is but because of when it is due.
Its appeal is a clean theorem. On one processor, with independent periodic tasks whose deadlines equal their periods, EDF meets every deadline exactly when the utilization satisfies
U=∑iCiTi≤1,U=\sum_i\frac{C_i}{T_i}\le 1,U=i∑TiCi≤1,
so it can use the whole CPU, where rate-monotonic scheduling is only guaranteed below a bound that falls toward 69 %. No other policy can schedule a task set that EDF cannot.
It behaves worse under overload, and that is why industry often prefers fixed priorities. When demand exceeds 100 % (a burst of interrupts, an execution time underestimated), rate-monotonic misses deadlines in its lowest-priority tasks, a predictable victim chosen at design time; EDF can miss deadlines in a cascade across many tasks, including the important ones, because a late task keeps the earliest deadline and pushes everyone else.
It costs bookkeeping at run time: deadlines must be tracked and the ready queue kept sorted, where a fixed-priority RTOS only looks at the highest-priority ready task. On a small microcontroller that overhead and the harder certification argument usually outweigh the extra utilization.
Linux offers it as SCHED_DEADLINE, and it appears in multimedia and networking where tasks have explicit deadlines and occasional misses are tolerable (real-time computing, firm and soft cases). Hard-real-time flight code typically stays on fixed priorities, checked by response-time analysis.