CMD Guide
Home › Concurrency › Concurrency Foundations

How a Lock Is Built — From Test-and-Set to Futex to Spin-then-Park

A lock feels like an abstraction — lock(), do work, unlock() — but underneath there is no magic keeper of order. There is a single word of memory and a promise from the CPU that one instruction can read-modify-write that word without any other core interleaving. Everything else — spinning, queueing, parking, fairness, the near-zero cost of an uncontended acquire — is engineering built on top of that one atomic instruction plus a way to wait.

This page builds the ladder rung by rung. We start at the silicon (test-and-set, compare-and-swap), watch the naive spinlock melt a multicore machine, fix it with test-and-test-and-set and backoff, remove the cache traffic entirely with queue locks, then confront the real problem: pure spinning burns a CPU while the lock holder is asleep. The answer — the futex — is the reason an uncontended std::mutex, pthread_mutex, or Go sync.Mutex costs a handful of nanoseconds and touches the kernel exactly zero times.

The two questions we are answering

Rung 0 — The hardware primitive: an atomic read-modify-write

The problem a lock solves is that if (free) { free = false; } is three separate operations — read, test, write — and two cores can both read "free" before either writes "false". Both think they won. The CPU fixes this by offering instructions that fuse read-modify-write into one indivisible step that the cache coherence protocol serializes.

Two matter for locks. Test-and-set (TAS): atomically write 1 to a word and return its old value. On x86 this is LOCK XCHG (exchange register with memory; the LOCK prefix makes it atomic). Compare-and-swap (CAS): atomically, "if the word equals expected, store new and report success; else report the actual value." On x86 this is LOCK CMPXCHG. CAS is strictly more expressive — it lets you build lock-free stacks, counters, and the futex fast path — but for a plain mutual-exclusion lock, TAS is enough.

// The primitives, as the CPU exposes them (C11 atomics over the hardware op).

// test-and-set: atomically set *p = 1, return the OLD value.
// Compiles to LOCK XCHG on x86-64.
int test_and_set(atomic_int *p) {
    return atomic_exchange(p, 1);   // returns previous value: 0 = we got it, 1 = someone held it
}

// compare-and-swap: if *p == expected, set *p = desired and return true;
// else write the actual value back into *expected and return false.
// Compiles to LOCK CMPXCHG on x86-64.
bool compare_and_swap(atomic_int *p, int *expected, int desired) {
    return atomic_compare_exchange_strong(p, expected, desired);
}

Why is this atomic and not merely fast? Because of cache coherence (MESI). To write a line, a core must own it Exclusive/Modified — it broadcasts a Read-For-Ownership (RFO) that invalidates every other core's copy. The LOCK prefix guarantees that for the duration of the read-modify-write, no other core can touch that line. That guarantee is the entire foundation of every lock below. It is also the source of every scaling problem we are about to hit: writes force cache lines to move between cores, and moving a cache line between cores is expensive.

Rung 1 — The naive spinlock (TAS): correct, then it melts

The simplest lock: loop calling test-and-set until it returns 0 (the word was free and is now ours).

// TAS spinlock — CORRECT but pathological under contention.
typedef struct { atomic_int locked; } spinlock;   // 0 = free, 1 = held

void spin_lock(spinlock *L) {
    while (atomic_exchange(&L->locked, 1) == 1) {
        // returned 1 → someone else holds it → keep hammering
        // NOTE: every iteration is a WRITE (xchg), even while we fail
    }
}

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

Correctness is fine. Scaling is a disaster. Every iteration of the loop executes xchg, which is a write, which demands the cache line in Exclusive state, which issues an RFO that invalidates the line in every other core's cache. With N cores spinning, the single lock word ping-pongs between caches continuously — the "cache line bouncing" storm. Worse, the core actually holding the lock now has to fight the spinners just to write the word to release it. Throughput doesn't plateau under contention; it collapses. This is the contention meltdown, and it is entirely caused by spinning with a write.

Rung 2 — Test-and-test-and-set (TTAS) + exponential backoff

