Earliest deadline First (EDF)

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

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

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

\begin{displaymath}d_{i.r} < d_{j.k} \Longrightarrow P_{i} > P_{j}\end{displaymath}

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:


\begin{displaymath}C_{i} \le D_{i} \le T_{i} \end{displaymath}


\begin{displaymath}r_{i.k} = \Phi_{i} + (k-1)T_{i} \end{displaymath}


\begin{displaymath}d_{i.k} = r_{i.k} + D_{i} \end{displaymath}

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


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

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
\includegraphics[width=4.0in]{scheduler_edf_5-3_4-4_5-6.eps}

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}$:

\begin{displaymath}\sum_{i=1}^{n} \frac{C_{i}}{T_{i}} \leq 1 \end{displaymath}

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

\begin{displaymath}\sum_{i=1}^{n} \frac{C_{i}}{D_{i}} \leq 1 \end{displaymath}

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

Gerd Doeben-Henisch 2013-01-16