Earliest deadline First (EDF)

Im Earliest Dedline first (EDF) Algorithmus werden die Prioritäten dynamisch anhand der absoluten Deadlines $d_{i.r}$ vergeben:

$$d_{i.r} = \Phi_{i} + (r-1)T_{i} + D_{i}$$

Die kleinste absolute Deadline bekommt die höchste Priorität

$$d_{i.r} < d_{j.k} \Longrightarrow P_{i} > P_{j}$$

Für die wichtigen Parameter Phase $\Phi$, worst case-Ausführungszeit $C_{i}$, relative Deadline $D_{i}$, die Periodendauer $T_{i}$, die k-te Auftretenszeit $r_{i.k}$, sowie die k-te absolute deadline $d_{i.k}$ gilt:

$$C_{i} \le D_{i} \le T_{i}$$

$$r_{i.k} = \Phi_{i} + (k-1)T_{i}$$

$$d_{i.k} = r_{i.k} + D_{i}$$

Dies entspricht der allgemeinen Formel für die k-te absolute Deadline mit

$$d_{i.k} = \Phi_{i} + (k-1)T_{i} + D_{i}$$

Ferner macht die EDF-Prioritätsregel keine expliziten Annahmen über die Periodizität der Ereignisse, d.h. die Ereignisse können sowohl periodisch wie aperiodisch sein.

Im Bild 4.5 sind beispielhaft Werte für eine kleine Taskmenge $\Gamma$ = { $\tau_{1}, \tau_{2}, \tau_{3}$ } gegeben. Der kgv-Wert (:= lcm (least common multiple)) ist 12. Diese Taskmenge ist mit der RM-Prioritätsregel nicht planbar! Eine Simulation der Planung mit der EDF-Regel (vgl. Bild 4.5) zeigt, dass dies mit der EDF-Regel möglich ist.

Figure 4.5: Beispiel für EDF-Scheduling Plan

Wir nehmen ein synchrones Auftreten aller Tasks $\tau_{i}$ an, so daß $\Phi_{i} = 0$. Dann gilt $d_{i.j} = (j-1)T_{i}+D_{i}$. Also:

1. Bei t=0 ist das j-te Auftreten j=1, dann gilt für die absoluten Deadlines $d_{1} = 3, d_{2}= 4, d_{3}=5$. Damit hat $\tau_{1}$ die höchste Priorität.
2. Bei t=1 ist das j-te Auftreten j=1, dann gilt für die absoluten Deadlines $d_{2}= 4, d_{3}=5$. Damit hat $\tau_{2}$ die höchste Priorität.
3. Bei t=3 ist das j-te Auftreten j=2 für $\tau_{1}$ und j=1 für $\tau_{3}$ , dann gilt für die absoluten Deadlines $d_{1} = 6, d_{3}=5$. Damit hat $\tau_{3}$ die höchste Priorität.
4. Bei t=4 ist das j-te Auftreten für $\tau_{1} j_{1}=2$, für $\tau_{2} j_{2}=2$, dann gilt für die absoluten Deadlines $d_{1} = 6, d_{2}=8$. Damit hat $\tau_{1}$ die höchste Priorität.
5. Bei t=5 ist $\tau_{2}$ alleine, dann hat $\tau_{2}$ die höchste Priorität.
6. Bei t=6 ist das j-te Auftreten für $\tau_{1} j_{1}=3$, für $\tau_{3} j_{3}=2$, dann gilt für die absoluten Deadlines $d_{1} = 9, d_{3}=10$. Damit hat $\tau_{1}$ die höchste Priorität.
7. Bei t=7 ist $\tau_{3}$ alleine, dann hat $\tau_{3}$ die höchste Priorität.
8. Bei t=8 ist das j-te Auftreten für $\tau_{2} j_{2}=3$, für $\tau_{3} j_{3}=2$, dann gilt für die absoluten Deadlines $d_{2} =12, d_{3}=11$. Damit hat $\tau_{3}$ die höchste Priorität.
9. Bei t=9 ist das j-te Auftreten für $\tau_{1} j_{1}=4$, für $\tau_{2} j_{2}=3$, dann gilt für die absoluten Deadlines $d_{1} =12, d_{2}=12$. Zusätzlioch soll bei Gleichstand die Rangfolge im Index gelten. Damit hat $\tau_{1}$ die höchste Priorität.
10. Bei t=10 ist $\tau_{2}$ alleine, dann hat $\tau_{2}$ die höchste Priorität.
11. Bei t=11 ist die CPU unbeschäftigt ('idle').

Für die EDF-Prioritätsregel gibt es folgende notwendige und hinreichende Bedingung für die Planbarkeit, falls $D_{i} = T_{i}$:

$$\sum_{i=1}^{n} \frac{C_{i}}{T_{i}} \leq 1$$

Für eine hybride Taskmenge mit $D_{i} \leq T_{i}$ gibt es die hinreichende Bedingung :

$$\sum_{i=1}^{n} \frac{C_{i}}{D_{i}} \leq 1$$

(vgl. [17]:S.31).