How does a mutex work? What does it cost?（转载）

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!

Also read CPU Memory – Why do I need a mutex?.

What is a mutex?

A mutex, in its most fundamental form, is just an integer in memory. This memory can have a few different values depending on the state of the mutex. Though usually when we speak of mutexes, we also talk of the locks which use the mutex. The integer in memory is not intriguing, but the operations around it are.

There are two fundamental operations which a mutex must provide to be useful:

• lock
• unlock

unlock is a simple case since it’s usually just one function. Unlocking a mutex makes it available for another process to lock. lock on the other hand usually has several variants. In most cases, we’d like to wait until we can lock the mutex, so the most common lock operation does exactly this. Other users may wish to only wait for a given period, and yet some other users may not want to wait at all.

There can be only one lock on a mutex at any given time. If another thread wishes to gain control, it must wait for the first to unlock it. This mutual exclusion is the primary goal of the mutex, and indeed the origin of the name. Attempting to lock an already locked mutex is called contention. In a well-planned program, contention should be quite low; you should be designing 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 obviously 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 simply an integer in memory. Its value starts as 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 has a function called “compare-and-set” or “test-and-set” which does exactly this. This function takes the address of the integer, and two integer values: a compare and 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 basic 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 really understand high-level threads and processes, so it isn’t in a position to implement waiting. The OS must provide the waiting functionality.

For the CPU to wait correctly, a caller is going to need to go through a system call. It is the only thing that can synchronize the various threads and provide the waiting functionality. So 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. So if a system call does provide a full mutex why would we bother with any sort of test-and-set in user space? 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. Non-contention cases are resolved in user space. Contention cases are delegated to the operating system to handle in a safe, albeit far costlier manner. The waiting is handled as part of the OS 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 signaling.

The Costs

There are a few points of interest when it comes to the cost of a mutex. The first most vital point is 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 the CPUs 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. Most costly however is the system call. Not only do you suffer the context switch overhead of the system call, the kernel now spends some time in its scheduling code.

---

本文地址：http://xnerv.wang/how-does-a-mutex-work-what-does-it-cost/
转载自：How does a mutex work? What does it cost?