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:
- 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. - 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
| Operation | Approximate latency | Notes |
|---|---|---|
| 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 ns | Cache-to-cache transfer |
| Atomic on a line owned by a core on another socket | ~100–300 ns | Crosses the inter-socket link (UPI / Infinity Fabric) |
futex syscall round trip (no sleep) | ~100–300 ns | Kernel entry/exit, more with mitigations |
| Sleep + wake via futex (context switch both sides) | ~2–10 µs | Scheduler 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:
| State | Meaning | Can read locally? | Can write locally? |
|---|---|---|---|
| Modified | Only copy, dirty (differs from memory) | Yes | Yes |
| Exclusive | Only copy, clean | Yes | Yes (silently becomes M) |
| Shared | Other caches may hold copies, clean | Yes | No — must invalidate others first |
| Invalid | Not present / stale | No | No |
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:
| Generation | Kernel | Mechanism | Problem solved |
|---|---|---|---|
| Test-and-set | ≤ 2.6.24 | Single flag | — |
| Ticket spinlock | 2.6.25 (2008) | next and owner counters; take a ticket, wait until owner == my_ticket | FIFO fairness |
| Queued spinlock (qspinlock) | 4.2 (2015) | MCS-style: each waiter spins on its own per-CPU node | Ticket 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) printsBUG: sleeping function called from invalid contextwhen 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:
| API | Disables | Use when the lock is also taken from |
|---|---|---|
spin_lock() | Preemption | Only process context (or only one IRQ handler) |
spin_lock_bh() | Preemption + softirqs (bottom halves) | Softirq / tasklet / network RX path |
spin_lock_irq() | Preemption + local IRQs | Hard IRQ handler, and you know IRQs were enabled |
spin_lock_irqsave(lock, flags) | Preemption + local IRQs, saving prior state | Hard 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— unlocked1— locked, no waiters2— locked, maybe waiters (unlock must callFUTEX_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 type | Behaviour |
|---|---|
PTHREAD_MUTEX_NORMAL / default | The 0/1/2 futex lock above; no owner tracking |
PTHREAD_MUTEX_ADAPTIVE_NP | Spins 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_ERRORCHECK | Stores owner TID; relocking or unlocking from the wrong thread returns EDEADLK / EPERM |
PTHREAD_MUTEX_RECURSIVE | Owner TID plus a count |
PTHREAD_PRIO_INHERIT protocol | Uses 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_ROBUST | Kernel 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:
- Fast path:
CAS(state, 0, mutexLocked). One atomic. - 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 30PAUSEinstructions) hoping the holder releases. - 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:
- 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 withrcu_dereference(), use the data, and leave. - 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). - 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);
}
| Mutex | RW lock | Seqlock | RCU | |
|---|---|---|---|---|
| Reader cost | Atomic + possible sleep | Atomic on shared line | Two loads of seq, maybe retry | ~Zero |
| Readers block writers? | Yes | Yes | No | No |
| Writers block readers? | Yes | Yes | Readers retry | No |
| Can follow pointers | Yes | Yes | No | Yes |
| Write cost | Cheap | Cheap | Cheap | Copy + grace period (ms) |
| Memory overhead | None | None | None | Old 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
| Reordering | x86-64 (TSO) | ARMv8 / AArch64 | POWER |
|---|---|---|---|
| Load → Load | No | Yes | Yes |
| Load → Store | No | Yes | Yes |
| Store → Store | No | Yes | Yes |
| Store → Load (store buffer) | Yes | Yes | Yes |
| Atomic RMW acts as full barrier | Yes (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-64 | AArch64 | |
|---|---|---|
store(release) | mov | stlr |
load(acquire) | mov | ldar (or ldapr with RCpc, ARMv8.3) |
store(seq_cst) | xchg (or mov + mfence) | stlr |
fetch_add(relaxed) | lock xadd | ldadd (LSE) or ldxr/stxr loop |
atomic_thread_fence(seq_cst) | mfence | dmb 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):
| Primitive | Meaning |
|---|---|
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 = 42afterready = 1if onlyreadyis 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:
- Low-priority task L takes mutex M.
- High-priority task H wakes and blocks on M. Fine — L should finish quickly and release it.
- Medium-priority task M-task, which does not need the lock, becomes runnable. It preempts L, because it outranks L.
- 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
| Technique | How it works | Where you see it |
|---|---|---|
| Priority inheritance | While H waits on a lock held by L, L temporarily runs at H's priority, so M-task can't preempt it | PTHREAD_PRIO_INHERIT, Linux rt_mutex, FUTEX_LOCK_PI, PREEMPT_RT spinlocks |
| Priority ceiling | Each lock has a ceiling = highest priority of any task that uses it; holders run at the ceiling immediately | PTHREAD_PRIO_PROTECT, many RTOSes, Ada |
| Avoid sharing across priorities | Hand work to the other priority level through a lock-free queue | Audio threads, game engines |
| Disable preemption while holding | Kernel spinlocks — nothing can preempt the holder | Linux 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
| Failure | Symptom | Cause | Fix |
|---|---|---|---|
| Lock convoy | Throughput collapses under load; CPU low, latency high | Lock handed to a sleeping waiter who must be scheduled; meanwhile nobody can enter | Shorter critical sections; allow barging (newcomers can grab a free lock); shard the lock |
| Thundering herd | Burst of wakeups, all but one go back to sleep | FUTEX_WAKE(INT_MAX) or pthread_cond_broadcast on a single resource | Wake one; FUTEX_REQUEUE / FUTEX_CMP_REQUEUE to move waiters from condvar to mutex (glibc does this) |
| False sharing | Linear slowdown as threads are added despite no logical sharing | Independent hot fields share a cache line | Padding, per-CPU / per-thread data; perf c2c |
| Cache-line ping-pong on a hot lock | Lock acquisition time grows with core count even with tiny critical sections | Every acquire moves the line | Shard (striped locks), per-CPU counters, RCU, batching |
| Spinning on a preempted holder | High CPU, no progress, especially in VMs | Holder descheduled | Spin-then-park; paravirt spinlocks; never pure-spin in userspace |
| Missing barrier | Rare corrupted reads, only on ARM, only under load | Plain variables used as flags | Atomics with acquire/release; ThreadSanitizer |
| Sleeping in atomic context | BUG: scheduling while atomic | Blocking call under a kernel spinlock | Move allocation outside, use GFP_ATOMIC, use a mutex |
| IRQ self-deadlock | CPU hard-locks; NMI watchdog hard LOCKUP | Lock shared with IRQ handler taken without _irqsave | spin_lock_irqsave; lockdep |
| Priority inversion | High-priority task misses deadlines intermittently | Unbounded preemption of a lock holder | Priority inheritance / ceiling |
| Dead owner | All threads hang on a process-shared lock forever | Process holding a shared-memory mutex crashed | Robust 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
| Observation | Likely meaning |
|---|---|
futex calls ≈ 0, high CPU | Uncontended or pure spinning — check perf top for pause / spin loops |
Many FUTEX_WAIT with EAGAIN | Heavy contention with short hold times — a sharding candidate |
Few FUTEX_WAIT but long average wait | Long critical sections — something slow (I/O, allocation, logging) is under the lock |
High nonvoluntary_ctxt_switches | CPU oversubscription; lock holders preempted — convoys likely |
| Throughput flat or dropping as threads increase | Serialized 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"]
| Situation | Choose | Avoid |
|---|---|---|
| Request counters, metrics | Per-thread/per-CPU counters, or relaxed atomic | Mutex around count++ |
| Config reloaded occasionally, read per request | Atomic pointer to immutable snapshot (RCU-style) | RW lock taken per request |
| Short critical section in userspace | Your language's standard mutex (already spins briefly) | Hand-rolled spinlock |
| Kernel data touched by an IRQ handler | spin_lock_irqsave | mutex_lock, plain spin_lock |
| Threads at different priorities share a lock | Priority-inheritance mutex, or lock-free hand-off | Default mutex |
| Lock in shared memory between processes | PTHREAD_PROCESS_SHARED + PTHREAD_MUTEX_ROBUST | Non-robust lock (dead owner hangs everyone) |
| Hot path needs a lock and profiles show contention | Reduce hold time first, then shard, then consider lock-free | Jumping straight to lock-free |
The order of operations
- Remove sharing (per-thread state, message passing).
- Shrink the critical section (no I/O, allocation, or logging under the lock).
- Shard the lock.
- Switch to a read-optimized scheme (RCU/snapshot) if reads dominate.
- 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.