Tag: atomics

Using atomics for thread synchronization in C++

In my previous blog post I wrote about spin locks, and how compilers must not move the locking loop above a prior unlock.

After thinking about this done more, I realised that is not something specific to locks — the same issue arises with any two step synchronization between threads.

Consider the following code

std::atomic<bool> ready1{false};
std::atomic<bool> ready2{false};

void thread1(){
  ready1.store(true, std::memory_order_release);
  while(!ready2.load(std::memory_order_acquire)){}
}

void thread2() {
  while(!ready1.load(std::memory_order_acquire)) {}
  ready2.store(true, std::memory_order_release);
}

thread1 sets ready1 to true, then waits for thread2 to set ready2 to true. Meanwhile, thread2 waits for ready1 to be true, then sets ready2 to true.

This is almost identical to the unlock/lock case from the previous blog post, except the waiting thread is just using plain load rather than exchange.

If the compiler moves the wait loop in thread1 above the store then both threads will hang forever. However it cannot do this for the same reason the spinlocks can't deadlock in the previous post: the store has to be visible to the other thread in a finite period if time, so must be issued before the wait loop. https://eel.is/c++draft/intro.multithread#intro.progress-18

An implementation should ensure that the last value (in modification order) assigned by an atomic or synchronization operation will become visible to all other threads in a finite period of time.

If the optimizer moved the store across the loop in thread1, then it could not guarantee that the value became visible to the other thread in a finite period of time. Therefore such an optimization is forbidden.

Posted by Anthony Williams
[/ cplusplus /] permanent link
Tags: , , ,
Stumble It! stumbleupon logo | Submit to Reddit reddit logo | Submit to DZone dzone logo

Comment on this post

Follow me on Twitter

Can non-overlapping spinlocks deadlock in C++?

There has been discussion on Twitter recently about whether or not the C++ memory model allows spinlocks to deadlock if they just use memory_order_acquire in lock and memory_order_release in unlock, due to compiler optimizations. The case in question is where a thread locks one mutex, unlocks it, and locks a second: can the compiler reorder the second lock above the first unlock? If it does, and another thread does the same in the reverse order, with the same optimization, then sequential locks could deadlock.

Here is the code in question, with all the lock/unlock code inlined.

std::atomic<bool> mutex1{false};
std::atomic<bool> mutex2{false};

int x=0;
int y=0;

void thread1(){
  while(mutex1.exchange(true,std::memory_order_acquire)){}  // #1
  x=1;
  mutex1.store(false,std::memory_order_release); // #2

  while(mutex2.exchange(true,std::memory_order_acquire)){} // #3
  y=1;
  mutex2.store(false,std::memory_order_release); // #4
}

void thread2(){
  while(mutex2.exchange(true,std::memory_order_acquire)){} // #5
  x=2;
  mutex2.store(false,std::memory_order_release); // #6

  while(mutex1.exchange(true,std::memory_order_acquire)){} // #7
  y=2;
  mutex1.store(false,std::memory_order_release); // #8
}

For there to even be the possibility of deadlock, thread1 must successfully execute line #1 before thread2 successfully executes line #7, and thread2 must successfully execute line #5 before thread1 successfully executes line #3. Because these are RMW operations, the threads must agree on the ordering.

The modification order of mutex1 must thus be #1(success), #2, #7(success), #8. Similarly, the modification order of mutex2 must be #5(success), #6, #3(success), #4.

All threads must agree on these modification orders. https://eel.is/c++draft/intro.multithread#intro.races-4

From the point of view of thread1, everything must run in program order: compilers can only optimize things as long as they run "as if" in program order.

The store to mutex1 at #2 is guaranteed to be visible to thread2 in "a finite period of time". https://eel.is/c++draft/intro.multithread#intro.progress-18

Consequently, thread2 must eventually see that store at line #7, even if it executes line #7 a large number of times first.

Therefore, the compiler cannot move line #3 completely above line #2, since doing so would not guarantee the visibility of #2 to other threads in a finite period of time. It can move an arbitrary number of executions of line #3 above line #2 (all of which will see that mutex2 is still true), but not all the executions of line #3.

Given that thread2 eventually sees the store from #2 at line #7, the exchange at line #7 will eventually succeed, and thread2 will eventually complete.

Likewise, the store at #6 must become visible to thread1 in a finite period of time. Therefore the exchange at line #3 will eventually see the value stored by

6, the exchange will succeed, and thread1 will complete, and the compiler is

not allowed to move all the executions of line #7 above #6.

No amount of compiler optimization is allowed to break this, so no: spinlocks cannot deadlock if they don't overlap.

Posted by Anthony Williams
[/ cplusplus /] permanent link
Tags: , , ,
Stumble It! stumbleupon logo | Submit to Reddit reddit logo | Submit to DZone dzone logo

Comment on this post

Follow me on Twitter