Earliest Deadline First
aus Wikipedia, der freien Enzyklopädie
Earliest Deadline First (EDF) ist eines der gebräuchlichsten Scheduling-Verfahren. 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 sie die Einhaltung aller Fristen garantiert.
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.
