From one bit
to a queue

The path: define what “good” means → understand the atomic primitives → TAS → cache-local polling → backoff → ticket locks → Anderson/Graunke–Thakkar → locality and NUMA → MCS → read the performance graph correctly.

1. First decide what a good lock is

It is easy to reduce this topic to “which lock is fastest?” That loses the point. The lecture gives you several axes because improving one can damage another.

The lecture explicitly starts with latency, handoff delay, contention/bandwidth, and space; fairness, locality, preemption, and available atomic primitives become unavoidable as the algorithms evolve.

Contention is not the same thing as bandwidth

Bandwidth consumption is how much traffic you generate. Contention is what happens when requests compete for the same finite resource and delay one another. They often rise together, but they are not identical.

A lock can generate only a few bytes per operation and still be pathological if every processor targets the same serialized cache line. Conversely, a machine can move a lot of data across independent links without severe contention. TAS gives you the bad combination: lots of repeated traffic, all focused on the same object.

2. The atomic instructions are different tools

The names are close enough to blur together in a lecture. Do not blur them. The algorithms later depend on the distinctions.

3. Start stupid: spin on test-and-set

acquire:
    while test_and_set(lock) == BUSY:
        pass

release:
    lock = FREE

This is beautiful under no contention. One atomic operation, tiny state, very low latency. That is why simple locks never disappear from the design space.

Now add many waiters. Every failed test_and_set is a read-modify-write attempt on the same location. On a coherent cache machine that means repeatedly trying to obtain exclusive ownership of the lock line. On a bus or interconnection network it means a stream of transactions aimed at one hot address.

This is the first systems lesson: waiting has a topology. A logically idle processor can be very physically busy.

4. Test-test-and-set: exploit the cache

The obvious waste is performing an atomic write attempt when we already know the lock is busy. So first poll it with ordinary reads, and only perform TAS after observing it free:

for (;;) {
    while (load(lock) == BUSY)
        pause();              // ordinary reads

    if (test_and_set(lock) == FREE)
        break;
}

On a cache-coherent machine, once a waiter has a shared copy of the lock line, repeated reads can hit in its local cache. That is what “spin on cache” means. It is not magic private state: it is a cached copy whose freshness is maintained by coherence.

Write-invalidate vs write-update

Suppose ten processors cache lock = BUSY. The owner releases.

With write-invalidate, the owner's write invalidates the other cached copies. On their next load, waiters miss and fetch the new value. With write-update, the new value is broadcast into their copies. Either way, the coherence mechanism is doing work to make the release visible. Invalidate tends to defer traffic until waiters next read; update pushes the new value immediately.

TTAS eliminates the continuous RMW storm while the lock remains busy, but release still creates a herd: everybody can discover FREE at roughly the same time and race into TAS. One wins; the others lose and go back to reading.

5. Backoff: do not solve congestion by generating more congestion

Another repair does not change the lock representation at all. It changes when losers retry.

delay = 1
while test_and_set(lock) == BUSY:
    pause(randomized(delay))
    delay = min(2 * delay, MAX_DELAY)

The networking analogy is exact enough to be useful: many agents collide on one shared resource; immediate synchronized retry recreates the collision; randomized exponential backoff spreads attempts out.

This reduces interconnect pressure, but now your delay policy directly affects handoff latency. If everyone happens to be sleeping when the lock becomes free, the resource sits idle. Backoff is therefore not a free improvement. It trades traffic against responsiveness.

Why fairness can get ugly

Suppose an old waiter has failed repeatedly and backed off to a long delay. A newcomer arrives with a tiny initial delay just after the lock becomes free. The newcomer can win before the old waiter even checks again. More failures can literally mean “I look less often,” creating newcomer bias and no FIFO guarantee.

6. Ticket locks: turn a race into a line

Use two monotonically increasing counters:

my = fetch_and_add(next_ticket, 1)
while now_serving != my:
    wait

// critical section
now_serving++

