arthrop0d

Brief articles on varied topics.

Linux Futexes: User-Space Fast Paths and Kernel Wait Queues

concurrencyoperating systems

A futex—short for “fast userspace mutex”—is a Linux mechanism that lets a thread wait on a value stored in user memory, while the kernel provides the wait queue and wake-up operations. The usual path is an atomic operation in user space; a system call is needed only when a thread has to sleep or wake another thread.

That division is why ordinary mutexes and condition variables can be cheap when uncontended without making blocked threads spin and waste CPU.

The problem futexes solve

A lock needs two different kinds of work:

If every lock operation entered the kernel, even a simple acquire-and-release pair would pay for a system call and a transition between user mode and kernel mode. That overhead would appear in ordinary code even when there is no competition.

The alternative—always checking the lock in a loop—avoids system calls but wastes a CPU while the owner is delayed. A futex combines the two approaches: check and modify the state in user space, then ask the kernel to sleep only when the fast check says waiting is necessary.

The shared word and the fast path

A futex is associated with a 32-bit, suitably aligned value in memory. The value is not generally owned by the kernel. It is synchronization state that user-space code, such as a thread library, reads and changes with atomic operations.

For a mutex, an uncontended acquire can look conceptually like this:

if (atomic_compare_exchange(&mutex->state, UNLOCKED, LOCKED)) {
    // Acquired without entering the kernel.
} else {
    // Someone else owns it; use the futex slow path.
}

A compare-and-exchange changes a value only if it still equals an expected value. This makes “observe that the mutex is unlocked and claim it” one indivisible operation: two threads cannot both successfully claim the same lock.

The exact state encoding varies. An implementation might use one value for unlocked, another for locked with no known waiters, and a third bit to indicate that waiters may exist. The important point is that the mutex library owns this policy; the kernel mostly sees a memory address and a value to wait for.

Unlocking is similarly cheap when nobody is waiting. The owner performs an atomic store or exchange that makes the word unlocked. If the implementation knows that no waiter exists, it does not need a system call at all.

These atomic operations also provide memory ordering: rules that ensure reads and writes before unlocking become visible to a thread that later acquires the mutex. Futexes do not replace those rules. The mutex implementation must use atomic operations with the ordering required by its locking protocol.

The slow path: wait only if the value is still expected

Suppose a thread fails the fast-path acquire. It cannot simply sleep unconditionally. The owner might release the mutex immediately after the failed check and before the waiting thread enters the kernel. If the release’s wake-up happened before the waiter registered itself, an unconditional sleep could miss the event and sleep forever. This is a lost wake-up.

The futex wait operation avoids that race. The thread asks Linux to wait on a futex word only if the word still contains a specified value. The kernel checks the value and, if it matches, places the thread on a kernel wait queue and blocks it as one coordinated operation. If the value has already changed, the kernel does not sleep the thread; it returns so the thread can retry.

In Linux’s futex interface, this is the role of FUTEX_WAIT; a mutex implementation typically invokes it through a library or an internal wrapper rather than calling it directly. A corresponding FUTEX_WAKE operation wakes some number of threads waiting on the same futex key. The key can represent a private process-local address or, for process-shared synchronization, a shared-memory futex identity.

A wake-up is only a hint that the state may now permit progress. After returning, the thread must inspect the mutex state again and retry the atomic acquire. It may find that another waiter won the race, or that it woke for an implementation-level reason. Therefore futex waits belong in a loop, never in a single “sleep, then assume success” step.

The kernel supplies parking and notification; user space remains responsible for deciding whether the lock is actually available.

How a mutex uses the mechanism

A typical contended mutex protocol is:

  1. Try an atomic exchange or compare-and-exchange in user space.
  2. If it succeeds, enter the critical section with no futex system call.
  3. If it fails, mark the state as contended if necessary.
  4. Call the futex wait operation while the state still says the mutex is unavailable.
  5. On wake-up, retry from the first step.
  6. On unlock, change the state to available and issue a futex wake if waiters might exist.

The “might exist” detail is an optimization. Waking when nobody is waiting costs work, so implementations track enough state to avoid it where possible. Correctness still comes from the atomic state transition and the wait operation’s value check, not from perfect knowledge of the waiter count.

Condition variables use the same split

A condition variable is a way for a thread to sleep until some shared condition may have changed. It does not itself contain the condition; application state does. For example, a consumer might wait until a queue is nonempty while holding a mutex.

A condition-variable wait must release the mutex and begin waiting as one coordinated operation. Otherwise a producer could make the queue nonempty and signal between those two actions, leaving the consumer asleep after the relevant notification.

Implementations commonly use a futex-backed sequence or generation value. Waiting records the current value, releases the associated mutex, and waits only while that value remains unchanged. Signaling advances the value and wakes one or more waiters. A woken thread reacquires the mutex and checks the application predicate again:

pthread_mutex_lock(&queue_mutex);
while (queue_empty()) {
    pthread_cond_wait(&queue_ready, &queue_mutex);
}
item = remove_item();
pthread_mutex_unlock(&queue_mutex);

The loop matters because wake-ups do not promise that this particular thread should proceed, and because several threads may compete for the mutex after a signal. The predicate—not the notification itself—is the source of truth.

What you see in practice

When a profile or stack trace shows a thread in futex, futex_wait, or a library function such as pthread_cond_wait, it usually means the fast path already failed and the thread is parked. A healthy uncontended lock may never appear there at all. This is the central performance property of futexes: common synchronization stays as atomic user-space memory operations, while the kernel becomes involved only to put blocked threads to sleep and wake them later.

← All articles