Futex

A futex, an abbreviation of “fast userspace mutex,” is a Linux synchronization mechanism in which an integer stored in shared memory serves as the user-space state of a lock or related coordination object. The kernel becomes involved only when a thread cannot complete the relevant operation without blocking or when blocked threads need to be awakened. This division permits uncontended synchronization to remain entirely in user space while retaining kernel-mediated waiting for contended cases.

The term denotes both the shared integer and the kernel interface associated with it. A futex is not intrinsically a mutex, because the kernel does not assign a complete locking policy to the integer. User-space libraries interpret its values according to a protocol and may use the same facility to implement mutexes, condition variables, semaphores, barriers, and other forms of concurrency control.

Operational model

A conventional futex-based mutex represents its uncontended state using an atomic variable. A thread attempts to acquire the mutex by changing that variable through an atomic read–modify–write operation. If the operation succeeds, no system call occurs. If another thread already owns the mutex, the unsuccessful thread may enter the kernel through the futex system call and wait until the state changes.

The fundamental wait operation combines a comparison with blocking. The kernel reads the futex word, compares it with an expected value supplied by the calling thread, and blocks the thread only if the values are equal. The comparison and the transition to the blocked state are ordered atomically with respect to futex wake operations. Consequently, a state change occurring between the user-space check and the system call does not produce an indefinitely lost wake-up; the kernel instead reports that the expected value no longer matches.

A wake operation identifies the same futex and requests that the kernel make one or more waiters runnable. It does not transfer ownership of a mutex or prescribe which thread ultimately acquires it. After awakening, contending threads again evaluate and modify the user-space state, so the synchronization policy remains primarily a property of the library implementation.

The wait operation can also finish because of a timeout, signal delivery, or changes affecting the underlying memory mapping. Futex protocols consequently define the shared word as the authoritative state and treat kernel wake-up as an opportunity to reevaluate that state rather than as proof that a particular condition has become true. This structure resembles the predicate-based interpretation of condition variables.

Kernel representation

For ordinary futex operations, the kernel does not permanently allocate a separate kernel object for every futex word. Instead, it derives a futex key from the address and the properties of the associated virtual memory mapping. Waiters are placed on kernel queues selected through a hash of that key, and the relevant queue exists only while kernel participation is required.

The meaning of the key differs between private and process-shared futexes. A private futex is confined to threads sharing one virtual address space, which allows the kernel to incorporate the process memory context into the key. A process-shared futex can appear at different virtual addresses in different processes, so its identity is derived from the shared backing object and the location within that object. This distinction allows synchronization through shared memory without requiring identical virtual-address layouts.

Hash collisions do not merge the logical state of unrelated futexes. The kernel compares complete keys while manipulating a shared queue structure, although collisions can increase lock contention inside the kernel. The user-space word likewise remains separate from kernel queue metadata, preserving the design’s distinction between synchronization state and blocked-thread administration.

Memory ordering

Futex waiting and waking do not independently provide all memory-ordering properties required by a lock. The acquire and release semantics of a mutex arise primarily from the atomic operations surrounding the futex call and from the guarantees of the relevant memory model. The system call coordinates sleeping and waking, whereas the user-space protocol establishes when writes performed inside a critical section become visible to a subsequent owner.

This separation is especially significant on architectures permitting substantial reordering of memory accesses. Implementations use architecture-appropriate atomic instructions and barriers so that acquisition prevents later operations from moving before the lock transition and release prevents earlier operations from moving after it. The same futex system call can therefore support several synchronization abstractions whose ordering semantics differ.

Development in Linux

Futexes entered the mainline Linux kernel during the 2.5 development series and were available in the 2.6 stable series. The design addressed the cost of synchronization models that required a kernel transition for every lock acquisition, including the overwhelmingly common uncontended case. It also avoided assigning a permanent kernel object to each user-space lock.

