330
6 Abbildung von Anwendungen
zielt vom Entwurf her auf die Minimierung der Anzahl der Prozessoren. Für HEFT
und CPOP ist Makespan die relevante Zielfunktion. Nur die letzte Zeile entspricht
der Minimierung mehrerer Kriterien, entweder in der Form eines einzelnen Kriteriums zur Zeit oder in Form einer multi-kriteriellen Optimierung auf der Basis der
Pareto-Optimalität.
Ähnlich wie die Beurteilung der Rechenleistung ist auch das Scheduling ein
Vorgang, der nicht nur ein einziges Mal während des Entwurfs durchgeführt wird.
Vielmehr werden Scheduling-Algorithmen während des Entwurfs mehrfach benötigt. Grobe Abschätzungen können sogar erforderlich werden, wenn die Spezifikation verfasst wird. Später werden evtl. genauere Vorhersagen der Ausführungszeiten
benötigt. Nach der Kompilierung gibt es noch genaueres Wissen über die Ausführungszeiten und dementsprechend können noch genauere Schedules erzeugt werden.
Schließlich kann auch möglicherweise zur Laufzeit entschieden werden, welche
Task/welcher Job als nächstes auszuführen ist.
In der Praxis ist es sehr wichtig zu wissen, ob ein Schedule für eine gegebene Menge an Tasks und Randbedingungen existiert. Eine Menge von Tasks heißt
schedulable bei einer gegebenen Menge von Randbedingungen, wenn ein Schedule
für diese Menge von Tasks und Randbedingungen existiert. Für viele Anwendungen sind Tests auf die Existenz eines Schedules (engl. schedulability tests) wichtig.
Tests, die immer ein exaktes Ergebnis liefern, sind in vielen Fällen NP-hart [178].
Daher werden notwendige und hinreichende Tests benutzt. Für hinreichende Tests
werden hinreichende Bedingungen für die Existenz eines Schedules geprüft. Es gibt
eine (hoffentlich kleine) Wahrscheinlichkeit dafür, dass ein Schedule nicht garantiert
werden kann, aber dennoch ein solches existiert. Notwendige Tests basieren auf notwendigen Bedingungen. Mit ihnen kann gezeigt werden, dass kein Schedule existiert.
Dennoch kann es Fälle geben, in denen die notwendigen Bedingungen erfüllt sind,
aber trotzdem kein Schedule existiert.
6.2 Scheduling für Einzelprozessoren
Wir betrachten zunächst den Fall von Einzelprozessoren. In der Triplet-Notation
entspricht dies dem Fall (1|..|..). Für diesen Abschnitt benutzen wir Material aus dem
Buch von Buttazzo [81]. Für zusätzliche Referenzen sei auf dieses Buch verwiesen.
6.2.1 Scheduling ohne Reihenfolgebeschränkungen
Weiterhin betrachten wir zunächst Scheduling ohne Reihenfolgebeschränkungen,
d.h. den Fall unabhängiger Jobs.
6 Abbildung von Anwendungen
zielt vom Entwurf her auf die Minimierung der Anzahl der Prozessoren. Für HEFT
und CPOP ist Makespan die relevante Zielfunktion. Nur die letzte Zeile entspricht
der Minimierung mehrerer Kriterien, entweder in der Form eines einzelnen Kriteriums zur Zeit oder in Form einer multi-kriteriellen Optimierung auf der Basis der
Pareto-Optimalität.
Ähnlich wie die Beurteilung der Rechenleistung ist auch das Scheduling ein
Vorgang, der nicht nur ein einziges Mal während des Entwurfs durchgeführt wird.
Vielmehr werden Scheduling-Algorithmen während des Entwurfs mehrfach benötigt. Grobe Abschätzungen können sogar erforderlich werden, wenn die Spezifikation verfasst wird. Später werden evtl. genauere Vorhersagen der Ausführungszeiten
benötigt. Nach der Kompilierung gibt es noch genaueres Wissen über die Ausführungszeiten und dementsprechend können noch genauere Schedules erzeugt werden.
Schließlich kann auch möglicherweise zur Laufzeit entschieden werden, welche
Task/welcher Job als nächstes auszuführen ist.
In der Praxis ist es sehr wichtig zu wissen, ob ein Schedule für eine gegebene Menge an Tasks und Randbedingungen existiert. Eine Menge von Tasks heißt
schedulable bei einer gegebenen Menge von Randbedingungen, wenn ein Schedule
für diese Menge von Tasks und Randbedingungen existiert. Für viele Anwendungen sind Tests auf die Existenz eines Schedules (engl. schedulability tests) wichtig.
Tests, die immer ein exaktes Ergebnis liefern, sind in vielen Fällen NP-hart [178].
Daher werden notwendige und hinreichende Tests benutzt. Für hinreichende Tests
werden hinreichende Bedingungen für die Existenz eines Schedules geprüft. Es gibt
eine (hoffentlich kleine) Wahrscheinlichkeit dafür, dass ein Schedule nicht garantiert
werden kann, aber dennoch ein solches existiert. Notwendige Tests basieren auf notwendigen Bedingungen. Mit ihnen kann gezeigt werden, dass kein Schedule existiert.
Dennoch kann es Fälle geben, in denen die notwendigen Bedingungen erfüllt sind,
aber trotzdem kein Schedule existiert.
6.2 Scheduling für Einzelprozessoren
Wir betrachten zunächst den Fall von Einzelprozessoren. In der Triplet-Notation
entspricht dies dem Fall (1|..|..). Für diesen Abschnitt benutzen wir Material aus dem
Buch von Buttazzo [81]. Für zusätzliche Referenzen sei auf dieses Buch verwiesen.
6.2.1 Scheduling ohne Reihenfolgebeschränkungen
Weiterhin betrachten wir zunächst Scheduling ohne Reihenfolgebeschränkungen,
d.h. den Fall unabhängiger Jobs.