Why are most mutex implementations unfair?

Question

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?

Answer 1

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.

Answer 2

'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?

Answer 3

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.