A Linux thread can acquire and release an uncontended lock without asking the kernel to do either operation. Futexes—fast userspace mutexes—make that division possible: the program handles an available lock in its own memory, while the kernel provides waiting and waking operations when necessary. Initial support entered Linux 2.5.7; the semantics described by today’s manual arrived in Linux 2.5.40.
Even when a lock becomes busy, not every operation must pass through the kernel. Userspace maintains the synchronization state, and futex operations connect that state to sleeping and waking threads.
A small word between program and kernel
The Linux manual describes a futex word as a four-byte integer aligned on a four-byte boundary. It remains 32 bits even on a 64-bit system. Threads can share the word within a process; separate processes can place it in shared memory.
For a simple lock, userspace can represent availability with a value in that word. An atomic compare-and-exchange instruction can change the state from available to acquired only if the previous value matches what the thread expects. Atomic means no competing thread can slip in between that read and write.
If the acquisition succeeds, the thread proceeds without a futex system call. The kernel maintains no information about that uncontended lock state. Releasing a lock can likewise stay in userspace when the synchronization protocol establishes that no waiter needs waking.
The futex manual calls these operations building blocks. Higher-level threading libraries use them to construct mutexes, condition variables, barriers and semaphores. The manual’s rationale is that well-designed programs try to avoid contention, so uncontended operations stay in userspace while the kernel arbitrates the contended case. Most application programmers encounter those library interfaces rather than making raw futex calls.
The gap between checking and sleeping
Contention introduces a problem that an atomic acquisition alone cannot solve. Suppose one thread holds a lock and another discovers it is unavailable. The second thread decides to sleep. Between that decision and actually sleeping, the owner might release the lock and send a wake-up.
If the second thread then sleeps without checking again, it can miss the notification it needed. This is the lost-wakeup problem. The lock is available, but the thread that wanted it has gone to sleep after the wake-up already happened.
FUTEX_WAIT closes that gap by taking an expected value. The kernel loads the futex word, compares it with that value and starts the wait atomically with respect to other futex operations on the same word. If the value has changed, the call immediately returns -1 and sets errno to EAGAIN, indicating that the expected value no longer matches, instead of putting the thread to sleep.
The comparison matters as much as the ability to sleep. Userspace may have made its decision using an older observation; the kernel checks whether the condition for waiting still holds when the wait is established.
A wake-up is a chance to check again
On release, the owner updates the userspace state before asking the kernel to wake waiters when needed. FUTEX_WAKE accepts a maximum number to wake. The manual gives one waiter and all waiters as common choices.
That notification does not by itself establish that a returning thread owns the lock. The FUTEX_WAIT documentation tells callers to assume that even a successful return can represent a spurious wake-up. The userspace synchronization scheme must inspect the state and decide whether the thread can proceed or needs to wait again.
Ordinary FUTEX_WAKE also gives no guarantee about which waiters are selected. A thread with a higher scheduling priority is not guaranteed to wake before one with a lower priority. Applications cannot infer a fairness policy merely from the presence of a futex.
Priority inheritance adds a different agreement
Linux provides priority-inheritance futexes for another difficulty: a high-priority thread can wait for a lock held by a low-priority thread, while intermediate-priority work prevents the owner from running. The owner cannot release the lock until it gets time to execute.
Priority inheritance temporarily raises the owner’s priority so it can make progress toward releasing the lock. These futex operations use a specified encoding: zero means unlocked, and an acquired lock records its owner’s thread identifier. A separate bit indicates waiting threads.
The kernel documentation emphasizes that this additional mechanism still preserves an uncontended userspace path. When acquisition needs kernel assistance, the kernel uses an internal mutex that supports priority inheritance. More demanding behavior requires a more specific agreement about the shared word.
Remembering a lock when its owner dies
The ordinary design’s small kernel footprint creates a further complication. A thread can die while holding an uncontended lock about which the kernel has no waiting queue. Without additional information, the kernel cannot identify that held lock for cleanup.
Robust futexes address this through a per-thread list of held robust locks maintained in userspace and registered with the kernel. At thread exit, the kernel can inspect that list, mark affected locks with an owner-died flag and wake a waiter. The userspace library and application still have recovery work to do; notification does not repair the protected data.
These extensions show the boundary of the original bargain. The shared word supports the quick operation; the kernel supplies waiting, waking and specified assistance when the protocol needs it. In the uncontended case, the thread changes the word and continues.
Related stories
Sources
- Linux manual: futex system call
- Linux manual: futex synchronization building blocks
- Linux manual: FUTEX_WAIT and lost wake-ups
- Linux manual: FUTEX_WAKE
- Linux kernel documentation: Lightweight PI-futexes
- Linux kernel documentation: robust futexes
- Featured image: Kurt Kaiser; Wikimedia Commons; CC0 (adapted from the original)
SIGNAL TITANS
Leave a Reply