futex: Waiting and Waking for User-Space Locks

futex is a low-level waiting and waking mechanism provided by Linux. Common mutexes keep the uncontended path in user space, entering the kernel only when blocking or waking is required. It is not a complete lock, nor is it the sole implementation path for all languages, platforms, or synchronization primitives.

When designing a synchronization protocol, you must answer separately: who owns the resource, how is data published, who needs to sleep, and who should be woken up after a state change. futex primarily addresses the latter two items and their connection with shared state.

Why You Cannot Simply Check Before Sleeping

Suppose W checks ready as 0 and is about to sleep; P subsequently changes ready to 1 and wakes, but W has not yet entered the wait queue. If W then unconditionally sleeps, and no further notification occurs, it will miss the change that has already happened.

FUTEX_WAIT reads the futex word, compares it with expected, and enters a wait, forming a "compare-and-block" operation that provides atomic guarantees against concurrent operations. If the value is already unequal, it returns EAGAIN and does not sleep. FUTEX_WAIT

This requires the publisher to modify the state first, then wake up according to the protocol. Calling WAKE alone without leaving an observable state cannot reliably notify a thread that has not yet started waiting. If values repeatedly change back to the same value, generations must be distinguished using algebra, sequence numbers, or more complete protocols; one cannot assume that a single comparison eliminates all ABA problems.

Two Basic Operations

The traditional futex word is a 32-bit value aligned to 4 bytes, even on 64-bit platforms. Ordinary WAIT does not modify the lock state for the user, WAKE does not deliver lock ownership, and there is no universal FIFO fairness guarantee. futex(2)

WAIT returning 0 only indicates that this wait was woken up; it does not allow direct entry into the critical section. EAGAIN indicates that the state changed during comparison, EINTR indicates interruption by a signal, and a timeout does not necessarily mean the business condition is false; all these paths require handling by the synchronization protocol.

The timeout for FUTEX_WAIT is relative time, while other operations may use absolute deadlines. If retrying a relative wait always resets the full original duration, the total timeout will unexpectedly extend; instead, calculate the remaining amount based on the same deadline, or use an appropriate absolute time interface.

How can WAIT avoid sleeping after a missed wake?

Publish then WAKE: zero threads may wake, but a later WAIT sees word=1 and returns EAGAIN. WAIT first, then publish and WAKE, removes the waiter. WAKE without publishing can return the waiter while word stays zero: waking and satisfying the condition differ.

A Three-State Ordinary Mutex Model

The following is pseudocode to explain the algorithm, not the internal layout of pthread_mutex_t or a drop-in replacement for libc. State 0 indicates idle, 1 indicates locked with no waiter flag, and 2 indicates locked with potential waiters.

lock:
    If CAS_acquire(state, 0, 1) succeeds: return
    Loop:
        old = exchange_acquire(state, 2)
        If old == 0: return
        WAIT(state, expected=2)
        Handle errors based on return value, then re-contend

unlock:
    old = exchange_release(state, 0)
    If old == 2: WAKE(state, 1)

Marking the state as 2 informs the releaser that a wake-up might be needed, not that it precisely counts the number of waiters. A woken thread that successfully changes the state from 0 to 2 retains the flag, allowing subsequent unlocks to continue pushing other waiters. Ordinary new threads may steal the lock before the woken thread, so this model does not guarantee fairness.

If the release happens before WAIT, the mismatch prevents missed sleeps; if the wait enters the queue first, the subsequent WAKE wakes it up. The algorithm also needs to handle address lifetime, cancellation, timeouts, abnormal exits, and edge-case errors; this is why applications typically use mature pthreads or language standard library locks.

Woken threads may still lose to newly arrived threads

The releaser first writes state to 0, then wakes W; while W is still waiting for scheduling, a new thread N successfully CAS(0, 1). When W runs and sees state=1, it must re-contend and cannot enter the critical section directly just because WAIT returned 0.

The value of state 2 lies in preserving the information that "subsequent releases may need notification." It is not proof that W owns the lock, nor is it the current number of waiters. This scheduling explains why ordinary futex locks may have good throughput but cannot directly promise waiting fairness or worst-case waiting time.

WAIT does not sleep when comparison mismatches

The following only verifies the comparison and return of the single-threaded futex interface, not implementing a concurrent lock. The word is already 1, yet it requests waiting for value 0; even if the timeout pointer is NULL, it should immediately return EAGAIN.

#define _GNU_SOURCE
#include <errno.h>
#include <linux/futex.h>
#include <stdint.h>
#include <stdio.h>
#include <sys/syscall.h>
#include <unistd.h>
int main(void) {
    _Alignas(4) uint32_t word = 1;
    errno = 0;
    long result = syscall(SYS_futex, &word, FUTEX_WAIT_PRIVATE,
                          0, NULL, NULL, 0);
    int saved = errno;
    printf("mismatch=%d\n", result == -1 && saved == EAGAIN);
    return !(result == -1 && saved == EAGAIN);
}

Save as futex-mismatch.c, compile and run expecting mismatch=1. This example uses libc syscall, so it sees -1 and errno; it does not concurrently modify the ordinary uint32_t. When extending it to a multi-threaded protocol, you must re-satisfy the atomic object and memory ordering constraints below. WAIT comparison semantics

Memory Ordering for Atomic Variables Cannot Be Omitted

Data protected by locks usually establishes a synchronization relationship between the release in unlock and the acquire in successful lock. The queue atomicity of futex cannot replace the data publication protocol of the language memory model, nor can it automatically turn concurrent reads and writes of ordinary shared integers into legal atomic operations.

