Linux Futexes and User-Space Mutex Waiting

18 Sep 2026 linuxconcurrencyoperating systems

A futex—short for fast userspace mutex—is a Linux kernel mechanism that lets a program wait on a value in memory without entering the kernel for every lock operation. A user-space mutex uses atomic instructions for the uncontended case, then uses a futex system call when a thread must actually sleep or wake another thread.

The futex is not itself a complete mutex. It is a small building block: a user-space memory word plus kernel operations that wait for, or wake threads based on, that word.

The problem futexes solve

A mutex protects shared data so that only one thread can access a critical section at a time. The simplest implementation would ask the kernel to acquire and release the mutex every time:

1. Enter the kernel to lock it.
2. Enter the kernel again to unlock it.
3. If the mutex is busy, ask the kernel to put the thread to sleep.

That works, but it makes the common case expensive. Most locks are uncontended: the thread finds the mutex free, takes it, does its work, and releases it without meeting another thread. A system call can involve privilege-level changes and kernel bookkeeping even when no thread needs to sleep.

Spinning is the opposite approach. A thread repeatedly checks the lock until it becomes available. This avoids system calls, but wastes a CPU while the owner is delayed or is running on another CPU. It can also make progress worse by consuming CPU time that the lock holder needs.

A futex combines both strategies: check and change the lock in user space first; sleep in the kernel only when spinning or retrying is no longer useful.

The fast path stays in user space

A typical mutex stores a small state in an aligned 32-bit integer. The exact encoding varies, but it might represent these states:

To lock the mutex, a thread performs an atomic compare-and-exchange: “if the state is 0, replace it with 1.” If that succeeds, the thread owns the mutex. No futex system call occurred, and the kernel may never know that the mutex was used.

To unlock an uncontended mutex, the owner can atomically change the state back to 0. That also stays entirely in user space.

These atomic operations need the appropriate memory ordering. Acquiring the mutex must make the previous owner’s writes visible to the new owner, and releasing it must publish the current owner’s writes before another thread acquires the lock. The mutex implementation supplies those ordering guarantees; an ordinary non-atomic load and store would not be enough.

The slow path waits on a value

Suppose a thread tries the atomic acquire and discovers that the mutex is already locked. It may retry briefly, but eventually it needs to sleep rather than burn CPU.

The implementation marks the state as contended if necessary, then invokes the Linux futex system call with the FUTEX_WAIT operation. Conceptually, it tells the kernel:

Sleep me if this memory word still contains the value I observed.

The kernel checks the word and, if it still matches the expected value, places the thread on a wait queue associated with that futex address. The thread then sleeps. The wait operation’s check and queueing are coordinated so that a release cannot slip between “I saw the lock was busy” and “I went to sleep,” creating a permanently sleeping thread.

The check still has to be repeated after the call returns. The value might have changed before the thread was queued, in which case the kernel returns without sleeping. A wake-up can also be spurious, interrupted, or caused by another state transition that does not give this particular thread the lock. Therefore a mutex always follows the futex wait with a loop that rereads the state and tries to acquire it again.

In simplified form, the algorithm is:

// Conceptual pseudocode, not a complete mutex implementation.
while (atomic_compare_exchange(&state, 0, 1) fails) {
    atomic_store(&state, CONTENDED);
    futex_wait(&state, CONTENDED);
}

// Critical section

if (atomic_exchange(&state, 0) == CONTENDED)
    futex_wake(&state, 1);

The actual futex interface is exposed through the Linux futex system call, and production mutexes handle races, memory ordering, cancellation, process sharing, and additional state more carefully than this sketch.

Unlocking wakes a waiter

When a contended owner releases the mutex, it changes the state to indicate that the lock is available. If it knows that another thread may be asleep, it calls the futex operation FUTEX_WAKE, usually asking the kernel to wake one waiter.

The wake does not hand ownership directly to that waiter. It merely makes the waiter runnable. The woken thread must compete with other threads, reread the user-space state, and atomically acquire the mutex. This design keeps ownership decisions in user space and lets the same mechanism handle races safely.

A wake can cause a context switch, but it does not necessarily do so immediately. The scheduler decides when the awakened thread runs. Likewise, a contended lock attempt may enter the kernel but discover that the lock became free just in time; it can return without sleeping.

What the kernel actually tracks

The futex word lives in the process’s memory. The kernel mainly uses its address and value to manage waiters. For threads in one process, the address normally identifies a private futex; futexes can also be configured for synchronization through shared memory between processes.

This is why a futex is efficient: the kernel is involved in the unusual part of synchronization—putting a blocked thread to sleep and waking it—but not in every successful lock and unlock.

When a stack trace, performance profile, or incident log mentions futex, it usually means a thread was waiting for this slow path: often on a mutex, condition variable, or another library synchronization primitive built on futexes. The important distinction is that seeing futex code does not mean every use of that primitive entered the kernel. In the normal uncontended case, the entire operation can be a handful of atomic user-space instructions.