Transactional Memory

Transactional Memory basiert auf der Idee der Transaktion aus der Datenbanktheorie. Transactional Memory soll den Umgang mit mehreren Threads deutlichen vereinfachen. Zum einen verhindern sie kritische Wettläufe und Verklemmungen, zum anderen können Transaktionen komponiert werden.

Eine Transaktion ist eine Aktion, die sich durch die Eigenschaften Atomicity, Consistency, Isolation und Durability (ACID) auszeichnet. Bis auf die Durability treffen alle Eigenschafen auch auf Transactional Memory in C++ zu. Daher bleiben nur noch drei kleine Fragen offen.

ACI(D)

Was bedeutet Atomicity, Consistency und Isolation für einen atomaren Block, der aus mehreren Anweisungen besteht?

atomic{
  statement1;
  statement2;
  statement3;
}

• Atomicity: Die Anweisungen des Blocks werden entweder alle oder gar nicht ausgeführt.
  
• Consistency: Das System ist immer in einem konsistenten Zustand. Entweder wurden alle Werte am Ende der Transaktion geändert oder kein Wert wurde geändert.
  
• Isolation: Jede Transaktion läuft in vollkommener Isolation von allen anderen Transaktionen ab.
  

Wie werden diese Garantien zugesichert? Eine Transaktion merkt sich ihren Anfangszustand. Dann wird die Transaktion ohne Synchronisation ausgeführt. Tritt ein Konflikt während der Ausführung der Transaktion auf, wird die Transaktion abgebrochen und auf ihren Anfangszustand gesetzt. Dieser Rollback führt dazu, dass die Transaktion nochmals ausgeführt wird. Gelten die Anfangsbedingungen selbst am Ende der Transaktion noch, wird diese veröffentlicht.

Eine Transaktion ist in diesem Sinne eine spekulative Aktion, die nur dann veröffentlicht wird, wenn ihre Anfangsbedingungen noch gelten. Im Gegensatz zu einem Mutex verfolgen Transaktionen ein optimistischen Ansatz. Die Transaktion wird ohne Synchronisation ausgeführt. Am Ende der Transaktion wird nur geprüft, ob sie veröffentlicht werden kann. Ein Mutex ist ein pessimistischer Ansatz. Zuerst stellt der teure Mutex sicher, das nur ein Thread den kritischen Bereich betreten darf und damit Zugriff auf diesen besitzt. Erst wenn der Thread den exklusiven Zugriff auf den Mutex besitzt und damit alle anderen Threads blockiert sind, betritt er den kritischen Bereich und führt seine Aktion aus.

C++ kennt Transactional Memory in zwei Formen als Synchronized Blocks und Atomic Blocks.

Transactional Memory

Bisher habe immer von einem Transaktion gesprochen. Nun werde ich auf die Varianten Synchronized Block und Atomic Block genauer eingehen, die ineinander verschachtelt werden können. Genau genommen sind Synchronized Blocks keine atomaren Blöcke, da sie transaction-unsafe Code erlauben. Das sind zum Beispiel Aktionen wie eine Ausgabe auf die Konsole, die nicht vollständig rückgängig gemacht werden können.

Synchronized Blocks

Synchronized Blocks verhalten sich, wie wenn diese durch ein einziges, globales Lock synchronisiert werden. Das heißt, dass alle Synchronized Blocks einer totalen Ordnung folgen. Somit stehen alle Änderungen am Ende eines Synchronized Blocks dem nächsten Synchronized Block zu Verfügung. Da Synchronized Blocks durch ein einziges, globales Lock synchronisiert werden, können sie, falls sie nicht mit anderen Synchronisationsmechanismen verwendet werden, keine Verklemmung verursachen. Während ein klassisches Lock den expliziten Zugriff von Threads synchronisiert, schützt das einzige, globale Lock in Synchronized Blocks automatisch alle Zugriffe aller Threads. Somit ist der folgende Code wohldefiniert:

 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

// synchronized.cpp

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

int i= 0;

void increment(){
  synchronized{ 
    std::cout << ++i << " ,";
  }
}

int main(){
  
  std::cout << std::endl;
    
  std::vector<std::thread> vecSyn(10);
  for(auto& thr: vecSyn)
    thr = std::thread([]{ for(int n = 0; n < 10; ++n) increment(); });
  for(auto& thr: vecSyn) thr.join();
  
  std::cout << "\n\n";
  
}

Auch wenn i in Zeile 7 eine globale Variable ist und die in dem Synchronized Block verwendeten Operationen transaction-unsafe sind, finden die Zugriffe auf std::cout und die globale Variable i in einer totalen Ordnung statt. Dies sichert Synchronized Blocks zu.

Die Ausgabe des Programms ist natürlich nicht sehr spannend. Die Werte für die Zahl i werden aufsteigend, durch ein Komma getrennt, ausgegeben. Der Vollständigkeit halber will ich sie schnell zeigen.

