Thread Scheduling Basics

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. The way those locks are requested can turn a correct program into one that stops making progress entirely.

Think of two people each holding one half of a pair of scissors and waiting for the other person to give up the second half. Neither person did anything wrong on their own, and neither will finish cutting. The stall comes from the arrangement of who holds what and who is waiting for what. This article looks at that arrangement in threads and mutexes, and at the tools the standard library offers to avoid it.

Consider two threads and two mutexes, called mutex1 and mutex2. Suppose thread1 acquires mutex1 and then tries to acquire mutex2. At the same moment, thread2 acquires mutex2 and then tries to acquire mutex1. Each thread now holds one mutex and is waiting for the mutex the other one holds. Neither can move forward, because the lock it needs is locked by the other thread, and that other thread will not release it while it is itself stuck.

The diagram below shows the same arrangement as a loop of ownership and waiting. 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.

Notice that each arrow in the loop describes a true fact at the same time. mutex1 is held by thread1, thread1 is waiting for mutex2, mutex2 is held by thread2, and thread2 is waiting for mutex1. Because the dependency closes into a circle, there is no starting point from which one thread can finish first.

Releasing a lock is something a thread does when it is done with the data. In the scenario above, each thread would have to finish its work to release its lock, but finishing its work requires the lock it is waiting for. Each thread's release depends on progress that requires the very lock it is waiting for, so the stall is permanent.

Because the dependency runs in a circle, no step can start the chain moving again. Waiting is not the problem by itself. Waiting becomes a deadlock when the waiting forms a loop in which every party is blocked by another party in the loop.

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 designed around 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.

These two guarantees break the circle that caused the deadlock. In the earlier scenario, thread1 was holding mutex1 while sleeping on mutex2. With lock(), a thread does not sit on a partial set of mutexes while waiting for the rest. It either obtains everything it asked for and continues, or it does not hold any of them while it waits. The sequence below shows the order of events when a thread calls lock() with two mutexes.

Acquiring locks is only half of the job. They also have to be released, or other threads will wait forever. The source material describes unique_lock as the tool that handles this. Each unique_lock object wraps a mutex, and its destructor releases that mutex when the object goes out of scope. 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 to lock() as well. The destructors of the individual unique_lock objects ensure that the mutexes are released when a thread leaves the scope. 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, including the case where the thread leaves that scope early.

The diagram shows that the mutex moves from unlocked to locked when the unique_lock takes ownership, and back to unlocked when the destructor runs. The arrow labeled scope exit covers both the normal end of the block and an early departure from it. The release is tied to scope rather than to an explicit call, so the programmer does not have to remember to unlock on every possible path.