This gives FIFO ordering and constant-size lock state. More importantly, position gives information. If you are ticket 44 and now_serving is 41, checking on every cycle is pointless. Proportional backoff can make the delay roughly proportional to your distance from the head.

Why not just use timestamps?

A timestamp sounds like a ticket because it gives an order. But the lock needs more than “time usually increases.” It needs a unique, globally agreed ordering operation under simultaneous arrivals. Two cores can read the same timestamp; clocks can have architecture-specific synchronization semantics; and you still need shared state that says which timestamp is currently entitled to enter. fetch_and_add directly performs the thing we actually need: atomically assign one unique position in a total order.

Is the ticket board still a hot spot?

Yes. This is the important limitation. Everybody ultimately watches now_serving. With coherent caches they may poll it locally while it is unchanged, but every increment must become visible to all those cached copies. Without coherent caching, repeated polling may be remote traffic.

So ticket locks solve fairness and make backoff intelligent, but they have not yet solved the structural problem that all waiters care about one shared word.

7. Central coordination is not itself the enemy

This is a subtle point worth keeping. Anderson and MCS still use a central atomic operation when a processor joins the queue. MCS atomically swaps the tail. Anderson atomically allocates a slot.

That is okay because the central operation happens a bounded number of times per acquisition. The pathological thing was unbounded repeated central traffic while waiting.

This distinction is more reusable than any individual lock algorithm.

8. Anderson: give every waiter its own place to spin

Anderson's queue lock uses an array of flags. A fetch-and-increment assigns each arriving processor a slot. Exactly one slot says “has lock”; the others say “must wait.” Each processor spins on its assigned slot, and release marks the next slot runnable.

On a coherent-cache machine, put different slots on different cache lines so one handoff does not invalidate unrelated waiters. On physically distributed shared memory, place slots in different / preferably local memory modules.

Why “different cache lines” matters

If eight logical flags share one 64-byte cache line, a write to P3's flag invalidates the line containing P4, P5, and P6's flags too. That is false sharing: logically independent state becomes physically coupled by the coherence granularity. Your elegant local-spinning algorithm collapses back toward shared traffic.

“How many cache lines do we even have?”

You are not likely to exhaust the cache-line namespace. The real issue is footprint. Padding one byte of useful flag to an entire 64-byte line means 64 waiters consume 4 KiB per lock. Multiply by thousands of locks and the representation becomes absurd. That is why space becomes a first-class metric.

Anderson's lock buys clean local spinning with an array sized to the maximum number of processors/waiters for each lock. The Graunke–Thakkar lock is another array-based point in this design space; among other differences it uses fetch-and-store rather than requiring fetch-and-increment. For this lecture's main arc, the important fact is simply that both distribute the spin locations, but pay substantial per-lock space.

9. NUMA makes “where?” impossible to ignore

So far “memory” sounded like one place. On NUMA systems it is not. A core reaches some memory through a nearby controller and other memory across sockets / interconnect links. Two loads with the same instruction count can have very different cost.

Now every lock algorithm gets another question:

A global ticket word can sit near one socket and far from another. An Anderson slot can be placed near its waiter. A per-waiter node can live in memory local to its processor and still be shared so that another processor can perform the one write that wakes it.

This is the bridge into MCS. We want FIFO order and local spinning without allocating a giant array inside every lock.

10. MCS: make the queue itself distributed

An MCS lock is almost comically small:

lock = pointer to tail node (or NIL)

qnode:
    next
    locked

The lock object does not contain all waiter state. Each contender brings a node. Those nodes form a linked list:

That last sentence is the point. With 64 waiters, a release does not need to become an event observed by 64 processors. It needs to become an event observed by one successor.

Acquisition, line by line

acquire(L, me):
    me.next = NIL
    pred = atomic_exchange(L.tail, me)

    if pred != NIL:
        me.locked = true
        pred.next = me
        while me.locked:
            spin locally

    // if pred == NIL, the queue was empty: I own the lock

1. me.next = NIL. Initialize your queue node.

2. pred = exchange(tail, me). This is the clever atomic step. In one indivisible operation, you make yourself the new tail and receive the identity of the old tail. That old tail is your predecessor.

