EDF (Earliest Deadline First), zu Deutsch „zuerst die nächste Frist", ist ein dynamisches Prioritätsverfahren für Real-Time-Scheduling. Statt fester Prioritäten bewertet der Scheduler bei jedem Wechsel neu, welche Aufgabe die früheste Deadline hat, und startet genau diese zuerst.
Dynamische Priorität
Bei EDF ist die Priorität einer Aufgabe nicht konstant, sondern hängt von ihrer aktuellen Frist ab. Eine Aufgabe, deren Deadline in 5 ms liegt, hat Vorrang vor einer, deren Deadline erst in 50 ms liegt. Dafür muss der Scheduler die anstehenden Aufgaben in einer Prioritätswarteschlange verwalten, die nach der Restzeit bis zur Frist sortiert ist.
Optimalität und Auslastung
EDF ist optimal für präemptive Einprozessor-Systeme: Wenn irgendein Scheduler eine Aufgabenmenge fristgerecht abarbeiten kann, dann schafft das auch EDF. Theoretisch kann EDF die CPU zu 100 % auslasten, während das statische Rate-Monotonic-Verfahren bereits bei etwa 69 % an seine Garantie-Grenze stößt.
Die Überlast-Falle
Der Preis für die Optimalität ist das Verhalten unter Überlast: Überschreitet die Gesamtlast die Prozessorkapazität, verpasst EDF eine Frist nach der anderen (Domino-Effekt), und es ist schwer vorherzusagen, welche Aufgaben zuerst scheitern. RMS degradiert in solchen Situationen kontrollierter, weil die wichtigsten (kurzperiodigen) Aufgaben ihre Priorität behalten. Deshalb setzen praktische Systeme häufig auf Mischformen: Linux bietet mit SCHED_DEADLINE seit Kernel 3.14 einen EDF-basierten Scheduler an, während klassische RTOS oft RMS-artige statische Prioritäten verwenden.
Verwandte Grundlagen: Scheduler, Preemption, Prozess-Scheduling, Scheduling-Policies.