Earliest deadline first scheduling
Earliest deadline first (EDF) or least time to go is a dynamic priority scheduling algorithm used in real-time operating systems to place processes in a priority queue.
EDF is an optimal scheduling algorithm on preemptive uniprocessors, in the following sense: if a collection of independent jobs, each characterized by an arrival time, an execution requirement and a deadline, can be scheduled (by any algorithm) in a way that ensures all the jobs complete by their deadline, the EDF will schedule this collection of jobs so they all complete by their deadline.
are their respective inter-arrival periods (assumed to be equal to the relative deadlines).
[2] That is, EDF can guarantee that all deadlines are met provided that the total CPU utilization is not more than 100%.
This task group meets utilization is no greater than 1.0, where utilization is calculated as 5/20+3/11+4/10+1/20 = 0.97 (two digits rounded), but it's still unscheduable, check EDF Scheduling Failure figure for details.
If this factor can be kept small, non-preemptive EDF can be beneficial as it has low implementation overhead.
The algorithm is also difficult to implement in hardware and there is a tricky issue of representing deadlines in different ranges (deadlines can not be more precise than the granularity of the clock used for the scheduling).
If a modular arithmetic is used to calculate future deadlines relative to now, the field storing a future relative deadline must accommodate at least the value of the (("duration" {of the longest expected time to completion} * 2) + "now").
Therefore EDF is not commonly found in industrial real-time computer systems.
The timing diagram's alternating blue and white shading indicates each process's periods, with deadlines at the color changes.
The first process scheduled by EDF is P2, because its period is shortest, and therefore it has the earliest deadline.
Since the least common multiple of the periods is 40, the scheduling pattern can repeat every 40 time slices.
This is especially important if the process running the critical section has a much longer time to complete and exit from its critical section, which will delay releasing the shared resource.
But the process might still be pre-empted in favour of others that have earlier deadlines but do not share the critical resource.
This hazard of deadline interchange is analogous to priority inversion when using fixed-priority pre-emptive scheduling.
In addition, the worst-case overhead of an EDF implementation (fully preemptive or limited/non-preemptive) for periodic and/or sporadic tasks can be made proportional to the logarithm of the largest time representation required by a given system (to encode deadlines and periods) using Digital Search Trees.
[5] In practical cases, such as embedded systems using a fixed, 32-bit representation of time, scheduling decisions can be made using this implementation in a small fixed-constant time which is independent of the number of system tasks.
In such situations experiments have found little discernible difference in overhead between the EDF and FPS, even for task sets of (comparatively) large cardinality.
