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 CPU 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 Sichtbarkeitsreihenfolge an, die dieses Ergebnis produziert. Die zweite Zeile enthält ein Beispiel.

   u	v	w	sequenziell konsistent	Sichtbarkeitsreihenfolge
   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: A (8 Byte), B (24 Byte) und C (8 Byte). Die Größe einer Cache-Zeile beträgt 32 Byte, so dass A und B in derselben Cache-Zeile X liegen, während C in Cache-Zeile Y liegt.

Der Prozessor P1 führt den folgenden Code aus:

4. Cache-Kohärenz bei der Arbeit

   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(A)
   1	read(B)
   2	read(B)
   2	read(C)
   1	read(B)
   1	write(A)
   2	read(B)
   2	write(C)

5. False Sharing (unechte gemeinsame Nutzung)

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

Cache-Kohärenz und Locks

Cache-Kohärenz ist teilweise ein kritischer Skalierungsfaktor für Lock-Implementierungen, da sie unnötige Bus-Nachrichten erzeugen und somit die Abarbeitung des CPUs verlangsamen.

6. Test-and-Set Locks

   Die in der Vorlesung besprochenen Test-and-Set Locks haben ein Skalierungsproblem durch ihre exclusiven Schreibzugriffe auf die Lockvariable selbst wenn der kritische Bereich, gerade belegt ist.
   
   Eine möglich Implementierung eines Test-and-Set Locks sieht wie folgt aus:
   

   class TSLock {
      private:
       unsigned int _lock
   
      public:
       TSLock() : _lock(0) {}
   
       void lock() {
           while (test_and_set(_lock) == 1) {}
       }
   
       void unlock() {
           _lock = 0;
       }
   };
   
   Überprüfen Sie die in der Vorlesung getroffene Aussage, indem Sie die unten stehende Tabelle vervollständigen.
   
   Die erste Spalte gibt an, welcher CPU gerade eine Instruktion ausführt. Spalte 2 gibt die ausgeführte Operation an. Spalte 3 gibt an wie der Zustand der Lockvariable nach Ausführung der Instruktion. Die nächsten 4 Spalten enthalten den MESI Zustand der Cachezeile der Lockvariable für den jeweiligen Prozessors.

   CPU	Operation	Lock	P1	P2	P3	P4
   		0	I	I	I	I
   1	lock (T&S)	1	M	I	I	I
   2	wait (T&S)	1	I	M	I	I
   4	wait (T&S)	1	I	I	I	M
   2	wait (T&S)
   3	wait (T&S)
   4	wait (T&S)
   3	wait (T&S)
   1	unlock
   3	lock (T&S)
   2	wait (T&S)
   4	wait (T&S)
   3	unlock
   2	lock (T&S)
   4	wait (T&S)
   4	wait (T&S)
   2	unlock

7. Test-Test-and-Set Locks

   In der Vorlesung wurde eine Erweiterung des Test-and-Set Locks vorgestellt, der eine zusätzliche Test-Operation vor dem blockieren des Locks ausführt.
   
   Eine möglich Implementierung eines Test-Test-and-Set Locks sieht wie folgt aus:
   

   class TTSLock {
      private:
       unsigned int _lock
   
      public:
       TTSLock() : _lock(0) {}
   
       void lock() {
           while (true) {
               while (_lock == 1) {}
   
               if (test_and_set(_lock) == 0)
                   break;
            }
       }
   
       void unlock() {
           _lock = 0;
       }
   };
   
   Wiederholen sie die obige Aufgabe unter Berücksichtigung der zusätzlichen Test-Operation des Test-Test-and-Set Locks. Berücksichtigen Sie, dass die Test-Operation nur ein normaler Lesezugriff ist.

   CPU	Operation	Lock	P1	P2	P3	P4
   		0	I	I	I	I
   1	test	0	E	I	I	I
   2	test	0	S	S	I	I
   1	lock (T&S)	1	M	I	I	I
   2	lock (T&S)
   3	wait
   4	wait
   2	wait
   3	wait
   4	wait
   1	unlock
   3	test
   3	lock (T&S)
   2	wait
   4	wait
   3	unlock
   2	test
   4	test
   2	lock (T&S)
   4	lock (T&S)
   4	wait
   4	wait
   2	unlock

8. False Sharing und Locks

   Früher in der Übung wurde false sharing (unechte gemeinsame Nutzung) besprochen. Beschreiben Sie kurz die Auswirkungen, wenn bei zwei unabhängige Lockvariablen l1 und l2 in der selben Cacheziele liegen.

Zusatzaufgaben

Die folgenden Aufgaben werden nicht in der Übung besprochen, sondern dienen eher als weiterführendes Material für besonders interessierte Stundenten.

1. Lock-frei

   Implementieren Sie 2-Adressen-Compare-and-Swap mit Hilfe von Compare-and-Swap.

2. Skalierbares Leser-Schreiber-Lock

   Faire Leser-Schreiber-Locks schützen einen kritischen Abschnitt so, dass mehrere Leser den kritischen Abschnitt gleichzeitig betreten können, solange kein Schreiber das Lock hält oder an diesem blockiert. Zu jedem Zeitpunkt darf höchstens ein Schreiber im kritischen Abschnitt sein, aber auch nur, wenn keine Leser im kritischen Abschnitt sind.

   1. Implementierung eines Leser-Schreiber Locks

      Implementieren Sie ein Leser-Schreiber-Lock mit Hilfe der atomaren Read-Modify-Write-Instruktionen aus der Vorlesung. Stellen Sie sicher, dass das Lock fair ist. Das heißt, sowohl Leser als auch Schreiber erhalten nach begrenzter Zeit das Lock.

   2. Faires schnelles skalierbares Leser-Schreiber Lock

      In ihrer Arbeit "A Fair Fast Scalable Reader-Writer Lock", präsentieren Krieger et al. eine skalierbare Leser-Schreiber-Lock-Implementierung basierend auf dem in der Vorlesung besprochenen MCS-Lock.

      1. Suchen Sie nach Tippfehlern in der readerUnlock-Funktion und korrigieren Sie sie. Begründen Sie, warum ein Fehler vorliegt. Wenn Sie keinen Fehler finden, begründen Sie, warum die Funktion korrekt ist.
      2. Beschreiben Sie, wie die readerUnlock-Funktion arbeitet.
      3. Anspruchsvolle Frage: Die Leser-Schreiber-Lock-Implementierung ist fair, obwohl eigentlich unfaire Spinlock-Implementierungen in der Funktion readerUnlock verwendet werden. Warum?

Materialien

• Orran Krieger, Michael Stumm, Ron Unrau, Jonathan Hanna: A Fair Fast Scalable Reader-Writer Lock, International Conference on Parallel Processing (ICPP), 1993
• Mellor-Crummey Scott: Algorithms for scalable synchronization on shared memory multiprocessors, ACM Transactions on Computer Systems, Volume 9, 1991