6.2 Scheduling für Einzelprozessoren
337
Abb. 6.10 Reihenfolgebeschränkungen
6
5
2
3
1
4
9
10
7
8
2. Zum anderen führt die Verfügbarkeit von Multiprozessoren zu der Idee der Aufspaltung von Tasks in Subtasks und der Ausführung der Subtasks in überlappender
Weise auf den verschiedenen Prozessoren. Das automatische Partitionieren von
Tasks in Subtasks, sodass parallele Prozessoren effizient genutzt werden können,
heißt automatische Parallelisierung. Automatische Parallelisierung ist sogar
noch schwieriger als das automatische Scheduling für eine gegebene Menge von
Subtasks (beispielsweise weil Datenabhängigkeiten analysiert werden müssen).
Beide Fälle der Erzeugung von DAGs können auch in Kombination Anwendung
finden: wir können Abhängigkeiten zwischen Tasks haben und Tasks können in
Subtasks aufgespalten werden. Nachfolgend nehmen wir an, dass DAGs jede der
eben beschriebenen Situationen repräsentieren können und wir sprechen in jedem
Fall von Task-Graphen (siehe auch Seite 39). Für das Scheduling ist es unwichtig,
wie der DAG erzeugt wurde.
Beispiel 6.4: Abb. 6.11 zeigt ein gültiges Schedule für einen einfacheren TaskGraphen einschließlich Kommunikation. Task τ 3 kann nur ausgeführt werden, wenn
τ 1 und τ 2 ausgeführt wurden und Nachrichten an τ 3 geschickt haben.
Abb. 6.11 Reihenfolgebeschränkungen
und Schedule
τ
τ
τ
τ
τ
τ
Μ3
Μ5
10 20 30 40 50
t
60 70
1
2
3
3
1
2
∇
Latest Deadline First-Algorithmus
Ein optimaler Algorithmus, der die maximale Verspätung im Falle gleichzeitig ankommender Tasks oder Jobs minimiert, wurde von Lawler vorgestellt [327]. Dieser
337
Abb. 6.10 Reihenfolgebeschränkungen
6
5
2
3
1
4
9
10
7
8
2. Zum anderen führt die Verfügbarkeit von Multiprozessoren zu der Idee der Aufspaltung von Tasks in Subtasks und der Ausführung der Subtasks in überlappender
Weise auf den verschiedenen Prozessoren. Das automatische Partitionieren von
Tasks in Subtasks, sodass parallele Prozessoren effizient genutzt werden können,
heißt automatische Parallelisierung. Automatische Parallelisierung ist sogar
noch schwieriger als das automatische Scheduling für eine gegebene Menge von
Subtasks (beispielsweise weil Datenabhängigkeiten analysiert werden müssen).
Beide Fälle der Erzeugung von DAGs können auch in Kombination Anwendung
finden: wir können Abhängigkeiten zwischen Tasks haben und Tasks können in
Subtasks aufgespalten werden. Nachfolgend nehmen wir an, dass DAGs jede der
eben beschriebenen Situationen repräsentieren können und wir sprechen in jedem
Fall von Task-Graphen (siehe auch Seite 39). Für das Scheduling ist es unwichtig,
wie der DAG erzeugt wurde.
Beispiel 6.4: Abb. 6.11 zeigt ein gültiges Schedule für einen einfacheren TaskGraphen einschließlich Kommunikation. Task τ 3 kann nur ausgeführt werden, wenn
τ 1 und τ 2 ausgeführt wurden und Nachrichten an τ 3 geschickt haben.
Abb. 6.11 Reihenfolgebeschränkungen
und Schedule
τ
τ
τ
τ
τ
τ
Μ3
Μ5
10 20 30 40 50
t
60 70
1
2
3
3
1
2
∇
Latest Deadline First-Algorithmus
Ein optimaler Algorithmus, der die maximale Verspätung im Falle gleichzeitig ankommender Tasks oder Jobs minimiert, wurde von Lawler vorgestellt [327]. Dieser