In einem System mit sequenzieller Konsistenz werden Speicheroperationen von jedem Prozessor in der vom Programm vorgegebenen Reihenfolge (en. Program Order) bearbeitet. Die Reihenfolge, in denen die Speicheroperationen auf dem gemeinsamen Verbindungsstück (z. B. Bus) für die anderen Prozessoren sichtbar sind, nennt man Sichtbarkeitsreihenfolge.
Drei Prozessoren (P1, P2 und P3) führen den folgenden Code in einem System mit geteiltem Speicher aus. A und B sind mit 0 initialisiert.
P1 | P2 | P3 |
|---|---|---|
A=1 (i) | u=A (ii) | v=B (iii) |
B=1 (iv) | w=A (v) |
Abhängig von der Sichtbarkeitsreihenfolge kann es hier zu unterschiedlichen Ergebnissen für das Tupel (u, v, w) kommen – einige Ergebnisse können auf einem sequenziell konsistenten System nicht herauskommen.
Diese Aufgabe wurde aus der Vorlesung "Advanced Operating Systems" der Professur für Betriebssysteme an der Technischen Universität Dresden übernommen.
Level 3: Anwenden
Vervollständigen Sie in der folgenden Tabelle für jede Zeile, ob das Ergebnis sequenziell konsistent ist. Wenn dem so ist, geben Sie eine mögliche Sichtbarkeitsreihenfolge an, die zu dem Ergebnis führt. Ein Beispiel ist in der zweiten Zeile gegeben.
u | v | w | sequenziell konsistent? | Sichtbarkeitsreihenfolge |
|---|---|---|---|---|
| 0 | 0 | 0 | ||
| 0 | 0 | 1 | Ja | ii, iii, i, v, iv |
| 0 | 1 | 0 | ||
| 0 | 1 | 1 | ||
| 1 | 0 | 0 | ||
| 1 | 0 | 1 | ||
| 1 | 1 | 0 | ||
| 1 | 1 | 1 |
u | v | w | sequenziell konsistent | Sichtbarkeitsreihenfolge |
|---|---|---|---|---|
| 0 | 0 | 0 | Ja | ii, iii, v, iv, i |
| 0 | 0 | 1 | Ja | ii, iii, i, v, iv |
| 0 | 1 | 0 | Ja | ii, iv, iii, v, i |
| 0 | 1 | 1 | Ja | ii, iv, i, iii, v |
| 1 | 0 | 0 | Ja | iii, v, i, ii, iv |
| 1 | 0 | 1 | Ja | i, ii, iii, v, iv |
| 1 | 1 | 0 | Nein | (v, i, ii, iv, |
| 1 | 1 | 1 | Ja | i, ii, iv, iii, v |
In dieser Aufgabe …