Transitivität der Acquire-Release-Semantik

Eine release-Operation synchronisiert sich mit einer acquire-Operation auf der gleichen atomaren Variable und erzeugt dazu noch eine Ordnungsbedingung. Damit lassen sich Threads auf performante Weise synchronisieren, wenn sie auf einer gemeinsamen atomaren Variablen agieren. Doch wie lassen sich zwei Threads mit der Acquire-Release-Semantik synchronisieren, wenn sie auf keiner gemeinsamen atomaren Variablen agieren? Eine globale Ordnung der Threads mit Hilfe der Sequenziellen Konsistenz ist oft zu schwergewichtig.

Die Lösung aus der Zwickmühle ist naheliegend. Dank der Transitivität der Acquire-Release-Semantik lassen sich Threads miteinander synchronisieren, die voneinander unabhängig agieren.

Transitivität

 In dem Beispiel ist Thread t2 mit seinem Arbeitspaket deliveryBoy das Verbindungsglied zwischen den unabhängig agierenden Threads t1 und t3. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

// transitivity.cpp

#include <atomic>
#include <iostream>
#include <thread>
#include <vector>

std::vector<int> mySharedWork;
std::atomic<bool> dataProduced(false);
std::atomic<bool> dataConsumed(false);

void dataProducer(){
    mySharedWork={1,0,3};
    dataProduced.store(true, std::memory_order_release);
}

void deliveryBoy(){
    while( !dataProduced.load(std::memory_order_acquire) );
    dataConsumed.store(true,std::memory_order_release);
}

void dataConsumer(){
    while( !dataConsumed.load(std::memory_order_acquire) );
    mySharedWork[1]= 2;
}

int main(){
    
  std::cout << std::endl;

  std::thread t1(dataConsumer);
  std::thread t2(deliveryBoy);
  std::thread t3(dataProducer);

  t1.join();
  t2.join();
  t3.join();
  
  for (auto v: mySharedWork){
      std::cout << v << " ";
  }
      
  std::cout << "\n\n";
  
}

 Die Ausgabe des Programms ist vollkommen deterministisch. mySharedWork besitzt immer die Werte 1,2 und 3.

 Wieso ist das Programm vollkommen deterministisch? Es gibt zwei wichtige Beobachtungen:

1. Thread t2 wartet in der Zeile 18 darauf, das Thread t3 in der Zeile 14 dataProduced auf true setzt.
2. Thread t1 wartet in der Zeile 23 darauf, das Thread t2 in der Zeile 19 dataConsumed auf true setzt.

Der Rest lässt sich am besten an der Graphik aufzeigen.

 Das Entscheidende an der Graphik sind die Pfeile.

• Die blauen Pfeile stehen für die sequenced-before Abhängigkeit. Das heißt, dass in einem Thread alle Operationen in der Sourcecodereihenfolge ausgeführt werden.
• Die roten Pfeile stehen für die synchronize-with Abhängigkeit. Diese ist in der Acquire-Release-Semantik der atomaren Operationen auf der gleichen atomaren Variable begründet. Damit findet die Synchronisation zwischen den Threads statt.
• Sowohl sequenced-before als auch synchronizes-with begründet eine happens-before Abhängigkeit.

Der Rest ist ganz einfach. Die zeitliche Reihenfolge der Instruktionen (happens-before) entspricht der Richtung der Pfeile von oben nach unten. Damit ist gewährleistet, dass mySharedWork[1]= 2 als letzte Instruktion ausgeführt wird.

Wie geht's weiter?

Das war wieder ein kurz und knackiger Artikel. Es ist aber meine Absicht, dass die Happen verdaulich bleiben. Deutlich mehr zum Verdauen gibt es im nächsten Artikel, wenn wir uns die legendäre std::memory_order_consume Ordnung genauer anschauen.

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.