362
6 Abbildung von Anwendungen
3
8
7
10
9
6
5
2
1
4
0
0
0
0
7
7
7
5
3
11
9
3
3
2
2
2
1
1
1
0
3
8
7
10
9
6
5
2
1
4
Abb. 6.29 Laufendes Beispiel: links: Mobilität; rechts: Zahl der Nachfolger;
weise mit der Ausführungszeit der Knoten gewichtet, vorausgesetzt, dass diese
Information bekannt ist. In Abb. 6.30 (links) wurde die Pfadlänge eingetragen.
LS verlangt die Kenntnis des einzuplanenden Task-Graphen, einer Abbildung
jedes Knotens des Graphen auf den entsprechenden Ressourcentyp l ∈ L, einer
Prioritätsfunktion (wie eben erklärt) und der Ausführungszeit für jede Task τ i in τ.
LS versucht dann, Knoten maximaler Priorität jedem der Zeitschritte zuzuordnen,
wobei die Randbedingungen nicht verletzt werden [528]:
for (t=0; sooange nicht eingeppante Tasks vorh.; t++) /* Zeit-Schheife */
for (l ∈ L) {
/* Schheife über Ressourcentypen */
τ ∗
t ,l = Menge der Tasks vom Typ l, die zur Zeit t noch ausgeführt werden;
τ ∗∗
t ,l = Menge der Tasks vom Typ l, die zur Zeit t starten können;
Berechne Menge τ ′
t ⊆ τ ∗∗
t ,l maximaaer Priorität, sodass
|τ ′
t | + |τ ∗
t ,l | ≤ B l .
/* Anzahh der Tasks ≤ Schranke?/
Setze Startzeiten aaaer τ i ∈ τ ′
t auf t: s i = t;
}
Beispiel 6.16: Abb. 6.30 zeigt das Ergebnis der Anwendung von List-Scheduling mit
der Pfadlänge als Prioritätsfunktion auf unser Beispiel von Abb. 6.26. Wir nehmen
an, dass alle Prozessoren von demselben Typ sind und wir erlauben maximal drei
Prozessoren (B 1 = 3). Zur Zeit 9 haben Tasks τ 2 , τ 4 und τ 5 den längsten Pfad und
daher die höchste Priorität. τ 4 beendet die Ausführung zur Zeit 17 und τ 3 wie auch τ 6
haben unter den verbleibenden Tasks die größte Pfadlänge. Wir nehmen an, dass wir
τ 3 einplanen. τ 5 beendet die Ausführung zur Zeit 19 und τ 6 kann gestartet werden.
Zum Zeitpunkt 28 werden τ 3 und τ 6 die Ausführung beenden, womit Prozessoren
für τ 7 und τ 8 frei werden. τ 7 wird zur Zeit 35 fertig gestellt, wodurch die abhängige
Task τ 10 starten und zur Zeit 42 fertig gestellt sein kann. Der Abschluss erfolgt nur
wenig später als in den ASAP- und ALAP-Schedules, obwohl nur drei Prozessoren
zur Verfügung stehen. Für die Zuordnung zu konkreten Prozessoren bestehen noch
Wahlmöglichkeiten.
6 Abbildung von Anwendungen
3
8
7
10
9
6
5
2
1
4
0
0
0
0
7
7
7
5
3
11
9
3
3
2
2
2
1
1
1
0
3
8
7
10
9
6
5
2
1
4
Abb. 6.29 Laufendes Beispiel: links: Mobilität; rechts: Zahl der Nachfolger;
weise mit der Ausführungszeit der Knoten gewichtet, vorausgesetzt, dass diese
Information bekannt ist. In Abb. 6.30 (links) wurde die Pfadlänge eingetragen.
LS verlangt die Kenntnis des einzuplanenden Task-Graphen, einer Abbildung
jedes Knotens des Graphen auf den entsprechenden Ressourcentyp l ∈ L, einer
Prioritätsfunktion (wie eben erklärt) und der Ausführungszeit für jede Task τ i in τ.
LS versucht dann, Knoten maximaler Priorität jedem der Zeitschritte zuzuordnen,
wobei die Randbedingungen nicht verletzt werden [528]:
for (t=0; sooange nicht eingeppante Tasks vorh.; t++) /* Zeit-Schheife */
for (l ∈ L) {
/* Schheife über Ressourcentypen */
τ ∗
t ,l = Menge der Tasks vom Typ l, die zur Zeit t noch ausgeführt werden;
τ ∗∗
t ,l = Menge der Tasks vom Typ l, die zur Zeit t starten können;
Berechne Menge τ ′
t ⊆ τ ∗∗
t ,l maximaaer Priorität, sodass
|τ ′
t | + |τ ∗
t ,l | ≤ B l .
/* Anzahh der Tasks ≤ Schranke?/
Setze Startzeiten aaaer τ i ∈ τ ′
t auf t: s i = t;
}
Beispiel 6.16: Abb. 6.30 zeigt das Ergebnis der Anwendung von List-Scheduling mit
der Pfadlänge als Prioritätsfunktion auf unser Beispiel von Abb. 6.26. Wir nehmen
an, dass alle Prozessoren von demselben Typ sind und wir erlauben maximal drei
Prozessoren (B 1 = 3). Zur Zeit 9 haben Tasks τ 2 , τ 4 und τ 5 den längsten Pfad und
daher die höchste Priorität. τ 4 beendet die Ausführung zur Zeit 17 und τ 3 wie auch τ 6
haben unter den verbleibenden Tasks die größte Pfadlänge. Wir nehmen an, dass wir
τ 3 einplanen. τ 5 beendet die Ausführung zur Zeit 19 und τ 6 kann gestartet werden.
Zum Zeitpunkt 28 werden τ 3 und τ 6 die Ausführung beenden, womit Prozessoren
für τ 7 und τ 8 frei werden. τ 7 wird zur Zeit 35 fertig gestellt, wodurch die abhängige
Task τ 10 starten und zur Zeit 42 fertig gestellt sein kann. Der Abschluss erfolgt nur
wenig später als in den ASAP- und ALAP-Schedules, obwohl nur drei Prozessoren
zur Verfügung stehen. Für die Zuordnung zu konkreten Prozessoren bestehen noch
Wahlmöglichkeiten.