Run strace on a busy multithreaded program and you'll notice something odd: pthread_mutex_lock almost never appears. Thousands of lock acquisitions per second, and the kernel hears about almost none of them. That's not the tracer missing events — it's the design. Linux mutexes are built on the futex ("fast userspace mutex"), a kernel primitive whose entire purpose is to stay out of the way until threads actually collide.
The mechanism is small enough to describe in a page. Using it correctly is another matter: Ulrich Drepper's classic paper on the subject is titled Futexes Are Tricky, and it opens by noting that the reference userspace code distributed by one of the futex's own inventors "is actually incorrect." A subtle version of the same class of bug lived in glibc's NPTL threading library "for many months," showing up only as mysterious slowdowns and bursts of CPU usage.
The interface: compare-and-block
Futexes shipped in Linux 2.5.7 in 2002, from Hubertus Franke, Rusty Russell, and Matthew Kirkwood, introduced in their paper "Fuss, Futexes and Furwocks: Fast User Level Locking in Linux." A futex is just an aligned 32-bit integer in ordinary memory — your memory, in your process. The kernel attaches no meaning to its value and keeps no state for it until someone blocks. The futex() syscall multiplexes several operations, but two carry the design:
FUTEX_WAIT(addr, val)— put me to sleep on this address, but only if the word ataddrstill equalsval. If it doesn't, return immediately withEAGAIN(a.k.a.EWOULDBLOCK).FUTEX_WAKE(addr, n)— wake up tonthreads sleeping on this address (in practice,nis 1 orINT_MAX).
The load, the comparison, and the enqueue-to-sleep in FUTEX_WAIT happen atomically inside the kernel, totally ordered against other futex operations on the same word. That atomic compare-and-block is the whole trick. It closes the classic lost-wakeup race: without it, a thread could observe "lock is held," get preempted, miss the holder's wakeup, and then sleep forever waiting for a signal that already happened. With it, if the value changed between your userspace check and your syscall, the kernel refuses to put you to sleep and you retry.
Internally the kernel hashes the futex's address into a bucket of wait queues; a blocked thread is queued there and woken when someone calls FUTEX_WAKE on the same address. Because keying is ultimately by physical page, two processes mapping the same shared memory wait on the same futex — which is how process-shared POSIX mutexes work. When the futex is private to one process, FUTEX_PRIVATE_FLAG (Linux 2.6.22+) skips that cross-process resolution work.
The mutex that looks right and isn't
Here's the obvious mutex, essentially Drepper's "take 1": treat 0 as unlocked, anything else as locked, and count waiters by incrementing.
void lock(int *f) {
int c;
while ((c = atomic_inc(f)) != 0) /* returns old value */
futex_wait(f, c + 1);
}
void unlock(int *f) {
*f = 0;
futex_wake(f, 1);
}It satisfies mutual exclusion, and it's broken three ways.
It can livelock. Two threads on different CPUs both call lock on a held mutex. Thread 1 increments and calls FUTEX_WAIT — but thread 2's increment has already changed the value, so the kernel bounces thread 1 back with EAGAIN. Thread 1 loops and increments again, which now invalidates thread 2's FUTEX_WAIT. Each thread's retry sabotages the other's attempt to sleep, and every retry is an atomic operation on a contended cache line. This is the bug that hid in NPTL; Drepper reports one real application on a four-processor machine that got eight to ten times faster when it was fixed, because the cache-line ping-pong of the futile retry storm was that expensive.
It can overflow. Every failed sleep increments the word, and FUTEX_WAIT can also return early on any signal. After 2³² increments — reachable in theory by a single unlucky thread — the counter wraps to 0 and the mutex spontaneously reports "unlocked."
It always syscalls on unlock. Even with zero waiters, ever, unlock pays for a futex_wake that wakes nobody. The state is too coarse to know the queue is empty.
Three values is exactly enough
The fix, Drepper's "take 2," is the algorithm to remember. The futex word gets exactly three states:
| Value | Meaning |
|---|---|
| 0 | unlocked |
| 1 | locked, no waiters |
| 2 | locked, one or more waiters |
void lock(int *f) {
int c;
if ((c = cmpxchg(f, 0, 1)) != 0) /* fast path: one atomic op */
do {
if (c == 2 || cmpxchg(f, 1, 2) != 0)
futex_wait(f, 2); /* sleep only while word == 2 */
} while ((c = cmpxchg(f, 0, 2)) != 0);
}
void unlock(int *f) {
if (atomic_dec(f) != 1) { /* old value 1 → nobody waiting */
*f = 0;
futex_wake(f, 1);
}
}Every problem from take 1 dies here:
- No syscall when uncontended. Lock is one
cmpxchg; unlock is oneatomic_decthat sees old value 1 and skips the kernel entirely. Zero syscalls in the common case — that's the fast pathstracenever shows you. - No livelock. A locked mutex's word changes at most once more — from 1 to 2, by the first waiter. Later arrivals see 2 and don't write, so they can't invalidate each other's
FUTEX_WAIT(f, 2)calls the way the unbounded counter did. - No overflow. The value never leaves {0, 1, 2}.
The subtle line is the loop condition: a woken thread acquires with cmpxchg(f, 0, 2) — it takes the lock in the waiters state, not state 1. Why? Because, as Drepper puts it, "we do not know any better." The woken thread can't prove no one else is still queued, and guessing wrong the other way eventually deadlocks: an unlock that sees state 1 would skip the wake, stranding a sleeper forever. The cost of pessimism is merely one possibly-spurious futex_wake. When wrong-but-slow competes with fast-but-deadlocked, you take slow. (On x86, "take 3" swaps the retry cmpxchgs for plain xchg to shave contended-path atomics; the shape is identical.)
The rest of the API exists for the herds
Once you see locking as "keep the kernel out of the happy path," the exotic futex operations make sense as patches for specific stampedes:
FUTEX_CMP_REQUEUEexists because ofpthread_cond_broadcast. Waking all waiters of a condition variable is pointless — each must then acquire the same mutex, so all but one immediately go back to sleep, after a round of cache-line ping-pong across every CPU involved. Requeue wakes one thread and moves the rest onto the mutex's wait queue, so they wake one at a time as the mutex is handed along. (The originalFUTEX_REQUEUElacked the value check and "proved to be broken and unusable" — the compare-and-act discipline applies to requeueing too.)FUTEX_LOCK_PIand friends implement priority inheritance for realtime code, where a low-priority lock holder must be temporarily boosted so it can't be preempted while a high-priority thread waits. These impose a fixed protocol on the word — 0 when free, the owner's TID when held, plus aFUTEX_WAITERSbit — because the kernel now needs to know who owns the lock, not just that someone does.
What to take away
You almost certainly shouldn't hand-roll futex code — that's the paper's actual thesis, demonstrated by its own bug reports. But the three-state design explains behavior you can observe today: why uncontended pthread_mutex_lock costs nanoseconds and contended locks cost microseconds, why lock convoys show up as syscall storms in strace, and why "just wake everyone up" is the most expensive sentence in concurrent programming. The kernel only hears about the fights — good lock design is arranging for as few fights as possible.