Earliest deadline first scheduling

Earliest deadline first scheduling, often shortened to EDF, is a dynamic priority scheduling algorithm used in real-time operating systems. Each time a scheduling event occurs, such as a task finishing or a new task being released, the ready queue is searched and the process closest to its deadline runs next. On a preemptive single processor it is optimal in a precise sense: if any algorithm can schedule a set of independent jobs, each with an arrival time, an execution requirement and a deadline, so that every job finishes in time, then EDF can too. For periodic tasks whose deadlines equal their periods, the schedulability test is that total processor utilization is at most 100 percent. That compares with a theoretical maximum of around 69 percent for fixed-priority rate-monotonic scheduling, although most real-time systems still use fixed priorities. EDF support has been added to the Linux kernel by projects such as AQuoSA.