On this page

Kernel Synchronization: Spinlocks, Futexes & Memory Barriers

Every lock you have ever used — pthread_mutex_lock, Go's sync.Mutex, Java's synchronized, Rust's std::sync::Mutex — bottoms out in the same handful of mechanisms: one atomic CPU instruction, a cache-coherence protocol that makes that instruction meaningful across cores, a decision about whether to spin or sleep, and (when sleeping) a kernel wait queue reached through the futex system call.

The Mutex, Semaphore & Monitor page explains what these primitives guarantee. This page explains how they are built, why their performance varies by three orders of magnitude depending on contention, and what goes wrong when the abstractions leak: false sharing, reordered memory operations, priority inversion, and lock convoys.


Why This Exists

A single core running a single thread needs no synchronization. Two things broke that world:

  1. Preemption and interrupts. Even on one CPU, the scheduler can stop a thread halfway through counter++ (which is really load, add, store), and an interrupt handler can run in the middle of kernel code that touches the same data.
  2. Multiple cores with private caches. Each core has its own L1/L2 cache. Two cores can each hold a copy of the same memory location. Without a protocol to keep those copies consistent and a way to perform read-modify-write as one indivisible step, "the value of x" has no single meaning.

The classic demonstration:

// race.c — gcc -O2 -pthread race.c && ./a.out
#include <pthread.h>
#include <stdio.h>

static long counter = 0;

static void *worker(void *arg) {
    for (int i = 0; i < 10000000; i++)
        counter++;              // load, add, store: three steps, not one
    return NULL;
}

int main(void) {
    pthread_t a, b;
    pthread_create(&a, NULL, worker, NULL);
    pthread_create(&b, NULL, worker, NULL);
    pthread_join(a, NULL);
    pthread_join(b, NULL);
    printf("%ld\n", counter);   // expected 20000000
}
$ ./a.out
10372841
$ ./a.out
11906223

Roughly half the increments vanish: both threads load the same value, both add one, both store — one update overwrites the other. Everything below is machinery for preventing that, as cheaply as possible.


Layer 1: Atomic Instructions

Hardware provides a few instructions that read, modify and write a memory location with no other core able to observe or interfere with the intermediate state.

Compare-and-Swap (CAS)

CAS(addr, expected, new):
    atomically {
        if *addr == expected: *addr = new; return true
        else: return false
    }

On x86 this is LOCK CMPXCHG. The LOCK prefix tells the core to hold the cache line in exclusive state for the duration of the instruction, so no other core can read or write it in between. Related x86 atomics: LOCK XADD (fetch-and-add), XCHG (always implicitly locked), LOCK INC, LOCK BTS (bit test-and-set).

Load-Linked / Store-Conditional (LL/SC)

ARM, RISC-V, POWER and MIPS traditionally use a pair of instructions instead:

loop:
    LDXR   x1, [x0]        // load-exclusive: read and set a reservation on the line
    ADD    x1, x1, #1
    STXR   w2, x1, [x0]    // store-exclusive: succeeds only if nobody touched the line
    CBNZ   w2, loop        // w2 != 0 means the reservation was lost — retry

LL/SC is more general than CAS (it detects any intervening write, which sidesteps the ABA problem discussed in Lock-Free Data Structures) but it can fail spuriously — an interrupt, a context switch, or even a cache eviction can clear the reservation. That is why C++ and Rust expose both compare_exchange_weak (may fail spuriously, cheap in a loop on LL/SC machines) and compare_exchange_strong (loops internally).

ARMv8.1 added LSE atomics (CAS, LDADD, SWP) — single instructions that the interconnect can execute near the data. Under heavy contention on many-core ARM servers (Graviton, Ampere) LSE atomics are dramatically faster than LL/SC loops because they do not ping-pong a reservation between cores. Compile with -march=armv8.1-a or -moutline-atomics (GCC 10+ default on aarch64) to get them.

What Atomics Cost

OperationApproximate latencyNotes
Plain load hitting L1~1 ns (4 cycles)Baseline
Uncontended LOCK CMPXCHG / LOCK XADD~5–10 ns (18–25 cycles)Line already exclusive in this core's cache
Atomic on a line last written by another core, same socket~40–80 nsCache-to-cache transfer
Atomic on a line owned by a core on another socket~100–300 nsCrosses the inter-socket link (UPI / Infinity Fabric)
futex syscall round trip (no sleep)~100–300 nsKernel entry/exit, more with mitigations
Sleep + wake via futex (context switch both sides)~2–10 µsScheduler latency dominates

The headline: an atomic is cheap when uncontended and expensive only because of cache-line movement. That is why the next layer matters more than the instruction itself.


Layer 2: Cache Coherence and MESI

