6.4 Abhängige Jobs auf homogenen Multiprozessor-Systemen
359
Bei diesem Algorithmus setzen wir voraus, dass alle Ausführungszeiten bekannt
sind und dass diese unabhängig sind von dem Prozessor, auf dem die Tasks ausgeführt
werden, d.h. wir nehmen an, dass die Prozessoren homogen sind. Der Algorithmus
berücksichtigt keine Beschränkungen hinsichtlich der Anzahl der Prozessoren und
setzt voraus, dass die benötigte Anzahl von Prozessoren zur Verfügung steht. Der
Algorithmus arbeitet wie folgt:
for (t=0; sooange es nicht eingeppante Tasks gibt; t++) {
τ ′ ={nicht eingeppante Tasks, deren Vorgänger beendet sind};
Setze die Startzeit aaaer Tasks in τ ′ auf t;
}
Beispiel 6.14: Wir nehmen an, dass der Task-Graph aus Abb. 6.26 (links) gegeben
ist. Jeder mit i bezeichnete Knoten repräsentiert eine Task τ i . Die rechte Seite der
Abb. 6.26 enthält die von uns angenommenen Ausführungszeiten.
6
5
2
3
1
4
9
10
7
8
Task C i
1
9
2
13
3
11
4
8
5
10
6
9
7
7
8
5
9
12
10
7
Abb. 6.26 Links: Task-Graph; rechts: Ausführungszeiten
Das ASAP-Scheduling wird das in Abb. 6.27 gezeigte Schedule erzeugen.
6
2
7
9
10
1
40
30
20
10
0
t
9
9
18
8
7
10
9
41
6
5
2
3
1
4
0
9
9
9
9
22
20
17
19
20
22
22
27
34
34
27
Abb. 6.27 Links: zeitlich eingeplanter Task-Graph; rechts: Zeitachse