3. If there was no predecessor, you acquired immediately. No queue existed.

4. Otherwise, link yourself behind the predecessor. Write pred.next = me.

5. Spin on your own flag. The predecessor will eventually clear exactly that flag. On a cache-coherent machine the repeated reads can be cache-local. On distributed shared memory, your node can be allocated in your local memory module.

Release looks weird because of one race

release(L, me):
    if me.next == NIL:
        if compare_and_swap(L.tail, me, NIL):
            return

        while me.next == NIL:
            spin

    me.next.locked = false

If me.next != NIL, life is easy: wake that successor.

The interesting case is me.next == NIL. You might conclude “nobody is behind me; clear the tail.” But there is a tiny window where a successor has already atomically swapped itself into L.tail and has not yet executed me.next = successor.

This is precisely why CAS is the right primitive. P0 is allowed to clear tail only if the tail is still P0. The CAS packages “verify nobody changed it” and “clear it” into one atomic act.

Why not plain test-and-set here?

Because the release race is not “who can set a bit first?” It is “clear this pointer only if it still has the exact value I previously observed.” That is conditional state transition territory. CAS expresses the invariant directly.

11. The ZooKeeper analogy was good

A common ZooKeeper lock recipe creates sequential nodes and watches only the immediately preceding node instead of having every waiter watch one global lock node. The substrate and failure model are completely different, but the structural move is the same:

That analogy is useful because it reveals that MCS is not primarily “a linked-list trick.” It is a way of turning broadcast competition into directed handoff.

12. Read the Butterfly graph as an experiment, not decoration

The BBN Butterfly used in the paper was a shared-memory multiprocessor with a multistage interconnection network, physically distributed memory, no cache coherence, and comparatively expensive atomic operations. That makes it a harsh test for algorithms that generate remote traffic.

The graph from lecture uses an empty critical section. That choice is deliberate. Useful work inside the lock is essentially removed, so the measured time exposes the synchronization machinery itself under contention.

The qualitative result to keep:

The paper's network-latency experiment is even more revealing than the lock timing graph: central TAS/ticket designs can increase latency for unrelated traffic because they create a hot network destination. MCS keeps both the hot-spot effect and unrelated-network impact tiny because waiters do not repeatedly access remote queue state.

So what is a “Butterfly”? And what is a “dance hall”?

Butterfly here is the BBN Butterfly multiprocessor, named for its interconnection network topology. Processors and distributed memory communicate through a multistage network; a remote memory operation traverses that network.

Dance hall is an architectural metaphor from this literature: processors are on one side, shared memory on the other, and shared locations are roughly equally remote rather than having useful processor-local placement. The MCS paper argues that locality is valuable: if wait flags can live near the processors that poll them, software can avoid synchronization-induced network contention.

13. Why didn't everybody just use MCS?

Because “scales beautifully” is not the same as “dominates every operating point.”

MCS has more machinery than a one-word TAS lock on the uncontended path. The caller needs a queue node that must survive from acquisition through release. Strict queueing also means preemption can hurt: if the next waiter in FIFO order is descheduled, processors behind it cannot simply barge past. And systems APIs may have been designed around a tiny opaque lock word rather than “lock plus caller-provided node.”

This is not merely historical. Modern Linux's queued spinlock is explicitly MCS-inspired, but its implementation comments explain that it modifies the classic design to preserve a 4-byte spinlock_t and the existing lock API. That is a nice real-world answer to the lecture question: good algorithms collide with ABI, memory footprint, fast paths, virtualization, preemption, and decades of surrounding code.

14. The whole lecture in one compression pass

15. Five checks before you call this learned

Sources and scope

This recap follows the lecture's progression through MCS and fills only gaps needed to make that progression cohere. It deliberately stops before the barrier algorithms.

Mellor-Crummey & Scott, “Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors” (1991)
Linux qspinlock.c — modern MCS-inspired queued spinlock
Earlier narrow explainer: “Why can a correct spinlock scale badly?”