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 der Task dem Prozessor zugeteilt, dessen Deadline als nächstes kommt, d.h. dessen Frist unter den bereitstehenden Tasks am ehesten abläuft.
Es werden immer die Zeitpunkte für das Scheduling betrachtet, an denen entweder ein neuer Task bereit wird, ein gerade noch aktiver Task beendet wird oder (bei periodischen Tasks) eine neue Periode eines Tasks 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.
