6.2 Scheduling für Einzelprozessoren
333
Zum Zeitpunkt 4 hat Job J 2 eine frühere Deadline. Daher wird J 1 verdrängt. Zur
Zeit 5 wird J 3 ausführungsbereit. Aufgrund der späteren Deadline wird J 2 nicht
verdrängt. J 3 startet erst, wenn J 2 beendet ist. Danach wird J 3 bis zu seinem Ende
ausgeführt. J 1 wird erst ausgeführt, wenn J 3 beendet ist.
∇
Wenn für die Warteschlange sortierte Listen verwendet werden, ist die Komplexität
von EDF O(n 2 ). Sogenannte Bucket-Arrays können zur Reduktion der Laufzeit beitragen. Die Prioritäten sind offensichtlich dynamisch: sie hängen davon ab, welche
Deadline die nächste ist. Da EDF dynamische Prioritäten benutzt, kann es es nicht
mit einem Betriebssystem verwendet werden, welches nur statische Prioritäten unterstützt. Allerdings wurde gezeigt, dass man Betriebssysteme so erweitern kann,
dass EDF auf Anwendungsebene simuliert wird [132].
Beweis (des Theorems 6.2): Sei S ein Schedule, welches durch einen von EDF
verschiedenen Algorithmus A erzeugt wird. Sei S E DF ein durch EDF erzeugtes
Schedule. Wir zerlegen nunmehr die Zeitachse in diskrete Zeitabschnitte von jeweils
einer Zeiteinheit4. Jeder Zeitabschnitt enthält die Zeiten im Intervall [t, t+1). Sei
S(t) der Job, der gemäß Schedule S im Zeitabschnitt [t, t+1) ausgeführt wird. Sei
E(t) der Job, der zur Zeit t unter allen verfügbaren Jobs die früheste Deadline besitzt.
Sei ferner t E (t) die Zeit (≥ t), zu welcher Job E(t) im Schedule S seine Ausführung
beginnt. Schedule S ist kein EDF-Schedule. Daher gibt es eine Zeit t, zu der nicht
der Job mit der frühesten Deadline ausgeführt wird. Für t gilt S(t) E(t) (siehe
Abb. 6.6).
=4
t
t
E t
( )=2
( E
t )=2
6
1
2
t
11
10
9
8
7
5
4
3
2
1
0
3
E
=5
t
J
J
J
( )=3
S
S
Abb. 6.6 ScheduleS
Mit denselben Argumenten wie bei Jacksons Regel können wir zeigen, dass die
Vertauschung S(t) E(t) wie in Abb. 6.7 nicht die maximale Verspätung erhöht.
Daher kann jedes Schedule, das kein EDF-Schedule ist, durch eine begrenzte
Anzahl von Vertauschungen in ein EDF-Schedule umgeformt werden, ohne die
maximale Verspätung zu erhöhen. Also ist EDF unter den möglichen Algorithmen
optimal.
Wir können zeigen, dass das Vertauschen alle Deadlines einhält, sofern sie im
Schedule S eingehalten wurden. Aufgrund der ursprünglichen Annahme ist die
4 Dieser Beweis nimmt an, dass wir mit diskreten Zeiten arbeiten. Er kann auf reelle (kontinuierliche)
Zeiten erweitert werden.
333
Zum Zeitpunkt 4 hat Job J 2 eine frühere Deadline. Daher wird J 1 verdrängt. Zur
Zeit 5 wird J 3 ausführungsbereit. Aufgrund der späteren Deadline wird J 2 nicht
verdrängt. J 3 startet erst, wenn J 2 beendet ist. Danach wird J 3 bis zu seinem Ende
ausgeführt. J 1 wird erst ausgeführt, wenn J 3 beendet ist.
∇
Wenn für die Warteschlange sortierte Listen verwendet werden, ist die Komplexität
von EDF O(n 2 ). Sogenannte Bucket-Arrays können zur Reduktion der Laufzeit beitragen. Die Prioritäten sind offensichtlich dynamisch: sie hängen davon ab, welche
Deadline die nächste ist. Da EDF dynamische Prioritäten benutzt, kann es es nicht
mit einem Betriebssystem verwendet werden, welches nur statische Prioritäten unterstützt. Allerdings wurde gezeigt, dass man Betriebssysteme so erweitern kann,
dass EDF auf Anwendungsebene simuliert wird [132].
Beweis (des Theorems 6.2): Sei S ein Schedule, welches durch einen von EDF
verschiedenen Algorithmus A erzeugt wird. Sei S E DF ein durch EDF erzeugtes
Schedule. Wir zerlegen nunmehr die Zeitachse in diskrete Zeitabschnitte von jeweils
einer Zeiteinheit4. Jeder Zeitabschnitt enthält die Zeiten im Intervall [t, t+1). Sei
S(t) der Job, der gemäß Schedule S im Zeitabschnitt [t, t+1) ausgeführt wird. Sei
E(t) der Job, der zur Zeit t unter allen verfügbaren Jobs die früheste Deadline besitzt.
Sei ferner t E (t) die Zeit (≥ t), zu welcher Job E(t) im Schedule S seine Ausführung
beginnt. Schedule S ist kein EDF-Schedule. Daher gibt es eine Zeit t, zu der nicht
der Job mit der frühesten Deadline ausgeführt wird. Für t gilt S(t) E(t) (siehe
Abb. 6.6).
=4
t
t
E t
( )=2
( E
t )=2
6
1
2
t
11
10
9
8
7
5
4
3
2
1
0
3
E
=5
t
J
J
J
( )=3
S
S
Abb. 6.6 ScheduleS
Mit denselben Argumenten wie bei Jacksons Regel können wir zeigen, dass die
Vertauschung S(t) E(t) wie in Abb. 6.7 nicht die maximale Verspätung erhöht.
Daher kann jedes Schedule, das kein EDF-Schedule ist, durch eine begrenzte
Anzahl von Vertauschungen in ein EDF-Schedule umgeformt werden, ohne die
maximale Verspätung zu erhöhen. Also ist EDF unter den möglichen Algorithmen
optimal.
Wir können zeigen, dass das Vertauschen alle Deadlines einhält, sofern sie im
Schedule S eingehalten wurden. Aufgrund der ursprünglichen Annahme ist die
4 Dieser Beweis nimmt an, dass wir mit diskreten Zeiten arbeiten. Er kann auf reelle (kontinuierliche)
Zeiten erweitert werden.