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, with a cost that depends on the CPU and cache state.

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.

The spinlock uses the x86 PAUSE instruction. Initialize its atomic lock field to zero before sharing it between threads.

#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.

#define _GNU_SOURCE
#include <linux/futex.h>
#include <sys/syscall.h>
#include <unistd.h>
#include <stdatomic.h>
#include <errno.h>
#include <stdlib.h>

/* Demonstration: Linux, 32-bit lock-free atomic_int.
   Before use: atomic_int m = ATOMIC_VAR_INIT(0); */
_Static_assert(sizeof(atomic_int) == 4, "futex requires 4 bytes");
_Static_assert(ATOMIC_INT_LOCK_FREE == 2, "lock-free atomics required");

static void wait_contested(atomic_int *m) {
    if (syscall(SYS_futex, m, FUTEX_WAIT, 2, NULL, NULL, 0) == -1
        && errno != EAGAIN && errno != EINTR) abort();
}

void futex_lock(atomic_int *m) {
    int expected = 0;
    if (atomic_compare_exchange_strong(m, &expected, 1)) return;
    /* exchange returns the PREVIOUS value; C CAS returns bool. */
    while (atomic_exchange(m, 2) != 0) {
        wait_contested(m);
        /* Always recheck after wakeup or EINTR/EAGAIN. */
    }
}

void futex_unlock(atomic_int *m) {
    if (atomic_exchange(m, 0) == 2) {
        if (syscall(SYS_futex, m, FUTEX_WAKE, 1, NULL, NULL, 0) == -1)
            abort();
    }
}

State 0 means unlocked, 1 means locked without marked contention, and 2 means locked with possible waiters. Two is not a count of sleeping threads. This demonstrates the WAIT/WAKE protocol; it does not implement recursion, owner-death handling or priority inheritance. Applications will usually use pthread_mutex_t.

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: context switching, scheduling and effects on cache locality. 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.

FUTEX_REQUEUE can move waiters to another futex’s queue without waking them all. It is an available optimization mechanism, not a guarantee about every implementation of pthread_cond_broadcast().

Cross-Process Futexes

Futexes can synchronize threads in different processes when the futex word is in the same shared memory. Virtual addresses need not match. The kernel derives the futex key from the mapping; describing it solely as a physical address is too simple.

#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
);

/* Check for MAP_FAILED, then atomic_init(shared_mutex, 0) before fork().
   Both processes must use operations without FUTEX_PRIVATE_FLAG. */

FUTEX_PRIVATE_FLAG tells the kernel that the futex is not shared between processes, enabling lookup optimizations. Do not use it for a mutex shared across processes. The underlying MAP_SHARED mapping and fork() determine how that memory is shared.

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

Many futex calls are a reason to investigate, not proof of contention on a particular mutex. Condition variables, semaphores and other primitives also use them. Examine waiting time and thread stacks before drawing a conclusion. Reading syscall traces with strace helps identify the calls.

When It Matters — Decision Matrix

Conclusion: the Futex as a Layer Worth Understanding

Check waiting-protocol correctness and contention cost separately. Returning from FUTEX_WAIT does not mean the lock was acquired: another atomic operation in userspace must establish that.

No syscall does not mean zero cost. Even the fast path can move a cache line between cores. Measure the whole workload before replacing a mutex with a spinlock or a lock-free structure.

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

Technical references: futex(2), FUTEX_WAIT, perf-lock(1).