338
6 Abbildung von Anwendungen
Algorithmus heißt Latest Deadline First (LDF)-Algorithmus. LDF liest den TaskGraphen und speichert den Knoten, der die späteste Deadline und keine Nachfolger
im Graphen hat, in einem Stapel. Dies wird für alle verbleibenden Knoten wiederholt,
wobei immer der Knoten mit der spätesten Deadline unter allen Knoten mit bereits
ausgewählten Nachfolgern gewählt wird. Dieser Knoten wird auf den Stapel gelegt.
Zur Laufzeit werden die Tasks einer Reihenfolge ausgeführt, bei der wir die Einträge
im Stapel von oben nach unten abarbeiten, d.h. in einer Reihenfolge, die gegenüber
der Reihenfolge der Betrachtung der Knoten im Task-Graphen umgekehrt ist. LDF
ist nicht verdrängend und optimal für Einzelprozessoren.
Beispiel 6.5: Wir betrachten das Beispiel aus Abb. 6.11. LDF würde zuerst τ 3 auf
dem Stapel ablegen, denn diese Task hat keinen Nachfolger. Danach sind alle Nachfolger von τ 1 und τ 2 bereits gewählt. Es hängt von der Deadline ab, welcher der
Knoten als nächstes gewählt wird. Der Knoten mit der späteren Deadline wird als
erstes auf den Stapel gelegt. Zur Laufzeit wird der Stapel in der umgekehrten Reihenfolge abgearbeitet und beispielsweise mit der Bearbeitung von τ 1 begonnen. ∇
Im Falle von asynchronen Ankunftszeiten der Tasks kann man mit einem modifizierten EDF-Algorithmus ein gültiges Schedule bestimmen. Die Grundidee besteht darin,
das Problem mit der gegebenen Menge abhängiger Tasks in eine äquivalente Menge unabhängiger Tasks mit unterschiedlichen Zeitparametern umzuwandeln [98].
Dieser Algorithmus ist wiederum optimal für Einzelprozessoren.
Wenn Tasks nicht verdrängt werden dürfen, kann der heuristische Algorithmus
aus [508] verwendet werden.
6.2.3 Periodisches Scheduling ohne Reihenfolgebeschränkungen
Jetzt betrachten wir periodische Abläufe. Wir werden anstelle von Jobs überwiegend
Tasks betrachten, da sich im periodischen Fall die meisten Eigenschaften für Tasks
zeigen lassen. Wir beschränken uns auf Tasks ohne Reihenfolgeabhängigkeiten, was
in der Triplet-Notation durch das Triplet (1|r i ,prmp, periodic| .. ) ausgedrückt werden
kann.
Notation
Bei periodischem Scheduling sind die für aperiodisches Scheduling relevanten Ziele
nicht sehr nützlich. Beispielsweise spielt die Minimierung der totalen Dauer des
Schedules keine Rolle, wenn wir eine unendliche Wiederholung von Jobs betrachten.
Wir können bestenfalls einen Algorithmus entwerfen, der, falls ein Schedule existiert,
dieses immer findet. Dies motiviert die Definition von Optimalität für periodische
Schedules.
Definition 6.9: Ein periodischer Scheduling-Algorithmus wird als optimal bezeichnet, wenn er immer ein Schedule findet, falls eines existiert.
6 Abbildung von Anwendungen
Algorithmus heißt Latest Deadline First (LDF)-Algorithmus. LDF liest den TaskGraphen und speichert den Knoten, der die späteste Deadline und keine Nachfolger
im Graphen hat, in einem Stapel. Dies wird für alle verbleibenden Knoten wiederholt,
wobei immer der Knoten mit der spätesten Deadline unter allen Knoten mit bereits
ausgewählten Nachfolgern gewählt wird. Dieser Knoten wird auf den Stapel gelegt.
Zur Laufzeit werden die Tasks einer Reihenfolge ausgeführt, bei der wir die Einträge
im Stapel von oben nach unten abarbeiten, d.h. in einer Reihenfolge, die gegenüber
der Reihenfolge der Betrachtung der Knoten im Task-Graphen umgekehrt ist. LDF
ist nicht verdrängend und optimal für Einzelprozessoren.
Beispiel 6.5: Wir betrachten das Beispiel aus Abb. 6.11. LDF würde zuerst τ 3 auf
dem Stapel ablegen, denn diese Task hat keinen Nachfolger. Danach sind alle Nachfolger von τ 1 und τ 2 bereits gewählt. Es hängt von der Deadline ab, welcher der
Knoten als nächstes gewählt wird. Der Knoten mit der späteren Deadline wird als
erstes auf den Stapel gelegt. Zur Laufzeit wird der Stapel in der umgekehrten Reihenfolge abgearbeitet und beispielsweise mit der Bearbeitung von τ 1 begonnen. ∇
Im Falle von asynchronen Ankunftszeiten der Tasks kann man mit einem modifizierten EDF-Algorithmus ein gültiges Schedule bestimmen. Die Grundidee besteht darin,
das Problem mit der gegebenen Menge abhängiger Tasks in eine äquivalente Menge unabhängiger Tasks mit unterschiedlichen Zeitparametern umzuwandeln [98].
Dieser Algorithmus ist wiederum optimal für Einzelprozessoren.
Wenn Tasks nicht verdrängt werden dürfen, kann der heuristische Algorithmus
aus [508] verwendet werden.
6.2.3 Periodisches Scheduling ohne Reihenfolgebeschränkungen
Jetzt betrachten wir periodische Abläufe. Wir werden anstelle von Jobs überwiegend
Tasks betrachten, da sich im periodischen Fall die meisten Eigenschaften für Tasks
zeigen lassen. Wir beschränken uns auf Tasks ohne Reihenfolgeabhängigkeiten, was
in der Triplet-Notation durch das Triplet (1|r i ,prmp, periodic| .. ) ausgedrückt werden
kann.
Notation
Bei periodischem Scheduling sind die für aperiodisches Scheduling relevanten Ziele
nicht sehr nützlich. Beispielsweise spielt die Minimierung der totalen Dauer des
Schedules keine Rolle, wenn wir eine unendliche Wiederholung von Jobs betrachten.
Wir können bestenfalls einen Algorithmus entwerfen, der, falls ein Schedule existiert,
dieses immer findet. Dies motiviert die Definition von Optimalität für periodische
Schedules.
Definition 6.9: Ein periodischer Scheduling-Algorithmus wird als optimal bezeichnet, wenn er immer ein Schedule findet, falls eines existiert.