The idea: sleep instead of spin

A mutex lets one thread at a time into a critical section, like a spinlock. The difference is what a waiting thread does: it does not spin, it goes to sleep in the kernel. Its CPU is then free for other work, and the thread is woken when the mutex is released.

Two panels. Spinlock: T1 holds the lock on CPU 0 while T2 keeps retrying on CPU 1, so CPU 1 is busy doing nothing useful. Mutex: T2 calls futex_wait and sleeps in the kernel wait queue, so CPU 1 is free to run other threads.
A spinning waiter burns its CPU; a mutex waiter sleeps in the kernel and leaves its CPU free.

Going to sleep needs the kernel, and a system call is slow compared with one atomic instruction. So a Linux mutex (pthread_mutex_t in glibc) is built so that the kernel is called only when threads actually collide. The tool for that is the futex ("fast user-space mutex"): an ordinary integer in the program's memory, plus a wait queue that the kernel keeps for that address.

How to use the animation

Each thread has its own CPU and runs the code once. Pick a scenario tab, then Step Tick or Run to End. Boxes fly from a CPU to the word m (atomic instructions in user space) or down into the kernel (system calls). A sleeping thread moves into the kernel's wait queue and its CPU turns grey: it is free. The strip at the bottom shows each CPU's ticks: K = system call or context switch, Z = asleep, CPU free.

The futex word: 0, 1 or 2

mMeaning
0free
1locked, and nobody waits
2locked, and someone may be asleep
 
lock:
    if (cmpxchg(&m, 0, 1) == 0) return;   /* fast path: 0 → 1        */
    while (xchg(&m, 2) != 0)              /* mark "maybe sleepers"   */
        futex_wait(&m, 2);               /* sleep while m == 2      */

unlock:
    if (xchg(&m, 0) == 2)                 /* was anyone waiting?     */
        futex_wake(&m, 1);               /* wake one sleeper        */

This is the mutex from Ulrich Drepper's paper Futexes Are Tricky; glibc's mutex works the same way. cmpxchg(&m, 0, 1) (compare-and-swap) writes 1 only if m is 0 and returns the old value; xchg writes and returns the old value. Both are single atomic instructions.

The fast path: no system call

When nobody else wants the mutex, lock is one cmpxchg (0 → 1) and unlock is one xchg that returns 1, so there is nobody to wake. The kernel is never involved (Fast path: 0 system calls). Most locks in real programs are uncontended most of the time, so this case matters most.

Sleep and wake

In Sleep and wake T2 finds the mutex locked. It sets m to 2 so that T1 will know it has to wake someone, and calls futex_wait(&m, 2). The kernel puts T2 in the wait queue for the address of m and runs something else on CPU 1. When T1 unlocks, xchg returns 2, so T1 calls futex_wake(&m, 1). T2 wakes up, is switched back onto its CPU and tries again: the mutex is not handed to it. It gets it with xchg(&m, 2), which returns 0.

Time-downward sequence with lanes T1, word m, T2 and kernel. T1 takes the mutex with cmpxchg (m = 1). T2's cmpxchg fails, xchg sets m = 2, and T2 calls futex_wait and sleeps in the kernel queue while CPU 1 is free. T1 unlocks with xchg, sees 2 and calls futex_wake; the kernel wakes T2, which retries xchg(&m, 2), gets 0 and enters the critical section.
Atomic instructions on m handle the lock; the kernel is called only to sleep (futex_wait) and to wake (futex_wake), and the woken T2 must try again.

T2 leaves m at 2, because it cannot know whether other threads are still asleep. So its own unlock calls futex_wake although nobody sleeps: 3 system calls in total. Glibc accepts these extra calls to keep the word to one integer.

Why futex_wait checks the value

Between T2's xchg(&m, 2) and its futex_wait, T1 can unlock. If T2 then went to sleep anyway, nobody would ever wake it: a lost wake-up. So futex_wait(&m, 2) checks, inside the kernel and under the queue's lock, that m is still 2. If it is not, the call returns EAGAIN at once and the thread tries again (Unlock races the sleep).

Mutex or spinlock?

SpinlockMutex
Waiting threadspins, keeps its CPU busysleeps, CPU is free
Uncontended costone atomic instructionone atomic instruction
Contended costCPU time while it waitssystem calls and two context switches
Holder preempted or blockedeveryone spinsfine, waiters sleep
Use whenvery short sections, kernel code that can't sleepalmost everything else

In Sleep and wake T2 waits 8 ticks, and 4 of them are free CPU time. But it also pays for a system call to sleep and a context switch to come back. When the critical section is only a few instructions, that costs more than spinning. That is why glibc's PTHREAD_MUTEX_ADAPTIVE_NP and the Linux kernel's own mutex spin for a short while first and sleep only if the holder keeps the lock.

Where you meet it

  • C and C++: pthread_mutex_lock, std::mutex (on Linux both are futex-based).
  • Java: synchronized and ReentrantLock spin briefly, then park the thread, which ends in a futex on Linux.
  • Go: sync.Mutex spins, then parks the goroutine in the runtime instead of the kernel.

What the page leaves out

  • Barging: a woken thread competes with newcomers, so a thread that just arrived can take the mutex first. That is faster but not fair. Fair locks hand the mutex over in queue order.
  • Mutex types: recursive mutexes (the owner may lock again), error-checking mutexes (unlocking someone else's mutex returns EPERM), priority-inheritance mutexes (FUTEX_LOCK_PI) against priority inversion.
  • How the kernel finds the queue: a hash table keyed by the futex's address, so any integer can be a futex and an unused mutex costs no kernel memory.
  • Real timing: a system call and a context switch cost far more than one tick of an atomic instruction.