Caches work in units of cache lines — 64 bytes on x86 and most ARM cores (128 bytes on Apple M-series; Intel's adjacent-line prefetcher effectively pairs 64-byte lines into 128-byte chunks). Coherence protocols track each line's state in each core's cache. The textbook protocol is MESI:

StateMeaningCan read locally?Can write locally?
ModifiedOnly copy, dirty (differs from memory)YesYes
ExclusiveOnly copy, cleanYesYes (silently becomes M)
SharedOther caches may hold copies, cleanYesNo — must invalidate others first
InvalidNot present / staleNoNo

Real CPUs use extensions (Intel MESIF adds Forward, AMD MOESI adds Owned) but the mental model is the same: to write a line, a core must own it exclusively, which means invalidating every other copy.

sequenceDiagram
    participant C0 as Core 0 cache
    participant Bus as Interconnect
    participant C1 as Core 1 cache

    Note over C0,C1: Line X is Shared in both caches
    C0->>Bus: Read-For-Ownership X (wants to write)
    Bus->>C1: Invalidate X
    C1-->>Bus: Ack, X now Invalid
    Bus-->>C0: X granted Exclusive
    Note over C0: Write, X becomes Modified
    C1->>Bus: Read X
    Bus->>C0: Snoop X
    C0-->>C1: Supply dirty data, both now Shared

Every contended atomic or lock acquisition is this dance. When 32 cores hammer one lock word, that cache line bounces between cores continuously; each transfer is tens of nanoseconds and they serialize. This is why a single global atomic counter can be slower than a mutex-protected per-thread counter merged at the end.

False Sharing

Coherence is per line, not per variable. Two unrelated variables that happen to sit in the same 64-byte line will ping-pong as if they were one contended variable.

// false_sharing.c — gcc -O2 -pthread false_sharing.c
#include <pthread.h>
#include <stdio.h>

struct counters {
    long a;                     // written by thread 1
    // char pad[56];            // uncomment to put b on its own line
    long b;                     // written by thread 2
} __attribute__((aligned(64)));

static struct counters c;

static void *inc_a(void *x) { for (long i = 0; i < 500000000; i++) __atomic_fetch_add(&c.a, 1, __ATOMIC_RELAXED); return NULL; }
static void *inc_b(void *x) { for (long i = 0; i < 500000000; i++) __atomic_fetch_add(&c.b, 1, __ATOMIC_RELAXED); return NULL; }

int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, inc_a, NULL);
    pthread_create(&t2, NULL, inc_b, NULL);
    pthread_join(t1, NULL); pthread_join(t2, NULL);
    printf("%ld %ld\n", c.a, c.b);
}

Typical result on a modern x86 desktop (illustrative; your numbers will differ but the ratio is the point):

same line:      real 6.9s
padded (56B):   real 1.1s

No data is shared, yet the unpadded version runs about 6x slower. perf c2c is purpose-built for finding this:

$ perf c2c record -- ./false_sharing
$ perf c2c report --stdio
...
  Shared Data Cache Line Table
  #  Total  Rmt   Lcl   Store  Data address        Symbol
  0  41.2%  0.0%  97%   ...    0x404040            c
     Offset  Code address  Symbol
     0x0     inc_a+0x14    inc_a
     0x8     inc_b+0x14    inc_b      <- two writers, same line, different offsets

Fixes, by language:

// Go: pad explicitly. golang.org/x/sys/cpu exposes the line size.
type shard struct {
    n   atomic.Int64
    _   cpu.CacheLinePad
}
// Rust: crossbeam's CachePadded aligns to 128 bytes on x86-64 and aarch64
use crossbeam_utils::CachePadded;
let counters: Vec<CachePadded<AtomicU64>> = (0..n).map(|_| CachePadded::new(AtomicU64::new(0))).collect();
// Java: @Contended (needs -XX:-RestrictContended outside the JDK)
@jdk.internal.vm.annotation.Contended volatile long value;

The Linux kernel uses ____cacheline_aligned_in_smp and per-CPU variables (DEFINE_PER_CPU) for the same reason — per-CPU data is the ultimate false-sharing fix because each CPU's copy lives on its own lines.

Rule of thumb

Hot, independently-written fields — per-thread counters, the head and tail indexes of a ring buffer, a lock word and the data it protects when they are written by different threads — belong on separate cache lines. Read-mostly fields can share lines freely.


Layer 3: Spinlocks

A spinlock is the simplest lock you can build from an atomic: keep trying until it works.

// Test-and-set spinlock (naive)
typedef struct { atomic_int locked; } spinlock_t;

void spin_lock(spinlock_t *l) {
    while (atomic_exchange_explicit(&l->locked, 1, memory_order_acquire))
        ;   // every iteration is a write attempt: line bounces constantly
}

void spin_unlock(spinlock_t *l) {
    atomic_store_explicit(&l->locked, 0, memory_order_release);
}

