346
6 Abbildung von Anwendungen
n
i=1
C i
D i
≤ n(2
1/n − 1)
(6.15)
6.2.4 Periodisches Scheduling mit Reihenfolgebeschränkungen
Scheduling für abhängige Tasks ist schwerer als das Scheduling für unabhängige
Tasks, v.a. falls keine Verdrängungen erlaubt sind (in der Triplet-Notation im Fall
(1|r i ,prec,periodic|L max )). Das Entscheidungsproblem hinsichtlich der Existenz eines Schedules für eine Menge abhängiger Tasks und einer gegebenen Deadline ist
NP-hart [178]. Es gibt verschiedene Strategien, um die Komplexität zu senken:
• Es werden zusätzliche Ressourcen bereit gestellt, sodass das Scheduling einfacher
wird.
• Das Scheduling wird in statische und dynamische Anteile zerlegt. Bei diesem
Ansatz werden so viele Entscheidungen wie möglich zur Entwurfszeit getroffen
und der verbleibende Rest wird zur Laufzeit vorgenommen.
6.2.5 Sporadische Ereignisse
Prinzipiell könnte man sporadische Ereignisse mit Interrupts verbinden und sie jedes
Mal sofort ausführen, wenn die Interrupt-Priorität die höchste im gesamten System
ist. Das hätte allerdings ein unvorhersagbares Verhalten für alle anderen Tasks zur
Folge. Daher werden besondere sporadic task server verwendet, die regelmäßig
ausgeführt werden und dabei prüfen, ob ausführungsbereite sporadische Ereignisse
existieren. So können sporadische Ereignisse praktisch in periodische Tasks umgewandelt werden, wodurch die Vorhersagbarkeit des Gesamtsystems deutlich verbessert wird.
6.3 Scheduling für unabhängige Jobs auf identischen
Multiprozessoren
Aufgrund der großen Verbreitung von Mehrkern-Systemen in aktuellen eingebetteten Systemen betrachten wir als nächstes Multiprozessor-Systeme. Beim Übergang
von Einzelprozessoren zu Multiprozessor-Systemen muss eine Vielzahl von Herausforderungen bewältigt werden. Zunächst betrachten wir den Fall von m identischen
Prozessoren. Weiterhin gehen wir von einem Task-System τ = {τ 1 , ..., τ n } aus, bei
dem jede Task i durch ihre größtmögliche Ausführungszeit C i und – bei periodischen
und sporadischen Tasks – ihre Periode charakterisiert ist. Sofern nichts anderes gesagt ist, nehmen wir an, dass die Periode auch die Deadline ist. Wenn die periodische
6 Abbildung von Anwendungen
n
i=1
C i
D i
≤ n(2
1/n − 1)
(6.15)
6.2.4 Periodisches Scheduling mit Reihenfolgebeschränkungen
Scheduling für abhängige Tasks ist schwerer als das Scheduling für unabhängige
Tasks, v.a. falls keine Verdrängungen erlaubt sind (in der Triplet-Notation im Fall
(1|r i ,prec,periodic|L max )). Das Entscheidungsproblem hinsichtlich der Existenz eines Schedules für eine Menge abhängiger Tasks und einer gegebenen Deadline ist
NP-hart [178]. Es gibt verschiedene Strategien, um die Komplexität zu senken:
• Es werden zusätzliche Ressourcen bereit gestellt, sodass das Scheduling einfacher
wird.
• Das Scheduling wird in statische und dynamische Anteile zerlegt. Bei diesem
Ansatz werden so viele Entscheidungen wie möglich zur Entwurfszeit getroffen
und der verbleibende Rest wird zur Laufzeit vorgenommen.
6.2.5 Sporadische Ereignisse
Prinzipiell könnte man sporadische Ereignisse mit Interrupts verbinden und sie jedes
Mal sofort ausführen, wenn die Interrupt-Priorität die höchste im gesamten System
ist. Das hätte allerdings ein unvorhersagbares Verhalten für alle anderen Tasks zur
Folge. Daher werden besondere sporadic task server verwendet, die regelmäßig
ausgeführt werden und dabei prüfen, ob ausführungsbereite sporadische Ereignisse
existieren. So können sporadische Ereignisse praktisch in periodische Tasks umgewandelt werden, wodurch die Vorhersagbarkeit des Gesamtsystems deutlich verbessert wird.
6.3 Scheduling für unabhängige Jobs auf identischen
Multiprozessoren
Aufgrund der großen Verbreitung von Mehrkern-Systemen in aktuellen eingebetteten Systemen betrachten wir als nächstes Multiprozessor-Systeme. Beim Übergang
von Einzelprozessoren zu Multiprozessor-Systemen muss eine Vielzahl von Herausforderungen bewältigt werden. Zunächst betrachten wir den Fall von m identischen
Prozessoren. Weiterhin gehen wir von einem Task-System τ = {τ 1 , ..., τ n } aus, bei
dem jede Task i durch ihre größtmögliche Ausführungszeit C i und – bei periodischen
und sporadischen Tasks – ihre Periode charakterisiert ist. Sofern nichts anderes gesagt ist, nehmen wir an, dass die Periode auch die Deadline ist. Wenn die periodische