patternMinor
Why are most mutex implementations unfair?
Viewed 0 times
implementationswhymutexareunfairmost
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#70125, answer score: 7
Revisions (0)
No revisions yet.