Explain the futex-style design used by modern mutexes: why an uncontended acquire needs no call into the operating system, and what has to happen once the lock is contended.

## The problem being solved Early kernel-provided mutexes required a system call on every lock and unlock, even when nobody was competing for the lock. Since well-designed programs acquire uncontended locks constantly and contend rarely, that made the *common* path pay the cost of the *rare* one. It also meant every mutex needed a kernel object, so kernel memory grew with the number of locks a process created. The futex design ("fast userspace mutex") inverts this: the lock lives in user memory, and the kernel is consulted only when a thread genuinely has to sleep. ## The user-space fast path The lock is one machine word in the process's own memory. Acquisition is an atomic compare-and-swap: ``` acquire(): if CAS(word, FREE, LOCKED) succeeded: return # done, no kernel release(): store(word, FREE) # done, no kernel ``` On a modern CPU an uncontended CAS on a cache line already in the local cache is a few nanoseconds. A system call is hundreds of nanoseconds to low microseconds once you include the mode transition and the associated cache and pipeline effects — and considerably more with speculative-execution mitigations enabled. So the fast path is two to three orders of magnitude cheaper than the syscall it avoids. Because the kernel has no idea the lock exists until someone blocks on it, a program may hold millions of such locks — one per hash bucket, one per object — at a cost of one word each and zero kernel objects. ## The contended path When the CAS fails, a thread must wait. It calls into the kernel with an operation of the form: > *wait on the queue identified by this memory address, but first verify that the address still contains the value V; if it does not, return immediately.* That conditional check is the crux. Consider the race without it: 1. Thread B fails to acquire; the lock is held by A. 2. **A releases** and, seeing no recorded waiters, issues no wake. 3. B enters the kernel and sleeps — forever, because the wake already happened. The kernel closes this by re-reading the word under its own internal lock and comparing it to the value the caller expected. If the value changed (because A released), the call returns immediately instead of sleeping and the thread retries in user space. This is a compare-and-block primitive, and it is what makes the whole scheme sound. The kernel keys its wait queues by the physical address of the word (or by an equivalent identity for shared mappings), so two processes mapping the same shared memory can synchronise through the same lock without either owning a kernel handle. ## Why three states, not two If the word were only FREE/LOCKED, the releaser could never know whether anyone was waiting, so it would have to issue a wake system call on *every* unlock — reintroducing exactly the cost the design removed. So the canonical encoding is: - **0 — free** - **1 — locked, no waiters known** - **2 — locked, waiters may exist** A thread that is about to block first sets the word to 2, then waits on the expected value 2. Release becomes: ``` release(): old = atomic_swap(word, 0) if old == 2: wake_one_waiter(&word) # syscall only in this branch ``` So the uncontended unlock — the overwhelmingly common case — is a single atomic store with a branch that is not taken. "May exist" is deliberate: the state can be conservatively 2 when the last waiter has already gone, costing at most one spurious wake call, which is a performance blemish rather than a correctness bug. ## How spinning fits in Most real implementations put a short adaptive spin between the failed CAS and the wait call: if the hold time is very short, the lock frees during the spin and the syscall is avoided entirely. So the full contended path is *CAS → brief spin → mark waiters → wait syscall*, and each stage exists to catch a different regime of hold time. The spin also has to be bounded, because parking is the only correct response to a long or blocked holder. ## Consequences worth naming - **Correctness lives in user space.** The lock word is ordinary process memory, so a buggy or malicious thread can corrupt it. There is no kernel-enforced ownership; this is the price of the fast path. - **Wake-ups need care.** Waking all waiters when only one can proceed creates a thundering herd; waking one plus "requeue to another wait queue" operations exist to move waiters between queues efficiently, which is how condition-variable signalling avoids a wake-then-immediately-block storm. - **Robustness on death.** If a thread dies holding the lock, the word simply stays locked. Recovering from that requires an explicit protocol (a registered owner list the kernel can mark as inconsistent), because nothing about the fast path tracks ownership by itself. - **The same machinery generalises.** Semaphores, condition variables, latches and read-write locks in modern runtimes are all built on the same pattern: an atomic word for the fast path, a kernel wait queue keyed by that word's address for the slow one. ## The one-sentence version Put the state where the fast path can reach it cheaply, and pay for the kernel only when a thread actually has to stop running — with an atomic compare inside the blocking call so the release cannot be missed.