How Futexes Work: Userspace Fast Path, Wait Queues, and Why Mutexes Avoid Syscalls

A mutex that takes a system call on every lock and unlock would dominate a hot critical section. The uncontended case is a few atomic instructions. The contended case needs a place to sleep and a way to be woken. Linux splits those two jobs. The word in user memory is the lock. The kernel only appears when a thread must wait or must wake someone who is already waiting.

That split is the futex: a 32-bit aligned uint32_t in user space plus a system call that waits or wakes on the address of that integer. glibc pthread mutexes, Go runtime locks, parking_lot, and most language runtimes on Linux are built on it. This article is about that contract: the userspace fast path, the compare-and-sleep race the kernel closes, wait queues keyed by address, requeue, private versus shared words, and why a mutex is not a syscall.

It is not a second tour of the syscall ABI, of CFS runqueues, or of RCU grace periods. Those describe how a trap is taken, how a sleeping task is placed, and how kernel readers skip locks. A futex is the userspace protocol that decides whether to take the trap. Related reading: How System Calls Work, How Linux CFS Works, How RCU Works, How CPU Caches Work.

The contract

A futex word is an aligned uint32_t that user code owns. The kernel does not allocate it, initialize it, or interpret a single canonical encoding for every caller. User code chooses a protocol. The kernel offers operations on the address:

• FUTEX_WAIT — if the word still equals an expected value, sleep on that address.
• FUTEX_WAKE — wake up to N threads sleeping on that address.
• Variants for bitmasks, requeue onto another address, priority inheritance, and process-private hashes.

The kernel never "holds" the mutex. It does not know which bit means locked unless the caller is using the PI protocol, which encodes the owner thread ID in the word. For the ordinary mutex and condition-variable case, the kernel only compares a value and parks or unparks tasks.

Why the fast path never enters the kernel

Take a simple exclusive lock. User space stores 0 for free and 1 for held with no waiters. A locker does:

if (atomic_cmpxchg(&word, 0, 1) == 0)
    return; /* acquired, no syscall */

An unlocker does:

if (atomic_xchg(&word, 0) == 1)
    return; /* no waiters were advertised, no syscall */

Those two paths are loads, stores, and compare-and-swap on a cache line the locker and unlocker already share. They use the same MESI machinery described in the CPU-cache article. They do not execute syscall.

The kernel becomes involved only when the cmpxchg fails because the word is not 0, or when unlock observes a state that means someone may be sleeping. That is the contended path. Production mutexes add a waiter bit so unlock can skip the wake syscall when the bit is clear.

The lost-wake-up race

Sleeping cannot be "wait on this address." Between the load that decided the lock was busy and the moment the thread is on a kernel wait list, the owner can unlock and issue FUTEX_WAKE. If the waiter is not on the list yet, the wake is a no-op. The waiter then sleeps forever.

FUTEX_WAIT(uaddr, expected) closes that window inside the kernel:

1. The kernel reads the user word atomically.
2. If the value is not expected, it returns immediately (EAGAIN / -EWOULDBLOCK). The lock changed; user space retries.
3. If the value still matches, the calling task is queued on a wait list hashed from the address and scheduled out.

Unlock stores the new value first, then calls FUTEX_WAKE. If the store happens before the kernel's compare, the waiter never sleeps. If the store happens after the waiter is queued, the wake finds the waiter. Either way the protocol makes progress. The compare is the whole reason the syscall takes the expected value as an argument.

Where the wait list lives

The kernel does not keep a wait queue inside the user page. It hashes the futex address (and, for shared futexes, the backing page) into a bucket in a global futex hash table. Each bucket has a lock and a list of waiters.

That design has consequences:

• Two unrelated mutexes can share a bucket. Contention on the bucket lock is rare at ordinary thread counts and shows up under microbenchmarks with tens of thousands of distinct words.
• The user page can be unmapped or the process can exit while waiters exist. The kernel must handle faults on the compare and clean robust lists on thread exit.
• FUTEX_PRIVATE_FLAG tells the kernel the word is visible only inside this process. The hash can use the virtual address alone and skip inode/offset identity. glibc sets this flag for normal process-private pthread objects.

A shared futex lives in MAP_SHARED memory. The hash key is the page's identity plus the offset so two processes mapping the same page at different virtual addresses still collide on one wait list. That is how a mutex in a POSIX shared-memory segment works across processes.

A compact mutex protocol

A widely used three-state encoding (the shape under many pthread implementations) is:

• 0 — unlocked
• 1 — locked, no waiters advertised
• 2 — locked, waiters may exist

Lock:

1. Try 0 → 1 with compare-and-swap. Success is the fast path.
2. On failure, swap in 2 (locked + waiters) and, if the previous value was not 0, call FUTEX_WAIT(&word, 2).
3. After wake or spurious return, loop from the top.

Unlock:

1. Atomic swap 0 into the word.
2. If the previous value was 2, call FUTEX_WAKE(&word, 1).

The waiter bit is conservative. A locker that fails the 0 → 1 attempt sets 2 even if no one is in the kernel yet. Unlock then pays one wake syscall that may find an empty list. That is cheaper than missing a real waiter. Some implementations spin a short time in user space before waiting, which absorbs the window where the owner is about to drop the lock.

