Deadline Scheduling (fristenbasierte Ablaufplanung) ist eine Familie von Scheduling-Verfahren, bei denen jeder Task eine Frist (Deadline) erhält, bis zu der er abgeschlossen sein muss. Der Scheduler ordnet die Ausführung so an, dass möglichst viele Fristen eingehalten werden. Es ist das zentrale Planungsverfahren in Real-Time-Scheduling-Systemen, etwa in Steuergeräten, Avionik oder Industrieautomation.
Fristen und ihre Arten
Man unterscheidet harte und weiche Fristen: Bei einer harten Frist (Hard Deadline) gilt das System als fehlerhaft, wenn der Task sie verfehlt – im schlimmsten Fall drohen Sach- oder Personenschäden. Bei einer weichen Frist (Soft Deadline) ist eine späte Fertigstellung unschön, aber nicht katastrophal, etwa bei einem verzögerten Video-Frame. Zusätzlich unterscheiden sich relative Fristen (Abstand zum Task-Start) von absoluten Fristen (fester Zeitpunkt auf der Uhr).
Wichtige Vertreter
- Earliest Deadline First (EDF): Der Task mit der nächsten absoluten Frist erhält die höchste dynamische Priorität. Auf einem Einzelprozessor ist EDF optimal: Ist die Prozessorauslastung kleiner oder gleich 100 Prozent, findet EDF immer einen planbaren Ablauf (Liu-Layland-Resultat). Details siehe EDF (Earliest Deadline First).
- Deadline Monotonic (DM): Statisches Gegenstück zu EDF: Tasks mit kürzerer relativer Frist bekommen fest höhere Priorität. DM ist optimal, wenn Fristen ungleich den Perioden sind.
- Rate Monotonic (RM): Priorität nach Periodenlänge (kürzere Periode = höhere Priorität), siehe Rate Monotonic.
Mehrprozessor-Erweiterungen
Auf Mehrprozessorsystemen wird EDF zu Global EDF (GEDF) erweitert: Tasks können auf jedem Prozessor laufen und wandern. Solche Systeme stehen vor ähnlichen Koordinationsfragen wie das Gang Scheduling, bei dem zusammengehörige Threads gleichzeitig auf mehreren Kernen laufen müssen.
Verwandte Grundlagen: Scheduling-Policies, Scheduler, Lottery Scheduling.