MCS Lock: The Scalable Queue-Based Spinlock That Fixed Cache-Line Contention

The Problem: Why Simple Spinlocks Don't Scale

A classic spinlock is a single memory word. To acquire it, every thread hammers an atomic test-and-set (or reads then test-and-sets in the TTAS variant) until it wins. On a cache-coherent multiprocessor this is a disaster at scale. Under the MESI protocol, each write attempt must acquire the cache line in exclusive/modified state, invalidating the copy held by every other spinning core.

• Cache-line ping-pong: the lock word bounces between caches; a single release triggers a thundering herd where N waiters simultaneously re-fetch and re-contend.
• Interconnect saturation: the traffic grows with the number of waiters, so even the thread doing useful work in the critical section is slowed by coherence storms.
• No fairness: whichever core happens to hold the line wins, so a nearby thread can barge ahead repeatedly and starve distant ones.

Mellor-Crummey and Scott's insight was that a waiting thread should never spin on a location any other thread writes. If each thread spins on a private flag, releasing the lock is a single write to exactly one successor's line — no herd, no ping-pong. That reduces the interconnect cost of contention from O(threads) to O(1).

How It Works: The Queue Protocol Step by Step

The lock is one shared pointer, tail, to the last node in a singly linked FIFO queue (or NULL if free). Each thread owns a qnode { next, locked }.

acquire(lock, I):
  I.next   = NULL
  I.locked = true
  pred = SWAP(lock.tail, I)      // fetch-and-store: append I, get old tail
  if pred != NULL:              // someone is ahead of us
      pred.next = I             // link myself behind predecessor
      while I.locked: spin      // busy-wait on MY OWN flag
  // else: queue was empty -> we hold the lock immediately

release(lock, I):
  if I.next == NULL:                        // no known successor
      if CAS(lock.tail, I, NULL): return    // queue now empty, done
      while I.next == NULL: spin             // successor mid-enqueue; wait for link
  I.next.locked = false                      // hand off: wake exactly one thread

The two subtle races are handled by design. On acquire, there is a window between the SWAP and writing pred.next = I where the predecessor can't yet see us; on release the CAS-then-spin sequence closes it. The CAS in release fires only in the uncontended case; the common contended path is a single flag write.

Complexity and a Worked Trace

Time (uncontended): one SWAP plus one CAS — constant. Remote memory references per acquisition: O(1) no matter how many threads wait, versus O(n) for TAS/ticket locks. Space: O(1) shared state plus one qnode per thread currently using the lock. The queue length is bounded by the number of threads, so worst-case wait to acquire is O(n) handoffs — but each handoff is a single cache miss, and FIFO order guarantees no starvation.

Trace with threads A, B, C arriving in that order on a free lock:

• A: SWAP(tail, A) returns NULL → A holds the lock, enters critical section.
• B: SWAP(tail, B) returns A → sets A.next = B, spins on B.locked.
• C: SWAP(tail, C) returns B → sets B.next = C, spins on C.locked.
• A releases: A.next = B so it writes B.locked = false. B wakes, runs.
• B releases: writes C.locked = false. C wakes.
• C releases: C.next == NULL, CAS(tail, C, NULL) succeeds → lock free.

Every wakeup touched exactly one remote line: the interconnect load stayed flat as the queue grew.

Where It's Used in Real Systems

MCS locks are the backbone of scalable synchronization far beyond academia:

• The Linux kernel replaced its ticket spinlock with qspinlock in 2014 (Waiman Long), an MCS-based design. To keep the common uncontended lock at a single word, it uses a compact 4-byte lock plus a small per-CPU array of MCS nodes indexed by preemption context (task / softirq / hardirq / NMI), spinning MCS-style only once contention appears.
• JVMs and language runtimes use MCS-style queue locks for their internal monitors and safepoint coordination on many-core boxes.
• Databases and storage engines (e.g., latch implementations in high-core-count OLTP systems) adopt MCS or MCS variants to avoid latch-contention collapse.
• HPC / NUMA runtimes use MCS as the building block for NUMA-aware cohort and hierarchical locks (HMCS), which batch handoffs within a socket before crossing the interconnect.

The design also shines on machines without cache coherence (early NUMA and message-passing multiprocessors), because a thread can allocate its qnode in memory local to its own processor and spin there — the original motivation in the 1991 paper.

Compared to Ticket, CLH, and Test-and-Set

The closest cousins each make a different tradeoff:

• vs. Ticket lock: ticket locks are also FIFO-fair and dead simple (one fetch-and-add), but all waiters spin on the same now-serving word, so a release invalidates every waiter's cache line — O(n) traffic. MCS trades a slightly heavier protocol and a per-thread node for O(1) traffic. Rule of thumb: ticket locks win at low core counts, MCS wins under heavy contention.
• vs. CLH lock (Craig, Landin & Hagersten): CLH also gives O(1) local spinning, but each thread spins on its predecessor's flag and needs only swap (no CAS). The catch: CLH spins on a remote node, so it performs poorly on cache-less NUMA machines where that line isn't local. MCS spins strictly on its own node, so it's NUMA/no-coherence friendly — at the cost of a CAS and the enqueue-race handling in release.
• vs. TAS/TTAS: simplest and lowest-latency when uncontended, but non-FIFO and catastrophic under load.

A practical hybrid, the K42 / standard-interface MCS, hides the qnode inside the lock word so callers don't have to pass a node explicitly.

Pitfalls, Failure Modes, and Significance

MCS is elegant but has sharp edges:

• Caller must supply a node. The classic API takes a qnode pointer whose lifetime must outlive the critical section and must not be reused while still queued. Passing a stack node that goes out of scope, or reusing a node for a nested lock, corrupts the queue.
• Not reentrant, not blocking-friendly. A thread holding an MCS lock must not sleep or be preempted for long: the lock is handed to a specific successor, so if that successor is descheduled, everyone behind it stalls (the convoy / preemption problem). Kernels mitigate this by disabling preemption while spinning.
• The release race is easy to get wrong. Omitting the while (I.next == NULL) spin after a failed CAS loses the wakeup and deadlocks the successor.
• No fairness escape hatch. Strict FIFO can hurt throughput on NUMA machines by forcing the lock across sockets every handoff — the reason hierarchical HMCS and cohort locks exist.

Its significance is foundational: MCS proved that lock scalability is an algorithmic property, not just a hardware one, and it remains the template for nearly every modern scalable lock, from qspinlock to RDMA and hardware-transactional designs.

MCS lock versus other spinlocks under high contention (per-acquisition remote memory traffic and fairness)

Lock	Spin traffic under contention	FIFO fair?	Atomic ops needed	Extra space
Test-and-set (TAS)	O(threads) invalidations, all spin on 1 word	No (starvation possible)	test-and-set	1 word
Test-and-test-and-set (TTAS)	Bursts on release, thundering herd	No	test-and-set	1 word
Ticket lock	O(threads) — all read shared now-serving word	Yes	fetch-and-add	2 words
MCS lock	O(1) — each spins on private flag	Yes	swap + CAS	1 tail word + 1 qnode/thread
CLH lock	O(1) — spins on predecessor's flag	Yes	swap	1 tail + 1 qnode/thread