The fix is to stop writing while you wait. In TTAS the spin loop is a plain read; you only fire the atomic when the read says the lock looks free. A read only needs the cache line in Shared state — many cores can hold a Shared copy simultaneously, so spinning generates no coherence traffic at all once every spinner has cached the line. The RFO storm only happens at the moment of an actual attempt.

// TTAS: test (cheap read) then test-and-set (the atomic), plus exponential backoff.
void ttas_lock(spinlock *L) {
    int backoff = 1;
    for (;;) {
        // TEST: spin on a plain load — line stays Shared, no bus traffic.
        while (atomic_load_explicit(&L->locked, memory_order_relaxed) == 1)
            cpu_relax();                 // x86 PAUSE: hint to the pipeline, cheap

        // Looks free — now TEST-AND-SET (the only write).
        if (atomic_exchange(&L->locked, 1) == 0)
            return;                      // acquired

        // Lost the race; back off to spread out the retries and cut collisions.
        for (int i = 0; i < backoff; i++) cpu_relax();
        if (backoff < 1024) backoff *= 2;
    }
}

The improvement is dramatic: instead of N cores each issuing writes every iteration, they issue writes only when the lock is released and they contend for it. The PAUSE instruction (cpu_relax()) tells the CPU this is a spin-wait, reducing power and easing memory-order speculation. Exponential backoff addresses the residual thundering herd — when the lock frees, all spinners attempt at once; backoff staggers the retries so they don't all collide again. TTAS is still not fair (whoever's cache is warmest tends to win), and a released lock still causes one invalidation burst, but it turns "meltdown" into "acceptable under moderate contention."

Rung 3 — Queue locks (MCS / CLH): everyone spins locally

TTAS still shares one word, so a release still invalidates every spinner's cached copy at once. Queue locks eliminate even that. The idea (Mellor-Crummey & Scott, 1991): form an explicit FIFO queue of waiters, where each waiter allocates its own node and spins on a flag inside its own node. Because no two waiters spin on the same memory, there is zero coherence traffic during the wait, and release touches exactly one cache line — the successor's.

// MCS lock. Each thread supplies its own node (usually stack-local).
typedef struct mcs_node {
    _Atomic(struct mcs_node *) next;
    atomic_int                 locked;   // 1 = must wait, 0 = go
} mcs_node;

typedef struct { _Atomic(mcs_node *) tail; } mcs_lock;   // tail = last in line

void mcs_lock_acquire(mcs_lock *L, mcs_node *self) {
    self->next = NULL;
    self->locked = 1;
    // Atomically append self to the queue; get the previous tail.
    mcs_node *pred = atomic_exchange(&L->tail, self);   // one XCHG
    if (pred != NULL) {                 // someone is ahead of us
        atomic_store(&pred->next, self); // tell predecessor to hand off to us
        while (atomic_load(&self->locked) == 1)   // SPIN ON OUR OWN NODE
            cpu_relax();                //   → line stays local, no bouncing
    }
    // pred == NULL → we are the head, lock is ours immediately.
}

void mcs_lock_release(mcs_lock *L, mcs_node *self) {
    mcs_node *succ = atomic_load(&self->next);
    if (succ == NULL) {                 // no known successor
        mcs_node *expected = self;      // try to close the queue
        if (atomic_compare_exchange_strong(&L->tail, &expected, NULL))
            return;                     // we were last; done
        while ((succ = atomic_load(&self->next)) == NULL)  // successor mid-enqueue
            cpu_relax();                //   wait for it to link itself
    }
    atomic_store(&succ->locked, 0);     // release: touch ONLY successor's line
}

MCS gives strict FIFO fairness (no starvation, no lucky-cache winner) and near-constant traffic regardless of core count — the property that made it the basis for the Linux kernel's qspinlock. CLH is a close cousin where each waiter spins on its predecessor's node instead of its own, which is simpler and works better on cache-coherent-only (non-NUMA-local) machines but spins on remote memory. The cost of queue locks: you must supply a node, release has that awkward mid-enqueue race to handle, and — like all spin locks — they still burn CPU while waiting. Which brings us to the real problem.

Rung 4 — The blocking problem, and the futex