Condition variables and requeue

A condition variable is not a second mutex. Waiters sleep on the condvar's own futex word. They must leave the associated mutex before sleeping and re-acquire it after wake. A naive wake of N waiters sends all of them at the mutex. All but one will fail the lock and sleep again, this time on the mutex word. That is a thundering herd plus two syscalls per waiter.

FUTEX_CMP_REQUEUE moves waiters from one address to another without waking them as runnable threads. pthread_cond_broadcast can wake one locker and requeue the rest onto the mutex futex. They will be woken one at a time as the mutex is released. FUTEX_CMP_REQUEUE also compares the source word so a concurrent change can abort the move, the same class of race FUTEX_WAIT closes.

FUTEX_WAKE_OP combines a wake on one address with an atomic operation on a second word. It exists so some lock-plus-signal sequences can finish in one trap.

Priority inheritance

A low-priority thread that holds a lock a high-priority thread needs creates priority inversion. Ordinary futex wait does not change the owner's scheduling weight. PI futexes do.

The PI protocol encodes the owner:

• 0 — free
• owner TID in the low bits when held
• FUTEX_WAITERS (the high bit 0x80000000) when waiters exist
• FUTEX_OWNER_DIED if the owner exited without unlock

FUTEX_LOCK_PI and FUTEX_UNLOCK_PI let the kernel boost the owner's priority to the highest waiter and drop the boost on unlock. Real-time threads and some glibc mutex types (PTHREAD_PRIO_INHERIT) use this path. It is slower than the three-state mutex because the kernel must know the owner. It is the path you want when a lock sits between tasks of different priority.

Robust lists

If a thread dies while holding a mutex in shared memory, survivors must not wait forever. User space registers a robust list with the kernel via set_robust_list. On thread exit the kernel walks that list, sets FUTEX_OWNER_DIED on words the thread still owned, and wakes one waiter. The next locker sees the died bit and decides whether to treat the lock as inconsistent. This is a process-lifetime protocol, not a substitute for crash-safe shared data.

Timeouts, clocks, and bitsets

FUTEX_WAIT accepts an optional timeout. Historically the clock was CLOCK_MONOTONIC relative. FUTEX_WAIT_BITSET plus FUTEX_CLOCK_REALTIME supports absolute realtime deadlines, which POSIX timed mutexes and condvars need for wall-clock timeouts.

Bitsets attach a 32-bit mask to each waiter. Wake with a mask; only waiters whose mask overlaps are resumed. The feature multiplexes several sleep channels onto one word. Walking every waiter to test the mask is more expensive than giving each channel its own futex, so the usual advice is separate words unless the protocol already shares one integer.

What a futex is not

A futex is not a mutex. It is the wait/wake primitive a mutex is built from. Atomic operations on the word are the lock. The syscall is the parking lot.

A futex is not a scheduler decision. Once FUTEX_WAIT queues the task, CFS (or whatever policy the task runs under) treats it as blocked. vruntime stops accumulating. Wake makes the task runnable again. Placement after wake is the scheduler's problem, described in the CFS article.

A futex is not RCU. RCU delays reclamation until readers finish. A futex parks a thread that cannot proceed until another thread changes a word and wakes it. The two solve opposite shapes of concurrency.

A futex is not epoll. epoll reports that a file descriptor is ready. A futex reports that a user integer changed in a way the waiter asked to observe. You can wait on a futex from one thread while another thread uses epoll; they do not substitute.

Where this shows up when something breaks

A hang in pthread_mutex_lock that never returns is often a missing unlock, a wrong shared/private flag, or a waiter that slept on a value the unlocker never produced. strace -e futex shows only the contended path. An uncontended lock produces no trace line. That is expected, not evidence the mutex is broken.

Spurious wakes are allowed. FUTEX_WAIT can return 0 because of a matching wake, a signal, or a hash-bucket collision that was woken for another word and then filtered. User code must re-read the word and loop. A protocol that treats any return as "the predicate is true" is wrong.

False sharing of adjacent mutexes is a cache problem, not a futex-hash problem. Two 32-bit words on one 64-byte line bounce the line between cores on every uncontended lock. Padding lock objects to a cache line is the usual fix; see the CPU-cache article.

Priority inversion on a non-PI mutex looks like a high-priority thread spinning or sleeping while a low-priority owner runs behind a medium-priority CPU hog. Switching that mutex to a PI type, or boosting the owner some other way, is the repair. Adding more spinning in user space does not fix inversion.

Takeaways

A futex is an address plus a kernel parking lot. User space owns the word and the protocol. The kernel compares, queues, and wakes.

Uncontended lock and unlock stay in user space. That is why a pthread mutex around a few arithmetic operations is affordable, and why tracing syscalls underestimates lock traffic.

Wait must compare the current value to the value the waiter observed. Without that compare, unlock can happen in the gap and the waiter never hears about it.

Requeue exists so a broadcast does not stampede the mutex. PI exists so the owner of a needed lock can run. Robust lists exist so a dead owner does not freeze shared memory. None of those features is the default fast path.

Build locks from atomics first. Call the kernel only when a thread has nothing useful to do until another thread writes the word.