Im Earliest Dedline first (EDF) Algorithmus werden die Prioritäten dynamisch anhand der absoluten Deadlines vergeben:
Die kleinste absolute Deadline bekommt die höchste Priorität
Für die wichtigen Parameter Phase , worst case-Ausführungszeit , relative Deadline , die Periodendauer , die k-te Auftretenszeit , sowie die k-te absolute deadline gilt:
Dies entspricht der allgemeinen Formel für die k-te absolute Deadline mit
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 = {
} 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 an, so daß . Dann gilt
. Also:
- Bei t=0 ist das j-te Auftreten j=1, dann gilt für die absoluten Deadlines
. Damit hat die höchste Priorität.
- Bei t=1 ist das j-te Auftreten j=1, dann gilt für die absoluten Deadlines
. Damit hat die höchste Priorität.
- Bei t=3 ist das j-te Auftreten j=2 für und j=1 für , dann gilt für die absoluten Deadlines
. Damit hat die höchste Priorität.
- Bei t=4 ist das j-te Auftreten für
, für
, dann gilt für die absoluten Deadlines
. Damit hat die höchste Priorität.
- Bei t=5 ist alleine, dann hat die höchste Priorität.
- Bei t=6 ist das j-te Auftreten für
, für
, dann gilt für die absoluten Deadlines
. Damit hat die höchste Priorität.
- Bei t=7 ist alleine, dann hat die höchste Priorität.
- Bei t=8 ist das j-te Auftreten für
, für
, dann gilt für die absoluten Deadlines
. Damit hat die höchste Priorität.
- Bei t=9 ist das j-te Auftreten für
, für
, dann gilt für die absoluten Deadlines
. Zusätzlioch soll bei Gleichstand die Rangfolge im Index gelten. Damit hat die höchste Priorität.
- Bei t=10 ist alleine, dann hat die höchste Priorität.
- 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 :
Für eine hybride Taskmenge mit
gibt es die hinreichende Bedingung :
(vgl. [17]:S.31).
Gerd Doeben-Henisch
2013-01-16