Every lock so far spins. Spinning is a bet: "the holder will release so soon that burning cycles is cheaper than going to sleep." On a multicore box with a two-instruction critical section, that bet wins. But if the lock holder gets descheduled by the OS — its timeslice ends, or it's preempted — the spinners now burn entire timeslices waiting for a thread that isn't even running. On a single core it's catastrophic: the spinner can't yield to the holder, so it spins uselessly until preempted. Spinning must eventually give way to blocking: tell the OS "put me to sleep until this word changes."

Naively, blocking means a syscall on every acquire and release to register/wake a waiter in the kernel — even when there's no contention and no one to wait for. That syscall (hundreds of nanoseconds) would dominate the lock cost. The futex (fast userspace mutex, Linux 2.6) is the insight that makes blocking cheap: keep the lock word in userspace, and only enter the kernel when a thread actually has to wait or has to wake someone.

The kernel provides two operations on a userspace address:

The crucial part: the kernel knows nothing about the lock when it is uncontended. No kernel object is allocated, no syscall is made. The kernel only materializes a wait-queue for that address when some thread calls FUTEX_WAIT.

// Futex-backed mutex — the classic 3-state design (Drepper, "Futexes Are Tricky").
// State: 0 = unlocked, 1 = locked no waiters, 2 = locked WITH waiters.
atomic_int m;   // the whole lock is one int

void mutex_lock(atomic_int *m) {
    int c = 0;
    // FAST PATH: try to CAS 0 → 1. Uncontended → done, NO SYSCALL.
    if (atomic_compare_exchange_strong(m, &c, 1))
        return;                         // c was 0; we own it. This is the common case.

    // SLOW PATH: contended.
    if (c != 2)                         // if state was 1, mark it 2 (waiters present)
        c = atomic_exchange(m, 2);
    while (c != 0) {                    // while still held by someone...
        futex(m, FUTEX_WAIT, 2);        //   sleep until it's not 2 (SYSCALL, only here)
        c = atomic_exchange(m, 2);      //   woke up: try to grab, re-marking "waiters"
    }
}

void mutex_unlock(atomic_int *m) {
    // FAST PATH: if state was 1 (no waiters), just drop to 0. NO SYSCALL.
    if (atomic_fetch_sub(m, 1) != 1) {  // returns old value; if it was 2 there are waiters
        atomic_store(m, 0);
        futex(m, FUTEX_WAKE, 1);        //   wake ONE waiter (SYSCALL, only when waiters exist)
    }
}

Trace the two worlds. Uncontended lock: one CAS 0→1, done — a few nanoseconds, entirely in userspace. Uncontended unlock: one atomic decrement 1→0, done. Zero syscalls on the entire critical section. This is why an uncontended lock is nearly free: the fast path is literally one atomic instruction, and the kernel is never involved. The syscall only appears on the branch where a thread genuinely could not proceed and had to sleep — exactly where paying for it is unavoidable anyway. The "3" state (waiters bit) exists so unlock can skip the FUTEX_WAKE syscall when it can prove no one is waiting.

Rung 5 — Adaptive spin-then-park: what real mutexes do

Pure blocking has its own waste: if the holder releases 50 nanoseconds after you failed the CAS, going through FUTEX_WAIT (syscall + context switch out, then a wakeup syscall + context switch back in — easily 1-2 microseconds) is far more expensive than just spinning for those 50 ns. So production mutexes are adaptive: on the slow path, spin a bounded number of times first (betting the holder releases soon), and only park (futex_wait) if the spin budget runs out. This captures the best of both: near-zero latency for short critical sections, and no CPU waste for long ones.

// Adaptive slow path (conceptual — glibc/pthreads and others do a version of this).
void mutex_lock_adaptive(atomic_int *m) {
    int c = 0;
    if (atomic_compare_exchange_strong(m, &c, 1)) return;   // fast path

    for (int spins = 0; spins < SPIN_LIMIT; spins++) {      // BET: holder releases soon
        if (atomic_load(m) == 0) {
            c = 0;
            if (atomic_compare_exchange_strong(m, &c, 1)) return;   // grabbed during spin
        }
        cpu_relax();
    }
    // Spin budget exhausted → holder is likely descheduled → PARK.
    slow_path_park(m);   // the futex_wait loop from Rung 4
}

