Asynchron, Abhängig, Präemptiv: Earliest Deadline First with Precedence (EDF*)

(Für diesen Abschnitt siehe Buttazo [11]:65ff, der wiederum auf Chetto et al.[14] verweist. Dort weitere Referenzen.)

In diesem Fall wird davon ausgegangen, daß eine Menge von periodischen Tasks $\Gamma_{per}$ und sporadischen Tasks $\Gamma_{spor}$ auftritt. Es soll ferner gelten, dass alle Tasks präemptiv (preemptable) sind und dass als allgemeine Schedulingregel EDF (Earliest Deadline First) gelten soll. Zwischen den sporadischen Tasks sollen Abhängigkeiten (dependencies) bestehen, die sich durch eine Präzedenzrelation ('precedence relation') $<$ beschreiben lassen. Ferner wird angenommen, dass die sporadischen Tasks $\Gamma_{spor}$, wenn sie zu einem bestimmten Zeitpunkt $t$ auftreten, als Block auftreten, und dass im Zeitintervall $[t,D^{*}+H]$ mit $D^{*}$ als größter Deadline aller sporadischen Tasks aus der Menge $\Gamma_{spor}$ kein sporadischer Task wiederholt auftritt.

Chetto et al. (1990)[14] haben nun einen Algorithmus entwickelt, der die bekannte EDF-Schedulingregel erweitert und daher $EDF^{*}$ genannt wird. $EDF^{*}$ kann zu jedem beliebigen Zeitpunkt $t$ entscheiden, ob eine Menge von sporadischen Tasks $\Gamma_{spor}$ unter Berücksichtigung der periodischen Taskmenge verarbeitet werden kann oder nicht.

Die Strategie von $EDF^{*}$ besteht darin, (i) zunächst die Abhängigkeiten so umzuformen, daß diese 'verschwinden', und dann (ii) für jeden Zeitpunkt, an dem neue Ereignisse auftreten, einen Akzeptanztest durchzuführen.