Earliest Deadline First
Earliest Deadline First (EDF) ist eines der gebräuchlichsten Scheduling-Verfahren in der Forschung. In der Industrie wird jedoch eher Deadline Monotonic Scheduling (DMS) eingesetzt. Es gehört zu den zeitbasierten Scheduling-Verfahren, denn es trifft seine Entscheidungen so, dass Fertigstellungstermine (Deadlines) eingehalten werden. Die präemptive Variante von Earliest Deadline First wird bevorzugt für Echtzeitsysteme verwendet, da, falls ein gültiger Schedule existiert, EDF diesen auch finden kann (Optimalitätskriterium).
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 (100%) einplanen. Dies gilt allerdings nur für Tasksysteme, in denen die Deadline jeder Task jeweils größer oder gleich der Periode der jeweiligen Task ist.
