CLH Lock: Implicit Queue Spinlock with Predecessor Flags

What It Is and the Problem It Solves

A spinlock lets a thread busy-wait until a lock is free instead of sleeping. The trouble is where everyone waits. A simple test-and-set lock has all contenders repeatedly writing one shared word; each write invalidates that cache line everywhere, so n spinners produce O(n) coherence messages per handoff and the memory bus saturates. Ticket locks add fairness but still broadcast the release to every waiter.

The CLH lock (Craig, Landin, Hagersten) is a list-based queue lock that gives each waiter a private place to spin. Arriving threads append a small record to an implicit FIFO queue and then spin only on a flag associated with their predecessor. When the predecessor finishes its critical section, it clears that flag, releasing exactly one successor. The queue is "implicit" because a thread does not store a pointer to its successor; it only remembers its predecessor, so the list exists via each thread's local reference rather than as an explicit doubly-linked structure.

How It Works, Step by Step

Each queue node holds one boolean, locked (true = owner/waiters must wait). The lock variable is a pointer to the tail node.

type Node = { locked: bool }
lock.tail = &dummyNode   // initially locked=false

// per thread, thread-local: myNode, predNode
acquire(lock):
  myNode.locked = true
  predNode = swap(&lock.tail, &myNode)   // atomic exchange, appends me
  while predNode.locked:                 // spin on PREDECESSOR's flag
    pause()

release(lock):
  myNode.locked = false                  // frees my successor
  myNode = predNode                       // recycle: reuse pred's node next time

The single atomic swap (XCHG / fetch-and-store) both enqueues the caller and returns its predecessor. If the swap returns the dummy node (or a released node), locked is already false and the thread enters immediately. On release, a thread does not free its own node — it keeps the predecessor's node for its next acquire, because a later successor is still spinning on the node it just released. This node recycling keeps steady-state allocation at zero.

Complexity and a Worked Step Trace

Time: acquire performs one atomic swap plus a spin that resolves in O(1) remote memory references once the predecessor releases — the spin variable changes exactly once, so it triggers one cache miss, not repeated bus traffic. Release is a single store. Space: O(1) per thread; with L locks and n threads, total node storage is O(L + n) because a thread carries one node and hands it forward.

Trace with threads A, B, C on an initially-free lock (dummy D, locked=false):

start: tail -> D(false)
A acquire: swap -> pred=D(false); D.locked false -> A ENTERS
B acquire: swap -> pred=A(true);  spins on A.locked
C acquire: swap -> pred=B(true);  spins on B.locked
tail now -> C(true)
A release: A.locked=false  -> B sees false, B ENTERS; A reuses D
B release: B.locked=false  -> C sees false, C ENTERS; B reuses A
C release: C.locked=false; C reuses B

Handoff order is exactly A → B → C: the order in which the atomic swaps linearized, which is why CLH is strictly FIFO.

Real-System Usage

Queue locks in the CLH family underpin high-contention paths where fairness and NUMA scalability matter. The Linux kernel's qspinlock — the default spinlock since kernel 4.2 — uses an MCS-style queued tail but shares the same core insight of per-waiter spinning that CLH pioneered; CLH and MCS are the two canonical designs cited in that work. The JVM's biased/lightweight locking and various JDK AbstractQueuedSynchronizer internals draw on the same queue-of-waiters idea, and CLH is explicitly named as the basis for Java's ReentrantLock sync queue in Doug Lea's AQS paper.

Database engines, user-space runtimes, and HPC/OpenMP libraries adopt CLH or MCS for barrier and lock implementations on many-core NUMA machines, where a test-and-set lock would cap scaling around a handful of cores. CLH's small footprint (one word per node, a single atomic per acquire) also makes it attractive for embedded and real-time systems that need bounded, FIFO worst-case acquisition.

Comparison to Alternatives and the Tradeoff

The closest cousin is the MCS lock (Mellor-Crummey & Scott, 1991). Both are FIFO O(1)-remote-reference queue locks, but they differ in one decisive place: MCS threads spin on a flag in their own node, while CLH threads spin on the predecessor's node. The practical consequences: CLH's acquire is shorter (one swap, no successor pointer to publish) and its release is a plain store, whereas MCS release must handle a race where no successor has linked yet. But because CLH's spin variable lives in a remote node, it needs a coherent cache to migrate that line locally; on a cacheless NUMA machine (no coherence, remote memory only) MCS wins because it always spins on locally-allocated memory.

Against a ticket lock, CLH replaces an O(n) broadcast-on-release with O(1) targeted wakeups, and against plain test-and-set it converts unbounded thrashing into a single cache-line transfer per handoff — at the cost of a small per-thread node and more complex code.

Pitfalls and Significance

Node ownership is the classic bug. After release a thread must adopt its predecessor's node, not free its own — freeing the just-released node while a successor still spins on it is a use-after-free. Getting the recycling wrong (or using a fresh node each acquire without swapping) breaks correctness or leaks. Cache placement matters too: nodes should be cache-line aligned/padded to avoid false sharing, or the per-waiter-line benefit evaporates. CLH also requires cache coherence to be efficient, offers no timeout/abort in its basic form (an aborting waiter can strand its successor), and is not reentrant by itself.

Its significance is foundational: CLH and MCS together established that mutual exclusion can scale linearly by localizing the spin, directly shaping modern queued spinlocks in operating-system kernels and language runtimes. Any discussion of scalable locking, NUMA-aware synchronization, or the Linux qspinlock traces back to these two 1990s queue-lock designs.

CLH versus other spinlocks under contention (n = number of threads/waiters)

Lock	Remote refs per acquire	FIFO fairness	Spins on	Works on cacheless NUMA
Test-and-set / TAS	O(n) (unbounded, thrashes)	No	Shared lock word	No
Ticket lock	O(n) per release (broadcast)	Yes	Shared now-serving word	No
CLH lock	O(1)	Yes	Predecessor's node (remote)	No (needs cache)
MCS lock	O(1)	Yes	Own node (local)	Yes