Earliest Deadline First
Earliest Deadline First (EDF) ist einer der gebräuchlichsten Scheduling-Algorithmen für Echtzeitsysteme (Realtime Systems). Er gehört zu den zeitbasierten Schedulingverfahren, denn seine Funktionsweise beruht auf der Einhaltung von Fristen (Deadlines).
Funktionsweise:
- Alle zu dem betrachteten Zeitpunkt t bereitstehenden Tasks werden nach ihrer aufsteigenden Deadline geordnet bzw. stehen geordnet zur Verfügung.
- Es wird immer genau die Task dem Prozessor zugeteilt, deren Deadline als nächstes kommt. D.h. deren Frist unter den bereitstehenden Tasks am ehesten abläuft.
Es werden immer die Zeitpunkte für das Scheduling betrachtet, an denen entweder eine neue Task bereit wird, eine gerade noch aktive Task beendet wird oder (bei periodischen Tasks) eine neue Periode einer Task anfängt.
EDF ist dabei sehr flexibel: Es kann sowohl für präemptives (d.h. unterbrechbares) Scheduling wie auch für nicht-präemptives verwendet werden. Außerdem kann es in aperiodischen sowie periodischen Plänen eingesetzt werden, egal ob statisch oder dynamisch geplant wird.
Optimalität:
EDF ist optimal für die Scheduling-Klasse 1|preempt, async|L_max, es ist nicht optimal i.A. bei 1|non-preempt, sync|L_max
- "1" steht für einen Prozessor
- "(non-)preempt" für (nicht-)unterbrechbare Tasks
- "(a)sync" für (a)synchrone Taskaktivierung, d.h. alle Tasks werden gleichzeitig bereit (sync) oder unterschiedlich (async)
- "L_max" ist die zu minimierende Kostenfunktion; steht für "max. Lateness", also der maximalen Zeit (l), die zwischen vollständiger Ausführung (c) und Deadline (d) verbleibt: l = c - d (L_max ist NEGATIV bei erfolgreicher Planung)
Auslastung:
EDF kann den Prozessor bis zur Auslastung 1 einplanen.
