![]() |
Real Time Scheduling Algorithms → Earliest Deadline First (EDF) |
The algorithm EDF (Earliest Deadline First) is a dynamic, preemptive
scheduling algorithm for aperiodic tasks with different arrival times
and is based on the following theorem of Horn (1974):
"Given a set of n independent tasks with arbitrary arrival times, any algorithm
that at any instant executes the task with the earliest absolute deadline among all the
ready tasks is optimal with respect to minimizing the maximum lateness."
EDF requires that, each time a new ready task arrives, it is inserted into a queue of ready tasks,
sorted by their deadlines. If a newly arrived task is inserted at the head of the queue, the
currently executing task is preempted. That means, if a task arrives with a earlier deadline as the
currently executed task, the currently executed task is interrupted and the new task will be executed.
Introduction > Real Time Scheduling Algorithms
> Earliest Deadline First (EDF)
Back | Next |