6.2 Scheduling für Einzelprozessoren
335
Zum Zeitpunkt 4 wird Job J 1 wie oben verdrängt. Zum Zeitpunkt 5 wird Job J 2
nun auch verdrängt, weil er einen höheren Schlupf hat als Job J 3 .
∇
LL ist auch ein verdrängendes (präemptives) Scheduling-Verfahren. Verdrängungen
sind dabei nicht auf Zeitpunkte beschränkt, zu denen neue Jobs ausführungsbereit
werden. Ein negativer Schlupf ist eine frühe Warnung für Deadlines, die verpasst
werden. Man kann zeigen (in [349] ist dies als Übung dem Leser überlassen), dass
LL auch ein optimales Scheduling-Verfahren für Einzelprozessor-Systeme in dem
Sinne ist, dass es ein Schedule findet, wenn ein Schedule existiert. Wegen seiner
dynamischen Prioritäten kann man es nicht in Standard-Betriebssystemen einsetzen,
da diese üblicherweise nur statische Task-Prioritäten verwalten können. Im Gegensatz zu EDF-Scheduling erfordert LL-Scheduling Wissen über die Ausführungszeit.
Seine Anwendungsgebiete sind daher auf solche Situationen beschränkt, in denen
seine Eigenschaften vorteilhaft sind. In den Unterabschnitten 6.3.3 und 6.3.4 wird
gezeigt werden, dass der Schlupf im Multiprozessor-Scheduling eine Rolle spielen
kann.
Verfahren ohne Verdrängung
Wir betrachten nunmehr den Fall, in dem Verdrängungen (engl. preemptions) nicht
erlaubt sind, in unserer Klassifikation als (1|r i |L max ) bezeichnet.
Theorem 6.3: Wenn Verdrängungen nicht erlaubt sind, dann müssen optimale Schedules den Prozessor zu gewissen Zeiten unbeschäftigt lassen, damit spät eintreffende
Jobs mit frühen Deadlines rechtzeitig beendet werden können.
Beweis: Nehmen wir an, dass ein optimaler nicht verdrängender Scheduler (der
kein Wissen über die Zukunft hat) den Prozessor immer auslastet. Dieser Scheduler
muss das Schedule in Abb. 6.9 optimal erzeugen (d.h. er muss ein Schedule finden,
wenn eines existiert). Für das Beispiel in Abb. 6.9 nehmen wir zwei Tasks an. Sei
τ
τ
2
1
2
3
4
5
6
7
8
9
1
0
t
Abb. 6.9 Der Scheduler darf den Prozessor nicht vollständig auslasten
τ 1 eine periodische Task mit C 1 = 2, T 1 = 4, D 1 = 4 und r 1 = 0. Sei τ 2 eine
sporadische Task mit C 2 = 1, D 2 = 1, T 2 = 4 und r 2 = 1, d.h. sporadisch zu
Zeiten 4 ∗ n + 1 ausführungsbereit werdend. Wir nehmen an, dass die gleichzeitige
Ausführung beider Tasks aufgrund von Ressourcenkonflikten nicht möglich ist.
Unter diesen Annahmen muss der Scheduler die Ausführung von Task τ 1 zum
Zeitpunkt 0 starten, da er ja den Prozessor voll auslasten soll. Da der Scheduler
335
Zum Zeitpunkt 4 wird Job J 1 wie oben verdrängt. Zum Zeitpunkt 5 wird Job J 2
nun auch verdrängt, weil er einen höheren Schlupf hat als Job J 3 .
∇
LL ist auch ein verdrängendes (präemptives) Scheduling-Verfahren. Verdrängungen
sind dabei nicht auf Zeitpunkte beschränkt, zu denen neue Jobs ausführungsbereit
werden. Ein negativer Schlupf ist eine frühe Warnung für Deadlines, die verpasst
werden. Man kann zeigen (in [349] ist dies als Übung dem Leser überlassen), dass
LL auch ein optimales Scheduling-Verfahren für Einzelprozessor-Systeme in dem
Sinne ist, dass es ein Schedule findet, wenn ein Schedule existiert. Wegen seiner
dynamischen Prioritäten kann man es nicht in Standard-Betriebssystemen einsetzen,
da diese üblicherweise nur statische Task-Prioritäten verwalten können. Im Gegensatz zu EDF-Scheduling erfordert LL-Scheduling Wissen über die Ausführungszeit.
Seine Anwendungsgebiete sind daher auf solche Situationen beschränkt, in denen
seine Eigenschaften vorteilhaft sind. In den Unterabschnitten 6.3.3 und 6.3.4 wird
gezeigt werden, dass der Schlupf im Multiprozessor-Scheduling eine Rolle spielen
kann.
Verfahren ohne Verdrängung
Wir betrachten nunmehr den Fall, in dem Verdrängungen (engl. preemptions) nicht
erlaubt sind, in unserer Klassifikation als (1|r i |L max ) bezeichnet.
Theorem 6.3: Wenn Verdrängungen nicht erlaubt sind, dann müssen optimale Schedules den Prozessor zu gewissen Zeiten unbeschäftigt lassen, damit spät eintreffende
Jobs mit frühen Deadlines rechtzeitig beendet werden können.
Beweis: Nehmen wir an, dass ein optimaler nicht verdrängender Scheduler (der
kein Wissen über die Zukunft hat) den Prozessor immer auslastet. Dieser Scheduler
muss das Schedule in Abb. 6.9 optimal erzeugen (d.h. er muss ein Schedule finden,
wenn eines existiert). Für das Beispiel in Abb. 6.9 nehmen wir zwei Tasks an. Sei
τ
τ
2
1
2
3
4
5
6
7
8
9
1
0
t
Abb. 6.9 Der Scheduler darf den Prozessor nicht vollständig auslasten
τ 1 eine periodische Task mit C 1 = 2, T 1 = 4, D 1 = 4 und r 1 = 0. Sei τ 2 eine
sporadische Task mit C 2 = 1, D 2 = 1, T 2 = 4 und r 2 = 1, d.h. sporadisch zu
Zeiten 4 ∗ n + 1 ausführungsbereit werdend. Wir nehmen an, dass die gleichzeitige
Ausführung beider Tasks aufgrund von Ressourcenkonflikten nicht möglich ist.
Unter diesen Annahmen muss der Scheduler die Ausführung von Task τ 1 zum
Zeitpunkt 0 starten, da er ja den Prozessor voll auslasten soll. Da der Scheduler