Wie sieht es mit kritischen Wettläufen aus? Die sind natürlich bei Synchronized Blocks möglich, da diese transaction-unsafe Code ausführen können. Eine kleine Modifikation des Programms macht dies möglich.

 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

// nonsynchronized.cpp

#include <chrono>
#include <iostream>
#include <vector>
#include <thread>

using namespace std::chrono_literals;

int i= 0;

void increment(){
  synchronized{ 
    std::cout << ++i << " ,";
    std::this_thread::sleep_for(1ns);
  }
}

int main(){
  
  std::cout << std::endl;
    
  std::vector<std::thread> vecSyn(10);
  std::vector<std::thread> vecUnsyn(10);
    
  for(auto& thr: vecSyn)
    thr = std::thread([]{ for(int n = 0; n < 10; ++n) increment(); });
  for(auto& thr: vecUnsyn)
    thr = std::thread([]{ for(int n = 0; n < 10; ++n) std::cout << ++i << " ,"; });
    
  for(auto& thr: vecSyn) thr.join();
  for(auto& thr: vecUnsyn) thr.join();
  
  std::cout << "\n\n";
  
}

Um den kritischen Wettlauf zu provozieren, lasse ich den Synchronized Block jeweils um eine Nanosekunde in Zeile 15 schlafen. Gleichzeitig greife ich auf std::cout von außerhalb des Synchronized Blocks in Zeile 29 zu. Dazu starte ich wiederum 10 Threads, die gleichzeitig die globale Variable i inkrementieren. Die Ausgabe des Programms bringt es deutlich auf den Punkt.

Ich habe die Unregelmäßigkeiten in der Ausgabe rot hervorgehoben. Dies sind die Stellen, in den std::cout von zu mindestens zwei Threads gleichzeitig verwendet wird. Da der C++ Standard zusichert, dass jeder einzelne Buchstabe atomar ausgegeben wird, ist das nur ein optischen Problem. Viel schlimmer ist aber, dass die die Variable i gleichzeitig von mindestens zwei Threads geschrieben wird. Ein klassisches data race. Damit ist das Programmverhalten undefiniert.

Die totale Ordnung der Synchronized Blocks gilt auch in ihrem Zusammenspiel mit den Atomic Blocks.

Atomic Blocks

Während in Synchronized Block transaction-unsafe Code ausgeführt werden kann, ist dies in einem Atomic Block nicht erlaubt. Atomic Blocks gibt es in drei Variationen atomic_noexcept, atomic_commit und atomic_cancel. Die drei Anhängsel _noexcept, _commit und _cancel legen fest, wie ein Atomic Block auf Ausnahmen zu reagieren hat.

• atomic_noexcept:Falls eine Ausnahme auftritt, wird std::abort aufgerufen und damit das Programm beendet.
  
• atomic_cancel:Im Standardfall wird std::abort aufgerufen. Dies gilt aber nicht, wenn eine transaction-safe Ausnahme auftrat, die für das Beenden einer Transaktion verwendet wird. In diesem Fall wird die Transaktion beendet, die Transaktion auf ihren Anfangszustand gesetzt und die Ausnahme geworfen.
  
• atomic_commit: Die Transaktion wird veröffentlicht und die Ausnahme geworfen.
  

transaction-safe Ausnahmen: std::bad_alloc, std::bad_array_length, std::bad_array_new_length, std::bad_cast, std::bad_typeid, std::bad_exception, std::exception und alle Ausnahmen, die von diesen abgeleitet sind, sind transaction-safe.

transaction_safe versus transaction_unsafe Code

Eine Funktion kann als transaction_safe deklariert werden oder das transaction_unsafe Attribut verwenden.

int transactionSafeFunction() transaction_safe;

[[transaction_unsafe]] int transactionUnsafeFunction();

transaction_safe ist Bestandteil des Typs einer Funktion. Doch was ist eine transaction_safe Funktion? Eine transaction_safe Funktion ist laut dem Proposal N4265 eine Funktion, die eine transaction_safe Definition besitzt. Das gilt, wenn die folgenden Eigenschaften auf ihre Definition nicht zutreffen.

• Sie besitzt volatile Parameter oder volatile Variablen.
• Sie enthält transaction-unsafe Anweisungen.
• Falls die Klasse eines Konstruktor oder Destruktor, der im Atomic Block verwendet wird, volatile nicht-statische Member besitzt.

Diese Definition von transaction_safe ist natürlich nicht ausreichend, da sie auf transaction_unsafe verweist. Was transaction_unsafe heißt, lässt sich zur Zeit am besten in dem Proposal N4265 nachlesen.

Wie geht's weiter?

Im nächsten Artikel geht es mit dem Fork-Join Paradigma weiter. Genauer gesagt, es geht um Task Blöcke.

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.