356
6 Abbildung von Anwendungen
Choi et al. [102] haben gezeigt, dass EDZL in jedem Fall besser ist als EDF.
Informell kann das wie folgt gezeigt werden7: Angenommen, S ist ein EDF-Schedule
und S ′ ist ein EDZL-Schedule für dieselbe Task-Menge. Wenn ein Job zur Zeit t
in EDZL eingeplant ist, aber nicht in EDF, dann verpasst er die Deadline in EDF,
aber nicht in EDZL. Das Schedule bleibt dasselbe, wenn beide Strategien den Job
einplanen. Damit gilt für den ersten Zeitpunkt, an dem S von S ′ verschieden ist, das
Folgende:
• entweder EDZL bleibt möglich, aber EDF nicht oder
• EDZL und EDF liefern kein Schedule.
Daher ist EDZL in jedem Fall besser als EDF. Piao et al. [452] haben die folgende
Auslastungsschranke für EDZL nachgewiesen
U sum ≤
m + 1
2
(6.33)
6.3.4 Globales Scheduling für feste Task-Prioritäten
Globales Rate-Monotonic Scheduling
Ähnlich wie wir EDF zu G-EDF erweitern, können wir auch RMS zu einem Verfahren für das Multiprozessor-Scheduling, genannt G-RM, erweitern. Dabei gibt es
für G-RM eine Anomalie bezüglich der Abschwächung von Anforderungen:
Lemma 6.4: Bei G-RM kann es Fälle geben, in denen ein Schedule für ein bestimmtes Task-System existiert, aber in denen es kein Schedule gibt, wenn wir Perioden
verlängern.
Beweis: Wir beweisen die Existenz dieser Anomalie durch ein Beispiel: Wir betrachten ein Task-System mit den Parametern m = 2, n = 3, T 1 = 3, C 1 = 2, T 2 = 4,
C 2 = 2, T 3 = 12 und C 3 = 7. Abb. 6.24 zeigt das dafür mit G-RM erzeugte Schedule.
τ
τ
τ
16
3
2
1
0
2
4
6
8
t
10
12
14
Abb. 6.24 Mit G-RM erzeugtes Schedule
7 Der Hinweis auf diese informelle Erklärung stammt von J.J. Chen, TU Dortmund.