Critical Sections, Futexes, and What a Mutex Really Costs

A mutex around a two-field update costs about twenty nanoseconds on an idle machine. The same mutex, protecting the same two fields, with sixteen threads arriving at once, costs hundreds of nanoseconds per acquisition and the throughput of the whole program falls rather than rises. Nothing about the code changed; the cost of the primitive is entirely a function of how many threads want it at the same moment.

That makes the mutex unusual among performance primitives. Its uncontended cost is small and easily measured, which encourages the belief that locks are cheap and can be added freely. Its contended cost is large, superlinear in the number of contenders, and invisible to any measurement taken on a single thread. The mechanism behind both numbers is worth walking through, because the design of Linux synchronization primitives is largely an exercise in keeping the first number small while preventing the second from becoming unbounded.

One atomic operation, then a syscall only if needed

The uncontended path is a single atomic compare-and-swap on a word in userspace memory. If the word holds “unlocked”, the swap writes “locked” and the caller proceeds. No syscall, no scheduling, no kernel involvement. On x86-64 this is a lock cmpxchg, and its cost is on the order of a few tens of cycles when the cache line is already exclusive in the local cache, which is what “uncontended” means mechanically: no other core has a copy of that line to invalidate.

The contended path is the interesting one, and it is where the futex exists. A naive spin lock would have every waiting thread issue compare-and-swap in a loop, saturating the interconnect with traffic to one cache line and starving the lock holder of cycles. A naive mutex that issued a syscall on every acquisition would cost thousands of cycles even when nothing contends. Linux resolves the tension with a userspace word and a kernel wait queue that is consulted only when the word says the lock is unavailable: fast path in userspace, kernel path only on contention.

The futex system call has a single entry point with a command selector. The two used by a mutex are FUTEX_WAIT, which atomically checks that the word at the given address still equals an expected value and, if it does, sleeps the calling thread on a kernel queue keyed by that address; and FUTEX_WAKE, which wakes up to a specified number of waiters on that address. The atomicity of the check in FUTEX_WAIT is the crucial detail: it closes the race in which a thread decides to sleep after the holder has already released and woken everyone. Without that atomic check-then-sleep, the waiter would sleep forever or the wake would be lost.

/* Sketch of a futex-based mutex; omits error handling and robustness. */
#include <linux/futex.h>
#include <sys/syscall.h>
#include <unistd.h>
#include <stdatomic.h>

static void futex_wait(atomic_int *addr, int expected) {
    syscall(SYS_futex, addr, FUTEX_WAIT_PRIVATE, expected, NULL, NULL, 0);
}

static void lock(atomic_int *m) {
    int unlocked = 0, locked = 1, contended = 2;
    if (!atomic_compare_exchange_strong(m, &unlocked, locked))
        return;                       /* fast path: one atomic op */
    do {
        if (atomic_exchange(m, contended) == unlocked)
            return;                   /* woke up and owned the lock */
        futex_wait(m, contended);     /* sleeps only if m == contended */
    } while (1);
}

The three-state design matters. The state “contended” (value 2) is what lets the unlock path know that waiters exist and that a FUTEX_WAKE is required. A two-state mutex cannot distinguish “locked with nobody waiting” from “locked with waiters”, so it must either issue FUTEX_WAKE on every unlock, which turns every uncontended unlock into a syscall, or never wake anyone, which loses wakeups.

What an unlock actually costs

In the two-state design with waiter tracking, unlock is an atomic exchange to zero followed by a futex wake only if the previous value indicated waiters. With no waiters, the unlock is one atomic store. With waiters, it is a store plus a syscall that enters the kernel, removes a thread from the queue, and marks it runnable on the target CPU.

