340
6 Abbildung von Anwendungen
Die Schranke für die Auslastung hat für große Werte von n einen Wert von ungefähr
0,7:
lim
n→∞
n ∗ (2
1/n − 1) = log e (2) = ln(2) ≈ 0, 7
(6.8)
Beim Rate Monotonic Scheduling ist die Priorität der Tasks eine monoton fallende
Funktion ihrer Periode. Anders ausgedrückt, haben Tasks mit einer kurzen Periode
eine höhere Priorität, wohingegen Tasks mit langer Periode eine geringere Priorität
haben. RM-Scheduling ist verdrängend mit festen Prioritäten.
Beispiel 6.6: Abb. 6.13 zeigt ein mit RMS erzeugtes Schedule. Pfeile mit zwei Spitzen deuten die Ankunftszeiten einer Task und die Deadline der vorherigen Task an.
Tasks τ 1 , τ 2 und τ 3 haben jeweils eine Periode von 2, 6 und 6. Die Ausführungszeiten
betragen 0,5, 2 und 1,75. Task τ 1 hat die kürzeste Periode und daher die höchste
Priorität. Die Task τ 2 wird mehrere Male verdrängt. Jedes Mal, wenn Task τ 1 ausführungsbereit ist, unterbricht ihr Job die gerade aktive Task. Task τ 2 hat die gleiche
Periode wie Task τ 3 , daher verdrängen sich diese beiden Tasks nicht.
τ
τ
τ
3
2
1
t
0
1
2
3
4
5
6
7
8
9
Abb. 6.13 Beispiel eines RM-Schedules
∇
Die Schranke in Ungleichung (6.7) erfordert, dass ein Teil der Rechenleistung des
Prozessors unbenutzt bleibt, um sicherzustellen, dass alle Anforderungen rechtzeitig
behandelt werden können. Warum gibt es diese Nutzungsschranke? Die Hauptursache dafür ist, dass die statischen Prioritäten des RMS bedingen, dass möglicherweise
eine Task verdrängt wird, die nahe ihrer Deadline ist und dafür eine andere, höher
priorisierte Task mit deutlich späterer Deadline zum Zuge kommt. Dadurch könnte
die Task mit niedrigerer Priorität dann ihre Deadline verpassen.
Lemma 6.1: Wenn die oben genannten sechs RM-Annahmen (siehe Seite 339)
erfüllt sind, werden alle Deadlines garantiert eingehalten (siehe Buttazzo [81]).
Beispiel 6.7: Die Task-Parameter der Abb. 6.14 sind: T 1 = 5, C 1 = 3,T 2 = 8, C 2 = 3.
Die Gesamtauslastung ist: U sum =
3
5 +
3
8 =
39
40 = 0, 975. Die Schranke der Ungleichung (6.7) ist 2 ∗ (2
1
2 − 1) ≈ 0, 828. Die Schranke wird damit nicht eingehalten somit
ist nicht garantiert, dass ein RM-Schedule existiert. Tatsächlich wird die Deadline
zur Zeit 8 verpasst. Wir nehmen hier an, dass die Berechnungen, die ihre Deadline
verpasst haben, nicht in der folgenden Periode nachgeholt werden.
∇
6 Abbildung von Anwendungen
Die Schranke für die Auslastung hat für große Werte von n einen Wert von ungefähr
0,7:
lim
n→∞
n ∗ (2
1/n − 1) = log e (2) = ln(2) ≈ 0, 7
(6.8)
Beim Rate Monotonic Scheduling ist die Priorität der Tasks eine monoton fallende
Funktion ihrer Periode. Anders ausgedrückt, haben Tasks mit einer kurzen Periode
eine höhere Priorität, wohingegen Tasks mit langer Periode eine geringere Priorität
haben. RM-Scheduling ist verdrängend mit festen Prioritäten.
Beispiel 6.6: Abb. 6.13 zeigt ein mit RMS erzeugtes Schedule. Pfeile mit zwei Spitzen deuten die Ankunftszeiten einer Task und die Deadline der vorherigen Task an.
Tasks τ 1 , τ 2 und τ 3 haben jeweils eine Periode von 2, 6 und 6. Die Ausführungszeiten
betragen 0,5, 2 und 1,75. Task τ 1 hat die kürzeste Periode und daher die höchste
Priorität. Die Task τ 2 wird mehrere Male verdrängt. Jedes Mal, wenn Task τ 1 ausführungsbereit ist, unterbricht ihr Job die gerade aktive Task. Task τ 2 hat die gleiche
Periode wie Task τ 3 , daher verdrängen sich diese beiden Tasks nicht.
τ
τ
τ
3
2
1
t
0
1
2
3
4
5
6
7
8
9
Abb. 6.13 Beispiel eines RM-Schedules
∇
Die Schranke in Ungleichung (6.7) erfordert, dass ein Teil der Rechenleistung des
Prozessors unbenutzt bleibt, um sicherzustellen, dass alle Anforderungen rechtzeitig
behandelt werden können. Warum gibt es diese Nutzungsschranke? Die Hauptursache dafür ist, dass die statischen Prioritäten des RMS bedingen, dass möglicherweise
eine Task verdrängt wird, die nahe ihrer Deadline ist und dafür eine andere, höher
priorisierte Task mit deutlich späterer Deadline zum Zuge kommt. Dadurch könnte
die Task mit niedrigerer Priorität dann ihre Deadline verpassen.
Lemma 6.1: Wenn die oben genannten sechs RM-Annahmen (siehe Seite 339)
erfüllt sind, werden alle Deadlines garantiert eingehalten (siehe Buttazzo [81]).
Beispiel 6.7: Die Task-Parameter der Abb. 6.14 sind: T 1 = 5, C 1 = 3,T 2 = 8, C 2 = 3.
Die Gesamtauslastung ist: U sum =
3
5 +
3
8 =
39
40 = 0, 975. Die Schranke der Ungleichung (6.7) ist 2 ∗ (2
1
2 − 1) ≈ 0, 828. Die Schranke wird damit nicht eingehalten somit
ist nicht garantiert, dass ein RM-Schedule existiert. Tatsächlich wird die Deadline
zur Zeit 8 verpasst. Wir nehmen hier an, dass die Berechnungen, die ihre Deadline
verpasst haben, nicht in der folgenden Periode nachgeholt werden.
∇