How does a mutex work? What does it cost?

concurrency, concurrent programming, contention, cpu memory, critical data, efficiency, fundamental operations, linux, lock, mutex
February 20, 2019

Concurrent programming requires synchronization. We can’t have more than one thread accessing data at the same time; otherwise, we end up with a data race. The most common solution is to wrap the critical data access in a mutex. Mutexes are, of course, not free. A mutex can have a significant impact on the cost of the code we are writing. When used correctly we’ll barely notice the overhead. When misused, it can cause a program to run worse in threaded mode than it would have single threaded!

Go further with the 🎞️ video class.

What is a mutex?

A mutex, in its most fundamental form, is just an integer in memory. This integer can have a few different values depending on the state of the mutex. When we speak of mutexes, we also need to speak about the locking operations. The integer in memory is not intriguing, but the operations around it are.

There are two fundamental operations which a mutex must provide:

lock
unlock

A thread wishing to use the mutex, must first call lock, then eventually call unlock to release it. There can be only one lock on a mutex at any given time. The thread holding the lock is the current owner of the mutex. If another thread wishes to gain control, it must wait for the first thread to unlock it. This mutual exclusion is the primary goal of the mutex, and indeed the origin of the name.

The lock operation has several variants. In most cases, we’d like to wait until we can lock the mutex, so the most common lock operation does precisely this. Other time we may wish to only wait for a given period, and sometimes we may not want to wait at all.

In contrast, unlock is usually just one function. It makes a mutex available for another process to lock.

Contention

Attempting to lock an already locked mutex is called contention. In a well-planned program, contention should be quite low. You should design your code so that most attempts to lock the mutex will not block.

There are two reasons why you want to avoid contention. The first is that any thread waiting on a mutex is not doing anything else — possibly resulting in unused CPU cycles. The second reason is more interesting, in particular for high-performance code. Locking a currently unlocked mutex is cheap compared to the contention case. We have to look at how the mutex works to understand why.

How does it work?

As mentioned before, the data of a mutex is an integer in memory. Its value starts at 0, meaning that it is unlocked. If you wish to lock the mutex, you check if it is zero and then assign one. The mutex is now locked, and you are the owner of it.

The trick is that the test-and-set operation has to be atomic. If two threads happen to read 0 at the same time, then both would write 1 and think they own the mutex. Without CPU support there is no way to implement a mutex in user space: this operation must be atomic with respect to the other threads. Fortunately, CPUs have a function called “compare-and-set” or “test-and-set” which does exactly this. This function takes the address of the integer and two values: a compare value and a set value. If the comparison value matches the current value of the integer, then it is replaced with the new value. In C style code this might like look this:

int compare_set( int * to_compare, int compare, int set );int mutex_value;int result = compare_set( &mutex_value, 0, 1 );if( !result ) { /* we got the lock */ }

The caller determines what happens by inspecting the return value. It is the dereferenced to_compare pointer value before the swap. If this value is equal to the compare value the caller knows the set was successful. If the value is different, then the call was unsuccessful. When the section of code no longer requires the lock, it can set the value back to 0. This makes up the fundamental part of our mutex.

Atomic increment/decrement functions could also be used and are the recommended way if using the Linux futex.

What about waiting?

Now comes the tricky part. Well, only in a way is it tricky, in another way it is simple. The above test-and-set mechanism provides no support for a thread to wait on the value (aside from a CPU intensive spin-lock). The CPU doesn’t fully understand high-level threads and processes, so it isn’t in a position to implement waiting. The operating system (OS) must provide the waiting functionality.

For the CPU to wait correctly, a caller needs to go through a system call. It is the only thing that can synchronize the various threads and provide the waiting functionality. If we have to wait on a mutex, or release a waiting mutex, we have no choice but to call the OS. Most OSs have built-in mutex primitives. In some cases, they provide full-fledged mutexes. If a system call does provide a full mutex, why would we bother with any test-and-set in userspace? The answer is that system calls have quite a bit of overhead and should be avoided when possible.

Various operating systems diverge at this point, and will likely change as time goes on. Under Linux, there is a system call futex which provides mutex like semantics. If there is no contention, the call is resolved in userspace. If there is contention, the call is delegated to the OS to handle in a safe, albeit far costlier manner. The OS handles the waiting as part of the process scheduler.

futex is quite flexible in allowing the creation of various locking mechanisms in addition to a mutex, such as a semaphore, a barrier, a read-write mutex, and event signalling.
See Also
How To Use Golang Mutex For Concurrent Programming

The Costs

There are a few points of interest when it comes to the cost of a mutex. The most vital point is the waiting time. Your threads should spend only a fraction of their time waiting on mutexes. If they are waiting too often, then you are losing concurrency. In a worst-case scenario many threads always trying to lock the same mutex may result in performance worse than a single thread serving all requests. This isn’t a cost of the mutex itself, but a serious concern with concurrent programming.

The overhead costs of a mutex relate to the test-and-set operation and the system call that implements a mutex. The test-and-set is likely a minuscule cost; being essential to concurrent processing, CPU vendors have a strong incentive to make it efficient. We’ve ignored another important instruction, however: the fence. This is used in all high-level mutexes and may have a higher cost than the test-and-set operation. I talk a bit more about fences in CPU Memory – Why do I need a mutex?. Most costly however is the system call. Not only do you suffer the context switch overhead, the kernel now spends some time in its scheduling code.

You may also be interested in reading CPU Memory – Why do I need a mutex?.

Please join me on Discord to discuss, or ping me on Mastadon.