JVM lock inflation is the same ladder wearing object-oriented clothes. Every Java object has a lock, but paying full weight for locks that are rarely contended is wasteful, so HotSpot escalates lazily: biased locking (the object is tagged with one thread's ID; that thread reacquires with no atomic at all — now largely removed/deprecated as multicore made the rebias cost dominate) → thin lock (an uncontended CAS on the object header's mark word, exactly Rung 4's fast path) → fat lock (on real contention, the JVM "inflates" the lock, allocating a heavyweight OS-monitor / ObjectMonitor that parks threads via the OS). Biased → thin → fat is JVM-speak for "no-atomic → CAS → OS-park."

Go's sync.Mutex runs the same play in the runtime. The fast path is a single CAS on the mutex's state word (goroutine-level, no OS thread involved). On contention it spins a few times (runtime_canSpin, only when it makes sense — multicore, holder running), then parks the goroutine on a runtime semaphore (runtime_SemacquireMutex), which is itself futex-backed at the OS-thread layer. Go adds a starvation mode: if a goroutine waits more than 1 ms, the mutex flips from "normal" (barging — a newly arriving goroutine can steal the lock, which is throughput-optimal but can starve the queue) to "starvation" (strict FIFO handoff directly to the head waiter), then flips back once the backlog clears. It's the fairness-vs-throughput knob made explicit.

A traced two-thread contention

Two threads, T1 and T2, a futex-backed mutex, one shared word m.

UNCONTENDED (T1 alone):
  T1  mutex_lock:   CAS m 0→1  ✓            cost: 1 atomic, ~10-20 ns, NO syscall
  T1  <critical section>
  T1  mutex_unlock: dec m 1→0, old==1 ✓      cost: 1 atomic, no waiters → NO syscall
  Total kernel crossings: 0

CONTENDED (T2 arrives while T1 holds it):
  T1  holds m (m==1)
  T2  mutex_lock:   CAS m 0→1  ✗ (got 1)     cost: 1 atomic (failed)
  T2  (adaptive)    spin SPIN_LIMIT times... T1 still in CS → budget exhausted
  T2  set m→2 (mark waiters)                 cost: 1 atomic
  T2  futex(m, WAIT, 2)  → sleeps            cost: SYSCALL + context switch OUT (~1 µs)
  ---- T1 finishes ----
  T1  mutex_unlock: dec m 2→1, old==2 → waiters! store m=0; futex(m, WAKE, 1)
                                             cost: 1 atomic + SYSCALL (wake)
  T2  wakes, CAS/exchange m→2, sees free, proceeds
                                             cost: context switch IN (~1 µs) + 1 atomic
  Kernel crossings: exactly 2 (one WAIT, one WAKE) — paid only because a thread truly slept.

The asymmetry is the whole point. The uncontended path is a couple of cache-local atomic instructions. The kernel — with its microsecond-scale syscalls and context switches — shows up only on the branch where a thread had nothing to do but sleep, which is exactly when that cost is amortized against real idle time rather than wasted.

Pitfalls

Selection & trade-offs

The through-line: spinning trades CPU to avoid the kernel; parking trades a syscall to free the CPU. TAS→TTAS→MCS optimize the spinning side (less coherence traffic, more fairness); the futex optimizes the crossing between the two (stay in userspace until you genuinely must sleep); adaptive spin-then-park picks the crossover point dynamically. Every real mutex you use is some tuning of exactly these axes.

Takeaways

Citations

🤖 Don't fully get this? Learn it with Claude

Stuck on How a Lock Is Built — From Test-and-Set to Futex to Spin-then-Park? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **How a Lock Is Built — From Test-and-Set to Futex to Spin-then-Park** (Concurrency) and want to truly understand it. Explain How a Lock Is Built — From Test-and-Set to Futex to Spin-then-Park from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **How a Lock Is Built — From Test-and-Set to Futex to Spin-then-Park** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **How a Lock Is Built — From Test-and-Set to Futex to Spin-then-Park** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **How a Lock Is Built — From Test-and-Set to Futex to Spin-then-Park** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Testing & Verifying Concurrent CodPriority Inversion — the Bug That →