6.3 Scheduling für unabhängige Jobs auf identischen Multiprozessoren
351
Allerdings bringt es diese bessere Auslastung mit sich, dass zusätzlicher Overhead für Scheduling-Entscheidungen, Verdrängungen und Verlagerungen von Jobs
entsteht.
Proportional fair (Pfair) scheduling
Die Grundidee von proportional fair (pfair)-Scheduling [39] ist es, jede Task mit
einer Rate auszuführen, die proportional zu ihrer Auslastung ist6. Wenn wir beispielsweise eine 50-prozentige Auslastung (d.h. u i = 0, 5) für eine Menge von Tasks
haben, dann sollte jede Task etwa zur Hälfte der Zeit ausgeführt werden, unabhängig
von der Anzahl der Prozessoren. Für pfair-Scheduling setzen wir voraus, dass die
Zeit quantisiert ist und mit ganzen Zahlen abgezählt ist. Jedes derart abgezählte
Zeitintervall nennen wir einen Zeitschlitz (engl. time slot). Ebenso nehmen wir an,
dass die C i und T i -Parameter von ganzen Zahlen repräsentiert werden.
Definition 6.18: Der Verzug (engl. lag) einer Task τ i zur Zeit t in Bezug auf ein
Schedule S, bezeichnet als lag(S, τ i , t), ist die Differenz zwischen der Anzahl von
Prozessorzeitschlitzen, die der Task schon zugewiesen wurden, und der Anzahl,
welche die Task schon bekommen sollte:
lag(S, τ i , t) = u i ∗ t −
t−1
u=0
alloc(S, τ i , u)
(6.27)
Der erste Term ist die gewünschte Ausführungszeit der Task τ i , der zweite Term
ist die realisierte Ausführungszeit im Schedule S. Ein Schedule heißt pfair-Schedule,
wenn der Verzug im Intervall (−1, +1) bleibt.
Beispiel 6.10: Abb. 6.19 zeigt die realisierte Ausführungszeit als Funktion der realen
Zeit. Die tatsächliche Ausführungszeit sollte die beiden gestrichelten Linien nicht
erreichen.
Ausführungszeit
t
+/- 1
Abb. 6.19 Ausführungszeit als Funktion der Zeit
∇
6 Die Darstellung von pfair-Scheduling basiert auf Folien von I. Puaut [462].
351
Allerdings bringt es diese bessere Auslastung mit sich, dass zusätzlicher Overhead für Scheduling-Entscheidungen, Verdrängungen und Verlagerungen von Jobs
entsteht.
Proportional fair (Pfair) scheduling
Die Grundidee von proportional fair (pfair)-Scheduling [39] ist es, jede Task mit
einer Rate auszuführen, die proportional zu ihrer Auslastung ist6. Wenn wir beispielsweise eine 50-prozentige Auslastung (d.h. u i = 0, 5) für eine Menge von Tasks
haben, dann sollte jede Task etwa zur Hälfte der Zeit ausgeführt werden, unabhängig
von der Anzahl der Prozessoren. Für pfair-Scheduling setzen wir voraus, dass die
Zeit quantisiert ist und mit ganzen Zahlen abgezählt ist. Jedes derart abgezählte
Zeitintervall nennen wir einen Zeitschlitz (engl. time slot). Ebenso nehmen wir an,
dass die C i und T i -Parameter von ganzen Zahlen repräsentiert werden.
Definition 6.18: Der Verzug (engl. lag) einer Task τ i zur Zeit t in Bezug auf ein
Schedule S, bezeichnet als lag(S, τ i , t), ist die Differenz zwischen der Anzahl von
Prozessorzeitschlitzen, die der Task schon zugewiesen wurden, und der Anzahl,
welche die Task schon bekommen sollte:
lag(S, τ i , t) = u i ∗ t −
t−1
u=0
alloc(S, τ i , u)
(6.27)
Der erste Term ist die gewünschte Ausführungszeit der Task τ i , der zweite Term
ist die realisierte Ausführungszeit im Schedule S. Ein Schedule heißt pfair-Schedule,
wenn der Verzug im Intervall (−1, +1) bleibt.
Beispiel 6.10: Abb. 6.19 zeigt die realisierte Ausführungszeit als Funktion der realen
Zeit. Die tatsächliche Ausführungszeit sollte die beiden gestrichelten Linien nicht
erreichen.
Ausführungszeit
t
+/- 1
Abb. 6.19 Ausführungszeit als Funktion der Zeit
∇
6 Die Darstellung von pfair-Scheduling basiert auf Folien von I. Puaut [462].