futex — How Mutexes Really Work in Linux

Why pthread_mutex_lock Usually Doesn’t Make a Syscall

The common intuition: taking a mutex means entering the kernel. pthread_mutex_lock() looks like a system operation, so “it probably makes a syscall.” Yet in the uncontended case — when the lock is free and nobody competes for it — pthread_mutex_lock() doesn’t touch the kernel even once. The entire operation is an atomic CPU instruction in userspace, costing a dozen-odd nanoseconds.

The secret is the futex (fast userspace mutex) — the synchronization primitive on which glibc builds mutexes, condition variables, semaphores, and barriers. The idea is brilliantly simple: don’t call the kernel until you have to. As long as there’s no contention, synchronization lives entirely in userspace. Only when a thread must sleep waiting for a lock does the futex() syscall happen.

This article dissects the futex into its fast path and slow path: the atomic CAS in userspace, the mechanics of FUTEX_WAIT/FUTEX_WAKE, the thundering herd problem, cross-process futexes, and — crucial for production decisions — when the overhead of a synchronization syscall actually matters.

The Problem: Why a Plain Variable Isn’t Enough

The simplest “lock” is a flag in memory: 0 = free, 1 = taken. The problem is that checking and setting the flag are two separate operations, and between them another thread can squeeze in and also set the flag — the classic race condition. What’s needed is an atomic operation: check-and-set in one indivisible instruction.

Processors provide this through instructions like compare-and-swap (CAS). On x86-64 it’s lock cmpxchg — it compares the value in memory with an expected one and, if it matches, atomically swaps it for a new one. The lock prefix guarantees no other core enters mid-operation.

#include <stdatomic.h>

/* The simplest spinlock — CAS in a loop, no kernel */
typedef struct {
    atomic_int locked;   /* 0 = free, 1 = taken */
} spinlock_t;

void spin_lock(spinlock_t *lock) {
    int expected = 0;
    /* Try to atomically change 0 → 1. If it fails, spin in the loop. */
    while (!atomic_compare_exchange_weak(&lock->locked, &expected, 1)) {
        expected = 0;        /* CAS overwrites expected — reset it */
        __builtin_ia32_pause();  /* PAUSE instruction — a hint to the CPU */
    }
}

void spin_unlock(spinlock_t *lock) {
    atomic_store(&lock->locked, 0);
}

A spinlock works, but has a fatal flaw: a thread waiting for the lock burns CPU in a loop. For a lock held for microseconds that’s acceptable. For a lock held for milliseconds — a disaster: the core spins idle instead of yielding time to other threads. This is where the futex comes in.

The Fast Path: the Futex Doesn’t Touch the Kernel

The key observation behind the futex: in the uncontended case a spinlock is ideal — one CAS and done, zero syscalls. The problem only appears under contention, when a thread must wait. The futex combines both worlds: a userspace fast path for the no-contention case, a slow path with a syscall only when a thread must sleep.

#include <linux/futex.h>
#include <sys/syscall.h>
#include <unistd.h>
#include <stdatomic.h>

/* Wrapper around the raw futex syscall — glibc doesn't expose it directly */
static int futex(atomic_int *uaddr, int op, int val) {
    return syscall(SYS_futex, uaddr, op, val, NULL, NULL, 0);
}

/* Mutex states: 0 = free, 1 = taken, 2 = taken + waiters present */
#define UNLOCKED 0
#define LOCKED   1
#define CONTESTED 2

void futex_lock(atomic_int *m) {
    int c;
    /* FAST PATH: try atomically 0 → 1. No contention = zero syscalls. */
    if ((c = 0, atomic_compare_exchange_strong(m, &c, LOCKED)))
        return;   /* lock acquired without touching the kernel */

    /* SLOW PATH: lock taken — mark as CONTESTED and sleep */
    do {
        /* If already CONTESTED or we manage to mark it — wait in the kernel */
        if (c == CONTESTED ||
            atomic_compare_exchange_strong(m, &c, CONTESTED) != UNLOCKED) {
            /* FUTEX_WAIT: sleep AS LONG AS *m == CONTESTED */
            futex(m, FUTEX_WAIT, CONTESTED);
        }
        c = 0;
    } while (!atomic_compare_exchange_strong(m, &c, CONTESTED));
}

void futex_unlock(atomic_int *m) {
    /* If there were waiters (value 2), they must be woken */
    if (atomic_fetch_sub(m, 1) != LOCKED) {
        atomic_store(m, UNLOCKED);
        /* FUTEX_WAKE: wake ONE waiting thread */
        futex(m, FUTEX_WAKE, 1);
    }
}

The core is the three-state design: the value 2 (CONTESTED) encodes the information “there are threads sleeping in the kernel on this lock.” This lets unlock avoid the FUTEX_WAKE syscall when nobody waits — if the value was 1, there’s no one to wake, so the syscall is skipped. The syscall appears only when someone actually has to be put to sleep or woken.

The Mechanics of FUTEX_WAIT and FUTEX_WAKE

Two operations form the core of the interface, and their semantics are precisely designed around one problem: the race between checking a condition and going to sleep.

The brilliance of FUTEX_WAIT lies in the *addr == val condition checked atomically in the kernel. Consider the race: thread A sees the lock taken and decides to sleep. Between that decision and actually sleeping, thread B releases the lock and calls FUTEX_WAKE — but A isn’t sleeping yet, so the wakeup hits nothing. A sleeps forever (a lost wakeup).

