6.2 Scheduling für Einzelprozessoren
343
τ
τ
τ
i +1
+1
i
i
t
Abb. 6.16 Falten von Tasks benachbarter Prioritäten
zur vierten Deadline von τ i . Deshalb können wir die Ausführungszeiten von Task
τ i+1 in die Ausführungszeiten von Task τ i hinein falten und eine neue Task τ ′
i+1
erzeugen, welche die Ausführungszeiten der beiden ursprünglichen Tasks enthält.
Dieses Falten ist möglich, wenn die gesamte Ausführungszeit der beiden Tasks nicht
die Periode von τ i+1 übersteigt. Dieses Verfahren kann in derselben Weise mit der
Task der nächstniedrigeren Priorität wiederholt werden. Dieses Falten ist möglich,
solange die Gesamtauslastung nicht größer ist als 1.
⊓ ⊔
Die Schranken in den Ungleichungen (6.7) oder (6.9) erlauben einen einfachen Test
für die Existenz eines Schedules.
Aufgrund des Theorems der kritischen Zeitpunkte muss man beim Beweis der
Optimalität von RMS nur den Fall betrachten, in dem alle Tasks gleichzeitig mit
allen anderen einer höheren Priorität ausführungsbereit werden.
Earliest Deadline First Scheduling
EDF kann auch auf Mengen periodischer Tasks angewendet werden. Es reicht offensichtlich aus, das Scheduling-Problem für eine einzelne Hyperperiode wie ein
aperiodisches Scheduling-Problem zu lösen. Die Lösung kann dann für alle weiteren
Hyperperioden angewandt werden. So beträgt beispielsweise die Dauer der Hyperperiode für das Beispiel von Abb. 6.14 40 Zeiteinheiten. Aus der Optimalität von
EDF für nicht-periodische Schedules ergibt sich, dass EDF auch für eine einzelne
Hyperperiode optimal ist, damit also auch für das gesamte Scheduling-Problem. Es
müssen also keine weiteren Bedingungen eingehalten werden, um die Optimalität
des Verfahrens zu garantieren. Daraus folgt, dass EDF auch für den Fall U sum = 1
optimal ist.
Beispiel 6.9: Dementsprechend wird keine Deadline verpasst, wenn für das Beispiel
aus Abb. 6.14 EDF-Scheduling verwendet wird (siehe Abb. 6.17). Zum Zeitpunkt 5
unterscheidet sich das Verhalten von dem Verhalten bei RM-Scheduling: durch die
frühere Deadline von τ 2 wird diese Task nicht verdrängt.
343
τ
τ
τ
i +1
+1
i
i
t
Abb. 6.16 Falten von Tasks benachbarter Prioritäten
zur vierten Deadline von τ i . Deshalb können wir die Ausführungszeiten von Task
τ i+1 in die Ausführungszeiten von Task τ i hinein falten und eine neue Task τ ′
i+1
erzeugen, welche die Ausführungszeiten der beiden ursprünglichen Tasks enthält.
Dieses Falten ist möglich, wenn die gesamte Ausführungszeit der beiden Tasks nicht
die Periode von τ i+1 übersteigt. Dieses Verfahren kann in derselben Weise mit der
Task der nächstniedrigeren Priorität wiederholt werden. Dieses Falten ist möglich,
solange die Gesamtauslastung nicht größer ist als 1.
⊓ ⊔
Die Schranken in den Ungleichungen (6.7) oder (6.9) erlauben einen einfachen Test
für die Existenz eines Schedules.
Aufgrund des Theorems der kritischen Zeitpunkte muss man beim Beweis der
Optimalität von RMS nur den Fall betrachten, in dem alle Tasks gleichzeitig mit
allen anderen einer höheren Priorität ausführungsbereit werden.
Earliest Deadline First Scheduling
EDF kann auch auf Mengen periodischer Tasks angewendet werden. Es reicht offensichtlich aus, das Scheduling-Problem für eine einzelne Hyperperiode wie ein
aperiodisches Scheduling-Problem zu lösen. Die Lösung kann dann für alle weiteren
Hyperperioden angewandt werden. So beträgt beispielsweise die Dauer der Hyperperiode für das Beispiel von Abb. 6.14 40 Zeiteinheiten. Aus der Optimalität von
EDF für nicht-periodische Schedules ergibt sich, dass EDF auch für eine einzelne
Hyperperiode optimal ist, damit also auch für das gesamte Scheduling-Problem. Es
müssen also keine weiteren Bedingungen eingehalten werden, um die Optimalität
des Verfahrens zu garantieren. Daraus folgt, dass EDF auch für den Fall U sum = 1
optimal ist.
Beispiel 6.9: Dementsprechend wird keine Deadline verpasst, wenn für das Beispiel
aus Abb. 6.14 EDF-Scheduling verwendet wird (siehe Abb. 6.17). Zum Zeitpunkt 5
unterscheidet sich das Verhalten von dem Verhalten bei RM-Scheduling: durch die
frühere Deadline von τ 2 wird diese Task nicht verdrängt.