76
2 Spezifikation und Modellierung
Nach dem Passieren der Zugriffskontrolle werden die Videowünsche für den
Zugriff auf das Dateisystem eingeplant. In Kooperation mit der Speichersteuerung
stellt das Dateisystem die Videos dem Kunden zur Verfügung.
∇
Für allgemeine Datenflussmodelle lassen sich geforderte Eigenschaften eines
Systems nur schwer beweisen. Daher kommen meist eingeschränkte Modelle zum
Einsatz.
Ein spezieller Typ von Datenfluss wird benutzt, um in Rechnerarchitekturen
dynamisches Scheduling von Befehlen zu realisieren. Dies bedeutet, dass die Reihenfolge der Ausführung von Maschinenbefehlen nicht unbedingt ihrer Anordnung
im Speicher entspricht, sondern dass diese Reihenfolge unter Beachtung von Datenabhängigkeiten geändert werden kann. Man spricht deshalb auch von out-of-order
scheduling. Es gibt zwei sehr bekannte Algorithmen für diese Form des dynamischen
Schedulings: scoreboarding und den Tomasulo-Algorithmus [544]. Beide Algorithmen werden in Büchern zur Rechnerarchitektur im Detail vorgestellt (siehe z.B.
Hennessy et al. [212]). Aus diesem Grund werden sie in diesem Buch nicht behandelt. Es gibt allerdings Varianten dieser Algorithmen, die auf Task-Ebene angewandt
werden (siehe z.B. Wang et al. [561]).
2.5.2 Kahn-Prozessnetzwerke
Kahn-Prozessnetzwerke (KPN) [279] sind ein Spezialfall solcher Datenflussmodelle. KPNs bestehen aus Knoten und Kanten. Knoten entsprechen von einer Task
bzw. einem Prozess ausgeführten Berechnungen. Wie alle Datenflussgraphen stellen
auch KPN-Graphen nur die durchzuführenden Berechnungen und deren Abhängigkeiten voneinander dar, nicht aber die Reihenfolge, in der die Berechnungen
durchgeführt werden müssen (im Gegensatz zu Spezifikationen in von-NeumannSprachen wie C). Die Kanten stellen Kommunikationskanäle mit potenziell unendlich großen FIFOs dar. Auch wenn die Berechnungs- und Kommunikationszeiten
variieren können, ist doch sichergestellt, dass Kommunikation innerhalb endlicher
Zeit stattfindet. Schreibvorgänge in KPNs sind nicht-blockierend, da angenommen
wird, dass die FIFOs eine entsprechende Größe aufweisen. Leseoperationen müssen einen bestimmten Kanal angeben, von dem gelesen werden soll. Dabei kann
ein Knoten vor dem Leseversuch nicht überprüfen, ob Daten zur Verfügung stehen.
Auch kann ein KPN-Prozess nicht auf Daten von mehr als einem Port gleichzeitig warten. Leseoperationen werden blockiert, wenn ein KPN-Prozess versucht, aus
einer leeren FIFO-Warteschlange zu lesen. Nur ein einziger KPN-Prozess darf aus
einer bestimmten Warteschlange lesen, ebenso darf nur ein einziger Prozess in eine
bestimmte Warteschlange schreiben. Wenn ein Prozess seine Ausgabedaten also an
mehrere Nachfolger senden will, müssen die Daten innerhalb des Prozesses dupliziert werden. Es gibt keine anderen Methoden für die Kommunikation zwischen
KPN-Prozessen.
2 Spezifikation und Modellierung
Nach dem Passieren der Zugriffskontrolle werden die Videowünsche für den
Zugriff auf das Dateisystem eingeplant. In Kooperation mit der Speichersteuerung
stellt das Dateisystem die Videos dem Kunden zur Verfügung.
∇
Für allgemeine Datenflussmodelle lassen sich geforderte Eigenschaften eines
Systems nur schwer beweisen. Daher kommen meist eingeschränkte Modelle zum
Einsatz.
Ein spezieller Typ von Datenfluss wird benutzt, um in Rechnerarchitekturen
dynamisches Scheduling von Befehlen zu realisieren. Dies bedeutet, dass die Reihenfolge der Ausführung von Maschinenbefehlen nicht unbedingt ihrer Anordnung
im Speicher entspricht, sondern dass diese Reihenfolge unter Beachtung von Datenabhängigkeiten geändert werden kann. Man spricht deshalb auch von out-of-order
scheduling. Es gibt zwei sehr bekannte Algorithmen für diese Form des dynamischen
Schedulings: scoreboarding und den Tomasulo-Algorithmus [544]. Beide Algorithmen werden in Büchern zur Rechnerarchitektur im Detail vorgestellt (siehe z.B.
Hennessy et al. [212]). Aus diesem Grund werden sie in diesem Buch nicht behandelt. Es gibt allerdings Varianten dieser Algorithmen, die auf Task-Ebene angewandt
werden (siehe z.B. Wang et al. [561]).
2.5.2 Kahn-Prozessnetzwerke
Kahn-Prozessnetzwerke (KPN) [279] sind ein Spezialfall solcher Datenflussmodelle. KPNs bestehen aus Knoten und Kanten. Knoten entsprechen von einer Task
bzw. einem Prozess ausgeführten Berechnungen. Wie alle Datenflussgraphen stellen
auch KPN-Graphen nur die durchzuführenden Berechnungen und deren Abhängigkeiten voneinander dar, nicht aber die Reihenfolge, in der die Berechnungen
durchgeführt werden müssen (im Gegensatz zu Spezifikationen in von-NeumannSprachen wie C). Die Kanten stellen Kommunikationskanäle mit potenziell unendlich großen FIFOs dar. Auch wenn die Berechnungs- und Kommunikationszeiten
variieren können, ist doch sichergestellt, dass Kommunikation innerhalb endlicher
Zeit stattfindet. Schreibvorgänge in KPNs sind nicht-blockierend, da angenommen
wird, dass die FIFOs eine entsprechende Größe aufweisen. Leseoperationen müssen einen bestimmten Kanal angeben, von dem gelesen werden soll. Dabei kann
ein Knoten vor dem Leseversuch nicht überprüfen, ob Daten zur Verfügung stehen.
Auch kann ein KPN-Prozess nicht auf Daten von mehr als einem Port gleichzeitig warten. Leseoperationen werden blockiert, wenn ein KPN-Prozess versucht, aus
einer leeren FIFO-Warteschlange zu lesen. Nur ein einziger KPN-Prozess darf aus
einer bestimmten Warteschlange lesen, ebenso darf nur ein einziger Prozess in eine
bestimmte Warteschlange schreiben. Wenn ein Prozess seine Ausgabedaten also an
mehrere Nachfolger senden will, müssen die Daten innerhalb des Prozesses dupliziert werden. Es gibt keine anderen Methoden für die Kommunikation zwischen
KPN-Prozessen.