336
6 Abbildung von Anwendungen
nicht-verdrängend ist, kann er τ 2 nicht starten, wenn er zum Zeitpunkt 1 ausführungsbereit ist. Daher verpasst τ 2 die Deadline. Wenn der Scheduler den Prozessor
nicht sofort belegt hätte (wie in Abb. 6.9 zum Zeitpunkt 4 gezeigt), hätte er ein
zulässiges Schedule gefunden. Daher ist dieser Scheduler nicht optimal. Dies ist ein
Widerspruch zur Annahme, dass optimale Scheduler existieren, die den Prozessor
immer voll auslasten.
⊓ ⊔
Abschließend stellen wir fest: um verpasste Deadlines zu vermeiden, muss der Scheduler Wissen über die Zukunft haben. Solche Algorithmen heißen hellsehend (engl.
clairvoyant). Ein Algorithmus, der Prozessoren trotz der Anwesenheit ausführungsbereiter Tasks unbeschäftigt lässt, heißt nicht arbeitserhaltend.
Definition 6.8: Ein Scheduling-Algorithmus heißt arbeitserhaltend (engl. work
conserving), wenn es keine Zeiten gibt, zu denen der Prozessor unbeschäftigt ist,
während es eine ausführungsbereite Task gibt [121].
Wenn es vorab keine Informationen über Ankunftszeiten gibt, dann kann kein online-Algorithmus entscheiden, ob er den Prozessor unbeschäftigt lassen soll. Wenn
Ankunftszeiten a priori bekannt sind, wird das Scheduling-Problem im nicht verdrängenden Fall im Allgemeinen NP-hart und Branch-and-Bound-Techniken werden
typischerweise zur Erzeugung von Schedules verwendet.
6.2.2 Scheduling mit Reihenfolgebeschränkungen
Als nächstes betrachten wir die Ablaufplanung mit vorhandenen Reihenfolgebeschränkungen, ausgedrückt durch eine Präzedenzrelation prec und in der TripletNotation als (1| r i , prmp, prec | L max ) bezeichnet.
Task-Graphen
Reihenfolgebeschränkungen werden in gerichteten azyklischen Abhängigkeitsgraphen (DAGs, siehe Definition 2.6) G = (τ, E) ausgedrückt. Die Menge τ stellt die
Knoten (engl. vertices oder nodes) und E ⊆ τ × τ seine Kanten (engl. edges) des
Graphen dar.
Beispiel 6.3: In der Abb. 6.10 drücken die Kanten aus, dass die Quellknoten (die
ersten Komponenten der Tupel, die eine Kante repräsentieren) vor den Zielknoten
(die zweiten Komponenten der Tupel, die eine Kante repräsentieren) ausgeführt
werden müssen. Die Knotenbeschriftungen bezeichnen Tasks.
∇
Es gibt mehrere Gründe, Anwendungen in Form von DAGs zu beschreiben.
1. Zum einen könnte jeder Knoten einer Task entsprechen und Kanten würden
Abhängigkeiten zwischen Tasks repräsentieren.
6 Abbildung von Anwendungen
nicht-verdrängend ist, kann er τ 2 nicht starten, wenn er zum Zeitpunkt 1 ausführungsbereit ist. Daher verpasst τ 2 die Deadline. Wenn der Scheduler den Prozessor
nicht sofort belegt hätte (wie in Abb. 6.9 zum Zeitpunkt 4 gezeigt), hätte er ein
zulässiges Schedule gefunden. Daher ist dieser Scheduler nicht optimal. Dies ist ein
Widerspruch zur Annahme, dass optimale Scheduler existieren, die den Prozessor
immer voll auslasten.
⊓ ⊔
Abschließend stellen wir fest: um verpasste Deadlines zu vermeiden, muss der Scheduler Wissen über die Zukunft haben. Solche Algorithmen heißen hellsehend (engl.
clairvoyant). Ein Algorithmus, der Prozessoren trotz der Anwesenheit ausführungsbereiter Tasks unbeschäftigt lässt, heißt nicht arbeitserhaltend.
Definition 6.8: Ein Scheduling-Algorithmus heißt arbeitserhaltend (engl. work
conserving), wenn es keine Zeiten gibt, zu denen der Prozessor unbeschäftigt ist,
während es eine ausführungsbereite Task gibt [121].
Wenn es vorab keine Informationen über Ankunftszeiten gibt, dann kann kein online-Algorithmus entscheiden, ob er den Prozessor unbeschäftigt lassen soll. Wenn
Ankunftszeiten a priori bekannt sind, wird das Scheduling-Problem im nicht verdrängenden Fall im Allgemeinen NP-hart und Branch-and-Bound-Techniken werden
typischerweise zur Erzeugung von Schedules verwendet.
6.2.2 Scheduling mit Reihenfolgebeschränkungen
Als nächstes betrachten wir die Ablaufplanung mit vorhandenen Reihenfolgebeschränkungen, ausgedrückt durch eine Präzedenzrelation prec und in der TripletNotation als (1| r i , prmp, prec | L max ) bezeichnet.
Task-Graphen
Reihenfolgebeschränkungen werden in gerichteten azyklischen Abhängigkeitsgraphen (DAGs, siehe Definition 2.6) G = (τ, E) ausgedrückt. Die Menge τ stellt die
Knoten (engl. vertices oder nodes) und E ⊆ τ × τ seine Kanten (engl. edges) des
Graphen dar.
Beispiel 6.3: In der Abb. 6.10 drücken die Kanten aus, dass die Quellknoten (die
ersten Komponenten der Tupel, die eine Kante repräsentieren) vor den Zielknoten
(die zweiten Komponenten der Tupel, die eine Kante repräsentieren) ausgeführt
werden müssen. Die Knotenbeschriftungen bezeichnen Tasks.
∇
Es gibt mehrere Gründe, Anwendungen in Form von DAGs zu beschreiben.
1. Zum einen könnte jeder Knoten einer Task entsprechen und Kanten würden
Abhängigkeiten zwischen Tasks repräsentieren.