Sequential Consistency applied

I have introduced In the post Sequential Consistency the default memory model. This model, in which all operations in all threads take place in a global time clock, has a big advantage but also a significant disadvantage.

Heavyweight synchronization

The significant advantage of sequential consistency is, that it matches our intuition of many threads running in parallel. The significant disadvantages are that the system has a lot of work to do to synchronize all the threads.

The following program synchronizes the producer and the consumer thread with the help of sequential consistency.

 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

// producerConsumer.cpp

#include <atomic>
#include <iostream>
#include <string>
#include <thread>

std::string work;
std::atomic<bool> ready(false);

void consumer(){
  while(!ready.load()){}
  std::cout<< work << std::endl;    
}

void producer(){
  work= "done";
  ready=true; 
}

int main(){
  std::thread prod(producer);
  std::thread con(consumer);
  prod.join(); 
  con.join();
}

The output of the program is concise and exciting.

Because of the sequential consistency, the program execution is deterministic. It always displays "done".

The graphic hit the spot. The consumer thread waits in the while-loop until the atomic variable ready is set to true. In case that happens, the consumer threads continue with their work.

It is easy to reason that the program will always return "done". I have only used the two characteristics of sequential consistency. On one hand, both threads execute their instructions in the source code order, on the other hand, each thread sees the operations of the other thread in the same order. So both threads are following the same global time clock. This time clock will also hold - with the help of the while(!ready.load()){}-loop - for the synchronization of the producer and the consumer thread.

But I can do the reasoning a lot more formally by using the terminology of the memory model. So the formal version:

=> Means it follows in the next lines:

1. work= "done"  is sequenced-before ready=true => work= "done" happens-before ready=true
2. while(!ready.load()){} is sequenced-before std::cout<< work << std::endl =>  while(!ready.load()){} happens-before std::cout<< work << std::endl
3. ready= true synchronizes-with while(!ready.load()){}  => ready= true inter-thread happens-before while (!ready.load()){} => ready= true happens-before while (!ready.load()){}

=>  Because the happens-before relation is transitive, it follows t: work= "done" happens-before ready= true happens-before while(!ready.load()){} happens-before std::cout<< work << std::endl

From the sequential consistency to the acquire-release semantic

A thread sees the operations of another thread and all other threads in the same order. The key characteristic of sequential consistency will not hold if we use the acquire-release semantic for atomic operations. This is an area in which C# or Java will not follow. But that's also an area where our intuition begins to wane.

There is no global synchronization between threads in the acquire-release semantic; there is only a synchronization between atomic operations on the same atomic variable. So a write operation on one thread synchronizes with a read operation on another on the same atomic variable. This synchronization relation on the same atomic variable helps to establish a happens-before relation between atomic variables and, therefore, between threads.

What's next?

The details of the acquire-release semantic will follow in the next post. This includes an optimized spinlock.