342
6 Abbildung von Anwendungen
1
τ i
n
t
t
t
t T
t
T
t kT
t
k
T
t T
C i
i
i
i
i
2
2
2
2
2
+1)
1
t
t
2
+
+
2
+
+
+
(
+
Abb. 6.15 Verzögern von Task τ n durch höher priorisierte Task τ i
τ n durch τ i eine gewisse Verzögerung bei der Ausführung der bei t 1 eintreffenden
Instanz von τ n bewirken, sofern nicht τ n vor t 2 fertig gestellt ist. Außerdem sehen
wir aus Abb. 6.15, dass ein Vorziehen der Zeit t 2 die Fertigstellung von τ n nicht beschleunigen würde. Durch ein solches Vorziehen bleibt die Fertigstellung entweder
unverändert oder sie wird verzögert. Also ist die Verzögerung in der Fertigstellung
von τ n am größten, wenn t 2 und t 1 übereinstimmen. Wir beweisen das Theorem,
indem wir das Argument für alle τ i , i = 2, ..., m − 1, wiederholen.”
⊓ ⊔
Implizit haben wir die Eigenschaft 6.1 im Beweis benutzt. Wenn wir den allgemeinen
Fall betrachten (d.h. den Fall, in dem die Eigenschaft 6.1 nicht gilt, siehe z.B. Baker
[33]), dann bleibt Theorem 6.4 gültig, aber der Beweis wird komplexer, wie von
Devillers et al. [129] und Bril [69] gezeigt5.
Das Theorem von den kritischen Zeitpunkten hilft, Schedules für Einzelprozessoren zu finden. Leider gilt dieses Theorem nicht für Multiprozessor-Systeme, sodass
Beweise wesentlich schwieriger werden. Man sollte sich also freuen, dass dieses
Theorem für Einzelprozessoren gilt!
Wir wollen uns nun andere Eigenschaften von RMS ansehen. Die freie Kapazität
des Prozessors wird nicht immer benötigt.
Theorem 6.5: Sei τ ein System mit periodischen Tasks. Wenn die Periode aller Tasks
ein Vielfaches der Periode der Task mit der höchsten Priorität ist, kann τ mit RMS
zeitlich eingeplant werden, wenn gilt:
U sum ≤ 1
(6.9)
Beispiel 6.8: Diese Voraussetzung wird z.B. erfüllt, wenn Tasks eines Fernsehers
mit den Raten von 25, 50 und 100 (oder 30, 60 und 120) Hertz ausgeführt werden
müssen.
∇
Beweis (von Theorem 6.5): Die Tasks seien nach Prioritäten sortiert, sodass gilt:
∀i : T i ≤ T i+1 . Wir betrachten eine Task τ i und die Task mit der nächstniedrigeren
Priorität, Task τ i+1 (siehe Abb. 6.16). Die zweite Deadline von τ i+1 passt sehr schön
5 Ich verdanke diesen Hinweis J.J. Chen von der TU Dortmund.
6 Abbildung von Anwendungen
1
τ i
n
t
t
t
t T
t
T
t kT
t
k
T
t T
C i
i
i
i
i
2
2
2
2
2
+1)
1
t
t
2
+
+
2
+
+
+
(
+
Abb. 6.15 Verzögern von Task τ n durch höher priorisierte Task τ i
τ n durch τ i eine gewisse Verzögerung bei der Ausführung der bei t 1 eintreffenden
Instanz von τ n bewirken, sofern nicht τ n vor t 2 fertig gestellt ist. Außerdem sehen
wir aus Abb. 6.15, dass ein Vorziehen der Zeit t 2 die Fertigstellung von τ n nicht beschleunigen würde. Durch ein solches Vorziehen bleibt die Fertigstellung entweder
unverändert oder sie wird verzögert. Also ist die Verzögerung in der Fertigstellung
von τ n am größten, wenn t 2 und t 1 übereinstimmen. Wir beweisen das Theorem,
indem wir das Argument für alle τ i , i = 2, ..., m − 1, wiederholen.”
⊓ ⊔
Implizit haben wir die Eigenschaft 6.1 im Beweis benutzt. Wenn wir den allgemeinen
Fall betrachten (d.h. den Fall, in dem die Eigenschaft 6.1 nicht gilt, siehe z.B. Baker
[33]), dann bleibt Theorem 6.4 gültig, aber der Beweis wird komplexer, wie von
Devillers et al. [129] und Bril [69] gezeigt5.
Das Theorem von den kritischen Zeitpunkten hilft, Schedules für Einzelprozessoren zu finden. Leider gilt dieses Theorem nicht für Multiprozessor-Systeme, sodass
Beweise wesentlich schwieriger werden. Man sollte sich also freuen, dass dieses
Theorem für Einzelprozessoren gilt!
Wir wollen uns nun andere Eigenschaften von RMS ansehen. Die freie Kapazität
des Prozessors wird nicht immer benötigt.
Theorem 6.5: Sei τ ein System mit periodischen Tasks. Wenn die Periode aller Tasks
ein Vielfaches der Periode der Task mit der höchsten Priorität ist, kann τ mit RMS
zeitlich eingeplant werden, wenn gilt:
U sum ≤ 1
(6.9)
Beispiel 6.8: Diese Voraussetzung wird z.B. erfüllt, wenn Tasks eines Fernsehers
mit den Raten von 25, 50 und 100 (oder 30, 60 und 120) Hertz ausgeführt werden
müssen.
∇
Beweis (von Theorem 6.5): Die Tasks seien nach Prioritäten sortiert, sodass gilt:
∀i : T i ≤ T i+1 . Wir betrachten eine Task τ i und die Task mit der nächstniedrigeren
Priorität, Task τ i+1 (siehe Abb. 6.16). Die zweite Deadline von τ i+1 passt sehr schön
5 Ich verdanke diesen Hinweis J.J. Chen von der TU Dortmund.