352
6 Abbildung von Anwendungen
Für das pfair-Scheduling teilen wir jede Task τ i in Subtasks τ
j
i auf, wobei j
die Ausführungsintervalle aufzählt. Für jede Subtask definieren wir eine PseudoBereitstellungszeit r(τ
j
i ) und eine Pseudo-Deadline d(τ
j
i ):
r(τ
j
i ) =
j − 1
u i
(6.28)
d(τ
j
i ) =
j
u i
(6.29)
Beispiel 6.11: Betrachte eine Task τ i mit C i = 8,T i = 11. Mögliche Intervalle für
die Anzahl der realisierten Ausführungszeitschlitze sind für jedes j in Abb. 6.20
gezeigt.
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
24
22
20
18
16
14
12
10
8
6
4
2
0
Abb. 6.20 Mögliche Intervalle realisierter Ausführungszeit
Beispielsweise gilt:
r(τ
6
i ) =
6 − 1
8/11
=
55
8
= 6
d(τ
6
i ) =
6
8/11
=
66
8
= 9
Daher muss die sechste Subtask von τ i im Intervall (6:9) ausgeführt werden.
∇
Ein spezieller Ansatz für die Zuordnung von einer korrekten Anzahl von Zeitschlitzen wird in dem Buch von Baruah et al. [38] vorgestellt. Im Allgemeinen gibt
es Variationen dieses Schemas: wir können EDF auf Pseudo-Deadlines anwenden
oder wir können EDF modifizieren, indem wir Regeln definieren, die im Fall eines
Gleichstands der Scheduling-Kriterien gelten. Es ist möglich, bis zu einer vollen
Prozessor-Auslastung, d.h. U sum ≤ m, Schedules zu garantieren.
Potentiell leidet pfair-Scheduling unter einer großen Zahl von Verlagerungen hin
zu anderen Prozessoren. Aufgrund der Überapproximation der Ausführungszeiten
durch ganze Zahlen ist es nicht arbeitserhaltend. Es wurden Varianten vorgeschlagen,
welche die Anzahl von Job-Verlagerungen reduzieren. Auch kann die Komplexität bei
manchen Varianten reduziert werden. Pfair-Scheduling findet viele Anwendungen
in Betriebssystemen, beispielsweise beim Scheduling in virtuellen Maschinen.
6 Abbildung von Anwendungen
Für das pfair-Scheduling teilen wir jede Task τ i in Subtasks τ
j
i auf, wobei j
die Ausführungsintervalle aufzählt. Für jede Subtask definieren wir eine PseudoBereitstellungszeit r(τ
j
i ) und eine Pseudo-Deadline d(τ
j
i ):
r(τ
j
i ) =
j − 1
u i
(6.28)
d(τ
j
i ) =
j
u i
(6.29)
Beispiel 6.11: Betrachte eine Task τ i mit C i = 8,T i = 11. Mögliche Intervalle für
die Anzahl der realisierten Ausführungszeitschlitze sind für jedes j in Abb. 6.20
gezeigt.
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
24
22
20
18
16
14
12
10
8
6
4
2
0
Abb. 6.20 Mögliche Intervalle realisierter Ausführungszeit
Beispielsweise gilt:
r(τ
6
i ) =
6 − 1
8/11
=
55
8
= 6
d(τ
6
i ) =
6
8/11
=
66
8
= 9
Daher muss die sechste Subtask von τ i im Intervall (6:9) ausgeführt werden.
∇
Ein spezieller Ansatz für die Zuordnung von einer korrekten Anzahl von Zeitschlitzen wird in dem Buch von Baruah et al. [38] vorgestellt. Im Allgemeinen gibt
es Variationen dieses Schemas: wir können EDF auf Pseudo-Deadlines anwenden
oder wir können EDF modifizieren, indem wir Regeln definieren, die im Fall eines
Gleichstands der Scheduling-Kriterien gelten. Es ist möglich, bis zu einer vollen
Prozessor-Auslastung, d.h. U sum ≤ m, Schedules zu garantieren.
Potentiell leidet pfair-Scheduling unter einer großen Zahl von Verlagerungen hin
zu anderen Prozessoren. Aufgrund der Überapproximation der Ausführungszeiten
durch ganze Zahlen ist es nicht arbeitserhaltend. Es wurden Varianten vorgeschlagen,
welche die Anzahl von Job-Verlagerungen reduzieren. Auch kann die Komplexität bei
manchen Varianten reduziert werden. Pfair-Scheduling findet viele Anwendungen
in Betriebssystemen, beispielsweise beim Scheduling in virtuellen Maschinen.