Earliest Deadline First (EDF)

Bei diesem Verfahren werden die Prioritäten dynamisch zur Laufzeit vergeben und können sich sehr oft ändern. Zu einem Zeitpunkt bekommt immer derjenige Thread die höchste Priorität zugewiesen, dessen Deadline zeitlich am nächsten ist. In [LiLa73] und [SSRB98] wird gezeigt, daß man dadurch die fehlerfreie Ausführung für beliebige periodische Threads bei einer Auslastung des Prozessors von bis zu 1 garantieren kann.

Abbildung 2.3 zeigt das Ablaufdiagramm unserer drei Threads unter Earliest Deadline First Scheduling.

Abbildung 2.3: Drei Threads unter Earliest Deadline First Scheduling

Einer der Vorteile von EDF ist, daß es in vielen Fällen auch mit Threads zurechtkommt, bei denen die relative Deadline und die Periode nicht übereinstimmen. Leider kann man für solche Threads aber nichts garantieren. Abbildung 2.4 zeigt ein Beispiel eines solchen Threads. Wenn drei solche Threads gleichzeitig gestartet werden, kann mindestens einer seine Deadline nicht einhalten, obwohl jeder Thread alleine den Prozessor nur zu $\frac{1}{6}$ auslastet.

Abbildung 2.4: Ein Thread mit $D_0\not=T_0$ (6,1,2)