TUD Logo

TUD Startseite » ... » Lehre » Verteilte Betriebssysteme » Speicherkonsistenz und Cache-Kohärenz

Betriebssysteme

Übung: Speicherkonsistenz und Cache-Kohärenz

In der Übungsstunde werden alle Lösungen von Studenten vorgeführt. Bitte erscheinen Sie für alle Fragen vorbereitet, da die Übung sich auf Diskussion konzentriert, nicht auf das Verstehen der Fragen und Zusammentragen des Wissens.

Speicherkonsistenz

  1. Sequenzielle Konsistenz

    In einem System mit sequenzieller Konsistenz führt jeder Prozessor Speicheroperationen immer in der durch das Programm spezifizierten Reihenfolge aus ("program order"). Die Reihenfolge, mit der die einzelnen Speicheroperationen für andere Prozessoren an derselben Verbindung (zum Beispiel dem Systembus) sichtbar werden, heißt Sichtbarkeits-Reihenfolge ("visibility order").

    Drei Prozessoren (P1, P2 und P3) mit gemeinsamem Hauptspeicher führen den folgenden Code aus (zu Beginn gilt A = B = 0).

    P1 P2 P3
    a1: A := 1 a2: u := A a3: v := B
    b2: B := 1 b3: w := A

    Dabei bezeichnet a1 die erste Operation auf Prozessor P1, a2 bezeichnet die erste Operation auf P2 und b2 bezeichnet die zweite Operation auf P2, usw.

    Das Ergebnis der Abarbeitung, bezeichnet durch das Tupel (u,v,w), kann abhängig von der Reihenfolge, in der die einzelnen Operationen jedes Prozessors global sichtbar werden, unterschiedlich sein. Einige Ergebnisse sind auf einem sequenziell konsistenten System nicht möglich. Vervollständigen Sie die folgende Tabelle mit möglichen Werten für (u,v,w): In jeder Zeile soll angegeben werden, ob das Ergebnis sequenziell konsistent ist. Wenn ja, geben Sie eine Sichtbarkeits-Reihenfolge an, die dieses Ergebnis produziert. Die zweite Zeile enthält ein Beispiel.

    u v w Sequenziell konsistent Sichtbarkeits-Reihenfolge
    0 0 0
    0 0 1 ja a2,a3,a1,b3,b2
    0 1 0
    0 1 1
    1 0 0
    1 0 1
    1 1 0
    1 1 1
  2. Abgeschwächte Konsistenz: Peterson-Algorithmus

    Ein bekannter Algorithmus für wechselseitigen Ausschluss ist Petersons Algorithmus (unten in Pseudocode angegeben). Erklären Sie, warum Petersons Algorithmus auch auf Systemen mit einem Schreibpuffer funktioniert, wenn dieser verhindert, dass Lesezugriffe frühere Schreibzugriffe auf dieselbe Speicherstelle überholen. Warum funktioniert der Algorithmus nicht mehr, wenn Lesezugriffe in Systemen mit Store-Forwarding frühere Schreibzugriffe auf dieselbe Speicherstelle überholen können (z.B. SPARC TSO).

    // global variables and initial values
    bool flag0 = false, flag1 = false;
    int turn = 0;

    // Process on CPU0
    flag0 = true;
    turn = 1;
    while (turn == 1 && flag1);
    // critical section flag0 = false;
    // Process on CPU1
    flag1 = true;
    turn = 0;
    while (turn == 0 && flag0);
    // critical section
    flag1 = false;
  3. Fence-Instruktionen

    Systeme mit abgeschwächter Speicherkonsistenz bieten üblicherweise eine Fence-Instruktionen an, mit der die Reihenfolge von Speicheroperationen eingegrenzt wird. Fügen Sie MFENCE-Instruktionen ("memory fence") zu Dekkers und Petersons Algorithmus hinzu um korrektes Verhalten auf Mehrprozessor-Systemen mit Schreibpuffer und Store Forwarding sicherzustellen. Benutzen Sie dabei so wenig Fence-Instruktionen wie möglich.

Cache-Kohärenz

Mehrprozessor-Systeme mit Caches benutzen ein Kohärenzprotokoll um sicherzustellen, dass Schreibzugriffe eines Prozessors irgendwann für alle anderen Prozessoren sichtbar werden und dass nie zwei Prozessoren gleichzeitig auf dieselbe Speicherstelle schreiben. Mit dem MESI-Protokoll wurde in der Vorlesung ein auf Ungültigmachen basierendes Protokoll besprochen.

Zwei Prozessoren (P1 und P2) und uniformer Speicher sind mit einem gemeinsamen Bus verbunden, welcher das MESI Cache-Kohärenzprotokoll implementiert. Im Speicher liegt eine Datenstruktur mit folgendem Aufbau: DATA_A (8 Byte), DATA_B (24 Byte) und DATA_C (8 Byte). Die Größe einer Cache-Zeile beträgt 32 Byte, so dass DATA_A und DATA_B in derselben Cache-Zeile X liegen, während DATA_C in Cache-Zeile Y liegt.

Der Prozessor P1 führt den folgenden Code aus:

DATA_A->read();
DATA_B->read();
// do something with DATA_A
DATA_B->read();
DATA_A->write();

Der Prozessor P2 führt den folgenden Code aus:

DATA_B->read();
DATA_C->read();
// do something with DATA_C
DATA_B->read();
DATA_C->write();
  1. Die folgende Tabelle listet die Speicheroperationen der einzelnen Prozessoren auf, wie sie auf dem gemeinsamen Bus auftreten. Die erste Spalte nennt den Prozessor und die zweite Spalte die ausgeführte Speicheroperation. Die nächsten beiden Spalten geben den MESI-Zustand der Cache-Zeilen X und Y auf jedem der Prozessoren an. Die letzten beiden Spalten beschreiben, ob der Zugriff dazu führt, dass eine Cache-Zeile zum/vom Speicher oder zu/von einem anderen Cache übertragen wird. Zu Beginn sind alle Cache-Zeilen ungültig (I – „invalid“).

    CPU Operation P1 P2 Speicher-Transfer Cache-Transfer
    I I I I
    1 READ(DATA_A)
    1 READ(DATA_B)
    2 READ(DATA_B)
    2 READ(DATA_C)
    1 READ(DATA_B)
    1 WRITE(DATA_A)
    2 READ(DATA_B)
    2 WRITE(DATA_C)
  2. False Sharing (unechte gemeinsame Nutzung)

    Da DATA_B in Cache-Zeile X liegt, tritt False Sharing mit DATA_A auf. Diskutieren Sie, wie sich dieses Problem beheben lässt und welche Auswirkungen das auf die Cache- und Speichertransfers hätte.

Stand: 9.6.2016, 15:42 Uhr
Autor: Dr.-Ing. Carsten Weinhold

Kontakt
Dr.-Ing.
Michael Roitzsch

Tel.: 463 42043
Fax: 463 38284
E-Mail-Kontaktformular

Regelungen
  • ModuleModule: INF-BI-1, INF-BAS4, INF-VERT4, DSE-E3
  • Credits6 Leistungspunkte
  • 2/1/0 = 3 SWS
Zeit und Ort

Dieser Kurs wird in diesem Semester nicht angeboten.