The futex(2) man page states the whole premise in one sentence: when a lock is uncontended, its state changes via atomic instructions that "are performed entirely in user mode, and the kernel maintains no information about the lock state." There is no registration step, no handle, no kernel object. A futex is just a 32-bit integer — "a variable of type int," four bytes on both 32- and 64-bit platforms, aligned to sizeof(int) — sitting anywhere in your process's ordinary memory. The kernel only learns it exists in the moment a thread actually has to sleep on it, and forgets it again when the wait queue drains. That is why pthread_mutex_t needs no system call to create, none to destroy, and — in the common case — none to lock or unlock.
The interesting part is what it takes to make that fast path safe. Ulrich Drepper's paper Futexes Are Tricky walks through a mutex built on futexes in three takes, and the first take — the obvious one — shipped a livelock that hid inside NPTL, glibc's thread library, for months.
The contract: wait only if the word still says what you think it says
The kernel interface is one multiplexing syscall. The two operations that matter here:
FUTEX_WAIT(addr, val)— put the calling thread to sleep on the wait queue foraddr, but only if*addrstill equalsval. The load, the comparison, and the enqueue happen atomically under the kernel's internal locks. If the value already changed, the call returns immediately withEWOULDBLOCK. It can also return early on a signal (EINTR) or a timeout (ETIMEDOUT).FUTEX_WAKE(addr, n)— wake up tonthreads from that queue and return how many were actually woken. In practice only two values ofnmake sense: 1 andINT_MAX, because you cannot control which waiters run next. The kernel does not scan the queue for the highest-priority thread; plain futexes are explicitly not realtime-safe.
The atomic value check is the entire trick. It closes the lost-wakeup race: between your user-space load of the lock word and your FUTEX_WAIT, another thread may have unlocked and called FUTEX_WAKE into an empty queue. The kernel-side comparison guarantees you never sleep on a stale view of the word.
The kernel keys wait queues by the physical address behind the futex word, so two processes that mmap the same shared memory get the same queue — inter-process mutexes fall out for free, with no names and no pointers inside the object.
Take 1: the obvious mutex, and the livelock it hides
Drepper's first attempt uses an atomic increment. Zero means unlocked; anything else means locked:
void lock () {
int c;
while ((c = atomic_inc (val)) != 0)
futex_wait (&val, c + 1);
}
void unlock () {
val = 0; futex_wake (&val, 1);
}This looks reasonable and is broken twice over. The subtle bug: every contending thread increments the word before sleeping. Thread 1 increments and calls FUTEX_WAIT; meanwhile thread 2 increments, so thread 1's expected value is stale and its wait fails with EWOULDBLOCK; it loops, increments again, and now thread 2's wait fails. Two threads can bounce off each other indefinitely — each one's attempt to sleep invalidates the other's. Drepper notes this bug "was present in some form for many months in the NPTL implementation," showing up as "mysterious slowdowns and occasional bursts of CPU usage," and that fixing it sped up one real-world application on a four-processor machine by eight to ten times.
The second bug is plainer: the counter wraps. After 2^32 failed lock attempts the word is zero again and the mutex is "magically" free. Signals interrupt FUTEX_WAIT, each retry increments, and unbounded increments are exactly what you get.
There's a performance problem too: unlock always makes a syscall, even when nobody is waiting — which, in real programs, is most of the time.
Take 2: three states, not two
The fix is to make the lock word say whether waiters might exist:
| Value | Meaning |
|---|---|
| 0 | unlocked |
| 1 | locked, no waiters |
| 2 | locked, one or more waiters |
Lock tries a single cmpxchg from 0 to 1. If that succeeds — the uncontended case — the cost is one atomic instruction, zero syscalls. Unlock atomically decrements; if the old value was 1, nobody is waiting, so it skips futex_wake entirely: again one atomic op, zero syscalls. Only when the word reads 2 does unlock reset it to 0 and pay for a syscall to wake exactly one thread.
A contending locker sets the word to 2 before sleeping, and FUTEX_WAIT always passes 2 as the expected value. The delicate line is what a woken thread does: it must re-acquire by setting the word from 0 to 2, not to 1 — because, as Drepper puts it, at that point "we cannot say with 100% certainty that there is not already a waiter," and guessing wrong the other way means a waiter nobody ever wakes. The price of erring safe is an occasional unnecessary futex_wake. His third take then shaves the slow path on IA-32/AMD64 by using an unconditional atomic xchg to write the 2, instead of looping on cmpxchg.
Why wake exactly one thread instead of all of them? Drepper's example: a mutex with 100 waiters on a multiprocessor. Wake them all and one wins; the other 99 touched the lock word, dragged its cache line across their CPUs, and went straight back to sleep. The wake-one discipline is a significant optimization, not a nicety.
Broadcast: don't wake waiters, move them
Condition variables make the thundering herd unavoidable-looking. POSIX requires every thread returning from pthread_cond_wait to re-acquire the associated mutex — so a naive pthread_cond_broadcast wakes N threads, one gets the mutex, and N−1 immediately block again, after a round of cache-line ping-pong on the mutex word across every processor involved.
The futex interface grew a dedicated operation for this: FUTEX_CMP_REQUEUE. It wakes a capped number of threads from one futex's wait queue (one, for broadcast) and moves the rest onto a different futex's queue — the mutex's — without waking them. A broadcast becomes roughly:
futex_requeue (cond_futex, 1, MAX_INT,
mutex_futex, cond_val);Each subsequent pthread_mutex_unlock then wakes exactly one requeued thread, which finds the mutex free and proceeds. In Drepper's summary: "one by one wakeup, no cache line ping-pong, and no more going back to sleep immediately for all but one thread." He adds that the win becomes measurable once threads run on more than about four processors — an experience value for IA-32.
The CMP in the name is load-bearing. The operation only proceeds if the condvar futex still holds the expected value (cond_val); otherwise it returns EAGAIN and the caller re-examines the world. The original FUTEX_REQUEUE skipped that check, and Drepper is blunt about the result: it "proved to be broken and unusable" — concurrent changes to the futexes went undetected and could deadlock — and it survives only for compatibility. One more API wart: the requeue cap is smuggled through the timeout parameter, reinterpreted as an integer.
The idea proved durable enough that it was re-derived for priority-inheritance locks: the kernel's futex-requeue-PI documentation describes FUTEX_CMP_REQUEUE_PI, which glibc's broadcast calls with nr_requeue = INT_MAX and signal calls with 0 — because without it, PI-aware condvars "must resort to waking all the tasks" and the priority chain breaks.
What to take away
- An uncontended pthread mutex is one atomic instruction to lock and one to unlock. If you're profiling and see
futexcalls dominating, you're measuring contention, not locking overhead. - The lock word needs a third state precisely so that unlock can know whether a syscall is required. Two-state designs either always pay the wake or lose wakeups.
FUTEX_WAIT's compare-under-lock is the primitive that makes user-space fast paths sound. Every correct futex protocol is organized around "what value do I expect the word to hold, and what does it mean if I'm wrong?"- When many threads must leave one queue for another, moving them beats waking them. Requeue exists because wakeups you immediately regret are the most expensive kind.