350
6 Abbildung von Anwendungen
Beweis: Siehe Lopez et al. [356].
Lopez et al. haben auch gezeigt, dass WF und WFI Gleichung (6.19) als ihre
untere Schranke haben, die anderen Algorithmen haben Gleichung (6.23) als ihre
untere Schranke. Die Schranke in Gleichung (6.19) nähert sich 1, wenn U max sich
der 1 nähert:
U B1 (1) = 1
(6.24)
Wenn U max sich der 1 nähert, so nähert sich β ebenfalls der 1 und für U B2 gilt:
U B2 (1) =
m + 1
2
(6.25)
Verglichen mit der Schranke in Gleichung (6.24) erlaubt uns die Schranke in
Gleichung (6.25) mehrere Prozessoren effizienter nutzen. Aufgrund dieser Schranken
sind daher WF und WFI schlechter als die anderen sieben Algorithmen. Empirisch
wurde gezeigt, dass FFD besser zu sein scheint als FF oder FFI und BFD scheint
besser zu sein als BF und BFI [38]. Es gibt auch theoretische Anhaltspunkte, welche
diese Beobachtung unterstützen [38].
Die skizzierten neun Algorithmen sind relativ einfache Algorithmen. Wir nehmen davon Abstand, ausgefeiltere Algorithmen für dasselbe Problem zu präsentieren,
denn das Problem ist zu stark vereinfacht, um realistische Anwendungen widerzuspiegeln.
• Das Scheduling-Problem, wie es in diesem Abschnitt behandelt wurde, ist ein sehr
eingeschränktes. Es gibt keine Reihenfolgebeschränkungen, keine Verdrängungen
und nur identische Prozessoren.
• Partitioniertes Scheduling kann selbst dann, wenn Jobs ausführungsbereit sind,
zu unbenutzten Prozessoren führen. Daher ist partitioniertes Scheduling nicht
arbeitserhaltend (engl. work conserving). Folglich ist Optimalität nicht garantiert.
Mithin enthält dieser Abschnitt Basiswissen, aber praktische Probleme benötigen
ausgefeiltere Ansätze, wie die in den nachfolgenden Abschnitten präsentierten.
6.3.2 Globales Scheduling mit dynamischen Prioritäten
Globales Scheduling kann verhindern, dass trotz vorhandener ausführbarer Jobs einige Prozessoren unbenutzt sind. Beim globalen Scheduling ist die Zuordnung von
Prozessoren zu Tasks oder Jobs dynamisch. Dies gibt uns mehr Flexibilität, v.a.
in Gegenwart von sich verändernden Arbeitslasten oder sich ändernden Verfügbarkeiten von Prozessoren. Aufgrund des Fortfalls von Ausführungsbeschränkungen
werden die oberen Schranken der Auslastungen wie in den Gleichungen (6.19) und
(6.23) ersetzt durch:
U sum ≤ m
(6.26)
6 Abbildung von Anwendungen
Beweis: Siehe Lopez et al. [356].
Lopez et al. haben auch gezeigt, dass WF und WFI Gleichung (6.19) als ihre
untere Schranke haben, die anderen Algorithmen haben Gleichung (6.23) als ihre
untere Schranke. Die Schranke in Gleichung (6.19) nähert sich 1, wenn U max sich
der 1 nähert:
U B1 (1) = 1
(6.24)
Wenn U max sich der 1 nähert, so nähert sich β ebenfalls der 1 und für U B2 gilt:
U B2 (1) =
m + 1
2
(6.25)
Verglichen mit der Schranke in Gleichung (6.24) erlaubt uns die Schranke in
Gleichung (6.25) mehrere Prozessoren effizienter nutzen. Aufgrund dieser Schranken
sind daher WF und WFI schlechter als die anderen sieben Algorithmen. Empirisch
wurde gezeigt, dass FFD besser zu sein scheint als FF oder FFI und BFD scheint
besser zu sein als BF und BFI [38]. Es gibt auch theoretische Anhaltspunkte, welche
diese Beobachtung unterstützen [38].
Die skizzierten neun Algorithmen sind relativ einfache Algorithmen. Wir nehmen davon Abstand, ausgefeiltere Algorithmen für dasselbe Problem zu präsentieren,
denn das Problem ist zu stark vereinfacht, um realistische Anwendungen widerzuspiegeln.
• Das Scheduling-Problem, wie es in diesem Abschnitt behandelt wurde, ist ein sehr
eingeschränktes. Es gibt keine Reihenfolgebeschränkungen, keine Verdrängungen
und nur identische Prozessoren.
• Partitioniertes Scheduling kann selbst dann, wenn Jobs ausführungsbereit sind,
zu unbenutzten Prozessoren führen. Daher ist partitioniertes Scheduling nicht
arbeitserhaltend (engl. work conserving). Folglich ist Optimalität nicht garantiert.
Mithin enthält dieser Abschnitt Basiswissen, aber praktische Probleme benötigen
ausgefeiltere Ansätze, wie die in den nachfolgenden Abschnitten präsentierten.
6.3.2 Globales Scheduling mit dynamischen Prioritäten
Globales Scheduling kann verhindern, dass trotz vorhandener ausführbarer Jobs einige Prozessoren unbenutzt sind. Beim globalen Scheduling ist die Zuordnung von
Prozessoren zu Tasks oder Jobs dynamisch. Dies gibt uns mehr Flexibilität, v.a.
in Gegenwart von sich verändernden Arbeitslasten oder sich ändernden Verfügbarkeiten von Prozessoren. Aufgrund des Fortfalls von Ausführungsbeschränkungen
werden die oberen Schranken der Auslastungen wie in den Gleichungen (6.19) und
(6.23) ersetzt durch:
U sum ≤ m
(6.26)