Earliest deadline first scheduling
|
|
Earliest deadline first 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.
Compared to static scheduling techniques like rate-monotonic scheduling, earliest deadline first will generally perform better, utilizing up to 100% of CPU time (when scheduling processor allocation time).
Because deadlines are dynamic, when the system is overloaded the process that misses its deadline will be 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 very difficult to implement in hardware (deadlines must be rounded to finite amounts, typically a few bits at most, causing a performance loss), and therefore it is not commonly found in real time computer systems.
de:Earliest Deadline First fr:Earliest deadline first scheduling ja:Earliest Deadline First nl:Earliest deadline first scheduling
Example
| Process | Execution Time | Period |
| P1 | 1 | 8 |
| P2 | 2 | 5 |
| P3 | 4 | 10 |
The utilization will be:
<math>\frac{1}{8} + \frac{2}{5} + \frac{4}{10} = 0.925<math>
The theoretical limit for 3 processes is 100% and so the system is schedulable!