6.2 Scheduling für Einzelprozessoren
341
Abb. 6.14 RM-Schedule verpasst die Deadline zum Zeitpunkt 8
Solche verpassten Deadlines können nicht auftreten, wenn die Prozessorlast sehr
gering ist, sie treten dagegen möglicherweise bei hoher Prozessorlast auf, wie in
Abb. 6.14 zu sehen. Wenn die Ungleichung (6.7) erfüllt ist, ist damit garantiert,
dass die Prozessorauslastung gering genug ist, um Probleme wie in Abb. 6.14 zu
vermeiden. Die Ungleichung (6.7) ist hinreichend, aber nicht notwendig. Es könnte
damit ein RM-Schedule geben, obwohl die Ungleichung nicht erfüllt ist. Es gibt
weitere hinreichende Schranken [54].
RMS hat die folgenden wichtigen Vorteile:
• Unter den verdrängenden Scheduling-Algorithmen mit fester Priorität für Einzelprozessoren ist RMS optimal [54].
• RMS basiert auf statischen Prioritäten. Das ermöglicht die Verwendung von
RMS in Standard-Betriebssystemen, die feste Prioritäten unterstützen.
• Wenn die sechs RM-Annahmen eingehalten werden, ist ein Schedule garantiert
(siehe [81]).
RMS ist die Basis vieler formaler Schedulability-Beweise. Bei der Konstruktion
von Beispielen und beim Führen von Beweisen ist es hilfreich, zu wissen, welche
Situationen hinsichtlich des Findens von Schedules mit RMS besonders kritisch sind.
Wir setzen dazu zunächst folgende Eigenschaft voraus:
Eigenschaft 6.1: Wir nehmen an, dass jeder Job beendet wird, bevor der nächste Job
derselben Task ausführungsbereit wird.
Definition 6.12: Ein kritischer Zeitpunkt (engl. critical time instant) für eine Task
τ i ist der Zeitpunkt t, an dem ein Eintreffen der Task zur größten Antwortzeit führt.
Theorem 6.4 (Critical instant theorem): Für ein Scheduling mit festen Prioritäten
auf einem Einzelprozessor ist die Antwortzeit für jede Task τ i maximiert, wenn τ i
gleichzeitig mit allen anderen Tasks einer höheren Priorität ausführungsbereit wird.
Beweis: Wir zeigen hier den originalen Beweis von Liu and Layland [348] in deutscher Übersetzung und mit Anpassung an unsere Notation: „Sei τ = {τ 1 , ..., τ n } eine
Menge von nach Prioritäten sortierten Tasks, wobei τ n die Task mit der niedrigsten
Priorität ist. Wir betrachten ein Eintreffen von τ n zur Zeit t 1 . Wir nehmen an, dass
zwischen der Zeit t 1 und der Zeit t 1 +T n (der Zeit, zu der die nächste Anforderung von
τ n erfolgt) Task τ i , i < n, zu den Zeitpunkten t 2 , t 2 + T i , t 2 + 2T i , ... , t 2 + kT i ausführungsbereit wird, wie in Abb. 6.15 gezeigt. Offensichtlich wird die Verdrängung von
τ
τ
1
2
t
24
22
20
18
14 16
10
8
4
2
12
6
0
341
Abb. 6.14 RM-Schedule verpasst die Deadline zum Zeitpunkt 8
Solche verpassten Deadlines können nicht auftreten, wenn die Prozessorlast sehr
gering ist, sie treten dagegen möglicherweise bei hoher Prozessorlast auf, wie in
Abb. 6.14 zu sehen. Wenn die Ungleichung (6.7) erfüllt ist, ist damit garantiert,
dass die Prozessorauslastung gering genug ist, um Probleme wie in Abb. 6.14 zu
vermeiden. Die Ungleichung (6.7) ist hinreichend, aber nicht notwendig. Es könnte
damit ein RM-Schedule geben, obwohl die Ungleichung nicht erfüllt ist. Es gibt
weitere hinreichende Schranken [54].
RMS hat die folgenden wichtigen Vorteile:
• Unter den verdrängenden Scheduling-Algorithmen mit fester Priorität für Einzelprozessoren ist RMS optimal [54].
• RMS basiert auf statischen Prioritäten. Das ermöglicht die Verwendung von
RMS in Standard-Betriebssystemen, die feste Prioritäten unterstützen.
• Wenn die sechs RM-Annahmen eingehalten werden, ist ein Schedule garantiert
(siehe [81]).
RMS ist die Basis vieler formaler Schedulability-Beweise. Bei der Konstruktion
von Beispielen und beim Führen von Beweisen ist es hilfreich, zu wissen, welche
Situationen hinsichtlich des Findens von Schedules mit RMS besonders kritisch sind.
Wir setzen dazu zunächst folgende Eigenschaft voraus:
Eigenschaft 6.1: Wir nehmen an, dass jeder Job beendet wird, bevor der nächste Job
derselben Task ausführungsbereit wird.
Definition 6.12: Ein kritischer Zeitpunkt (engl. critical time instant) für eine Task
τ i ist der Zeitpunkt t, an dem ein Eintreffen der Task zur größten Antwortzeit führt.
Theorem 6.4 (Critical instant theorem): Für ein Scheduling mit festen Prioritäten
auf einem Einzelprozessor ist die Antwortzeit für jede Task τ i maximiert, wenn τ i
gleichzeitig mit allen anderen Tasks einer höheren Priorität ausführungsbereit wird.
Beweis: Wir zeigen hier den originalen Beweis von Liu and Layland [348] in deutscher Übersetzung und mit Anpassung an unsere Notation: „Sei τ = {τ 1 , ..., τ n } eine
Menge von nach Prioritäten sortierten Tasks, wobei τ n die Task mit der niedrigsten
Priorität ist. Wir betrachten ein Eintreffen von τ n zur Zeit t 1 . Wir nehmen an, dass
zwischen der Zeit t 1 und der Zeit t 1 +T n (der Zeit, zu der die nächste Anforderung von
τ n erfolgt) Task τ i , i < n, zu den Zeitpunkten t 2 , t 2 + T i , t 2 + 2T i , ... , t 2 + kT i ausführungsbereit wird, wie in Abb. 6.15 gezeigt. Offensichtlich wird die Verdrängung von
τ
τ
1
2
t
24
22
20
18
14 16
10
8
4
2
12
6
0