Part 6 of 7 · 4 min read
EDF
Earliest deadline first
In plain words: An alternative is to let the priority change: always run the task whose deadline is nearest. Earliest deadline first (EDF) does this. When a job becomes ready, it receives a deadline (the end of its period), and the processor always runs the ready job with the earliest deadline.
On the same two tasks (T1: 2 every 5, T2: 4 every 7), EDF gives this timeline:
time: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
runs: 1 1 2 2 2 2 1 1 2 2 2 2 1 1
At time 0, T1's job (deadline 5) goes before T2's (deadline 7). T2 runs 2 to 6 and finishes at 6, before its deadline of 7. At 5, T1's second job arrives with deadline 10, and T2's job has the earlier deadline 7, so T2 keeps the processor. T1 then runs 6 to 8, within its deadline of 10. The second T2 job (ready at 7, deadline 14) runs 8 to 12. T1's third job (ready at 10, deadline 15) runs 12 to 14. No deadline is missed, though RM missed one.
EDF is optimal on one processor for this model: if any scheduler can meet all the deadlines, EDF can, and the condition is just that the total utilisation does not exceed 1. Here 0.97 is below 1. The price: the deadlines must be known and tracked, and when the machine is overloaded (more than 1), EDF can fail in an uncontrolled way, with many tasks late at once, while RM tends to protect the high-priority tasks.
| RM | EDF | |
|---|---|---|
| Priorities | Fixed, from the period | Change, from the deadline |
| Guaranteed up to | n × (2^(1/n) − 1), about 0.69 to 0.83 |
1.0 |
| On overload | Low-priority tasks fail first | Failures spread unpredictably |
| Used in | Many embedded systems | Linux SCHED_DEADLINE (a form of it) |
Earliest deadline first
Earliest deadline first (EDF) is a dynamic-priority policy that always runs the ready job whose deadline is nearest, and that meets all the deadlines of a set of periodic tasks on one processor whenever their total utilisation is at most 1.
Example: at time 5 in the trace, T2's job (deadline 7) keeps the processor against T1's new job (deadline 10).
Common mistake
Believing that "real time" means "fast". A real-time system is one whose timing is predictable and bounded. A very fast system that sometimes stalls for 50 ms is not real-time.
Interview angle
Answer in your head first, then open it.
What is the difference between hard and soft real-time?
A missed deadline is a failure in hard real-time and a loss of quality in soft real-time.
What is rate-monotonic scheduling?
Fixed priorities, a shorter period meaning a higher priority.
Why is EDF optimal on one processor?
It meets all deadlines whenever total utilisation is at most 1.
What is processor affinity?
The set of processors a task may or prefers to run on.
Why does Linux use a queue per processor?
To avoid a lock fight on one shared list and to keep a task near its cache.
Check yourself: 1. In the EDF timeline, why did T2 keep the processor at time 5? 2. What utilisation limit does EDF guarantee? 3. What happens under RM when the system is overloaded?
Words you will meet
| Word | Meaning |
|---|---|
| Load balancing | Moving tasks between processors' queues |
| Migration | One move of a task to another processor |
| Soft affinity | A preference to stay on one processor |
| Hard affinity | A rule to run only on listed processors |
| NUMA | Memory that is faster to reach from some processors |
| Hard real-time | A missed deadline is a failure |
| Soft real-time | A missed deadline lowers quality |
| Period | The time between two releases of a periodic task |
| Utilisation | Computation time divided by period |
| Rate-monotonic | Shorter period, higher fixed priority |
| EDF | Nearest deadline first |
Quick notes
- Load balancing is the movement of tasks from the ready queue of a busy processor to that of a less busy one, so that all processors have about equal work and none idles while another has waiting tasks.
- Soft affinity is the tendency of a scheduler to keep a task on the processor it last ran on, so that its cached data stays useful, without a guarantee; **hard.
- A hard real-time system must complete every task by its deadline, because a late result is a failure; a soft real-time system treats a late result as a loss of quality, but still tolerates it.
- Rate-monotonic scheduling is a fixed-priority policy for periodic tasks in which the task with the shortest period has the highest priority and preempts any lower one; it is guaranteed to.
- Earliest deadline first (EDF) is a dynamic-priority policy that always runs the ready job whose deadline is nearest, and that meets all the deadlines of a set of periodic tasks.