Mutexes and Critical Sections

Many useful actions cannot be finished with a single shared resource. A program may need to update one data structure and then another, and each update must be protected so that no other thread changes the data in the middle of the operation. Locks, implemented as mutexes, provide that protection. The trouble begins when a task needs more than one lock at the same time, because the order in which those locks are requested can turn a correct program into one that stops making progress entirely.

Picture two people sharing one pair of scissors. Each person holds one half of the scissors and waits for the other person to give up the second half. Neither person will finish cutting. Neither did anything wrong on their own. The stall comes from the arrangement of who holds what and who is waiting for what. The same kind of arrangement can happen with threads and mutexes.

A mutex is a lock that protects data. Before a thread touches shared data, it acquires the mutex that guards that data. While it holds the mutex, no other thread can acquire it, so other threads wait. When the thread is done, it releases the mutex and the next waiting thread may proceed. The protected stretch of code is often called a critical section, because only one thread should be inside it at a time.

Consider two threads and two mutexes, called mutex1 and mutex2. Thread1 acquires mutex1 and then tries to acquire mutex2. At the same moment, Thread2 acquires mutex2 and then tries to acquire mutex1. Trace the steps below and keep track of which mutex each thread owns after each one.

Steps one and two are harmless. Each thread successfully takes the first lock it needs. The problem appears at steps three and four. Thread1 now holds mutex1 and is sleeping on mutex2. Thread2 holds mutex2 and is sleeping on mutex1. Each thread is waiting for the mutex the other one holds, so neither can move forward.

The arrangement above forms a loop. Each mutex points back to the thread that holds it, and each thread points to the mutex it is trying to get. Following the arrows around the loop shows why no one can move first. This closed loop of waiting is called a circular wait, and it is the core of a deadlock.

The stall is permanent because releasing a lock is something a thread does only when it is done with the data. Thread1 would have to finish its work to release mutex1, but finishing that work requires mutex2, which Thread2 holds. Thread2 is in the same position with respect to mutex1. Because the dependency runs in a circle, no step can start the chain moving again.

The standard library offers an operation for this situation: lock(). Instead of grabbing one mutex and then asking for the next, a thread hands all of the mutexes it needs to lock() as arguments. The operation is built on two guarantees. First, lock() proceeds only after it has acquired all of its mutex arguments. Second, it never blocks, meaning it never goes to sleep, while it is holding a mutex.

The one-at-a-time version creates the circle because a thread can hold mutex1 while it sleeps waiting for mutex2. The lock() version has no such gap. A thread either obtains everything it asked for and continues, or it does not hold any of those mutexes while it waits. Without a partial set held during a wait, the circular chain from the earlier scenario cannot form. In short, the lock() operation prevents deadlocks by acquiring all mutexes at once.

Acquiring locks is only half of the job. They also have to be released, or other threads wait forever. The unique_lock tool handles release. Each unique_lock object wraps a mutex, and its destructor releases that mutex when the object goes out of scope. In practical terms, when a thread leaves the block of code where the unique_lock was declared, the mutex it guards is released without the programmer writing an explicit unlock.

The source ties this release behavior to the lock() operation. The destructors of the individual unique_lock objects ensure that the mutexes are released when a thread leaves the scope. This means a thread that has acquired its mutexes through lock() and wrapped each one in a unique_lock can rely on scope exit to free them. The guarantee holds when the thread leaves that scope, so the release is tied to the structure of the code rather than to a separate call the programmer must remember.

A deadlock forms when each of two threads holds one mutex and waits for the one the other holds. The waiting forms a closed loop, and because each release depends on progress that needs the lock being waited for, the stall is permanent. The lock() operation prevents this by acquiring all of its mutex arguments together, proceeding only after it has every one, and never sleeping while it holds a mutex. A unique_lock releases its mutex through its destructor when the thread leaves the scope.