Linux - futex

A futex (short for Fast Userspace Mutex) is a fundamental Linux kernel mechanism used to build high-performance synchronization primitives—such as mutexes, semaphores, and condition variables—in user space.

The Problem Futex Solves

Traditional synchronization mechanisms required calling into the kernel (a system call) every time a thread wanted to lock or unlock a resource. Context switching between user space and kernel space is relatively slow and expensive.

In practice, most lock operations are uncontended—meaning no other thread is holding the lock when a thread requests it. A futex avoids kernel overhead by handling the fast (uncontended) case entirely in user space.

How Futex Works

A futex consists of two parts:

1. An integer in user space: A standard 32-bit integer alignment-bound in shared or process memory that holds the lock state (e.g., 0 for unlocked, 1 for locked, 2 for locked with waiters).
2. A kernel-managed wait queue: A queue inside the Linux kernel where threads sleep if they fail to acquire the lock.

The Two Paths:

• Uncontended Path (Fast Path - No System Call): A thread uses an atomic instruction (like Compare-And-Swap / atomic_cmpxchg) directly on the integer in user space. If the lock is free, it acquires it in a few CPU instruction cycles without invoking the kernel.
• Contended Path (Slow Path - Kernel System Call): If another thread already holds the lock, the atomic operation fails. The thread then makes a futex() system call with the operation FUTEX_WAIT, telling the kernel: "If the integer still equals X, put me to sleep." When the lock holder finishes, it calls futex() with FUTEX_WAKE to wake up the sleeping threads.

Key Futex Operations

The futex(2) system call supports several operations, with the primary two being:

Operation	Description
FUTEX_WAIT	Checks if the futex integer matches an expected value. If it matches, the calling thread is suspended until waked. If it doesn't match, it returns immediately to prevent race conditions.
FUTEX_WAKE	Wakes up a specified number of threads waiting on the futex address.
FUTEX_REQUEUE	Wakes up some waiters and moves the rest to a different futex queue (commonly used in pthread_cond_broadcast).
FUTEX_LOCK_PI	Priority-inheritance futex operation to prevent priority inversion bugs.

Who Uses Futexes?

Application developers rarely call futex() directly. Instead, high-level threading libraries use futexes under the hood:

• POSIX Threads (pthreads) (pthread_mutex_t, pthread_cond_t)
• C++ Standard Library (std::mutex, std::condition_variable)
• Java Virtual Machine (JVM) (Java object monitors and ReentrantLock)
• Go Runtime (channels and sync.Mutex)