360
6 Abbildung von Anwendungen
Blaue Zahlen bedeuten Startzeiten, grüne Zahlen bedeuten das jeweilige Ausführungsende. Tasks τ 2 bis τ 6 starten alle unmittelbar, nachdem Task τ 1 beendet ist.
Tasks τ 7 bis τ 9 starten ebenfalls sofort nachdem der letzte ihrer Vorgänger die Ausführung beendet hat. Die rote Linie in Abb. 6.27 (rechts) zeigt, dass im Maximum
fünf Prozessoren benötigt werden, da ASAP-Scheduling weder eine Grenze für die
Anzahl der Prozessoren noch das Ziel einer ausgewogenen Prozessorbelastung berücksichtigt.
∇
ASAP-Scheduling minimiert den Makespan, da alle Tasks so früh wie möglich
ausgeführt werden. Der vorgestellte Algorithmus kann so erweitert werden, dass
als Ausführungszeiten auch reelle Zahlen benutzt werden. ASAP-Scheduling ist von
linearer Komplexität, vorausgesetzt wir benutzen eine intelligente Methode, um τ ′
zu berechnen. Der Algorithmus kann auch im täglichen Leben angewandt werden:
er entspricht der Situation, in der jede Person begierig alle Arbeiten so früh wie
möglich startet.
6.4.2 As-Late-As-Possible-Scheduling
As-Late-As-Possible (ALAP)-Scheduling ist der zweite einfache Algorithmus. Beim
ALAP-Scheduling werden alle Tasks so spät wie möglich gestartet. Der Algorithmus
funktioniert wie folgt:
for (t=0; sooange es nicht eingeppante Tasks gibt; t--) {
τ ′ ={aaae Tasks ohne Abhängigkeit zu einer nicht eingeppanten Task};
Setze die Startzeit aaaer Tasks in τ ′ auf (t - ihre Ausführungszeit);
}
Schiebe aaae Startzeiten so, dass die erste Task zur Zeit t=0 startet.
Der Algorithmus betrachtet zunächst die Tasks, von denen keine weitere Task
abhängt. Es wird angenommen, dass diese Tasks zum Zeitpunkt 0 enden. Ihre Startzeit wird dann aus ihrer Ausführungsdauer berechnet. Danach iteriert die Schleife
rückwärts über Zeitschritte. Wenn ein Zeitschritt erreicht wird, zu dem eine Task
spätestens beendet sein soll, wird die Startzeit dieser Task berechnet und die Task
eingeplant. Nach dem Ende der Schleife werden alle Zeiten so angepasst, dass die
erste Task zum Zeitpunkt 0 startet. Wir könnten ALAP-Scheduling auch als eine
Variante des ASAP-Scheduling betrachten, die am „anderen” Ende des Graphen
beginnt.
Beispiel 6.15: Für den Task-Graphen in Abb. 6.26 würde ALAP-Scheduling das in
Abb. 6.28 gezeigte Ergebnis generieren. Die Farbkodierung ist dieselbe wie beim
ASAP-Beispiel. Jede Task wird so spät wie möglich beendet. Insbesondere werden
Tasks τ 7 bis τ 9 erst zur Zeit 34 beendet. Tasks τ 4 bis τ 6 sind später als beim ASAPSchedule abgeschlossen. Tasks τ 1 , τ 2 , τ 9 und τ 10 werden wie beim ASAP-Schedule
eingeplant, denn diese Tasks bestimmen den Makespan. Wir sagen, dass die Tasks,
welche den Makespan bestimmen, auf dem kritischen Pfad liegen. Der roten Linie
ist zu entnehmen, dass die Lösung in Abb. 6.28 fünf Prozessoren benötigt.
6 Abbildung von Anwendungen
Blaue Zahlen bedeuten Startzeiten, grüne Zahlen bedeuten das jeweilige Ausführungsende. Tasks τ 2 bis τ 6 starten alle unmittelbar, nachdem Task τ 1 beendet ist.
Tasks τ 7 bis τ 9 starten ebenfalls sofort nachdem der letzte ihrer Vorgänger die Ausführung beendet hat. Die rote Linie in Abb. 6.27 (rechts) zeigt, dass im Maximum
fünf Prozessoren benötigt werden, da ASAP-Scheduling weder eine Grenze für die
Anzahl der Prozessoren noch das Ziel einer ausgewogenen Prozessorbelastung berücksichtigt.
∇
ASAP-Scheduling minimiert den Makespan, da alle Tasks so früh wie möglich
ausgeführt werden. Der vorgestellte Algorithmus kann so erweitert werden, dass
als Ausführungszeiten auch reelle Zahlen benutzt werden. ASAP-Scheduling ist von
linearer Komplexität, vorausgesetzt wir benutzen eine intelligente Methode, um τ ′
zu berechnen. Der Algorithmus kann auch im täglichen Leben angewandt werden:
er entspricht der Situation, in der jede Person begierig alle Arbeiten so früh wie
möglich startet.
6.4.2 As-Late-As-Possible-Scheduling
As-Late-As-Possible (ALAP)-Scheduling ist der zweite einfache Algorithmus. Beim
ALAP-Scheduling werden alle Tasks so spät wie möglich gestartet. Der Algorithmus
funktioniert wie folgt:
for (t=0; sooange es nicht eingeppante Tasks gibt; t--) {
τ ′ ={aaae Tasks ohne Abhängigkeit zu einer nicht eingeppanten Task};
Setze die Startzeit aaaer Tasks in τ ′ auf (t - ihre Ausführungszeit);
}
Schiebe aaae Startzeiten so, dass die erste Task zur Zeit t=0 startet.
Der Algorithmus betrachtet zunächst die Tasks, von denen keine weitere Task
abhängt. Es wird angenommen, dass diese Tasks zum Zeitpunkt 0 enden. Ihre Startzeit wird dann aus ihrer Ausführungsdauer berechnet. Danach iteriert die Schleife
rückwärts über Zeitschritte. Wenn ein Zeitschritt erreicht wird, zu dem eine Task
spätestens beendet sein soll, wird die Startzeit dieser Task berechnet und die Task
eingeplant. Nach dem Ende der Schleife werden alle Zeiten so angepasst, dass die
erste Task zum Zeitpunkt 0 startet. Wir könnten ALAP-Scheduling auch als eine
Variante des ASAP-Scheduling betrachten, die am „anderen” Ende des Graphen
beginnt.
Beispiel 6.15: Für den Task-Graphen in Abb. 6.26 würde ALAP-Scheduling das in
Abb. 6.28 gezeigte Ergebnis generieren. Die Farbkodierung ist dieselbe wie beim
ASAP-Beispiel. Jede Task wird so spät wie möglich beendet. Insbesondere werden
Tasks τ 7 bis τ 9 erst zur Zeit 34 beendet. Tasks τ 4 bis τ 6 sind später als beim ASAPSchedule abgeschlossen. Tasks τ 1 , τ 2 , τ 9 und τ 10 werden wie beim ASAP-Schedule
eingeplant, denn diese Tasks bestimmen den Makespan. Wir sagen, dass die Tasks,
welche den Makespan bestimmen, auf dem kritischen Pfad liegen. Der roten Linie
ist zu entnehmen, dass die Lösung in Abb. 6.28 fünf Prozessoren benötigt.