6.2 Scheduling für Einzelprozessoren
339
Definition 6.10: Für periodische und sporadische Task-Systeme τ = {τ 1 , .., τ n } definieren wir die Task-Auslastung (engl. task utilization) als
u i =
C i
T i
(6.4)
Damit benutzen wir für sporadische Systeme dieselbe Notation, obwohl T i nur den
minimalen Abstand zwischen zwei Jobs bedeutet.
Definition 6.11: Für ein Task-System τ = {τ 1 ...τ n } mit der Auslastung u i von Task
τ i definieren wir das Maximum U max und die Gesamtauslastung U sum durch:
U max = max
i
(u i )
(6.5)
U sum =
i
u i
(6.6)
Rate Monotonic Scheduling
Rate Monotonic Scheduling (RMS) [348] ist wohl der bekannteste SchedulingAlgorithmus für unabhängige periodische Tasks. RMS basiert auf den folgenden
Annahmen („RM-Annahmen“):
1. Alle Tasks mit harter Deadline sind periodisch.
2. Alle Tasks sind voneinander unabhängig.
3. D i = T i für alle Tasks.
4. C i ist konstant und für alle Tasks bekannt.
5. Die Zeit für einen Kontextwechsel ist vernachlässigbar.
6. Für einen Prozessor und n Tasks wird die folgende Schranke bzgl. der Gesamtauslastung U sum eingehalten:
U sum =
n
i=1
C i
T i
≤ n(2
1/n − 1)
(6.7)
Abb. 6.12 zeigt Werte der Schranke in Ungleichung (6.7).
Abb. 6.12 Werte der rechten
Seite von Ungleichung (6.7)
0,2
0,4
0,6
0,8
1
0,724
0,728
0,734
0,743
0,757
0,780
0,828
n
1
8
2
7
6
5
4
3
1
1
(2 -1)
n n
339
Definition 6.10: Für periodische und sporadische Task-Systeme τ = {τ 1 , .., τ n } definieren wir die Task-Auslastung (engl. task utilization) als
u i =
C i
T i
(6.4)
Damit benutzen wir für sporadische Systeme dieselbe Notation, obwohl T i nur den
minimalen Abstand zwischen zwei Jobs bedeutet.
Definition 6.11: Für ein Task-System τ = {τ 1 ...τ n } mit der Auslastung u i von Task
τ i definieren wir das Maximum U max und die Gesamtauslastung U sum durch:
U max = max
i
(u i )
(6.5)
U sum =
i
u i
(6.6)
Rate Monotonic Scheduling
Rate Monotonic Scheduling (RMS) [348] ist wohl der bekannteste SchedulingAlgorithmus für unabhängige periodische Tasks. RMS basiert auf den folgenden
Annahmen („RM-Annahmen“):
1. Alle Tasks mit harter Deadline sind periodisch.
2. Alle Tasks sind voneinander unabhängig.
3. D i = T i für alle Tasks.
4. C i ist konstant und für alle Tasks bekannt.
5. Die Zeit für einen Kontextwechsel ist vernachlässigbar.
6. Für einen Prozessor und n Tasks wird die folgende Schranke bzgl. der Gesamtauslastung U sum eingehalten:
U sum =
n
i=1
C i
T i
≤ n(2
1/n − 1)
(6.7)
Abb. 6.12 zeigt Werte der Schranke in Ungleichung (6.7).
Abb. 6.12 Werte der rechten
Seite von Ungleichung (6.7)
0,2
0,4
0,6
0,8
1
0,724
0,728
0,734
0,743
0,757
0,780
0,828
n
1
8
2
7
6
5
4
3
1
1
(2 -1)
n n