Einführung

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

Startseite   Tutorials   Einführung