11
$\begingroup$

My understanding is that most popular implementations of a mutex (e.g. std::mutex in C++) do not guarantee fairness -- that is, they do not guarantee that in instances of contention, the lock will be acquired by threads in the order that they called lock(). In fact, it is even possible (although hopefully uncommon) that in cases of high contention, some of the threads waiting to acquire the mutex might never acquire it.

This seems like an unhelpful behavior to me -- it seems to me that a fair mutex would yield behavior more in line with what a programmer would want/expect.

The reason given for why mutexes are typically not implemented to be fair is "performance", but I'd like to understand better what that means -- in particular, how does relaxing the mutex's fairness requirement improve performance? It seems like a "fair" mutex would be trivial to implement -- just have lock() append the calling thread to the tail of the mutex's linked list before putting the thread to sleep, and then have unlock() pop the next thread from the head of that same list and wake it up.

What mutex-implementation insight am I missing here, that would explain why it was considered worthwhile to sacrifice fairness for better performance?

$\endgroup$
3
  • 1
    $\begingroup$ That linked list for every mutex would have to be a shared data structure, right? So, how are you going to prevent data races on that without decreasing performance? $\endgroup$ Feb 10, 2017 at 8:11
  • $\begingroup$ Using a lockless linked-list mechanism, I think. What data structure does an unfair mutex use, in order to find the next thread to wake? $\endgroup$ Feb 10, 2017 at 16:01
  • 1
    $\begingroup$ You'll have to look that up, but does a lockless linked list guarantee fairness? I think you'll find that guarantees like fairness in concurrent programming are hard to come by. $\endgroup$ Feb 10, 2017 at 23:02

3 Answers 3

7
$\begingroup$

Jim Sawyer's answer points to one answer: When you have threads with differing priorities, "fair" behaviour would be incorrect. When you have multiple threads which could run, the highest priority thread is generally the one that should run.

However, there's a little-discussed secret of operating system implementation which you should be aware of, which is that occasionally operating systems run code as the user by hijacking a user thread. For safety reasons, most operating systems that do this only do it while a thread is blocked. When the operating system is done, the thread is re-suspended, and this typically has the effect of moving the thread to the back of the wait queue.

A typical example is a signal handler in Unix, an asynchronous system trap in VMS, or an asynchronous procedure call in Windows NT. These are all essentially the same thing: The operating system needs to notify the user process that some event happened, and this is is handled by running code in user space.

Many operating system services such as asynchronous I/O are often implemented on top of this facility.

Another example is if the process is under the control of a debugger. In that case, the debugging system may execute code as the user task for various reasons.

$\endgroup$
4
$\begingroup$

'Priority inversion' is one reason that fairness can be undesirable. A low priority process hits the locked mutex and sleeps. Then a higher priority process hits it, and also sleeps. When the mutex unlocks, which process should get the lock next?

$\endgroup$
1
  • $\begingroup$ Welcome to the site and thanks for answering a question that's been sitting around for a while with no answers! Your answer is, of course correct, but I feel it could have a bit more detail. $\endgroup$ Apr 9, 2017 at 11:24
3
$\begingroup$

A fair mutex will spend more of its lifetime locked than an unfair mutex, all else being equal. Because a thread releasing an unfair mutex can always just unlock it. But a thread releasing a fair mutex can only unlock it when the waiter queue is empty. Otherwise, the releasing thread must leave the mutex locked for the sake of the next thread, aka the first thread on the waiter queue, which is then dequeued and awoken. The mutex remains locked at least until the newly awoken thread is scheduled on a CPU, which could be a long time if there are many currently runnable threads.

And if the releasing thread promptly tries to re-acquire the same mutex, it must put itself in the rear of the waiter queue and go to sleep. This would not have happened if the thread didn't release the mutex to begin with. Therefore this incentivizes longer "more greedy" critical sections.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.