Futex Wait and Wake: How a Lock Sleeps Without a Syscall on the Fast Path

An uncontended mutex must cost almost nothing. A contended one must not burn a processor. Those two requirements conflict, because the cheapest uncontended implementation is a single atomic instruction in user space, and the only way to stop running is to ask the kernel. The futex interface resolves the conflict by splitting the operation: user space does the atomic work and only enters the kernel when a thread actually has to wait, and the kernel stores nothing about the lock until that moment.

A lock with no kernel object

The design starts from an observation about the shape of a lock’s state. The state is one aligned 32-bit word in the process’s own memory. Zero means free, one means held with no waiters, and a larger value or a separate bit means held with waiters. All transitions among those states are done with compare-and-swap or exchange in user space. The kernel is not consulted, holds no lock record, and allocates nothing for a lock that is never contended.

The kernel enters only when a thread fails to acquire and decides to block. At that point it calls futex(FUTEX_WAIT, addr, expected), passing the address of the word and the value it expects to find there. The kernel compares the current value at addr with expected. If they differ, the call returns EAGAIN immediately, because the state changed between the failed acquisition and the syscall and the thread should retry the user-space path rather than sleep. If they match, the kernel enqueues the thread on a wait queue keyed by the address and puts it to sleep.

The comparison is the fix for the lost wakeup at the kernel boundary. The unlock path increments the word and then calls FUTEX_WAKE. If the wake happens before the waiter’s FUTEX_WAIT, the waiter’s expected value no longer matches and it does not sleep. If the wake happens after, the waiter is already queued and the wake finds it. There is no window in between, because the kernel performs the comparison and the enqueue under the same lock that the wake path takes to scan the queue.

#include <linux/futex.h>
#include <sys/syscall.h>
#include <unistd.h>
#include <stdatomic.h>

/* Mutex states: 0 free, 1 held, 2 held with possible waiters. */
static atomic_int mtx;

static int futex_wait(atomic_int *p, int expected)
{
    return syscall(SYS_futex, (int *)p, FUTEX_WAIT, expected,
                   NULL, NULL, 0);
}

static void lock(void)
{
    int c = 0;
    /* Uncontended: one compare-and-swap, no syscall. */
    if (atomic_compare_exchange_strong_explicit(&mtx, &c, 1,
            memory_order_acquire, memory_order_relaxed))
        return;

    /* Contended: mark the word as having waiters, then sleep on it. */
    if (c != 2)
        c = atomic_exchange_explicit(&mtx, 2, memory_order_acquire);
    while (c != 0) {
        futex_wait(&mtx, 2);    /* EAGAIN if the word is no longer 2 */
        c = atomic_exchange_explicit(&mtx, 2, memory_order_acquire);
    }
}

static void unlock(void)
{
    /* 1 means no waiters, so 1 becomes 0 with no syscall at all. */
    if (atomic_fetch_sub_explicit(&mtx, 1, memory_order_release) != 1) {
        atomic_store_explicit(&mtx, 0, memory_order_release);
        syscall(SYS_futex, (int *)&mtx, FUTEX_WAKE, 1, NULL, NULL, 0);
    }
}

Two properties of this sketch are worth naming. The slow path sets the word to 2 before sleeping, so that an unlocker which sees 2 knows it must issue a wake; a lock that never sets the waiter state would leave sleeping threads with nobody to wake them. And the acquire on the successful compare-and-swap is what orders the critical section’s loads and stores, as discussed in acquire and release ordering.

Where the wait queues live

The kernel keeps a hash table of wait queues. The key is derived from the address of the futex word, and in older implementations from the physical page backing it and the offset within the page, so that threads in different address spaces mapping the same page share a queue. The table is a fixed size chosen at boot, and collisions are resolved by chaining, which means two unrelated futex words can share a queue. Sharing a queue is harmless for correctness because every waiter records the address it is waiting on and the wake path filters by address; it costs only the scan of a longer list.

Because the table is keyed by the address rather than by any kernel-allocated handle, a futex has no lifetime beyond the memory it sits in. The kernel drops its reference to the page once the key has been computed, so nothing needs to be freed when the memory goes away, and nothing notifies a waiting thread when it does: a task already asleep on a word is released only by a wake, a signal, or its own timeout, which is why unmapping a futex page is a programming error rather than a way to clean up waiters. That same absence of a handle is the property that lets futex-based locks be embedded in ordinary structures, copied by memcpy, and placed in shared memory without registration. It is also the property that makes the interface dangerous: the address must be aligned to four bytes, and a futex word that moves, as when a structure containing it is relocated, silently breaks every waiter.

