Einführung

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

Startseite   Tutorials   Einführung