The store side has a cost that is easy to overlook: the atomic exchange must take the cache line exclusively. If sixteen cores are spinning or have recently read the line, the line bounces to the writer and then back out to whoever acquires next. Each bounce is a coherent transaction over the interconnect, and the cost per bounce on a multi-socket machine is measured in hundreds of cycles rather than tens. This is why “the critical section is short so the lock is cheap” is a dangerous argument: short critical sections are exactly the case where the line bounces fastest and the ratio of transfer cost to useful work is worst.

Waking a thread is far more expensive than the lock

The most expensive part of contention is not the synchronization operation; it is the scheduler. Waking a thread that has been descheduled costs a context switch in each direction, and the time-to-wake is bounded by the scheduler’s operation: the thread must be placed on a run queue, the now-running thread must be preempted or must yield the CPU voluntarily, and the woken thread must be scheduled. On Linux, sched_latency governs the scheduling period, and a woken thread is normally treated favourably, but the range of outcomes for a thread that has actually gone to sleep is on the order of microseconds, not nanoseconds.

A waiter that sleeps and is woken for every acquisition therefore converts a nanosecond-scale operation into a microsecond-scale one, three orders of magnitude worse. Spin-then-block designs exist for this reason: the thread spins on the atomic word for a bounded number of iterations, hoping the holder releases soon and the whole handoff happens in cache, and only falls back to FUTEX_WAIT after the spin budget is exhausted. The budget is a tuning parameter with no universally right value; too small and every acquisition sleeps, too large and the spin traffic slows the holder.

The self-tuning mechanism used by some mutex implementations measures whether the lock was acquired during the spin phase and adjusts the spin count accordingly, so that behavior adapts to the actual hold time rather than requiring the programmer to know it.

Contention is a queue, and queues behave like queues

Once threads are waiting, the mutex is a queue with a service time equal to the critical section duration. Throughput through the lock is therefore one item per critical section length, regardless of how many threads wait, and the number waiting is the number of threads that have arrived and not yet been served.

Under that model, adding threads makes things worse once the lock is saturated. The extra threads do no useful work, consume scheduling slots on cores that could be running the holder, and add traffic on the lock word. The system reaches a point where throughput with sixteen threads is lower than with four, and the effect is sharp rather than gradual. The general form of this decline is derived in The Universal Scalability Law: Why Throughput Peaks and Then Falls.

Fairness is the other axis. A lock that hands the critical section to whichever thread happens to win the atomic operation is fast but unfair: a thread can arrive, retry repeatedly, and starve. A lock that queues waiters in order (a handoff lock) is fair but requires the unlocking thread to name the next owner, which is an extra atomic operation and a store into another thread’s cache line. Under light contention the unfair lock is faster; under heavy contention fairness bounds the worst-case wait, which is often what matters for tail latency.

Options when the lock is the bottleneck

The interventions that work are structural, and they generally fall into four kinds.

Reduce the critical section’s duration. The serial cost is the time inside the section, so moving an allocation, a format operation, or a syscall outside changes the throughput ceiling directly. This is only allowed when the moved operation does not depend on the protected state.

Reduce the frequency. Coarser operations amortize the lock cost: accumulating a hundred items in a local buffer and inserting them at once turns a hundred lock acquisitions into one. The cost is up to a hundred items of delay for the first item in the batch, which is the subject of Batching and the Amortization of Per-Item Cost.

Partition the state to reduce sharing. A counter protected by one lock becomes four counters with four locks, with the combined value read by summing. Sharding trades the ability to answer “what is the exact value now” for parallel write throughput. The false-sharing hazards of this technique are treated in Sharded Counters, Padding, and False Sharing.

Replace exclusion with optimistic concurrency. Where the update is a single word, an atomic read-modify-write does the job with no lock at all. Where the update touches several words, the optimistic protocol reads, computes, and attempts an atomic commit; the cost moves into the retry rate, which is the subject of Compare-and-Swap Retry Loops Under Contention.

The honest summary is that mutexes are cheap exactly when they are not needed and expensive exactly when they are. The design question is not how to make the lock faster but what work can be removed from behind it.