Earliest deadline first scheduling

Earliest deadline first (EDF) or least time to go is a dynamic scheduling algorithm used in real-time operating systems to place 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 is the next to be scheduled for execution.

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.

With scheduling periodic processes that have deadlines equal to their periods, EDF has a utilization bound of 100%. Thus, the schedulability test for EDF is:

where the ${\displaystyle \left\{C_{i}\right\}}$ are the worst-case computation-times of the ${\displaystyle n}$ processes and the ${\displaystyle \left\{T_{i}\right\}}$ are their respective inter-arrival periods (assumed to be equal to the relative deadlines).

...
Wikipedia