The futex solves this as follows: FUTEX_WAIT passes the expected value to the kernel. The kernel atomically checks whether *addr still holds it — if B managed to change it, FUTEX_WAIT returns immediately with EAGAIN instead of sleeping. The thread won’t sleep on a stale condition. This is exactly the core that a naive “check the flag, then sleep” implementation lacks.

Spinning vs Sleeping — Adaptive Mutexes

A pure futex sleeps immediately under contention. But putting a thread to sleep and waking it is also a cost: a context switch (~1–5 µs), cache eviction, scheduling. If the lock is held for less than the cost of sleeping, it’s cheaper to spin briefly in a loop than to sleep. Hence adaptive mutexes (PTHREAD_MUTEX_ADAPTIVE_NP): they first spin for a bounded number of iterations, and only when that doesn’t help — call FUTEX_WAIT.

The spin-vs-sleep decision is the same kind of engineering trade-off as the choice of I/O model — where syscall overhead determines whether a more complex mechanism is worth it. The same “measure where the syscall actually hurts” logic is dissected in the article on epoll vs io_uring.

Thundering Herd — Whom to Wake

Suppose 100 threads sleep on one lock, and it’s just been released. A naive FUTEX_WAKE(addr, INT_MAX) wakes all 100 — which lunge for the lock, but one acquires it while the other 99 immediately go back to sleep. This is the thundering herd: 99 needless context switches, 99 failed CAS attempts, complete waste.

The solution is to wake one thread at a time (FUTEX_WAKE(addr, 1)) — exactly how the mutex code above works. For condition variables, where you sometimes must wake everyone (pthread_cond_broadcast), glibc uses the FUTEX_REQUEUE optimization: instead of waking 100 threads on the condition variable, it moves 99 of them directly into the mutex’s wait queue, waking only one. The rest are requeued without being woken — eliminating the thundering herd at the source.

Cross-Process Futexes

A futex works within a single process by default, but its true power shows between processes. Because a futex is identified by the physical address of a memory page (not the virtual one), two processes mapping the same shared memory can synchronize on the same futex.

#include <sys/mman.h>

/* A mutex in shared memory — synchronization BETWEEN processes */
atomic_int *shared_mutex = mmap(
    NULL, sizeof(atomic_int),
    PROT_READ | PROT_WRITE,
    MAP_SHARED | MAP_ANONYMOUS,   /* shared with child processes */
    -1, 0
);

/* After fork() both processes see THE SAME futex — the kernel maps
   the virtual address to the same physical page address.
   futex_lock(shared_mutex) works identically across process boundaries. */

For futexes within a process, glibc adds the FUTEX_PRIVATE_FLAG, which lets the kernel skip the costly translation to a physical address and use faster, local hashing — hence private futexes are faster than shared ones. The shared-memory mechanism behind a cross-process futex is the same MAP_SHARED dissected in the article on mmap and memory-mapped I/O, and the process-thread relationship is covered in the article on the fork() system call.

Priority Inheritance — PI Futexes

A classic real-time problem: priority inversion. A low-priority thread holds a lock that a high-priority thread needs. The high one waits — but a medium-priority thread preempts the low one, so the lock isn’t released, and the high priority waits indefinitely, blocked indirectly by the medium.

The kernel solves this with PI futexes (FUTEX_LOCK_PI): when a high-priority thread blocks on a lock held by a low one, the kernel temporarily raises the lock holder’s priority to the waiter’s level. The low thread finishes the critical section faster, releases the lock, and returns to its own priority. This is a key mechanism for real-time systems and drivers, where deterministic response times are a requirement, not a luxury.

Diagnostics — Tools

A practical signal: if strace -c -f shows hundreds of thousands of futex calls per second, you have real lock contention — threads spend time sleeping and waking instead of working. That’s the moment to profile with perf lock and revisit lock granularity. Observing the syscalls themselves is the same technique dissected in the article on strace and reading syscalls.

When It Matters — Decision Matrix

Conclusion: the Futex as a Layer Worth Understanding

The futex isn’t an exotic primitive for library authors — it’s the foundation under every pthread_mutex_lock, every condition variable, and every semaphore you use. Understanding the split between the fast path (atomic CAS in userspace, zero syscalls) and the slow path (FUTEX_WAIT/FUTEX_WAKE only under contention) turns “mutexes are slow because they make a syscall” into a precise model: they’re slow only when there’s actually something to compete for.

The key understandings: an uncontended lock is one CAS without the kernel; the CONTESTED value encodes the presence of waiters, letting you skip a needless FUTEX_WAKE; the atomic *addr == val check eliminates lost wakeups; FUTEX_REQUEUE kills the thundering herd; and PI futexes protect real-time systems from priority inversion. This knowledge turns synchronization from a black box into a measurable, debuggable, and optimizable aspect of the system.

Next time someone says “mutexes are expensive because they enter the kernel” — you now know that in the typical case they don’t enter at all. The cost appears only under real contention, and that’s measurable with a single strace -c.

Related articles

• epoll vs io_uring — When the Event Loop Isn’t Enough — the same syscall-overhead trade-off, in the I/O context
• mmap — When Memory-Mapped I/O Beats read() and write() — MAP_SHARED as the foundation of cross-process futexes
• What fork() in Linux Really Does Under the Hood — processes, threads, and sharing memory
• strace as a Debugging Primitive — When the Stack Trace Lies — observing futex calls in practice