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:

U = \sum_{i=1}^{n} \frac{C_i}{T_i} \leq 1,

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

That is, EDF can guarantee that all deadlines are met provided that the total CPU utilization is not more than 100%. Compared to fixed priority scheduling techniques like rate-monotonic scheduling, EDF can guarantee all the deadlines in the system at higher loading.

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 can't 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.

Instead, most real-time computer systems use fixed priority scheduling (usually rate-monotonic scheduling). With fixed priorities, it is easy to predict that overload conditions will cause the low-priority processes to miss deadlines, while the highest-priority process will still meet its deadline.

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.

Example

Consider 3 periodic processes scheduled on a preemptive uniprocessor. The execution times and periods are as shown in the following table:

Process Timing Data
ProcessExecution TimePeriod
P118
P225
P3410

In this example, the units of time may be considered to be schedulable time slices. The deadlines are that each periodic process must complete within its period.

Timing diagram

Timing Diagram showing part of one possible schedule for the example.

In the timing diagram, the columns represent time slices with time increasing to the right, and the processes all start their periods at time slice 0. 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. Likewise, when P2 completes, P1 is scheduled, followed by P3.

At time slice 5, both P2 and P3 have the same deadline, needing to complete before time slice 10, so EDF may schedule either one.

Utilization

The utilization will be:

\left ( \frac{1}{8} + \frac{2}{5} + \frac{4}{10} \right ) = \left ( \frac{37}{40} \right ) = 0.925 = {\mathbf{92.5\%}}

Since the least common multiple of the periods is 40, the scheduling pattern can repeat every 40 time slices. But, only 37 of those 40 time slices are used by P1, P2, or P3. Since the utilization, 92.5%, is not greater than 100%, the system is schedulable with EDF.

Deadline interchange

Main article: Priority inheritance

Undesirable deadline interchanges may occur with EDF scheduling. When a shared resource is accessed by processes using critical sections within a process (to prevent it from being pre-empted by another process with an earlier deadline waiting for access to the same shared resource), it becomes important for the scheduler to temporarily assign the earliest deadline from amongst the other processes waiting for the resource, to the process while it is within its critical section to prevent the processes with earlier deadlines miss their respective deadline, especially if the process within its critical section has a much longer time to complete and its exit from its critical section and subsequent release of the shared resource may be delayed. Also it may be further delayed by other processes with earlier deadlines which do not share the same resource and thus can preempt it during its critical section. This hazard of deadline interchange within a critical section is analogous to priority inversion when using fixed priority pre-emptive scheduling.

To speed up the search within a linked list queue, the waiting processes within the list should be sorted according to their deadlines. When a cyclic or new process is given a new deadline, it is then inserted before the first process with a later deadline. This way, the processes with the earliest deadlines are always at the beginning of the list, reducing the time to find them.

Heavy traffic analysis for EDF queues with reneging

In a heavy-traffic analysis of the behavior of a single-server queue under an Earliest-Deadline-First (EDF) scheduling policy with reneging, the processes have deadlines and are served only until their deadlines elapse. The fraction of “reneged work,” defined as the residual work not serviced due to elapsed deadlines, is an important performance measure.

Kernels implementing EDF scheduling

Although EDF implementations are not common in commercial real-time kernels, here are a few links of open-source and real-time kernels implementing EDF:

See also

References

  1. ↑ Cucinotta, Tommaso (April 2008). "Access Control for Adaptive Reservations on Multi-User Systems". 14th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2008).
  2. ↑ Pierre G. Jansen, Sape J. Mullender, Paul J.M. Havinga, Hans Scholten. Lightweight EDF Scheduling with Deadline Inheritance