![]() |
Real-Time Scheduling-Algorithmen → Earliest Deadline First (EDF) |
Der Algorithmus EDF (Earliest Deadline First) ist ein dynamischer, präemptiver
Scheduling-Algorithmus für aperiodische Task mit unterschiedlichen
Ankunkftszeiten und basiert auf dem Theorem von Horn (1974):
"Wenn eine Menge von n Tasks mit beliebigen Ankunftszeiten gegeben ist, so ist ein Algorithmus,
der zu jedem Zeitpunkt diejenigen ausführungsbereite Task mit der frühesten absoluten
Deadline ausführt, optimal in Bezug auf die Minimierung der maximalen Verspätung."
Jede ankommende ausführungsbereite Task wird in eine Warteschlange von ausführungsbereiten
Tasks eingefügt. Die Tasks in der Warteschlange sind dabei nach ihrer Deadline sortiert. Wenn eine
neu angekommene Task als erstes Element in die Warteschlange eingefügt wird, muss die Deadline
der neuen Task mit der Deadline der gerade ausgeführten Task verglichen werden. Ist die Deadline
der neuen Task früher als die der gerade
ausgeführten Task, wird die neue Task an den Kopf der Warteschlange eingefügt. Das bedeutet,
die Ausführung der aktuellen Task wird unterbrochen und die neue Task
wird ausgeführt.
Einführung > Real-Time Scheduling-Algorithmen
> Earliest Deadline First (EDF)
zurück | weiter |