The naive version is terrible under contention: every waiting core keeps issuing exclusive-ownership requests, flooding the interconnect. The standard fix is test-and-test-and-set — spin on a plain read (which lets the line sit in Shared state in every waiter's cache, generating no traffic) and only attempt the atomic when the lock looks free:

void spin_lock(spinlock_t *l) {
    for (;;) {
        if (!atomic_exchange_explicit(&l->locked, 1, memory_order_acquire))
            return;
        while (atomic_load_explicit(&l->locked, memory_order_relaxed))
            __builtin_ia32_pause();   // x86 PAUSE: saves power, yields to SMT sibling,
                                      // avoids memory-order mis-speculation on exit
    }
}

Fairness: Ticket and Queued Spinlocks

Test-and-test-and-set is unfair: when the lock is released, whichever core wins the race gets it, and cores closer to the previous owner tend to win repeatedly. Linux has gone through three generations:

GenerationKernelMechanismProblem solved
Test-and-set≤ 2.6.24Single flag—
Ticket spinlock2.6.25 (2008)next and owner counters; take a ticket, wait until owner == my_ticketFIFO fairness
Queued spinlock (qspinlock)4.2 (2015)MCS-style: each waiter spins on its own per-CPU nodeTicket locks still have every waiter spinning on one line; MCS gives each waiter a private line, so a release touches only the next waiter
graph LR
    L["lock word<br/>tail = CPU3"] --> N1
    subgraph "MCS queue of waiters"
        N1["CPU1 node<br/>spins on own flag"] --> N2["CPU2 node<br/>spins on own flag"] --> N3["CPU3 node<br/>spins on own flag"]
    end
    O["Owner CPU0"] -.->|"on unlock: set CPU1 flag"| N1

When Spinning Beats Sleeping

Sleeping costs a context switch on both sides — microseconds. Spinning costs CPU time for as long as the wait lasts. The break-even is simple:

Spin if the expected wait is shorter than the cost of sleeping and being woken (≈ 2× context switch, a few microseconds). Sleep otherwise.

Two more conditions must hold for spinning to make sense:

  • The lock holder must be running. Spinning while the holder is descheduled burns your whole time slice for nothing. On one CPU, spinning is always wrong. In virtual machines this becomes the lock-holder preemption problem — the hypervisor deschedules the vCPU holding the lock while other vCPUs spin. Linux mitigates this with paravirtual spinlocks (pv_qspinlock) and hardware pause-loop exiting (Intel PLE, AMD Pause Filter).
  • The holder must not sleep while holding it. In the kernel, you cannot call anything that might block (kmalloc(GFP_KERNEL), copy_from_user, mutex_lock) inside a spinlock. Kernel lock debugging (CONFIG_DEBUG_ATOMIC_SLEEP) prints BUG: sleeping function called from invalid context when you do.

IRQ-Safe Variants

Inside the kernel there is an extra hazard: an interrupt handler can run on the same CPU as code holding a spinlock. If the handler tries to take the same lock, it spins forever — the holder cannot run until the handler returns. Self-deadlock on one CPU.

sequenceDiagram
    participant T as Process context on CPU0
    participant L as spinlock dev_lock
    participant I as IRQ handler on CPU0

    T->>L: spin_lock - acquired
    Note over T: updating device ring
    I->>T: hardware interrupt preempts CPU0
    I->>L: spin_lock - already held
    Note over I: spins forever, holder can never resume

So the kernel offers variants that also disable local interrupts or softirqs:

APIDisablesUse when the lock is also taken from
spin_lock()PreemptionOnly process context (or only one IRQ handler)
spin_lock_bh()Preemption + softirqs (bottom halves)Softirq / tasklet / network RX path
spin_lock_irq()Preemption + local IRQsHard IRQ handler, and you know IRQs were enabled
spin_lock_irqsave(lock, flags)Preemption + local IRQs, saving prior stateHard IRQ handler, IRQ state unknown — the safe default
// Typical driver pattern
static DEFINE_SPINLOCK(rx_lock);

irqreturn_t my_irq(int irq, void *dev)
{
    spin_lock(&rx_lock);           // IRQs already off in a hard IRQ handler
    push_rx_descriptor(dev);
    spin_unlock(&rx_lock);
    return IRQ_HANDLED;
}

void my_poll(struct my_dev *dev)
{
    unsigned long flags;
    spin_lock_irqsave(&rx_lock, flags);   // keep the IRQ handler off this CPU
    drain_rx_ring(dev);
    spin_unlock_irqrestore(&rx_lock, flags);
}

The lockdep validator (CONFIG_PROVE_LOCKING) records every lock's usage context and reports inconsistent {IN-HARDIRQ-W} -> {HARDIRQ-ON-W} usage the first time it sees a lock taken in IRQ context and elsewhere with IRQs enabled — before the deadlock ever happens in production.

PREEMPT_RT changes the rules

With the real-time patch set (merged into mainline in Linux 6.12, 2024), most spinlock_t instances become sleeping, priority-inheriting rt_mutex locks so that high-priority tasks are never stuck behind a long non-preemptible section. Code that genuinely must spin uses raw_spinlock_t. If you write kernel code, "a spinlock never sleeps" is only true for raw spinlocks.


Layer 4: How a Userspace Mutex Actually Works

Userspace cannot disable interrupts and should not spin for long, so it needs a way to sleep. Before 2002, Linux userspace locks either spun or made a system call on every lock operation (System V semaphores) — slow even with zero contention. The futex ("fast userspace mutex"), introduced in Linux 2.5.7 and described by Franke, Russell and Kirkwood in Fuss, Futexes and Furwocks (Ottawa Linux Symposium, 2002), split the problem:

  • Fast path, in userspace: the lock is just a 32-bit integer in your process's memory. An uncontended lock or unlock is one atomic instruction. No system call.
  • Slow path, in the kernel: only when a thread actually needs to wait does it call futex(FUTEX_WAIT). The kernel keeps a hash table of wait queues keyed by the futex's address; it does not know or care what the integer means.

The kernel interface is tiny:

// "If *uaddr still equals val, put me to sleep until woken." (atomic check-and-sleep)
futex(uaddr, FUTEX_WAIT_PRIVATE, val, timeout, NULL, 0);

// "Wake up to n threads sleeping on uaddr."
futex(uaddr, FUTEX_WAKE_PRIVATE, n, NULL, NULL, 0);

The "if *uaddr still equals val" check is the crucial piece: it closes the race where the lock is released between your userspace check and your call into the kernel. The kernel re-reads the word under its own hash-bucket lock; if it changed, FUTEX_WAIT returns EAGAIN immediately and you retry.

A Correct Futex Mutex

Ulrich Drepper's paper Futexes Are Tricky walks through why the obvious designs are wrong. The standard correct design uses three states:

  • 0 — unlocked
  • 1 — locked, no waiters
  • 2 — locked, maybe waiters (unlock must call FUTEX_WAKE)
#include <linux/futex.h>
#include <stdatomic.h>
#include <sys/syscall.h>
#include <unistd.h>

static long futex(atomic_int *uaddr, int op, int val) {
    return syscall(SYS_futex, uaddr, op, val, NULL, NULL, 0);
}

void mutex_lock(atomic_int *m) {
    int c = 0;
    // Fast path: 0 -> 1, one CAS, no syscall
    if (atomic_compare_exchange_strong_explicit(m, &c, 1,
            memory_order_acquire, memory_order_relaxed))
        return;

    // Slow path: mark the lock contended (2) and sleep while it stays held
    if (c != 2)
        c = atomic_exchange_explicit(m, 2, memory_order_acquire);
    while (c != 0) {
        futex(m, FUTEX_WAIT_PRIVATE, 2);        // sleep only if *m is still 2
        c = atomic_exchange_explicit(m, 2, memory_order_acquire);
    }
}

void mutex_unlock(atomic_int *m) {
    // Fast path: 1 -> 0 means nobody was waiting, no syscall
    if (atomic_fetch_sub_explicit(m, 1, memory_order_release) != 1) {
        atomic_store_explicit(m, 0, memory_order_release);
        futex(m, FUTEX_WAKE_PRIVATE, 1);        // wake exactly one waiter
    }
}
stateDiagram-v2
    [*] --> Unlocked
    Unlocked --> Locked: CAS 0 to 1, userspace only
    Locked --> Unlocked: dec 1 to 0, userspace only
    Locked --> Contended: second locker swaps in 2, then FUTEX_WAIT
    Contended --> Contended: more lockers swap 2, FUTEX_WAIT
    Contended --> Unlocked: unlock sees 2, stores 0, FUTEX_WAKE 1
    Unlocked --> Contended: woken waiter swaps in 2

Note the woken waiter re-acquires by swapping in 2, not 1 — it cannot know whether other waiters remain, so it conservatively forces the next unlock to issue a wake. That costs at most one spurious FUTEX_WAKE and is what keeps the design correct.

Seeing It in strace

Uncontended locking produces zero futex syscalls. Contention produces pairs of WAIT and WAKE:

$ strace -f -e trace=futex ./contended_mutex 2>&1 | head
[pid 41231] futex(0x55d1c8a0e040, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>
[pid 41230] futex(0x55d1c8a0e040, FUTEX_WAKE_PRIVATE, 1) = 1
[pid 41231] <... futex resumed>)        = 0
[pid 41232] futex(0x55d1c8a0e040, FUTEX_WAIT_PRIVATE, 2, NULL) = -1 EAGAIN (Resource temporarily unavailable)

$ strace -c -f -e trace=futex ./contended_mutex
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
100.00    2.814431          12    231877     38114 futex

The EAGAIN lines are the race-closing check doing its job: the lock word changed between the userspace attempt and the kernel's re-check. A high futex count in strace -c or perf trace -s is one of the quickest signs of lock contention in a process.

_PRIVATE means the futex is only shared among threads of one process, so the kernel can key the hash table on the virtual address alone. Process-shared futexes (in shared memory, used by PTHREAD_PROCESS_SHARED mutexes — see IPC) must be keyed on the underlying physical page, which is slower.

glibc pthread_mutex

pthread_mutex_lock in glibc (NPTL) is essentially the design above, with options selected by mutex type:

Mutex typeBehaviour
PTHREAD_MUTEX_NORMAL / defaultThe 0/1/2 futex lock above; no owner tracking
PTHREAD_MUTEX_ADAPTIVE_NPSpins in userspace for a bounded number of iterations (tuned adaptively, cap set by the glibc.pthread.mutex_spin_count tunable, default 100) before sleeping
PTHREAD_MUTEX_ERRORCHECKStores owner TID; relocking or unlocking from the wrong thread returns EDEADLK / EPERM
PTHREAD_MUTEX_RECURSIVEOwner TID plus a count
PTHREAD_PRIO_INHERIT protocolUses FUTEX_LOCK_PI / FUTEX_UNLOCK_PI; the lock word holds the owner's TID so the kernel can boost the owner's priority
PTHREAD_MUTEX_ROBUSTKernel walks a per-thread robust list on thread death and sets FUTEX_OWNER_DIED, so the next locker gets EOWNERDEAD instead of hanging forever

Condition variables (pthread_cond_wait) are also futexes, as are pthread_rwlock, sem_wait, pthread_barrier and pthread_join. Linux 5.16 added futex_waitv (wait on several futexes at once), originally motivated by Windows WaitForMultipleObjects emulation in Wine/Proton.

Go's sync.Mutex

Go cannot let a blocked goroutine block an OS thread, so sync.Mutex parks goroutines in the Go runtime's own semaphore table (runtime/sema.go) and only the scheduler's idle OS threads end up in futex sleeps. The design has three tiers:

  1. Fast path: CAS(state, 0, mutexLocked). One atomic.
  2. Spinning: if the lock is held, the machine is multicore, GOMAXPROCS > 1, and at least one other P is running, spin briefly (up to 4 rounds of 30 PAUSE instructions) hoping the holder releases.
  3. Parking: enqueue on the semaphore and let the scheduler run something else.

Go 1.9 added starvation mode. In normal mode, a woken waiter competes with newly arriving goroutines that are already on-CPU — and usually loses, because they don't have to be scheduled first. If any waiter has waited more than 1 ms, the mutex switches to starvation mode: ownership is handed directly to the waiter at the front of the queue, newcomers do not spin or attempt to grab it, and they queue at the tail. It switches back when the queue drains or a waiter waited less than 1 ms.

// Measuring Go mutex contention: built in, no external tools
import (
    "net/http"
    _ "net/http/pprof"
    "runtime"
)

func main() {
    runtime.SetMutexProfileFraction(5)   // sample 1 in 5 contention events
    runtime.SetBlockProfileRate(1_000)   // record blocking events >= 1µs
    go http.ListenAndServe("localhost:6060", nil)
    // ...
}
$ go tool pprof http://localhost:6060/debug/pprof/mutex
(pprof) top
      flat  flat%   sum%        cum   cum%
    4.21s 81.33% 81.33%      4.21s 81.33%  sync.(*Mutex).Unlock
         0     0% 81.33%      4.21s 81.33%  main.(*Cache).Get

The mutex profile attributes delay to the unlocking stack — the code that held the lock while others waited — which is usually where you want to look.

Rust std::sync::Mutex

Since Rust 1.62, std::sync::Mutex on Linux is a 4-byte futex-based lock (previously it boxed a pthread_mutex_t), using the same 0/1/2 scheme with a short bounded spin. parking_lot provides a similar lock in one byte, with the wait queues in a global hash table — the same "lock word in user memory, queues elsewhere" idea as the kernel futex.

The Whole Picture

graph TD
    A["lock() called"] --> B{"CAS 0 to 1 succeeds?"}
    B -->|"yes (uncontended, ~10ns)"| Z["Critical section"]
    B -->|no| C{"Spin budget left<br/>and holder running?"}
    C -->|yes| D["PAUSE, re-read lock word"] --> B
    C -->|no| E["Swap in contended state"]
    E --> F["futex FUTEX_WAIT<br/>(enter kernel)"]
    F --> G{"Word still contended?"}
    G -->|"no: EAGAIN"| E
    G -->|yes| H["Sleep on hash-bucket wait queue"]
    H -->|"FUTEX_WAKE from unlocker<br/>(~2-10µs later)"| E

Beyond Mutexes: Read-Mostly Synchronization

Mutexes and reader-writer locks both write to a shared lock word on every acquisition — even readers. On a 64-core machine, a reader-writer lock taken by every request is a single cache line bouncing between 64 cores; readers do not block each other logically but they still serialize physically. The kernel's answer is to make readers write nothing shared.

Seqlocks

A seqlock protects small data that is read very often and written rarely, where readers can tolerate retrying. The writer increments a sequence counter before and after writing (so it is odd during a write); readers copy the data and retry if the counter was odd or changed.

// Writer (one at a time — writers still serialize on a spinlock)
write_seqlock(&lock);         // seq++ (now odd), smp_wmb()
data.sec  = new_sec;
data.nsec = new_nsec;
write_sequnlock(&lock);       // smp_wmb(), seq++ (now even)

// Reader: no writes to shared memory at all
unsigned seq;
do {
    seq  = read_seqbegin(&lock);        // spin while odd, then smp_rmb()
    sec  = data.sec;
    nsec = data.nsec;
} while (read_seqretry(&lock, seq));    // smp_rmb(), retry if seq changed

The best-known seqlock is the timekeeping data that clock_gettime() reads through the vDSO (see System Calls & Kernel Internals): millions of reads per second, written on every timer tick, readers entirely in userspace with no lock acquisition at all.

Limitations: readers can starve if writes are constant, and reader code must tolerate seeing torn data before the retry check — so you cannot follow pointers read under a seqlock (they may point to freed memory). Seqlocks are for small, plain-value data.

RCU (Read-Copy-Update)

RCU, merged in Linux 2.5.43 (2002) and developed largely by Paul McKenney, solves the pointer problem. It is the reason Linux scales routing tables, the dentry cache, module lists and thousands of other read-mostly structures to hundreds of cores.

The idea:

  1. Readers enter a read-side critical section (rcu_read_lock() — on a non-preemptible kernel this compiles to nothing, on preemptible kernels it bumps a per-task counter), dereference a pointer with rcu_dereference(), use the data, and leave.
  2. Writers never modify data in place. They copy the structure, modify the copy, and publish it with a single pointer store (rcu_assign_pointer(), which is a release store).
  3. The old version cannot be freed immediately — a reader might still be using it. The writer waits for a grace period: a point after which every CPU has passed through a quiescent state (context switch, idle, or user mode), proving no reader from before the publish can still be running. Then it frees the old copy.
sequenceDiagram
    participant R1 as Reader A
    participant P as global pointer
    participant W as Writer
    participant R2 as Reader B

    R1->>P: rcu_read_lock, load old v1
    W->>W: copy v1 to v2, modify v2
    W->>P: rcu_assign_pointer to v2
    R2->>P: rcu_read_lock, load new v2
    W->>W: synchronize_rcu - waits
    R1->>R1: rcu_read_unlock - done with v1
    Note over W: grace period ends, every CPU has passed a quiescent state
    W->>W: kfree v1
    R2->>R2: rcu_read_unlock
struct config { int timeout_ms; char name[32]; };
static struct config __rcu *cur_cfg;
static DEFINE_SPINLOCK(cfg_lock);       // writers still serialize among themselves

int get_timeout(void)                    // reader: no atomics, no shared writes
{
    int t;
    rcu_read_lock();
    t = rcu_dereference(cur_cfg)->timeout_ms;
    rcu_read_unlock();
    return t;
}

void set_timeout(int ms)                 // writer
{
    struct config *new = kmalloc(sizeof(*new), GFP_KERNEL), *old;
    spin_lock(&cfg_lock);
    old = rcu_dereference_protected(cur_cfg, lockdep_is_held(&cfg_lock));
    *new = *old;
    new->timeout_ms = ms;
    rcu_assign_pointer(cur_cfg, new);
    spin_unlock(&cfg_lock);
    synchronize_rcu();                   // or call_rcu() to free asynchronously
    kfree(old);
}
MutexRW lockSeqlockRCU
Reader costAtomic + possible sleepAtomic on shared lineTwo loads of seq, maybe retry~Zero
Readers block writers?YesYesNoNo
Writers block readers?YesYesReaders retryNo
Can follow pointersYesYesNoYes
Write costCheapCheapCheapCopy + grace period (ms)
Memory overheadNoneNoneNoneOld versions until grace period

Userspace has RCU too: liburcu (used by LTTng, Knot DNS, and GlusterFS). Garbage-collected languages get a version of it for free — publishing a new immutable map via atomic.Pointer[T] in Go or AtomicReference in Java and letting the GC reclaim the old one is RCU with the GC acting as the grace-period detector. Rust's arc-swap crate does the same with reference counting.


Memory Ordering and Barriers

Atomics make individual operations indivisible. They do not, by themselves, say anything about the order in which other cores see your other memory operations. Both the compiler and the CPU reorder:

  • Compiler: may hoist loads out of loops, sink stores, merge or eliminate accesses it can prove are redundant in single-threaded execution.
  • CPU: store buffers let a core keep executing after a store before it is visible to others; out-of-order execution issues loads early; weakly-ordered architectures may make stores visible in a different order than program order.

The Classic Bug: Message Passing

// Thread 1 (producer)        // Thread 2 (consumer)
data = 42;                     while (ready == 0) ;
ready = 1;                     print(data);   // can print 0!

With plain variables this can print 0 for three independent reasons: the compiler reorders the two stores; the compiler hoists the ready load out of the loop and spins forever; or (on ARM/POWER) the CPU makes the ready store visible before the data store, or the consumer's CPU executes the data load before the ready load.

x86 TSO vs ARM Weak Ordering

Reorderingx86-64 (TSO)ARMv8 / AArch64POWER
Load → LoadNoYesYes
Load → StoreNoYesYes
Store → StoreNoYesYes
Store → Load (store buffer)YesYesYes
Atomic RMW acts as full barrierYes (LOCK prefix)No (depends on ordering suffix)No

x86 is Total Store Order: the only reordering visible to other cores is that a core's later load can complete before its earlier store drains from the store buffer. That means acquire loads and release stores are plain MOV instructions on x86; only sequentially consistent stores need MFENCE (or an XCHG). ARM allows nearly everything, so ordering costs real instructions: LDAR (load-acquire), STLR (store-release), DMB ISH (full barrier).

This difference is a real-world source of bugs: code with missing barriers that "worked for years" on x86 fails when the same binary's source is compiled for Graviton or Apple Silicon. Apple's Rosetta 2 runs translated x86 code with a hardware TSO mode on the M-series cores precisely so that x86 programs relying on TSO keep working.

The Store-Buffer Litmus Test

Even x86 is not sequentially consistent:

Initially x = y = 0
Thread 1:  x = 1;  r1 = y;
Thread 2:  y = 1;  r2 = x;
Can r1 == 0 && r2 == 0?   On x86: YES.

Each core's store sits in its own store buffer while the subsequent load reads the old value from cache. Dekker's and Peterson's mutual exclusion algorithms are broken on x86 without an MFENCE between the store and the load. This is the one reordering TSO allows, and it is why seq_cst stores are more expensive than release stores on x86.

Acquire and Release

Instead of thinking in terms of full barriers, modern code expresses ordering on the operations themselves:

  • Release store: all memory operations before it in program order become visible before the store. "Publish."
  • Acquire load: no memory operation after it in program order can be performed before it. "Subscribe."
  • If an acquire load reads the value written by a release store, everything before the release happens-before everything after the acquire.
// Correct message passing, C11
atomic_int ready = 0;
int data;

// producer
data = 42;
atomic_store_explicit(&ready, 1, memory_order_release);

// consumer
while (!atomic_load_explicit(&ready, memory_order_acquire)) ;
assert(data == 42);    // guaranteed

What it compiles to:

x86-64AArch64
store(release)movstlr
load(acquire)movldar (or ldapr with RCpc, ARMv8.3)
store(seq_cst)xchg (or mov + mfence)stlr
fetch_add(relaxed)lock xaddldadd (LSE) or ldxr/stxr loop
atomic_thread_fence(seq_cst)mfencedmb ish

Every lock is an acquire on lock() and a release on unlock(). That is why a mutex makes the data it protects visible to the next holder — the futex code above uses exactly those orderings. The Lock-Free page covers the full ladder from relaxed to seq_cst for userspace code.

Linux Kernel Barrier Primitives

The kernel predates C11 atomics and has its own memory model (formalized as LKMM, in tools/memory-model):

PrimitiveMeaning
READ_ONCE(x) / WRITE_ONCE(x, v)Force a single, untorn, non-elided access; prevent compiler merging. No CPU ordering.
barrier()Compiler-only barrier: asm volatile("" ::: "memory")
smp_mb()Full barrier on SMP
smp_rmb() / smp_wmb()Read-read / write-write barrier
smp_load_acquire() / smp_store_release()Acquire load / release store
smp_mb__before_atomic()Upgrade a following non-returning atomic (e.g. atomic_inc) to be ordered
mb() / rmb() / wmb()Also order against device (MMIO / DMA) accesses, even on UP

Why volatile Isn't Enough

In C and C++, volatile was designed for memory-mapped device registers and setjmp/signal handlers. It tells the compiler "every access to this variable must actually happen, in the order written relative to other volatile accesses". It does not:

  • Make x++ atomic — it is still a separate load and store.
  • Order volatile accesses against non-volatile ones — the compiler may still move data = 42 after ready = 1 if only ready is volatile.
  • Emit any CPU barrier — on ARM the hardware can still reorder the stores.
volatile int ready;
int data;
data = 42;
ready = 1;     // compiler may legally sink "data = 42" below this; CPU may reorder too

Use _Atomic / std::atomic / AtomicXxx / sync/atomic. (Java and C# are different: there, volatile does have acquire/release semantics. The keyword means different things in different languages, which is half the confusion.)

Data races are undefined behaviour

In C, C++ and Rust, a data race (concurrent unsynchronized access where at least one is a write, to a non-atomic variable) is undefined behaviour — not merely "you might read a stale value." The compiler is allowed to assume it never happens, which is how it justifies hoisting the ready load out of the spin loop. Go's memory model is gentler (races on word-sized values give you some value that was written), but go test -race will still flag it, and races on interfaces, slices and maps can corrupt memory.


Priority Inversion

Priority-based schedulers promise that the highest-priority runnable task runs. Locks break that promise:

  1. Low-priority task L takes mutex M.
  2. High-priority task H wakes and blocks on M. Fine — L should finish quickly and release it.
  3. Medium-priority task M-task, which does not need the lock, becomes runnable. It preempts L, because it outranks L.
  4. H is now waiting on L, which is waiting on M-task — for as long as M-task runs. H's effective priority is below M-task's.
gantt
    title Unbounded priority inversion
    dateFormat X
    axisFormat %s
    section High
    blocked on mutex     :crit, h1, 2, 10
    runs                 :h2, 10, 12
    section Medium
    runs, preempts Low   :m1, 3, 9
    section Low
    holds mutex          :l1, 0, 3
    preempted holding it :crit, l2, 3, 9
    releases             :l3, 9, 10

Mars Pathfinder, 1997

The best-documented case. A few days after landing on 4 July 1997, the Pathfinder lander began resetting itself repeatedly, losing data each time. JPL engineers reproduced it on a ground replica. As Glenn Reeves, the flight software lead, described in his widely circulated account (relayed by Mike Jones in What really happened on Mars?, December 1997):

  • The VxWorks system had an "information bus" — a shared memory area protected by a mutex.
  • A high-priority bus management task moved data through it frequently.
  • A low-priority meteorological data task occasionally took the mutex to publish weather data.
  • A medium-priority, long-running communications task did not need the mutex.
  • When the communications task preempted the meteorological task while it held the mutex, the bus management task was blocked long enough that a watchdog noticed a scheduled bus cycle had not completed — and reset the whole system.

The mutex had been created with priority inheritance disabled. Because VxWorks included a C interpreter that could be invoked remotely, the team uploaded a small patch that flipped the mutex's initialization parameter to enable priority inheritance. The resets stopped.

The Fixes

TechniqueHow it worksWhere you see it
Priority inheritanceWhile H waits on a lock held by L, L temporarily runs at H's priority, so M-task can't preempt itPTHREAD_PRIO_INHERIT, Linux rt_mutex, FUTEX_LOCK_PI, PREEMPT_RT spinlocks
Priority ceilingEach lock has a ceiling = highest priority of any task that uses it; holders run at the ceiling immediatelyPTHREAD_PRIO_PROTECT, many RTOSes, Ada
Avoid sharing across prioritiesHand work to the other priority level through a lock-free queueAudio threads, game engines
Disable preemption while holdingKernel spinlocks — nothing can preempt the holderLinux non-RT kernels
pthread_mutexattr_t attr;
pthread_mutexattr_init(&attr);
pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);   // uses FUTEX_LOCK_PI
pthread_mutex_init(&m, &attr);

Priority inversion is not just a real-time-system problem. It shows up anywhere priorities differ: niced background jobs holding a lock that a latency-sensitive thread needs, a low-priority GC thread holding a heap lock, or Android's UI thread blocked on a binder call to a low-priority service (Android uses binder priority inheritance for exactly this reason). See Real-Time Systems for scheduling theory and Deadlocks for the related failure where the wait never ends at all.


Failure Modes

FailureSymptomCauseFix
Lock convoyThroughput collapses under load; CPU low, latency highLock handed to a sleeping waiter who must be scheduled; meanwhile nobody can enterShorter critical sections; allow barging (newcomers can grab a free lock); shard the lock
Thundering herdBurst of wakeups, all but one go back to sleepFUTEX_WAKE(INT_MAX) or pthread_cond_broadcast on a single resourceWake one; FUTEX_REQUEUE / FUTEX_CMP_REQUEUE to move waiters from condvar to mutex (glibc does this)
False sharingLinear slowdown as threads are added despite no logical sharingIndependent hot fields share a cache linePadding, per-CPU / per-thread data; perf c2c
Cache-line ping-pong on a hot lockLock acquisition time grows with core count even with tiny critical sectionsEvery acquire moves the lineShard (striped locks), per-CPU counters, RCU, batching
Spinning on a preempted holderHigh CPU, no progress, especially in VMsHolder descheduledSpin-then-park; paravirt spinlocks; never pure-spin in userspace
Missing barrierRare corrupted reads, only on ARM, only under loadPlain variables used as flagsAtomics with acquire/release; ThreadSanitizer
Sleeping in atomic contextBUG: scheduling while atomicBlocking call under a kernel spinlockMove allocation outside, use GFP_ATOMIC, use a mutex
IRQ self-deadlockCPU hard-locks; NMI watchdog hard LOCKUPLock shared with IRQ handler taken without _irqsavespin_lock_irqsave; lockdep
Priority inversionHigh-priority task misses deadlines intermittentlyUnbounded preemption of a lock holderPriority inheritance / ceiling
Dead ownerAll threads hang on a process-shared lock foreverProcess holding a shared-memory mutex crashedRobust mutexes (EOWNERDEAD → pthread_mutex_consistent)

Measuring Lock Contention

First Look

# How much time is going to futex waits?
$ perf trace -s -p $(pidof myserver) -- sleep 10
 myserver (41230), 1281904 events, 99.8%
   syscall            calls  errors  total       min       avg       max
                                     (msec)    (msec)    (msec)    (msec)
   --------------- -------- ------ -------- --------- --------- ---------
   futex             412873  61204 38121.334     0.001     0.092    41.880
   epoll_wait         51290      0  9120.120     0.000     0.178    10.003

# Voluntary context switches climbing is another tell (each futex sleep is one)
$ grep ctxt /proc/$(pidof myserver)/status
voluntary_ctxt_switches:        8812001
nonvoluntary_ctxt_switches:     10234
$ pidstat -w -t -p $(pidof myserver) 1

perf lock

perf lock contention (perf 6.x, BPF-based with -b) aggregates contention by lock and caller, for both kernel locks and, with -u/user-space options on newer versions, pthread mutexes:

$ sudo perf lock contention -a -b -- sleep 5
 contended   total wait     max wait     avg wait         type   caller

     18342    412.90 ms      2.31 ms     22.51 us     spinlock   __queue_work+0x2b4
      6120    188.07 ms    911.20 us     30.73 us        mutex   ext4_buffered_write_iter+0x6e
      2201     40.11 ms    204.53 us     18.22 us      rwsem:R   do_user_addr_fault+0x1a8

On kernels built with CONFIG_LOCK_STAT, /proc/lock_stat gives per-lock-class contention counts and hold times, at a significant runtime cost — a debugging kernel feature, not something to leave on.

Off-CPU Flame Graphs

CPU flame graphs show where threads run. Lock contention is time spent not running. Off-CPU analysis records the stack at the moment a thread blocks and the duration until it runs again (Brendan Gregg's technique, implemented in bcc's offcputime):

$ sudo offcputime-bpfcc -df -p $(pidof myserver) 30 > out.stacks
$ ./flamegraph.pl --color=io --title="Off-CPU" --countname=us < out.stacks > offcpu.svg

In the resulting SVG, a wide tower ending in futex_wait_queue → do_futex → __lll_lock_wait → pthread_mutex_lock → Cache::get says exactly which lock is costing wall-clock time and how much. Pair it with the on-CPU flame graph of the holder to see what it is doing while others wait.

For the JVM, async-profiler -e lock profiles monitor contention; for Go, the mutex and block profiles shown earlier; for .NET, dotnet-counters exposes monitor-lock-contention-count.

Reading the Numbers

ObservationLikely meaning
futex calls ≈ 0, high CPUUncontended or pure spinning — check perf top for pause / spin loops
Many FUTEX_WAIT with EAGAINHeavy contention with short hold times — a sharding candidate
Few FUTEX_WAIT but long average waitLong critical sections — something slow (I/O, allocation, logging) is under the lock
High nonvoluntary_ctxt_switchesCPU oversubscription; lock holders preempted — convoys likely
Throughput flat or dropping as threads increaseSerialized on something — run perf c2c and off-CPU analysis

Decision Guide

graph TD
    A["Shared mutable state?"] -->|no| Z0["No synchronization. Prefer this."]
    A -->|yes| B{"Single word, simple update?<br/>(counter, flag, pointer swap)"}
    B -->|yes| Z1["Atomic with acquire/release<br/>(relaxed for pure counters)"]
    B -->|no| C{"Reads vastly outnumber writes?"}
    C -->|yes| D{"Small plain values,<br/>readers can retry?"}
    D -->|yes| Z2["Seqlock"]
    D -->|no| Z3["RCU / atomic pointer swap<br/>of immutable snapshot"]
    C -->|no| E{"Critical section tiny<br/>and holder never sleeps?"}
    E -->|"yes, in kernel"| Z4["Spinlock (irqsave if IRQ shares it)"]
    E -->|"yes, userspace"| Z5["Adaptive mutex<br/>(spin briefly, then futex)"]
    E -->|no| Z6["Plain mutex<br/>(futex-backed)"]
    Z6 --> F{"Contended on many cores?"}
    F -->|yes| Z7["Shard the lock, per-CPU data,<br/>or batch work outside the lock"]
SituationChooseAvoid
Request counters, metricsPer-thread/per-CPU counters, or relaxed atomicMutex around count++
Config reloaded occasionally, read per requestAtomic pointer to immutable snapshot (RCU-style)RW lock taken per request
Short critical section in userspaceYour language's standard mutex (already spins briefly)Hand-rolled spinlock
Kernel data touched by an IRQ handlerspin_lock_irqsavemutex_lock, plain spin_lock
Threads at different priorities share a lockPriority-inheritance mutex, or lock-free hand-offDefault mutex
Lock in shared memory between processesPTHREAD_PROCESS_SHARED + PTHREAD_MUTEX_ROBUSTNon-robust lock (dead owner hangs everyone)
Hot path needs a lock and profiles show contentionReduce hold time first, then shard, then consider lock-freeJumping straight to lock-free

The order of operations

  1. Remove sharing (per-thread state, message passing).
  2. Shrink the critical section (no I/O, allocation, or logging under the lock).
  3. Shard the lock.
  4. Switch to a read-optimized scheme (RCU/snapshot) if reads dominate.
  5. Only then consider lock-free algorithms — they are harder to get right than all the above combined.

Interview Questions

"Why is an uncontended mutex lock so cheap?" Because modern mutexes are futex-based: the lock word lives in user memory and an uncontended acquire is a single atomic compare-and-swap (~10–20 ns) with no system call. The kernel is only involved when a thread must actually sleep.

"What does the futex WAIT value argument protect against?" The lost-wakeup race. Between checking the lock in userspace and sleeping in the kernel, the holder might unlock and issue its wake — which would be missed. FUTEX_WAIT atomically re-checks that the word still has the expected value under the kernel's hash-bucket lock and refuses to sleep (EAGAIN) if it changed.

"When would you use a spinlock instead of a mutex?" When the critical section is shorter than the cost of a sleep/wake cycle (a few microseconds), the holder is guaranteed to be running (not preemptible, or kernel code with preemption disabled), and — in the kernel — when you are in a context that cannot sleep at all, such as an interrupt handler. In userspace, almost never directly; standard mutexes already spin briefly before sleeping.

"What is false sharing and how do you detect it?" Independent variables written by different cores that share a cache line, causing coherence traffic as if they were one contended variable. Detect with perf c2c; fix with padding/alignment to cache-line size or per-thread data.

"Why doesn't volatile make code thread-safe in C?" It prevents the compiler from eliding or reordering accesses to that variable relative to other volatile accesses, but provides no atomicity for read-modify-write, no ordering with respect to non-volatile accesses, and emits no CPU barriers — so weakly-ordered CPUs can still reorder. Use atomics with acquire/release.

"Explain priority inversion and how Pathfinder fixed it." A high-priority task blocks on a lock held by a low-priority task, which is preempted by a medium-priority task, delaying the high-priority task indefinitely. On Pathfinder, this tripped a watchdog and reset the lander. JPL uploaded a patch enabling priority inheritance on the mutex, so the low-priority holder was boosted while the high-priority task waited.

"How can RCU readers have zero overhead?" Readers do not write any shared memory. Writers publish new versions with a release store and defer freeing old versions until a grace period has elapsed — every CPU has passed through a quiescent state such as a context switch — which proves no pre-existing reader still holds a reference.