6.1 Problemdefinition
327
Wir sprechen von Tasks mit impliziten Deadlines (engl. implicit deadline tasks),
wenn D i = T i für alle i gilt. Wir nennen diese Tasks dann auch Liu-and-Layland
(L & L) tasks [348]. Dieser Fall wird durch einen Eintrag D i = T i gekennzeichnet.
Wir sprechen von Tasks mit beschränkten Deadlines (engl. constrained deadline
tasks) wenn D i ≤ T i für alle i gilt.
Wenn es hinsichtlich der Deadlines keine Beschränkungen gibt, sprechen wir von
Mengen von Tasks mit beliebigen Deadlines (engl. arbitrary deadline tasks).
Diese Information hinsichtlich der Deadlines wird ebenfalls durch eine entsprechende Komponente im β-Feld kenntlich gemacht.
Wir können dieses Feld auch benutzen, um zu beschreiben, welche Form von
Scheduling benutzt werden soll. Beispielsweise können wir Komponenten fixedjob-prio bzw. fixed-task-prio verwenden, um auszudrücken, dass Jobs bzw. Tasks
eine feste Priorität haben sollen.
Außerdem könnten wir zwischen statischem und dynamischem Scheduling unterscheiden. Dynamische Scheduler treffen Entscheidungen zur Laufzeit. Sie sind
sehr flexibel, aber sie erzeugen zur Laufzeit Overhead. Außerdem sind ihnen globale Zusammenhänge wie der Ressourcenbedarf und Reihenfolgebeschränkungen in der Regel nicht bekannt. Bei eingebetteten Systemen sind solche globalen
Zusammenhänge meist verfügbar und sie sollten ausgenutzt werden.
Statische Schedules nutzen Entscheidungen zur Entwurfszeit. Sie basieren darauf,
dass die Startzeiten von Jobs vorab geplant werden und dass Tabellen mit den
Startzeiten einem einfachen Dispatcher mitgeteilt werden. Der Dispatcher trifft
keine Entscheidungen, sondern startet lediglich die Jobs entsprechend der Zeiten,
die in der Tabelle eingetragen sind. Der Dispatcher kann durch einen Zeitgeber
getriggert werden, der ihn die Tabelle analysieren lässt. Systeme, die vollständig
durch einen Zeitgeber kontrolliert werden, heißen vollständig zeitgesteuert (engl.
entirely time triggered (TT systems)). Derartige Systeme werden im Buch von
Kopetz [304] detailliert vorgestellt.
τ1
τ2
τ1
...
...
Zeit
...
...
22
47
38
17
10
...
...
WCET
20
12
Aktion
sende M3
sende M5
starte
stoppe
starte
Dispatcher
Abb. 6.3 TDL in einem zeitgesteuerten System
„In einem vollständig zeitgesteuerten System wird der zeitliche Ablauf aller Tasks vorab durch off-line Werkzeuge geplant. Dieser zeitliche Ablauf
wird gespeichert in einer TaskDescriptor List (TDL), die den
zyklischen Ablauf aller Aktivitäten ... enthält (siehe Abb. 6.3).
Der Ablauf beachtet Reihenfolgebedingungen und den gegenseitigen Ausschluss zwischen Tasks, sodass eine
explizite Koordination der Tasks durch das Betriebssystem zur Laufzeit nicht
notwendig ist. Der Dispatcher wird durch synchronisierte Taktsignale aktiviert.
Er sieht sich die TDL an und führt dann die Aktion aus, die für diesen Zeitpunkt
geplant ist”.
Der Hauptvorteil des statischen Schedulings ist, dass man einfach prüfen kann,
ob die Zeitschranken eingehalten sind. „Die Vorhersagbarkeit des Systemver-
327
Wir sprechen von Tasks mit impliziten Deadlines (engl. implicit deadline tasks),
wenn D i = T i für alle i gilt. Wir nennen diese Tasks dann auch Liu-and-Layland
(L & L) tasks [348]. Dieser Fall wird durch einen Eintrag D i = T i gekennzeichnet.
Wir sprechen von Tasks mit beschränkten Deadlines (engl. constrained deadline
tasks) wenn D i ≤ T i für alle i gilt.
Wenn es hinsichtlich der Deadlines keine Beschränkungen gibt, sprechen wir von
Mengen von Tasks mit beliebigen Deadlines (engl. arbitrary deadline tasks).
Diese Information hinsichtlich der Deadlines wird ebenfalls durch eine entsprechende Komponente im β-Feld kenntlich gemacht.
Wir können dieses Feld auch benutzen, um zu beschreiben, welche Form von
Scheduling benutzt werden soll. Beispielsweise können wir Komponenten fixedjob-prio bzw. fixed-task-prio verwenden, um auszudrücken, dass Jobs bzw. Tasks
eine feste Priorität haben sollen.
Außerdem könnten wir zwischen statischem und dynamischem Scheduling unterscheiden. Dynamische Scheduler treffen Entscheidungen zur Laufzeit. Sie sind
sehr flexibel, aber sie erzeugen zur Laufzeit Overhead. Außerdem sind ihnen globale Zusammenhänge wie der Ressourcenbedarf und Reihenfolgebeschränkungen in der Regel nicht bekannt. Bei eingebetteten Systemen sind solche globalen
Zusammenhänge meist verfügbar und sie sollten ausgenutzt werden.
Statische Schedules nutzen Entscheidungen zur Entwurfszeit. Sie basieren darauf,
dass die Startzeiten von Jobs vorab geplant werden und dass Tabellen mit den
Startzeiten einem einfachen Dispatcher mitgeteilt werden. Der Dispatcher trifft
keine Entscheidungen, sondern startet lediglich die Jobs entsprechend der Zeiten,
die in der Tabelle eingetragen sind. Der Dispatcher kann durch einen Zeitgeber
getriggert werden, der ihn die Tabelle analysieren lässt. Systeme, die vollständig
durch einen Zeitgeber kontrolliert werden, heißen vollständig zeitgesteuert (engl.
entirely time triggered (TT systems)). Derartige Systeme werden im Buch von
Kopetz [304] detailliert vorgestellt.
τ1
τ2
τ1
...
...
Zeit
...
...
22
47
38
17
10
...
...
WCET
20
12
Aktion
sende M3
sende M5
starte
stoppe
starte
Dispatcher
Abb. 6.3 TDL in einem zeitgesteuerten System
„In einem vollständig zeitgesteuerten System wird der zeitliche Ablauf aller Tasks vorab durch off-line Werkzeuge geplant. Dieser zeitliche Ablauf
wird gespeichert in einer TaskDescriptor List (TDL), die den
zyklischen Ablauf aller Aktivitäten ... enthält (siehe Abb. 6.3).
Der Ablauf beachtet Reihenfolgebedingungen und den gegenseitigen Ausschluss zwischen Tasks, sodass eine
explizite Koordination der Tasks durch das Betriebssystem zur Laufzeit nicht
notwendig ist. Der Dispatcher wird durch synchronisierte Taktsignale aktiviert.
Er sieht sich die TDL an und führt dann die Aktion aus, die für diesen Zeitpunkt
geplant ist”.
Der Hauptvorteil des statischen Schedulings ist, dass man einfach prüfen kann,
ob die Zeitschranken eingehalten sind. „Die Vorhersagbarkeit des Systemver-