Requeue: moving waiters instead of waking them

A condition variable built on futexes has the same barging problem as any other, but it has an extra cost. A signaller that wakes one waiter on the condition variable’s own futex word forces that waiter to then contend for the associated mutex. Under broadcast, every waiter wakes, enters the kernel’s run queue, fails to take the mutex, and sleeps again on the mutex’s word. That is two syscalls per waiter to accomplish nothing.

FUTEX_REQUEUE exists to collapse the pair. It takes two futex addresses and two counts: at most the first count of waiters are woken on the spot, and at most the second count are moved from the first queue to the second without being woken. A condition variable signal can therefore move one waiter from the condition variable’s word to the mutex’s word, where it will be woken by the unlock that the signaller is about to perform. The compare-and-requeue variant additionally checks the value at the first address before acting, which closes the race between the signaller’s predicate check and the kernel’s queue scan. The saving is one kernel entry per waiter and, more importantly, one wakeup per waiter: the threads moved do not run until the mutex is actually released.

The same mechanism is why glibc keeps a sequence counter in the condition variable rather than waiting directly on the predicate, and why the ordering of the operations inside the signaller matters. Requeue is a kernel operation on two user addresses, so both must be valid futex words at the time of the call.

Priority inheritance inside the kernel

Ordinary futex wait queues carry no notion of scheduling priority. Waiting tasks are recorded in a kernel data structure keyed by the futex address, and a wake scans it for tasks waiting on that word; the order in which they are woken is an implementation detail rather than a documented guarantee, and a wake that targets one task may or may not pick the one that arrived first. A high-priority thread queued behind a low-priority one therefore inherits the inversion. The kernel offers a separate family of operations, collectively the PI futexes, in which the kernel itself owns the lock state and tracks ownership: FUTEX_LOCK_PI and FUTEX_UNLOCK_PI, plus FUTEX_TRYLOCK_PI and the robust variants that survive a thread dying while holding the lock.

In that mode the futex word encodes the owner’s thread ID, and the kernel maintains a list of waiters and a chain of ownership. When a high-priority thread blocks on a lock held by a lower-priority thread, the kernel temporarily raises the holder’s priority to the waiter’s, and propagates the boost transitively if the holder is itself blocked on another lock. The cost is that every lock and unlock is a syscall, which is why PI futexes are used only where the scheduling hazard justifies it: real-time code paths, and the internal locks of the pthread library that guard mutex state.

The mechanism is developed in priority inversion and inheritance. The relevant point here is that inheritance cannot be implemented in user space alone, because raising another thread’s priority and following a chain of blocked owners requires the scheduler’s data structures.

Robustness, timeouts, and the failure cases

The interface has a set of behaviours that a user-space lock must handle explicitly.

futex_wait may return EINTR when a signal arrives, either before it sleeps or when it is woken early; the caller must then re-check the word and retry rather than treat the interruption as an acquisition. A timeout returns ETIMEDOUT. An invalid address returns EFAULT, and an unaligned address returns EINVAL; a word that is no longer equal to the expected value returns EAGAIN rather than sleeping.

The hard case is a thread that dies while holding a futex-based lock. Nothing in the ordinary interface records ownership, so the lock stays held forever. The robust mutex protocol addresses this with a value stored in the futex word that marks the owner, plus a consistency check performed by the kernel when the owner exits. The next thread to acquire a mutex left behind by a dead owner receives EOWNERDEAD; it must repair the protected state and then mark the mutex consistent before unlocking, or every subsequent waiter will receive ENOTRECOVERABLE instead. The protocol works only if the protected data can be brought to a consistent state by the recovering thread, which is a property of the data structure, not of the lock.

Another boundary is process-shared use. A futex word in shared memory works across processes, since the kernel keys the queue by the mapped page. A futex word in private anonymous memory does not, because each process maps a different physical page. The distinction shows up as a lock that works between threads of one process and hangs between processes after a fork.

Finally, the fast path’s cost deserves a number. An uncontended compare-and-swap is a single instruction plus the coherence traffic for the cache line, on the order of tens of cycles when the line is already owned by the core. A FUTEX_WAIT that actually sleeps costs a syscall entry plus two context switches, which is thousands of cycles. The interface exists to keep the common case in the first regime and to pay the second only when a thread genuinely has to stop.

For the condition variable interface that sits on top of requeue, see condition variables and lost wakeups. For the user-space lock that spins before it sleeps, see spinlock contention and queued locks.