328
6 Abbildung von Anwendungen
haltens ist der wichtigste Aspekt, um Zeitschranken in harten Echtzeitsystemen
einzuhalten; Scheduling vor der Ausführungszeit ist häufig die einzige praktische
Methode, um in einem komplexen System Vorhersagbarkeit zu bieten” [604]. Der
Hauptnachteil ist, dass die Antwortzeit auf Ereignisse recht schlecht sein kann.
• Scheduling-Algorithmen für Mehrprozessor-Systeme können entweder lokal auf
einem Prozessor ausgeführt werden oder unter einer Menge von Prozessoren
aufgeteilt werden. Wir können daher zwischen zentralisiertem und verteiltem
Scheduling unterscheiden. Diese Unterscheidung könnte auch im β-Feld ausgedrückt werden.
Das γ-Feld
Das γ-Feld beschreibt die Zielfunktion. In diesem Buch betrachten wir die folgenden
Werte für dieses Feld:
• Ein Eintrag L max bedeutet, dass die maximale Verspätung zu minimieren ist.
Definition 6.6: Die maximale Verspätung (engl. maximum lateness) ist definiert als die Differenz zwischen dem Berechnungsende f i und der Deadline d i ,
maximiert über alle Tasks i.
Die maximale Verspätung ist negativ, wenn alle Tasks ihre Berechnungen vor
ihrer Deadline beenden.
• Ein Eintrag MS max bezeichnet die Minimierung des Makespan, d.h. der Zeit, zu
der die letzte Ausführung beendet ist.
Definition 6.7: Der Makespan ist definiert als3
MS max = max i ( f i )
(6.3)
• Zusätzlich zu den Einträgen, die Pinedo betrachtet, sind auch weitere Einträge für
eingebettete Systeme relevant. Beispielsweise möchten wir vielleicht den Energieverbrauch minimieren oder wir möchten Tradeoffs (also z.B. Pareto-Kurven)
zwischen verschiedenen Bewertungskriterien betrachten.
Es gibt eine riesige Menge an Scheduling-Algorithmen und eine umfassende Behandlung existierender Algorithmen wäre selbst dann nicht möglich, wenn ein vollständiges Buch oder ein ganzer Kurs zur Verfügung stünden. In einem üblichen Bachelorstudium gibt es üblicherweise nicht ausreichend Stundenvolumen, um einen
Kurs vollständig dem Scheduling zu widmen (aber das kann für ein Masterstudium anders sein). Deshalb geben wir hier nur eine kurze Einführung in das Thema.
Viele Scheduling-Algorithmen sind sehr komplex [38, 455] und häufig können nur
annähernd optimale Ablaufpläne garantiert werden. Das wirft die Frage auf, welche
Algorithmen hier präsentiert werden sollten. Wir werden in diesem Kapitel eine
3 Pinedo bezeichnet den Makespan als C ma x . Mit der Bezeichnung M S ma x möchten wir eine
Verwechslung mit Ausführungszeiten vermeiden.
6 Abbildung von Anwendungen
haltens ist der wichtigste Aspekt, um Zeitschranken in harten Echtzeitsystemen
einzuhalten; Scheduling vor der Ausführungszeit ist häufig die einzige praktische
Methode, um in einem komplexen System Vorhersagbarkeit zu bieten” [604]. Der
Hauptnachteil ist, dass die Antwortzeit auf Ereignisse recht schlecht sein kann.
• Scheduling-Algorithmen für Mehrprozessor-Systeme können entweder lokal auf
einem Prozessor ausgeführt werden oder unter einer Menge von Prozessoren
aufgeteilt werden. Wir können daher zwischen zentralisiertem und verteiltem
Scheduling unterscheiden. Diese Unterscheidung könnte auch im β-Feld ausgedrückt werden.
Das γ-Feld
Das γ-Feld beschreibt die Zielfunktion. In diesem Buch betrachten wir die folgenden
Werte für dieses Feld:
• Ein Eintrag L max bedeutet, dass die maximale Verspätung zu minimieren ist.
Definition 6.6: Die maximale Verspätung (engl. maximum lateness) ist definiert als die Differenz zwischen dem Berechnungsende f i und der Deadline d i ,
maximiert über alle Tasks i.
Die maximale Verspätung ist negativ, wenn alle Tasks ihre Berechnungen vor
ihrer Deadline beenden.
• Ein Eintrag MS max bezeichnet die Minimierung des Makespan, d.h. der Zeit, zu
der die letzte Ausführung beendet ist.
Definition 6.7: Der Makespan ist definiert als3
MS max = max i ( f i )
(6.3)
• Zusätzlich zu den Einträgen, die Pinedo betrachtet, sind auch weitere Einträge für
eingebettete Systeme relevant. Beispielsweise möchten wir vielleicht den Energieverbrauch minimieren oder wir möchten Tradeoffs (also z.B. Pareto-Kurven)
zwischen verschiedenen Bewertungskriterien betrachten.
Es gibt eine riesige Menge an Scheduling-Algorithmen und eine umfassende Behandlung existierender Algorithmen wäre selbst dann nicht möglich, wenn ein vollständiges Buch oder ein ganzer Kurs zur Verfügung stünden. In einem üblichen Bachelorstudium gibt es üblicherweise nicht ausreichend Stundenvolumen, um einen
Kurs vollständig dem Scheduling zu widmen (aber das kann für ein Masterstudium anders sein). Deshalb geben wir hier nur eine kurze Einführung in das Thema.
Viele Scheduling-Algorithmen sind sehr komplex [38, 455] und häufig können nur
annähernd optimale Ablaufpläne garantiert werden. Das wirft die Frage auf, welche
Algorithmen hier präsentiert werden sollten. Wir werden in diesem Kapitel eine
3 Pinedo bezeichnet den Makespan als C ma x . Mit der Bezeichnung M S ma x möchten wir eine
Verwechslung mit Ausführungszeiten vermeiden.