Transactional Memory

Contents[Show]

Transactional memory is based on the idea of a transaction from the database theory. Transactional memory shall make the handling with threads a lot easier. That for two reasons. Data races and deadlocks disappear. Transactions are composable.

A transaction is an action that has the properties Atomicity, Consistency, Isolation, and Durability (ACID). Except for the durability, all properties hold for transactional memory in C++. Therefore, only three short questions are left.

ACI(D)

What means atomicity, consistency, and isolation for an atomic block consisting of some statements?

atomic{
  statement1;
  statement2;
  statement3;
}
  • Atomicity: Either all or no statement of the block is performed.
  • Consistency: The system is always in a consistent state. All transaction build a total order.
  • Isolation: Each transaction runs in total isolation from the other transactions.

How are these properties guaranteed? A transaction remembers its initial state. Then the transaction will be performed without synchronisation. If a conflict happens during its execution, the transaction will be interrupted and put to its initial state. This rollback causes that the transaction will be executed once more. If the initial state of the transaction even holds at the end of the transaction, the transaction will be committed.

A transaction is a kind of speculative action that is only committed if the initial state holds. It is in contrary to a mutex an optimistic approach. A transaction is performed without synchronisation. It will only be published if no conflict to its initial state happens. A mutex is a pessimistic approach. At first, the mutex ensures that no other thread can enter the critical region. The thread only will enter the critical region if it is the exclusive owner of the mutex and hence all other threads are blocked.

C++ supports transactional memory in two flavours: synchronised blocks and atomic blocks.

Transactional Memory

Up to now, I only wrote about transactions. No, I will write about synchronised blocks and atomic blocks. Both can be encapsulated in the other. To be specific, synchronised blocks are no atomic blocks because they can execute transaction-unsafe. This may be code like the output to the console which can not be made undone. That is the reason, synchronised blocks are often called relaxed.

Synchronized Blocks

Synchronized block behave such as they are protected by a global lock. That means all synchronized blocks obey a total order. Therefore, all changes to a synchronized block are available in the next synchronized block. There is a synchronize-with relation between the synchronized blocks. Because synchronized blocks behave like protected by a global lock, they can not cause a deadlock. While a classical lock protects a memory area, a global lock of a synchronized block protects the total program. That is the reason, why the following program is well-defined:

 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";
  
}

 

Although the variable i in line 7 is a global variable and the operations in the synchronized block are transaction-unsafe, the program is well-defined. The access to i and std::cout happen in total order. That is due to the synchronized block.

The output of the program is not so thrilling. The values for i are written in an increasing sequence, separated by a comma. Only for completeness.

synchronized

What about data races? You will have them with synchronized blocks. Only a small modification is necessary.

 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";
  
}

 

To observe the data race, I let the synchronized block sleep for a nanosecond (line 15). At the same time, I access std::cout without a synchronized block (line 29). Therefore I launch 10 threads that increment the global variable i. The output shows the issue.

nonsynchronizedEdit

I put red circles around the issues in the output. These are the spots, at which std::cout is used by at least two threads at the same time. Because of the C++11 standard guarantees that the characters will be written in an atomic way that is only an optical issue. But what is worse, is that the variable i is be written by at least two threads. That is a data race. Therefore the program has undefined behaviour.

The total order of synchronized blocks also holds for atomic blocks.

Atomic Blocks

You can execute transaction-unsafe code in a synchronized block but not in an atomic block. Atomic blocks are available in the forms: atomic_noexcept, atomic_commit, and atomic_cancel. The three suffixes  _noexcept, _commit, and _cancel defines how an atomic block should manage an exception.

  • atomic_noexcept: If an exception throws,  std::abort will be called and the program aborts.
  • atomic_cancel: In the default case, std::abort is called. That will not hold if a transaction-safe exception throws that is responsible for the ending of the transaction. In this case, the transaction will be canceled, put to its initial state and the exception will be thrown.
  • atomic_commit: If an exception is thrown, the transaction will be committed normally.

transaction-safe exceptions: std::bad_alloc, std::bad_array_length, std::bad_array_new_length, std::bad_cast, std::bad_typeid, std::bad_exception, std::exception, and all exceptions that are derived from them are transaction-safe.

transaction_safe versus transaction_unsafe Code

You can declare a function as transaction_safe or attach the transaction_unsafe to it.

int transactionSafeFunction() transaction_safe;

[[transaction_unsafe]] int transactionUnsafeFunction();

transaction_safe is part of the type of a function. But what does a transaction_safe mean? A transaction_safe function is according to the proposal N4265 a function that has a transaction_safe definition. This holds true if the following properties do not apply to its definition.

  • It has a volatile parameter or a volatile variable.
  • It has transaction-unsafe statements.
  • If the function uses a constructor or destructor of a class in its body that has a volatile non-static member.

Of course, this definition of transaction_safe is not sufficient because it uses the term transaction_unsafe. You can read the proposal N4265 what does transaction_unsafe means.

What's next?

The next post is about the fork-join paradigm. To be specific, it's about task blocks.

 

 

 

 

title page smalltitle page small Go to Leanpub/cpplibrary "What every professional C++ programmer should know about the C++ standard library".   Get your e-book. Support my blog.

Tags: C++20

Comments   

0 #1 Milan 2017-03-04 22:45
Your method of telling everything in this paragraph is genuinely
good, every one be able to without difficulty understand it, Thanks a lot.
Quote

Add comment


My Newest E-Book

Latest comments

Subscribe to the newsletter (+ pdf bundle)

Blog archive

Source Code

Visitors

Today 346

All 278869

Currently are 177 guests and no members online