Earliest deadline first scheduling
Encyclopedia
Earliest deadline first or least time to go is a dynamic scheduling algorithm used in real-time operating system
s. 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 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) such that all the jobs complete by their deadlines, the EDF will schedule this collection of jobs such that they all complete by their deadlines.
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
are the worst-case computation-times of the 
processes and the 
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%. So, 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 must be rounded to finite amounts, typically a few bytes at most). If one uses modular arithmetic 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.
The utilization will be:
The theoretical limit for any number of processes is 100% and so the system is schedulable.
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.
Real-time operating system
A real-time operating system is an operating system intended to serve real-time application requests.A key characteristic of a RTOS is the level of its consistency concerning the amount of time it takes to accept and complete an application's task; the variability is jitter...
s. It places processes in a priority queue
Priority queue
A priority queue is an abstract data type in computer programming.It is exactly like a regular queue or stack data structure, but additionally, each element is associated with a "priority"....
. 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) such that all the jobs complete by their deadlines, the EDF will schedule this collection of jobs such that they all complete by their deadlines.
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
are the worst-case computation-times of the processes and the 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
Central processing unit
The central processing unit is the portion of a computer system that carries out the instructions of a computer program, to perform the basic arithmetical, logical, and input/output operations of the system. The CPU plays a role somewhat analogous to the brain in the computer. The term has been in...
utilization is not more than 100%. So, compared to fixed priority scheduling techniques like rate-monotonic scheduling
Rate-monotonic scheduling
In computer science, rate-monotonic scheduling is a scheduling algorithm used in real-time operating systems with a static-priority scheduling class...
, 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
Computer hardware
Personal computer hardware are component devices which are typically installed into or peripheral to a computer case to create a personal computer upon which system software is installed including a firmware interface such as a BIOS and an operating system which supports application software that...
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). If one uses modular arithmetic 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
Fixed priority pre-emptive scheduling
Fixed-priority pre-emptive scheduling is a scheduling system commonly used in real-time systems. With fixed priority pre-emptive scheduling, the scheduler ensures that at any given time, the processor executes the highest priority task of all those tasks that are currently ready to execute.The...
(usually rate-monotonic scheduling
Rate-monotonic scheduling
In computer science, rate-monotonic scheduling is a scheduling algorithm used in real-time operating systems with a static-priority scheduling class...
). 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
Real-time computing
In computer science, real-time computing , or reactive computing, is the study of hardware and software systems that are subject to a "real-time constraint"— e.g. operational deadlines from event to system response. Real-time programs must guarantee response within strict time constraints...
; 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 using EDF, the following acceptance test shows that all deadlines will be met.| Process | Execution Time = C | Period = T |
|---|---|---|
| P1 | 1 | 8 |
| P2 | 2 | 5 |
| P3 | 4 | 10 |
The utilization will be:
The theoretical limit for any number of processes is 100% and so the system is schedulable.
Deadline interchange
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 inversionPriority inversion
In computer science, priority inversion is a problematic scenario in scheduling when a higher priority task is indirectly preempted by a lower priority task effectively "inverting" the relative priorities of the two tasks....
when using fixed priority pre-emptive scheduling
Fixed priority pre-emptive scheduling
Fixed-priority pre-emptive scheduling is a scheduling system commonly used in real-time systems. With fixed priority pre-emptive scheduling, the scheduler ensures that at any given time, the processor executes the highest priority task of all those tasks that are currently ready to execute.The...
.
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:- SHARK The SHaRK RTOS, implementing various versions of EDF scheduling and resource reservation scheduling algorithms
- ERIKA Enterprise ERIKA Enterprise, which provides an implementation of EDF optimized for small microcontrollers with an API similar to the OSEKOSEKOSEK is a standards body that has produced specifications for an embedded operating system, a communications stack, and a network management protocol for automotive embedded systems...
API. - The Everyman Kernel The Everyman Kernel implements either EDF or Deadline Monotonic scheduling depending on the user's configuration.
- MaRTE OS MaRTE OS acts as a runtime for Ada applications and implements a wide range of scheduling algorithms including EDF.
- The AQuoSAAQuoSAAQuoSA is an open architecture for the provisioning of adaptive Quality of Service functionality into the Linux kernel. The project features a flexible, portable, lightweight and open architecture for supporting QoS related services on the top of a general-purpose operating system as Linux...
project constitutes a modification to the Linux kernel enriching the process scheduler with EDF scheduling capabilities. The timing of the scheduling cannot be as precise as in the case of the above hard real-time Operating Systems, yet it is sufficiently precise so as to greatly enhance predictability, and thus fulfill the real-time requirements, of multimedia applications. - Recently, a new EDF scheduling class for the Linux kernel, called SCHED_DEADLINE, has been proposed to the kernel community. The implementation supports multicore and embedded platforms, and integrates with the PREEMPT_RT patch. The code has been developed under a FP7 European project called ACTORS, and financially supported by the European commission.
- The real-time scheduler developed in the context of the IRMOS European Project is a multi-processor real-time scheduler for the Linux kernel, particularly suitable for temporal isolation and provisioning of QoS guarantees to complex multi-threaded software components and also entire virtual machineVirtual machineA virtual machine is a "completely isolated guest operating system installation within a normal host operating system". Modern virtual machines are implemented with either software emulation or hardware virtualization or both together.-VM Definitions:A virtual machine is a software...
s. It features hierarchical EDF/FP scheduling where at the outer level there is a partitioned EDF scheduling on the available CPUs. However, reservations are multi-CPU, and global FP over multi-processors is used at the inner level in order to schedule the threads (and/or processes) attached to each outer EDF reservation. See also the article appeared on lwn.net for a general overview about it and a short tutorial. - Xen has an EDF scheduler for some time now. The man page contains a short info. KVM: The scheduler will probably copied by the KVM developers at some point in the future.