CppMem - Sukzessive Optimierung 1

Heute will ich mit CppMem einen Schritt weiter gehen und die Sukzessive Optimierung der gleichnamigen Miniserie dieses Blogs genauer analysieren.

Unsere erste Variante des Programms im vorherigen Artikel hatte einen kritischen Wettlauf. Der Einfachheit halber verwende ich die CppMem-Syntax zur Darstellung der Sourcecodes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int main() {
  int x=0; 
  int y=0;
  {{{ { 
        x= 2000; 
        y= 11;
      }
  ||| {
        y;
        x;
      }  
  }}}
}

Die naheliegende Idee, einen kritischen Bereich zu schützen, ist ein std::lock_guard.

Locks

Leider habe ich es nicht geschafft, einen std::lock_guard in CppMem zu verwenden. Die Details dazu gibt es in dem Sukzessive Optimierung - Locks.

Weiter geht es mit dem Schlüsselwort volatile.

volatile

volatile besitzt keine Multithreading-Semantik in C++. Das zeigt der Artikel Sukzessive Optimierung - Volatile. Genau der gleichen Ansicht ist CppMem.

Das leicht modifizierte Programm. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int main(){
  volatile int x= 0; 
  volatile int y= 0;
  {{{ { 
      x= 2000; 
      y= 11;
      }
  ||| {
      y;
      x;
      } 
  }}}
}

Die Ergebnisse sind identisch zu den Ergebnissen des letzten Artikels. Es macht keinen Unterschied, ob die Variablen x oder y mit dem Qualifier volatile versehen sind.

Weiter geht's mit der Sequenziellen Konsistenz.

Sequenzielle Konsistenz

Werden die zwei Variablen x und y zu atomaren Variablen, so schlägt die Sequenzielle Konsistenz zu. Das bedeutet, das jeder Thread seine Anweisungen in der Sourcecodereihenfolge ausführt und alle Threads einem globalen Zeittakt folgen. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int main(){
  atomic_int x= 0; 
  atomic_int y= 0;
  {{{ { 
      x.store(2000);
      y.store(11);
      }
  ||| {
      y.load();
      x.load();
      } 
  }}}
}

Zuerst eine kleine syntaktische Besonderheit von CppMem. CppMem verwendet in Zeile 2 und 3 den typedef atomic_int für std::atomic<int>.  Dies gilt für alle weiteren Aliase. 

Führe ich das Programm aus, werde ich von der Anzahl der Ausführungsmöglichkeiten erschlagen.

384 (1) mögliche Ausführungsreihenfolgen der Threads, nur 6 davon sind konsistent. Keine Ausführung besitzt einen kritischen Wettlauf. Wie passt das zusammen? 

Tatsächlich interessieren mich in diesem konkreten Fall nur die konsistenten Ausführungen. Mit dem Interface (2) kann ich mir die sechs annotierten Graphen anschauen. Sie sind nicht konsistent. Das heißt zum Beispiel, sie respektieren nicht die modification order. Daher werde ich diese Ausführungen in meiner weiteren Analyse ignorieren.

Aus dem Artkel Sukzessive Optimierung - Sequenzielle Konsistenz wissen wir bereits, dass alle Ergebnisse mit Ausnahme von y= 11, x= 0 möglich sind. Das sicher das Default-Speichermodell zu.

Wie kommt es zu den Ergebnissen? Die Symbole im annotierten Graph habe ich bereits in dem Artikel CppMem - Nicht synchronisierter Zugriff vorgestellt, so dass ich jetzt nur noch zu den drei möglichen Ergebnissen der Variablen x und y die Graphen darstellen will.

Ausführung für (y= 0, x= 0)

Ausführungen für (y= 0, x= 2000)

Ausführung für (y= 11, x= 2000)

Was hat es mit den Nummern in den Graphen auf sich? Ganz einfach, ich bin mit meiner Analyse noch nicht fertig.

Tiefere Einsichten

Betrachte ich alle 6 verschränkten Ausführungen der Threads in der folgenden Graphik, stellt sich natürlich die Frage. Welcher Ausführungsreihenfolge entspricht welcher Graph?

Hier ist die Lösung. Jeder verschränkten Ausführung eines Threads habe ich die entsprechende Nummer des Graphs zugeordnet.

Verschränkte Ausführung

Zuerst zu den einfachen Fällen:

• (1): Relativ einfach ist der Graph (1) der verschränkten Ausführung (1) zuzuordnen. In der verschränkten Ausführung  (1) besitzt x und y die Werte 0, da y.load() und x.load() vor den Speicheroperationen x.store(2000) und y.store(11) ausgeführt werden.
• (6): Ähnlich naheliegend ist die Argumentation für die Ausführung (6). y besitzt den Wert 11 und x den Wert 2000, wenn alle Lade nach den Speicher-Operationen ausgeführt werden.
• (2),(3),(4),(5): Deutlich spannender sind schon die Ausführungen, bei denen y den Wert 0 und x den Wert 2000 besitzt. Für die Argumentation helfen die gelben Pfeile (sc) in dem Graphen, den sie bezeichnen die Sequenz der ausführten Befehle. Exemplarisch will ich den Fall (2) durchspielen.
  • (2): Die Sequenz der gelben Pfeile (sc) im Graphen (2) lautet: Write x= 2000 => Read y= 0 => Write y= 11 => Read x= 2000. Diese Sequenz entspricht genau der Sequenz der zweiten verschränkten Ausführung (2). 

   

Wie geht's weiter?

Mein Ziel für diesen Artikel war es, neben der Sequenziellen Konsistenz auch deren Bruch mit Hilfe von CppMem genauer analysieren. Diese Analyse muss ich auf den nächsten Artikel verschieben. Der Informationsgehalt von CppMem ist einfach zu groß.

Go to Leanpub/cpplibrary "What every professional C++ programmer should know about the C++ standard library".   Hole dir dein E-Book. Unterstütze meinen Blog.