Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What are the exact inter-thread reordering constraints on mutex.lock() and .unlock() in c++11 and up?

According to https://en.cppreference.com/w/cpp/atomic/memory_order mutex.lock() and mutex.unlock() are acquire and release operations. An acquire operation makes it impossible to reorder later instructions in front of it. And release operations make it impossible to reorder earlier instructions after it. This makes it such that the following code:

[Thread 1]
mutex1.lock();
mutex1.unlock();
mutex2.lock();
mutex2.unlock();
[Thread 2]
mutex2.lock();
mutex2.unlock();
mutex1.lock();
mutex1.unlock();

Can be reordered into the following (possibly deadlocking) code:

[Thread 1]
mutex1.lock();
mutex2.lock();
mutex1.unlock();
mutex2.unlock();
[Thread 2]
mutex2.lock();
mutex1.lock();
mutex2.unlock();
mutex1.unlock();

Is it possible for this reordering to occur. Or is there a rule preventing it?

like image 444
Flipvs Avatar asked Apr 06 '21 14:04

Flipvs


People also ask

What is mutex lock and unlock?

Locks a mutex object, which identifies a mutex. Mutexes are used to protect shared resources. If the mutex is already locked by another thread, the thread waits for the mutex to become available. The thread that has locked a mutex becomes its current owner and remains the owner until the same thread has unlocked it.

What are the two functions used with mutex locks?

The mutex can be unlocked and destroyed by calling following two functions :The first function releases the lock and the second function destroys the lock so that it cannot be used anywhere in future. int pthread_mutex_unlock(pthread_mutex_t *mutex) : Releases a mutex object.

Which of the following is the correct syntax to initialize mutex locks to achieve synchronization?

A mutex is initialized and then a lock is achieved by calling the following two functions : int pthread_mutex_init(pthread_mutex_t *restrict mutex, const pthread_mutexattr_t *restrict attr); int pthread_mutex_lock(pthread_mutex_t *mutex);

What happens when a mutex is unlocked?

If a thread attempts to unlock a mutex that it has not locked or a mutex that is unlocked, an error is returned. If the mutex type is PTHREAD_MUTEX_RECURSIVE, the mutex maintains the concept of a lock count. When a thread successfully acquires a mutex for the first time, the lock count is set to one.

What happens when a thread tries to unlock a mutex?

If a thread attempts to relock a mutex that it has already locked, an error will be returned. If a thread attempts to unlock a mutex that it has not locked or a mutex which is unlocked, an error will be returned. If the mutex type is PTHREAD_MUTEX_RECURSIVE, then the mutex maintains the concept of a lock count.

What is the Order of lock and unlock operations on mutex?

All lock and unlock operations on the mutex follow a single total order, with all visible effects synchronized between the lock operations and previous unlock operations on the same object.

How do you unlock a mutex in C++?

A mutex is initialized in the beginning of the main function. The same mutex is locked in the ‘doSomeThing ()’ function while using the shared resource ‘counter’ At the end of the function ‘doSomeThing ()’ the same mutex is unlocked. At the end of the main function when both the threads are done, the mutex is destroyed.

What is the non-member function lock in mutex?

The non-member function lock allows to lock more than one mutex object simultaneously, avoiding the potential deadlocks that can happen when multiple threads lock/unlock individual mutex objects in different orders.


1 Answers

Almost a duplicate: How C++ Standard prevents deadlock in spinlock mutex with memory_order_acquire and memory_order_release? - that's using hand-rolled std::atomic spinlocks, but the same reasoning applies:

The compiler can't compile-time reorder mutex acquire and release in ways that could introduce a deadlock where the C++ abstract machine doesn't have one. That would violate the as-if rule.
It would effectively be introducing an infinite loop in a place the source doesn't have one, violating this rule:

ISO C++ current draft, section 6.9.2.3 Forward 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.


The ISO C++ standard doesn't distinguish compile-time vs. run-time reordering. In fact it doesn't say anything about reordering. It only says things about when you're guaranteed to see something because of synchronizes-with effects, and the existence of a modification order for each atomic object, and the total order of seq_cst operations. It's a misreading of the standard to take it as permission to nail things down into asm in a way that requires mutexes to be taken in a different order than source order.

Taking a mutex is essentially equivalent to an atomic RMW with memory_order_acquire on the mutex object. (And in fact the ISO C++ standard even groups them together in 6.9.2.3 :: 18 quoted above.)

You're allowed to see an earlier release or relaxed store or even RMW appear inside a mutex lock/unlock critical section instead of before it. But the standard requires an atomic store (or sync operation) to be visible to other threads promptly, so compile-time reordering to force it to wait until after a lock had been acquired could violate that promptness guarantee. So even a relaxed store can't compile-time / source-level reorder with a mutex.lock(), only as a run-time effect.

This same reasoning applies to mutex2.lock(). You're allowed to see reordering, but the compiler can't create a situation where the code requires that reordering to always happen, if that makes execution different from the C++ abstract machine in any important / long-term observable ways. (e.g. reordering around an unbounded wait). Creating a deadlock counts as one of those ways, whether for this reason or another. (Every sane compiler developer would agree on that, even if C++ didn't have formal language to forbid it.)

Note that mutex unlock can't block, so compile-time reordering of two unlocks isn't forbidden for that reason. (If there are no slow or potentially blocking operations in between). But mutex unlock is a "release" operation, so that's ruled out: two release stores can't reorder with each other.


And BTW, the practical mechanism for preventing compile-time reordering of mutex.lock() operations is just to make them regular function calls that the compiler doesn't know how to inline. It has to assume that functions aren't "pure", i.e. that they have side effects on global state, and thus the order might be important. That's the same mechanism that keeps operations inside the critical section: How does a mutex lock and unlock functions prevents CPU reordering?

An inlinable std::mutex written with std::atomic would end up depending on the compiler actually applying the rules about making operations visible promptly and not introducing deadlocks by reordering things at compile-time. As described in How C++ Standard prevents deadlock in spinlock mutex with memory_order_acquire and memory_order_release?

like image 193
Peter Cordes Avatar answered Sep 30 '22 18:09

Peter Cordes