6.3 Scheduling für unabhängige Jobs auf identischen Multiprozessoren
355
Eine ähnliche Idee wird im EDF(k)-Scheduling-Algorithmus benutzt. Bei diesem
Algorithmus erhalten k Tasks der höchsten Auslastung die höchste Priorität, wobei
bei Auslastungsgleichheit beliebig entschieden wird. Alle anderen Tasks werden
nach EDF eingeplant.
Theorem 6.10: Sei τ ein sporadisches Task-System mit impliziten Deadlines. EDF(k)
wird τ auf m homogenen Prozessoren einplanen, wobei
m = (k − 1) +
U(τ (k+1) )
1 − u k
(6.32)
ist und U(τ (k+1) ) ist die Auslastung für die Task-Menge abzüglich der ersten k Tasks.
Auch für dieses Theorem kann der Beweis bei Baruah [38] gefunden werden.
EDZL-Scheduling
G-EDF kann Deadlines für Task-Mengen verpassen, für die ein Schedule möglich
wäre. Wir können G-EDF verbessern, indem wir auch den Schlupf betrachten: der
EDZL-Algorithmus benutzt G-EDF, sofern der Schlupf größer ist als Null (siehe Baruah et al. [38], Kapitel 20). Wenn der Schlupf eines Jobs allerdings Null wird, dann
wird die Priorität dieses Jobs auf die höchste Priorität unter allen Jobs angehoben,
einschließlich der gerade ausgeführten Jobs.
Beispiel 6.13: Wir betrachten das Beispiel in Abb. 6.23, welches von I. Puaut übernommen wurde [461]. Die Parameter in diesem Beispiel sind: n = 3, m = 2,
T 1 = T 2 = T 3 = 3 und C 1 = C 2 = C 3 = 2. Aus der Abb. 6.23 (links) geht hervor,
dass G-EDF für diese Parameter die Deadlines für τ 3 zu den Zeiten t = 3n mit
n = 1, 2, 3, ... verpasst. Aus Abb. 6.23 (rechts) kann gesehen werden, dass EDZL
τ
τ
τ
0
1
2
3
t
5
4
6
3
2
1
τ
τ
τ
0
1
2
3
t
5
4
6
3
2
1
Abb. 6.23 G-EDF: links: verpasste Deadlines; rechts: Verbesserung durch EDZL
dagegen die Deadlines einhält. Die Details des Verhaltens hängen dabei etwas von
der Prozessor-Zuordnung ab, die EDZL vornimmt.
∇
355
Eine ähnliche Idee wird im EDF(k)-Scheduling-Algorithmus benutzt. Bei diesem
Algorithmus erhalten k Tasks der höchsten Auslastung die höchste Priorität, wobei
bei Auslastungsgleichheit beliebig entschieden wird. Alle anderen Tasks werden
nach EDF eingeplant.
Theorem 6.10: Sei τ ein sporadisches Task-System mit impliziten Deadlines. EDF(k)
wird τ auf m homogenen Prozessoren einplanen, wobei
m = (k − 1) +
U(τ (k+1) )
1 − u k
(6.32)
ist und U(τ (k+1) ) ist die Auslastung für die Task-Menge abzüglich der ersten k Tasks.
Auch für dieses Theorem kann der Beweis bei Baruah [38] gefunden werden.
EDZL-Scheduling
G-EDF kann Deadlines für Task-Mengen verpassen, für die ein Schedule möglich
wäre. Wir können G-EDF verbessern, indem wir auch den Schlupf betrachten: der
EDZL-Algorithmus benutzt G-EDF, sofern der Schlupf größer ist als Null (siehe Baruah et al. [38], Kapitel 20). Wenn der Schlupf eines Jobs allerdings Null wird, dann
wird die Priorität dieses Jobs auf die höchste Priorität unter allen Jobs angehoben,
einschließlich der gerade ausgeführten Jobs.
Beispiel 6.13: Wir betrachten das Beispiel in Abb. 6.23, welches von I. Puaut übernommen wurde [461]. Die Parameter in diesem Beispiel sind: n = 3, m = 2,
T 1 = T 2 = T 3 = 3 und C 1 = C 2 = C 3 = 2. Aus der Abb. 6.23 (links) geht hervor,
dass G-EDF für diese Parameter die Deadlines für τ 3 zu den Zeiten t = 3n mit
n = 1, 2, 3, ... verpasst. Aus Abb. 6.23 (rechts) kann gesehen werden, dass EDZL
τ
τ
τ
0
1
2
3
t
5
4
6
3
2
1
τ
τ
τ
0
1
2
3
t
5
4
6
3
2
1
Abb. 6.23 G-EDF: links: verpasste Deadlines; rechts: Verbesserung durch EDZL
dagegen die Deadlines einhält. Die Details des Verhaltens hängen dabei etwas von
der Prozessor-Zuordnung ab, die EDZL vornimmt.
∇