40
2 Spezifikation und Modellierung
nungen abgeschlossen sind. Solche Reihenfolgebeschränkungen implizieren eine
Präzedenzrelation und sie werden typischerweise in Abhängigkeitsgraphen als
Kanten dargestellt. Abb. 2.2 zeigt einen Abhängigkeitsgraph für eine Menge von
Berechnungen.
Abb. 2.2 Abhängigkeitsgraph
τ
τ
τ
τ
τ
2
1
5
4
3
Definition 2.6: Ein Abhängigkeitsgraph ist ein gerichteter azyklischer Graph (engl.
Directed Acyclic Graph (DAG)) G = (τ, E) mit der Knotenmenge τ und der Kantenmenge E. E ⊆ τ × τ stellt eine Relation auf τ dar. Wenn (τ 1 , τ 2 ) ∈ E, dann
wird τ 1 ein direkter Vorgänger von τ 2 genannt, entsprechend heißt τ 2 direkter
Nachfolger von τ 1 . Sei nun E ∗ die transitive Hülle von E. Wenn (τ 1 , τ 2 ) ∈ E ∗ , dann
ist τ 1 Vorgänger von τ 2 und τ 2 ist Nachfolger von τ 1 .
Solche Abhängigkeitsgraphen sind Spezialfälle von Task-Graphen. Task-Graphen
können mehr Informationen enthalten als in Abb. 2.2 dargestellt. Beispielsweise können Task-Graphen die Abhängigkeitsgraphen um folgende Eigenschaften erweitern:
1. Zeit-Informationen: Tasks können Ankunftszeiten, Deadlines, Perioden und
Ausführungszeiten haben. Um diese graphisch darzustellen, kann es sinnvoll sein,
sie in den Graphen darzustellen. In diesem Buch werden wir diese Informationen
aber unabhängig von den Graphen repräsentieren.
2. Unterscheidung von verschiedenen Beziehungsarten zwischen Berechnungen:
Präzedenzrelationen modellieren lediglich Reihenfolgebeschränkungen für die
Ausführung. Auf einer detaillierteren Ebene kann es hilfreich sein, zwischen
Bedingungen für das Scheduling und für die Kommunikation zwischen Berechnungen zu unterscheiden. Kommunikation kann wieder durch Kanten beschrieben werden. Es können allerdings weitere Informationen zu jeder dieser Kanten
bekannt sein, etwa der Zeitpunkt der Kommunikation und die ausgetauschte Datenmenge. Präzedenzrelationen können als eigene Kantenart betrachtet werden,
da es Situationen geben kann, in denen Tasks nacheinander ausgeführt werden
müssen, obwohl sie keine Informationen miteinander austauschen.
In Abb. 2.2 sind Ein- und Ausgaben (engl. Input/Output (I/O)) nicht explizit
dargestellt. Implizit wird angenommen, dass Knoten ohne Vorgänger im Graphen
irgendwann eine Eingabe erhalten. Weiter wird angenommen, dass sie nach einer
gewissen Zeit eine Ausgabe für den Nachfolgerknoten erzeugen. Diese Ausgabe
ist erst dann verfügbar, wenn die Berechnung abgeschlossen ist. Es ist oft nützlich,
Ein- und Ausgaben eindeutiger zu beschreiben. Um dies zu erreichen, wird ein
weiterer Relationstyp benötigt. Wir verwenden die Notation von Thoen [538], in
der Kreise mit Punkt Ein- und Ausgaben darstellen, wie in Abb. 2.3 zu sehen.
2 Spezifikation und Modellierung
nungen abgeschlossen sind. Solche Reihenfolgebeschränkungen implizieren eine
Präzedenzrelation und sie werden typischerweise in Abhängigkeitsgraphen als
Kanten dargestellt. Abb. 2.2 zeigt einen Abhängigkeitsgraph für eine Menge von
Berechnungen.
Abb. 2.2 Abhängigkeitsgraph
τ
τ
τ
τ
τ
2
1
5
4
3
Definition 2.6: Ein Abhängigkeitsgraph ist ein gerichteter azyklischer Graph (engl.
Directed Acyclic Graph (DAG)) G = (τ, E) mit der Knotenmenge τ und der Kantenmenge E. E ⊆ τ × τ stellt eine Relation auf τ dar. Wenn (τ 1 , τ 2 ) ∈ E, dann
wird τ 1 ein direkter Vorgänger von τ 2 genannt, entsprechend heißt τ 2 direkter
Nachfolger von τ 1 . Sei nun E ∗ die transitive Hülle von E. Wenn (τ 1 , τ 2 ) ∈ E ∗ , dann
ist τ 1 Vorgänger von τ 2 und τ 2 ist Nachfolger von τ 1 .
Solche Abhängigkeitsgraphen sind Spezialfälle von Task-Graphen. Task-Graphen
können mehr Informationen enthalten als in Abb. 2.2 dargestellt. Beispielsweise können Task-Graphen die Abhängigkeitsgraphen um folgende Eigenschaften erweitern:
1. Zeit-Informationen: Tasks können Ankunftszeiten, Deadlines, Perioden und
Ausführungszeiten haben. Um diese graphisch darzustellen, kann es sinnvoll sein,
sie in den Graphen darzustellen. In diesem Buch werden wir diese Informationen
aber unabhängig von den Graphen repräsentieren.
2. Unterscheidung von verschiedenen Beziehungsarten zwischen Berechnungen:
Präzedenzrelationen modellieren lediglich Reihenfolgebeschränkungen für die
Ausführung. Auf einer detaillierteren Ebene kann es hilfreich sein, zwischen
Bedingungen für das Scheduling und für die Kommunikation zwischen Berechnungen zu unterscheiden. Kommunikation kann wieder durch Kanten beschrieben werden. Es können allerdings weitere Informationen zu jeder dieser Kanten
bekannt sein, etwa der Zeitpunkt der Kommunikation und die ausgetauschte Datenmenge. Präzedenzrelationen können als eigene Kantenart betrachtet werden,
da es Situationen geben kann, in denen Tasks nacheinander ausgeführt werden
müssen, obwohl sie keine Informationen miteinander austauschen.
In Abb. 2.2 sind Ein- und Ausgaben (engl. Input/Output (I/O)) nicht explizit
dargestellt. Implizit wird angenommen, dass Knoten ohne Vorgänger im Graphen
irgendwann eine Eingabe erhalten. Weiter wird angenommen, dass sie nach einer
gewissen Zeit eine Ausgabe für den Nachfolgerknoten erzeugen. Diese Ausgabe
ist erst dann verfügbar, wenn die Berechnung abgeschlossen ist. Es ist oft nützlich,
Ein- und Ausgaben eindeutiger zu beschreiben. Um dies zu erreichen, wird ein
weiterer Relationstyp benötigt. Wir verwenden die Notation von Thoen [538], in
der Kreise mit Punkt Ein- und Ausgaben darstellen, wie in Abb. 2.3 zu sehen.