42
2 Spezifikation und Modellierung
sollte die DCT als einzelner Knoten modelliert werden. Hierarchische Knoten
helfen dabei, häufige Wechsel der Granularität zu vermeiden. Auf einer hohen
Hierarchieebene können die Knoten dann z.B. komplexe Aufgaben beschreiben,
auf einer niederen Ebene Basisblöcke6 oder auf einer noch niedrigeren Ebene
einzelne arithmetische Operationen. Abb. 2.5 zeigt eine hierarchische Version
des Abhängigkeitsgraphen aus Abb. 2.2, in dem ein hierarchischer Knoten durch
ein Rechteck dargestellt wird.
Abb. 2.5 Hierarchischer Task-Graph
τ
τ
τ
τ
τ
3
4
5
1
2
Wie oben beschrieben, lassen sich Berechnungsmodelle anhand der Kommunikationsmodelle (dargestellt durch Kanten im Task-Graphen) und der Berechnungsmodelle innerhalb der Komponenten (dargestellt durch die Knoten des Task-Graphen)
klassifizieren. Im Folgenden führen wir einige bekannte Beispiele für Berechnungsmodelle auf:
• Kommunikationsmodelle: Wir unterscheiden zwischen zwei Kommunikationsparadigmen: Gemeinsamer Speicher und Nachrichtenaustausch. Weitere existierende Kommunikationsmodelle (wie z.B. verschränkte Zustände in der Quantenmechanik [62]) werden in diesem Buch nicht betrachtet.
– Gemeinsamer Speicher (engl. shared memory)
Bei diesem Modell greifen kommunizierende Komponenten auf gemeinsamen
Speicher zu. Zugriffe auf gemeinsamen Speicher sollten geschützt werden, solange nicht ausschließlich Lesezugriffe erfolgen. Sobald ein Schreibzugriff
verwendet wird, muss exklusiver Zugriff auf den Speicher für alle beteiligten
Komponenten garantiert werden. Die Programmabschnitte, die den exklusiven Zugriff benötigen, werden kritische Abschnitte genannt (siehe auch Lee’s
Beispiel 2.2). Zu den Methoden, die exklusiven Zugriff sicherstellen, gehören
Semaphore, bedingte kritische Abschnitte und Monitore. Die einzelnen Techniken sind im Detail in Betriebssystem-Lehrbüchern, wie z.B. von Stallings
[507], beschrieben. Kommunikation über gemeinsamen Speicher kann sehr
schnell sein. Allerdings ist die Implementierung für Multiprozessor-Systeme
schwierig zu realisieren, wenn kein physikalisch gemeinsamer Speicher vorhanden ist und dieser daher simuliert werden muss.
6 Basisblöcke sind Codeblöcke von maximaler Länge, die – außer möglicherweise an ihrem Ende –
keinen Sprungbefehl enthalten und in die nicht von anderen Codeblöcken aus hinein verzweigt
wird.
2 Spezifikation und Modellierung
sollte die DCT als einzelner Knoten modelliert werden. Hierarchische Knoten
helfen dabei, häufige Wechsel der Granularität zu vermeiden. Auf einer hohen
Hierarchieebene können die Knoten dann z.B. komplexe Aufgaben beschreiben,
auf einer niederen Ebene Basisblöcke6 oder auf einer noch niedrigeren Ebene
einzelne arithmetische Operationen. Abb. 2.5 zeigt eine hierarchische Version
des Abhängigkeitsgraphen aus Abb. 2.2, in dem ein hierarchischer Knoten durch
ein Rechteck dargestellt wird.
Abb. 2.5 Hierarchischer Task-Graph
τ
τ
τ
τ
τ
3
4
5
1
2
Wie oben beschrieben, lassen sich Berechnungsmodelle anhand der Kommunikationsmodelle (dargestellt durch Kanten im Task-Graphen) und der Berechnungsmodelle innerhalb der Komponenten (dargestellt durch die Knoten des Task-Graphen)
klassifizieren. Im Folgenden führen wir einige bekannte Beispiele für Berechnungsmodelle auf:
• Kommunikationsmodelle: Wir unterscheiden zwischen zwei Kommunikationsparadigmen: Gemeinsamer Speicher und Nachrichtenaustausch. Weitere existierende Kommunikationsmodelle (wie z.B. verschränkte Zustände in der Quantenmechanik [62]) werden in diesem Buch nicht betrachtet.
– Gemeinsamer Speicher (engl. shared memory)
Bei diesem Modell greifen kommunizierende Komponenten auf gemeinsamen
Speicher zu. Zugriffe auf gemeinsamen Speicher sollten geschützt werden, solange nicht ausschließlich Lesezugriffe erfolgen. Sobald ein Schreibzugriff
verwendet wird, muss exklusiver Zugriff auf den Speicher für alle beteiligten
Komponenten garantiert werden. Die Programmabschnitte, die den exklusiven Zugriff benötigen, werden kritische Abschnitte genannt (siehe auch Lee’s
Beispiel 2.2). Zu den Methoden, die exklusiven Zugriff sicherstellen, gehören
Semaphore, bedingte kritische Abschnitte und Monitore. Die einzelnen Techniken sind im Detail in Betriebssystem-Lehrbüchern, wie z.B. von Stallings
[507], beschrieben. Kommunikation über gemeinsamen Speicher kann sehr
schnell sein. Allerdings ist die Implementierung für Multiprozessor-Systeme
schwierig zu realisieren, wenn kein physikalisch gemeinsamer Speicher vorhanden ist und dieser daher simuliert werden muss.
6 Basisblöcke sind Codeblöcke von maximaler Länge, die – außer möglicherweise an ihrem Ende –
keinen Sprungbefehl enthalten und in die nicht von anderen Codeblöcken aus hinein verzweigt
wird.