You have already built a lock from an atomic read-modify-write: spin on a compare-and-swap until the word flips from free to held. That lock is correct. It is also, on a real 64-core server, a performance catastrophe. This lesson is about the gap between a lock that works and a lock that scales — the gap the Linux kernel spent two decades closing, and the reason your kernel's mutex is a small state machine and not a one-line spin loop.

We climb a ladder of four designs. The naive test-and-set spinlock; the test-and-test-and-set refinement; the ticket lock that adds fairness; and the MCS queue lock, where each waiter spins on its own cache line — the scalability fix that underlies modern kernel locks. Then we lift to user space with the futex: fast in the common case, kernel-assisted only when threads actually collide.

First question: spin or block?

Before choosing which lock, choose what kind. A spinlock busy-waits — the waiting core loops, burning cycles, until the lock frees. A blocking lock (a mutex) instead parks the waiting thread: the scheduler runs someone else and wakes the waiter later. The trade is stark and it is all about the ratio of wait time to context-switch cost.

Parking and waking a thread costs a couple of context switches — call it a few microseconds. If the lock is held for only a hundred nanoseconds, blocking is madness: you would spend microseconds of overhead to avoid nanoseconds of spinning. Spin. But if the lock is held across a disk read of ten milliseconds, spinning wastes an eternity of CPU that another runnable thread could have used. Block. The rule of thumb: spin when the expected wait is shorter than the cost of a context switch; block otherwise.

Crucially, a spinlock is forbidden from holding across anything that can block: if the holder sleeps while others spin, the spinners burn CPU forever and can deadlock the machine. Kernel spinlocks therefore disable pre-emption (and sometimes interrupts) while held. Everything below is about making the spin itself cheap.

The naive spinlock and its cache-line disease

Recall the test-and-set (TAS) spinlock: every waiter hammers an atomic write on the single lock word. By MESI, an atomic write demands the cache line in Modified state — the sole copy. So each waiter's every attempt yanks the line to its own cache, invalidating everyone else. With n cores spinning, the lock line ping-pongs endlessly, and each bounce is a full coherence transaction across the interconnect. Worse, when the holder finally wants to release, it must itself re-acquire the line the spinners keep stealing. Contention makes the lock slower to release the more cores want it — the opposite of what you want.

Test-and-test-and-set (TTAS) is the first patch: spin on a plain read (\texttt{while (lock != free)}), which lets every core hold the line in cheap Shared state, and only attempt the atomic write when the read says it looks free. Quiet reads instead of screaming writes — until the moment of release, when everyone's read fails at once and they all storm the write together (a thundering herd). Better, but still O(n) coherence traffic per handoff, and still unfair: nothing stops one unlucky core from being starved forever while its neighbours keep winning the race.

Ticket locks: fairness, one bakery number at a time

A ticket lock borrows the deli counter. Two counters live in the lock: \texttt{next} (the number handed to the next arrival) and \texttt{owner} (the number now being served). To acquire, atomically fetch-and-increment \texttt{next} to grab your ticket, then spin until \texttt{owner} equals it. To release, increment \texttt{owner}. This is strict FIFO — you are served in arrival order, so no one starves. Linux used ticket spinlocks as its kernel spinlock from 2008.

But every waiter still spins on the same \texttt{owner} word, so releasing it invalidates all spinners at once even though only one — the next ticket-holder — can proceed. The coherence storm per handoff is still O(n). Fairness solved; scalability not yet.

MCS: everyone spins on their own doorbell

The MCS lock (Mellor-Crummey & Scott, 1991) is the breakthrough. Instead of one word everyone watches, each waiter enqueues a small node of its own and spins on a \texttt{locked} flag inside that node — a cache line touched by nobody else. The lock itself is just a pointer to the tail of a queue of these nodes.

• Acquire: atomically swap yourself onto the tail. If there was a predecessor, set your own flag to "wait", link the predecessor to you, and spin on your flag;
• Release: if a successor is linked, flip its flag — a single write that invalidates exactly one cache line, waking exactly one waiter.

The picture is the whole lesson. On the left, ticket/TTAS: three cores staring at one word that bounces between them. On the right, MCS: three cores, each staring at a private flag; the release pokes only the next node. Coherence traffic per handoff drops from O(n) to O(1), independent of how many cores are queued.

MCS is why the Linux kernel's spinlock became the qspinlock (a queued spinlock, MCS in spirit) in 2014, and why big-server locks scale to hundreds of cores without collapsing. The cost is a little extra bookkeeping — a per-waiter node — and slightly higher latency when uncontended. For a lock that is only ever contended by one core, plain TTAS can still win; MCS earns its keep exactly when the crowd arrives.

Simulate the handoff traffic

Let's count coherence invalidations per lock handoff for a ticket lock versus MCS, as the number of spinning cores grows. The model is deliberately simple: releasing a ticket lock invalidates the shared word in every spinner's cache; releasing an MCS lock writes exactly one successor's flag. Watch the ticket cost climb with the crowd while MCS stays flat.

Futexes: the kernel only when it must

Everything so far assumed the lock lives in the kernel. But most locks a program takes are uncontended — no one else wants them right now — so trapping into the kernel to acquire them is pure waste (recall a syscall is hundreds of cycles). The Linux futex ("fast userspace mutex") splits the job in two:

• Fast path, in user space: the lock is just an integer. To acquire, a single atomic compare-and-swap flips it 0→1. If that succeeds — the uncontended case — you are done. No syscall at all.
• Slow path, into the kernel: only if the CAS fails (someone holds it) do you call \texttt{futex(FUTEX\_WAIT)} to park until the holder calls \texttt{futex(FUTEX\_WAKE)} on release.

So the kernel maintains no data for a lock nobody is fighting over — it learns the lock exists only the instant two threads collide. This is the mechanism behind every modern \texttt{pthread\_mutex}, Go's mutex, Rust's \texttt{std::sync::Mutex}, and glibc's condition variables. It is the perfect embodiment of the OS design maxim: make the common case fast and pay the kernel only for the rare, contended case.