Earliest deadline first (EDF) scheduling is a dynamic scheduling principle used in real-time operating systems. It places processes in a priority queue. Whenever a scheduling event occurs (task finishes, new task released, etc.) the queue will be searched for the process closest to its deadline. This process will then be scheduled for execution next. Scheduling is the process of assigning tasks to a set of resources. ... A real-time operating system (RTOS) is an operating system that has been developed for real-time applications. ... A priority queue is an ADT (abstract data type) supporting the following two operations: add an element to the queue with an associated priority remove the element from the queue that has the highest priority, and return it The simplest way to implement a priority queue data type is to...

With scheduling periodic processes that have deadlines equal to their periods, EDF has a utilization bound of 100%. That is, EDF can guarantee that all deadlines are met provided that the total CPU utilization is not more than 100%. So, compared to fixed priority scheduling techniques like rate-monotonic scheduling, EDF can guarantee all the deadlines in the system at higher loading. Intel 80486DX2 microprocessor in a ceramic PGA package A central processing unit (CPU), or sometimes simply processor, is the component in a digital computer that interprets instructions and processes data contained in software. ... In computer science, rate-monotonic scheduling [Liu73] is an optimal preemptive static-priority scheduling algorithm used in real-time operating systems. ...

However, when the system is overloaded, the set of processes that will miss deadlines is largely unpredictable (it will be a function of the exact deadlines and time at which the overload occurs.) This is a considerable disadvantage to a real time systems designer. The algorithm is also difficult to implement in hardware and there is a tricky issue of representing deadlines in different ranges (deadlines must be rounded to finite amounts, typically a few bytes at most). Therefore EDF is not commonly found in industrial real-time computer systems. Computer hardware is the physical part of a computer, as distinguished from the computer software or computer programs and data that operate within the hardware. ...

There is a significant body of research dealing with EDF scheduling in real-time computing; it is possible to calculate worst case response times of processes in EDF, to deal with other types of processes than periodic processes and to use servers to regulate overloads. It has been suggested that this article or section be merged into Real-time. ...

Example

Consider 3 periodic processes scheduled using EDF, the following acceptance test shows that all deadlines will be met.

The utilization will be:

The theoretical limit for any number of processes is 100% and so the system is schedulable.