6.3 Scheduling für unabhängige Jobs auf identischen Multiprozessoren
353
6.3.3 Globales Scheduling für feste Job-Prioritäten
G-EDF-Scheduling
Wir können versuchen, das zweidimensionale Problem mit Erweiterungen von Scheduling-Algorithmen für Einzelprozessoren zu lösen. Beispielsweise können wir Global EDF (G-EDF) benutzen. G-EDF definiert – wie EDF – Job-Prioritäten anhand
der Nähe der nächsten Deadlines. Wenn m Prozessoren verfügbar sind, werden jene
m Jobs ausgeführt, welche die höchsten Prioritäten unter allen verfügbaren Jobs haben. Offensichtlich sind solche Prioritäten abhängig vom Job und nicht nur von der
Task. In einer globalen Scheduling-Strategie möchten wir preemptions von Jobs und
Verlagerungen von Jobs zu anderen Prozessoren möglichst selten haben. Für G-EDF
hängt die Häufigkeit davon ab, wie wir Tasks oder Jobs den Prozessoren zuordnen
[189].
Lemma 6.3: G-EDF ist nicht optimal.
Beweis: Der Beweis erfolgt durch Gegenbeispiel, übernommen von Cho et al. [101].
Wir betrachten ein Task-System mit m = 2 und C 1 = 3, D 1 = 4, C 2 = 2, D 2 = 3,
C 3 = 2 und D 3 = 3. In Abb. 6.21 (links) ist zu sehen, dass G-EDF aufgrund der
früheren Deadline J 2 und J 3 zuerst einplant. J 1 verpasst die Deadline, obwohl ein
Schedule möglich ist, wie in Abb. 6.21 (rechts) gezeigt.
1
2
J
J
J 3
3
J
J
J
2
1
t
0
1
2
3
4
4
3
2
1
0
t
Abb. 6.21 Links: G-EDF verpasst Deadline bei t = 4; rechts: mögliches Schedule
⊓ ⊔
Das Problem rührt offenbar von der Unfähigkeit her, den zweiten Prozessor für
t > 2 zu nutzen.
Allgemein leidet G-EDF unter Anomalien wie dem sogenannten Dhall-Effekt
[130]: periodische Task-Mengen, in denen eine Task eine Auslastung nahe Eins hat,
können nicht mit G-EDF eingeplant werden.
Beispiel 6.12: Wir betrachten den Fall n = m + 1, um den Effekt zu demonstrieren.
353
6.3.3 Globales Scheduling für feste Job-Prioritäten
G-EDF-Scheduling
Wir können versuchen, das zweidimensionale Problem mit Erweiterungen von Scheduling-Algorithmen für Einzelprozessoren zu lösen. Beispielsweise können wir Global EDF (G-EDF) benutzen. G-EDF definiert – wie EDF – Job-Prioritäten anhand
der Nähe der nächsten Deadlines. Wenn m Prozessoren verfügbar sind, werden jene
m Jobs ausgeführt, welche die höchsten Prioritäten unter allen verfügbaren Jobs haben. Offensichtlich sind solche Prioritäten abhängig vom Job und nicht nur von der
Task. In einer globalen Scheduling-Strategie möchten wir preemptions von Jobs und
Verlagerungen von Jobs zu anderen Prozessoren möglichst selten haben. Für G-EDF
hängt die Häufigkeit davon ab, wie wir Tasks oder Jobs den Prozessoren zuordnen
[189].
Lemma 6.3: G-EDF ist nicht optimal.
Beweis: Der Beweis erfolgt durch Gegenbeispiel, übernommen von Cho et al. [101].
Wir betrachten ein Task-System mit m = 2 und C 1 = 3, D 1 = 4, C 2 = 2, D 2 = 3,
C 3 = 2 und D 3 = 3. In Abb. 6.21 (links) ist zu sehen, dass G-EDF aufgrund der
früheren Deadline J 2 und J 3 zuerst einplant. J 1 verpasst die Deadline, obwohl ein
Schedule möglich ist, wie in Abb. 6.21 (rechts) gezeigt.
1
2
J
J
J 3
3
J
J
J
2
1
t
0
1
2
3
4
4
3
2
1
0
t
Abb. 6.21 Links: G-EDF verpasst Deadline bei t = 4; rechts: mögliches Schedule
⊓ ⊔
Das Problem rührt offenbar von der Unfähigkeit her, den zweiten Prozessor für
t > 2 zu nutzen.
Allgemein leidet G-EDF unter Anomalien wie dem sogenannten Dhall-Effekt
[130]: periodische Task-Mengen, in denen eine Task eine Auslastung nahe Eins hat,
können nicht mit G-EDF eingeplant werden.
Beispiel 6.12: Wir betrachten den Fall n = m + 1, um den Effekt zu demonstrieren.