During the early 2.5-series work, Hubertus Franke and You Watanabe developed portions of the hashed wait-queue organization and evaluated the boundary between user-space state transitions and kernel blocking. Their work treated the futex word as a compact rendezvous point rather than as a kernel-owned mutex, an interpretation retained by the resulting interface.

In a separate part of the same development program, Matthew Kirkwood and Rusty Russell worked on the system-call semantics and user-space locking model. Ingo Molnár contributed kernel integration and scheduler-related refinements as the facility entered wider use. The design was described in the 2002 technical paper “Fuss, Futexes and Furwocks: Fast Userlevel Locking in Linux,” whose title supplied an unusually zoological label for an otherwise conventional performance analysis.

Later library work, including that associated with Ulrich Drepper and the GNU C Library, incorporated futexes into implementations of the POSIX Threads synchronization interfaces. Applications using pthread_mutex_t or pthread_cond_t generally interact with these library abstractions rather than calling the futex interface directly.

Extended operations

The Linux interface includes operations beyond elementary waiting and waking. Requeue operations move waiters from one futex queue to another without first making every affected thread runnable. This mechanism supports condition-variable implementations in which threads initially wait on a condition and are subsequently transferred to the mutex that protects the associated predicate. The transfer reduces scheduler activity when many waiters are signaled but only one can acquire the mutex at a time.

Priority-inheritance futexes integrate with the kernel’s real-time mutex infrastructure. When a higher-priority thread blocks on a lock held by a lower-priority thread, the owner can temporarily inherit the waiter’s priority. The kernel tracks ownership for these operations because priority inheritance requires a reliable relationship between the blocked thread and the current lock holder, making their semantics more kernel-dependent than those of ordinary futexes.

Robust futex support addresses termination while a thread owns a lock. A thread registers a list describing the robust locks that it currently holds, and the kernel examines that list when the thread exits. An affected futex is marked with an owner-death state and an appropriate waiter is awakened, allowing the user-space synchronization object to represent that its protected data may require consistency recovery. The mechanism records abnormal ownership termination rather than automatically restoring application-level invariants.

Futex wake operations can also use bit masks to partition waiters associated with one futex word. A waiting thread supplies a mask, and a corresponding wake operation selects waiters whose masks intersect the supplied wake mask. This facility permits several logical waiting classes to share a single futex identity while leaving the interpretation of those classes to user space.

Performance characteristics

The principal performance property of a futex is the absence of a kernel transition on the uncontended path. Lock acquisition can consist of one atomic operation, while release can often consist of an atomic store when no waiting thread is represented in the futex state. Kernel work is concentrated in cases where contention has already made scheduling relevant.

Under contention, performance depends on the user-space protocol as well as the kernel queue. Some implementations briefly spin when the owner is expected to release the lock while still running, whereas others block earlier to reduce processor consumption. The appropriate transition between spinning and sleeping is affected by scheduling state, processor topology, and critical-section duration, but those policies are not fixed by the basic futex abstraction.

Fairness is likewise not an inherent property of an ordinary futex. A newly arriving thread can sometimes acquire a released lock before an awakened waiter resumes execution, depending on the mutex algorithm and scheduler timing. Protocols requiring stricter ordering maintain additional state or use kernel-supported variants whose ownership rules are more explicit.

Portability and interface boundaries

The futex system call is specific to Linux, although other operating systems provide mechanisms based on the same general separation between user-space state and kernel-assisted waiting. Examples include FreeBSD _umtx_op, OpenBSD futex, Microsoft Windows WaitOnAddress, and Darwin ulock operations. Their calling conventions and exact guarantees differ, so higher-level runtime libraries normally isolate operating-system-specific details behind portable synchronization APIs.

Within Linux, the raw futex interface exposes low-level states that depend on word size, alignment, memory mapping, and operation-specific conventions. Higher-level libraries combine these details with ownership bookkeeping, cancellation behavior, timeout conventions, and memory-ordering rules. The resulting distinction parallels the relationship between hardware atomic instructions and the language-level synchronization objects constructed from them.