volatile only affects specific compiler access semantics and cannot replace cross-thread atomicity and acquire/release. If directly implementing a futex wrapper, you must also confirm the size, alignment, lock-free support of the atomic object, and compatibility of the target ABI with the kernel interface.

The PRIVATE flag indicates that the waiting parties use the object in the same address space, allowing kernel lookup optimization. Inter-process shared objects must use operations suitable for shared mappings; PRIVATE cannot be treated as an unconditionally faster option. Before destroying, unmapping, or reusing a futex address, you must also ensure that no old operations still reference it.

PI and Robust Solve Different Problems

Priority Inheritance (PI) addresses the situation where a low-priority lock holder is constantly preempted by a medium-priority task, causing a high-priority waiter to be unable to proceed. The kernel can elevate the effective priority of the lock holder along the wait chain, helping it complete the critical section. PI requires specific owner encoding and operation protocols; it cannot be casually implemented using ordinary WAIT/WAKE.

The pthread interface selects PTHREAD_PRIO_INHERIT via mutex attributes. It does not solve deadlocks, does not shorten the critical section itself, and does not guarantee meeting deadlines under arbitrary scheduling conditions.

Robust mutexes, on the other hand, handle the death of the lock-holding thread: the next pthread_mutex_lock may return EOWNERDEAD, at which point the caller already holds the lock, but the protected data may be inconsistent. The application should fix the data and call pthread_mutex_consistent, then unlock. If unlocked without restoring consistency, subsequent operations may receive ENOTRECOVERABLE.

You cannot directly treat EOWNERDEAD as "lock acquisition failed, did not get the lock," nor can you uniformly mark everything as consistent without checking the data. The kernel provides the abnormal owner state and does not automatically roll back business modifications. Robust mutex

Complete Recovery Example: Recovering Uncommitted Updates with a Committed Copy

The following creates only one worker thread within the process. The normal invariant is working == committed; the worker thread holds the lock, changes working to 99, and then exits directly, simulating an uncommitted update. The recovery party chooses to "discard uncommitted content," restoring working to committed=7, then marking it consistent.

#define _POSIX_C_SOURCE 200809L
#include <errno.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
static pthread_mutex_t mutex;
static int committed = 7, working = 7;
static void require(int result) { if (result != 0) abort(); }
static void *unfinished(void *unused) {
    (void)unused;
    require(pthread_mutex_lock(&mutex));
    working = 99;
    return NULL;  /* Intentionally exit thread holding robust mutex. */
}
int main(void) {
    pthread_mutexattr_t attr;
    require(pthread_mutexattr_init(&attr));
    require(pthread_mutexattr_setrobust(&attr, PTHREAD_MUTEX_ROBUST));
    require(pthread_mutex_init(&mutex, &attr));
    require(pthread_mutexattr_destroy(&attr));
    pthread_t thread;
    require(pthread_create(&thread, NULL, unfinished, NULL));
    require(pthread_join(thread, NULL));
    int result = pthread_mutex_lock(&mutex);
    if (result != EOWNERDEAD) abort();
    if (working != 99 || committed != 7) abort();
    working = committed;
    require(pthread_mutex_consistent(&mutex));
    require(pthread_mutex_unlock(&mutex));
    require(pthread_mutex_lock(&mutex));
    int recovered = working == 7 && working == committed;
    require(pthread_mutex_unlock(&mutex));
    require(pthread_mutex_destroy(&mutex));
    printf("recovered=%d\n", recovered);
    return !recovered;
}

Save as robust-demo.c, compile with cc -Wall -Wextra -pthread robust-demo.c -o robust-demo. Expect recovered=1, and the next lock after recovery should return 0 normally. Robust mutex recovery protocol

In this example, the committed copy was not modified by the abnormal thread, so the recovery rule is clear. Complex objects may also involve partial writes, linked list structures, and external side effects; if committed itself might be incomplete, simple assignment does not constitute valid recovery. You should first define verifiable invariants and recovery data, then decide when to call consistent.

EOWNERDEAD: lock acquired, data not repaired

After owner death, lock yields both EOWNERDEAD and recovery-thread ownership. Unlock directly to make the mutex unrecoverable; restore working, declare consistency and unlock to allow a normal later lock. Data repair and consistency declaration are distinct required steps.

Boundaries of Other Operations and futex2

Operations like FUTEX_REQUEUE can move wait queues, reducing thundering herd effects in certain condition variable patterns. FUTEX_WAKE_OP combines an atomic operation on a second word with conditional waking; it is not "atomic add followed by WAIT," FUTEX_OP is a macro encoding the operation. FUTEX_WAKE_OP

futex_waitv accepts a set of words to compare and waits for any one of them to be woken, suitable for multiple wait sources. After returning an index, you still need to check the business state; it does not represent acquiring multiple locks simultaneously. This interface uses absolute timeouts and specified clocks.

"futex2" involved many extension ideas; you cannot write all the widths, NUMA, and scheduling features in the proposal as facts already possessed by all 6.x kernels. The kernel futex2 documentation checked in this article explicitly requires FUTEX_32 for waitv, although the structure fields reserve space for extensions. Kernel futex2 documentation

How to Understand Performance

The uncontended path may have no system calls, but atomic read-modify-write still brings cache coherence overhead. When contending, it may also include spinning, queue operations, context switches, scheduling delays, and cross-NUMA data transmission. There is no universal conclusion of a fixed "20 ns" or exactly one WAIT plus one WAKE per contention.

When observing slow locks, distinguish between hold time, wait time, contention frequency, and scheduling impact. Tracing methods from function entry to return can be found in ftrace and bpftrace.

Keywords: futex, compare and block, lost wakeup, FUTEX_WAIT, FUTEX_WAKE, acquire release, PI, robust mutex, EOWNERDEAD, futex_waitv