Do mutexes guarantee ordering of acquisition? Unlocking thread takes it again while others are still waiting

Question

A coworker had an issue recently that boiled down to what we believe was the following sequence of events in a C++ application with two threads:

• Thread A holds a mutex.

• While thread A is holding the mutex, thread B attempts to lock it. Since it is held, thread B is suspended.

• Thread A finishes the work that it was holding the mutex for, thus releasing the mutex.

• Very shortly thereafter, thread A needs to touch a resource that is protected by the mutex, so it locks it again.

• It appears that thread A is given the mutex again; thread B is still waiting, even though it "asked" for the lock first.

Does this sequence of events fit with the semantics of, say, C++11's std::mutex and/or pthreads? I can honestly say I've never thought about this aspect of mutexes before.

Are there any fairness guarantees to prevent starvation of other threads for too long, or any way to get such guarantees?

Headstone

c++ - Creating a lock that preserves the order of locking attempts in C++11 - Stack Overflow – Austinaustina

Answer 1

Known problem. C++ mutexes are thin layer on top of OS-provided mutexes, and OS-provided mutexes are often not fair. They do not care for FIFO.

The other side of the same coin is that threads are usually not pre-empted until they run out of their time slice. As a result, thread A in this scenario was likely to continue to be executed, and got the mutex right away because of that.

Superscribe

Another of looking at it is that the OS, when A first gives up the mutex, merely marks B as ready to run. The OS won't actually perform the context switch until it absolutely has to because it's expensive. It happens either (as you say) when A's time slice has expired, or A makes a call to a blocking function, or B has a higher priority than A (which is assessed by the OS when A gives up the mutex). If you start using thread priority to get things to happen in the right order then you may need an OS that resolves priority inversions (so not stock Linux, or Windows. Linux+PREMPT_RT is OK). – Zizith

Windows native synchronization types (CreateMutex, CreateSemaphore, WaitForSingleObject, WaitForMultipleObjects) use some type of queue so that requests are granted in FIFO order, based on actual testing, but I haven't found this documented. – Kerbstone

Answer 2

The guarantee of a std::mutex is enable exclusive access to shared resources. Its sole purpose is to eliminate the race condition when multiple threads attempt to access shared resources.

The implementer of a mutex may choose to favor the current thread acquiring a mutex (over another thread) for performance reasons. Allowing the current thread to acquire the mutex and make forward progress without requiring a context switch is often a preferred implementation choice supported by profiling/measurements.

Alternatively, the mutex could be constructed to prefer another (blocked) thread for acquisition (perhaps chosen according FIFO). This likely requires a thread context switch (on the same or other processor core) increasing latency/overhead. NOTE: FIFO mutexes can behave in surprising ways. E.g. Thread priorities must be considered in FIFO support - so acquisition won't be strictly FIFO unless all competing threads are the same priority.

Adding a FIFO requirement to a mutex's definition constrains implementers to provide suboptimal performance in nominal workloads. (see above)

Protecting a queue of callable objects (std::function) with a mutex would enable sequenced execution. Multiple threads can acquire the mutex, enqueue a callable object, and release the mutex. The callable objects can be executed by a single thread (or a pool of threads if synchrony is not required).

Flay

Answer 3

•Thread A finishes the work that it was holding the mutex for, thus releasing the mutex. •Very shortly thereafter, thread A needs to touch a resource that is protected by the mutex, so it locks it again

In real world, when the program is running. there is no guarantee provided by any threading library or the OS. Here "shortly thereafter" may mean a lot to the OS and the hardware. If you say, 2 minutes, then thread B would definitely get it. If you say 200 ms or low, there is no promise of A or B getting it.

Number of cores, load on different processors/cores/threading units, contention, thread switching, kernel/user switches, pre-emption, priorities, deadlock detection schemes et. al. will make a lot of difference. Just by looking at green signal from far you cannot guarantee that you will get it green.

If you want that thread B must get the resource, you may use IPC mechanism to instruct the thread B to gain the resource.

Zygoma

200 milliseconds is still forever, way longer than a scheduling timeslice, and vastly longer than inter-core latency (usually 40 to 80 nanoseconds) for an unlock to wake up any sleeping threads. Even 200 microseconds would be quite a long time, unless all other cores were already running stuff and the OS chose to let them finish their timeslices before waking the thread that was waiting for the lock. (Most modern OSes have OS-assisted sleep/wake for locks, not just waking up to poll.) – Hebraist

Answer 4

You are inadvertently suggesting that threads should synchronise access to the synchronisation primitive. Mutexes are, as the name suggests, about Mutual Exclusion. They are not designed for control flow. If you want to signal a thread to run from another thread you need to use a synchronisation primitive designed for control flow i.e. a signal.

Larrylars

When stated that generically, it is wrong. There are OSes which provide for fair mutexes, and in those OSes OP's scenario would work as expected. – Superscribe

Answer 5

You can use a fair mutex to solve your task, i.e. a mutex that will guarantee the FIFO order of your operations. Unfortunately, C++ standard library doesn't have a fair mutex.

Thankfully, there are open-source implementations, for example yamc (a header-only library).

Feet

Answer 6

The logic here is very simple - the thread is not preempted based on mutexes, because that would require a cost incurred for each mutex operation, which is definitely not what you want. The cost of grabbing a mutex is high enough without forcing the scheduler to look for other threads to run.

If you want to fix this you can always yield the current thread. You can use std::this_thread::yield() - http://en.cppreference.com/w/cpp/thread/yield - and that might offer the chance to thread B to take over the mutex. But before you do that, allow me to tell you that this is a very fragile way of doing things, and offers no guarantee. You could, alternatively, investigate the issue deeper:

1. Why is it a problem that the B thread is not started when A releases the resource? Your code should not depend on such logic.

2. Consider using alternative thread synchronization objects like barriers (boost::barrier or http://linux.die.net/man/3/pthread_barrier_wait ) instead, if you really need this sort of logic.

3. Investigate if you really need to release the mutex from A at that point - I find the practice of locking and releasing fast a mutex for more than one time a code smell, it usually impacts terribly the performace. See if you can group extraction of data in immutable structures which you can play around with.

4. Ambitious, but try to work without mutexes - use instead lock-free structures and a more functional approach, including using a lot of immutable structures. I often found quite a performance gain from updating my code to not use mutexes (and still work correctly from the mt point of view)

Transubstantiate

Answer 7

How do you know this:

While thread A is holding the mutex, thread B attempts to lock it. Since it is held, thread B is suspended.

How do you know thread B is suspended. How do you know that it is not just finished the line of code before trying to grab the lock, but not yet grabbed the lock:

Thread B:

x = 17; // is the thread here?
// or here? ('between' lines of code)
mtx.lock();  // or suspended in here?
// how can you tell?

You can't tell. At least not in theory.

Thus the order of acquiring the lock is, to the abstract machine (ie the language), not definable.

Isochronal

Just FYI knowing for sure is trivial if the work performed by the threads is different. eg; Thread A multiplies x by 2 and Thread B increments x by 3. Order of operations will result in unique results. – Wite

@Wite sure, after the fact you can tell which happened first. The question is, how can you tell if a thread is currently waiting on a mutex, vs is the thread just suspended by the scheduler one instruction before waiting on the mutex. You can't tell (unless you are inside the OS/kernel/scheduler). – Isochronal