Do mutexes guarantee ordering of acquisition?

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?

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.

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).