Why can a correct
spinlock scale badly?

The path: a tiny counter → cache-line ownership → test-and-set pathology → why test-test-and-set only partly helps → MCS local spinning → the design rule underneath it.

01Start with something that should be easy

Suppose 32 cores repeatedly increment one shared counter. The critical section is almost insultingly small:

On one core, this looks cheap. The protected work may be only a handful of instructions. So it is tempting to predict that adding cores will at worst flatten throughput once the counter itself becomes serialized.

But a naive spinlock can do worse than flatten. Throughput can fall as contenders increase. The useful work is serialized, yes, but now the waiting itself also consumes coherence bandwidth and delays the owner. The machine spends more effort deciding who may increment than incrementing.

This is the distinction to keep in your head for synchronization papers: who is allowed to enter? is the correctness question. what shared state do the waiters touch while they wait? is often the scalability question.

02The hardware fact that makes the story go

We only need a simplified cache-coherence model. A core can cheaply keep reading a cache line it already has. But before it writes that line, a coherent multiprocessor must give it write permission—conceptually, ownership—and invalidate or otherwise revoke conflicting copies elsewhere.

So a shared writable cache line behaves less like a whiteboard everyone can scribble on simultaneously and more like a marker that must move between cores. A read can often stay local. A write to a line another core owns requires coherence traffic.

Now put the lock word itself on such a line.

03The innocent-looking test-and-set lock

A basic spinlock can use an atomic exchange: write 1 into the lock and receive the old value. If the old value was 0, you acquired it. Otherwise keep trying.

Correctness is fine: only one exchange observes the transition from 0 to 1. The pathology is hidden in the losing iterations. A loser is not merely asking, “is the lock still held?” It is performing another read-modify-write on the same cache line.

Walk four cores through it. P0 owns the critical section. P1, P2, and P3 are waiting:

The losers can therefore interfere with the winner. They repeatedly demand the very cache line the owner eventually needs to release the lock. More contenders mean more ownership transfers, more invalidations, and more interconnect pressure.

04First repair: stop writing while you know you will lose

Test-test-and-set (TTAS) separates observation from competition:

While the lock is held, waiters mostly issue ordinary loads. After each waiter has a readable copy of the lock line, repeated polling can often hit locally. The line is no longer ricocheting between cores on every spin iteration.

That is a major improvement, and it explains why hardware manuals recommend variants of test-test-and-set rather than a hot loop of locked RMW operations.

But ask the next question: what happens at release?

TTAS removes the continuous storm while the lock is held. It does not remove the synchronized burst when the lock becomes free. With many waiters, every unlock is a starting gun.

So we have improved the constant factors and changed when contention occurs, but the lock word is still a global rendezvous point.

05What would a truly scalable waiting pattern look like?

At this point, do not memorize MCS yet. Derive the requirement.

If 32 waiters all repeatedly inspect one shared location, release must somehow become visible to 32 observers. If 32 waiters all try to write that location, they fight for ownership. The obvious escape is: do not make all waiters spin on the same location.

Give each waiter a private flag. Then arrange the waiters in a queue. Core P7 should wait on a flag associated with P7, not on a global lock word. Its predecessor alone will wake it.

That is the key move in the Mellor-Crummey–Scott queue lock.

06MCS: queue globally, spin locally

Each contender owns a small queue node, conceptually:

To acquire, a thread atomically appends its node to the lock's tail. If there was a predecessor, it links itself behind that predecessor and spins on its own locked flag. The predecessor, on release, clears that successor's flag.

Imagine P0 holds the lock and P1, P2, P3 arrive:

Only the next waiter needs to observe the handoff. P2 does not wake merely because P1 became runnable. P3 does not race P1 for a central word. The coherence event is targeted.

This changes the scaling law of waiting traffic. The original MCS paper's central idea is local spinning: each processor spins on a separate locally accessible flag, and another processor ends that spin with a single remote write. The queue gives us exactly the predecessor-successor relationship needed to know who should perform that write.

07A small mechanism model

The widget below is deliberately not a cycle-accurate processor simulator. It counts illustrative “coherence pressure units” per handoff to expose the shape of the algorithms. The constants are arbitrary; the scaling behavior is the lesson.

As the number of waiters grows, TAS makes waiting traffic grow aggressively because every waiter keeps participating. TTAS is much better while the lock remains held, but its release burst still grows with the crowd. MCS makes the ordinary handoff depend mainly on the predecessor and successor, not every queued thread.

08Now return to the 32-core counter

We began with one unavoidable serialization point: only one core may update the counter at a time. That sets a ceiling. A scalable lock cannot make the counter update parallel.

What it can do is prevent the queue of waiting cores from making the serialized operation progressively more expensive. That is a different and extremely important goal.

With a naive TAS lock, 31 waiters can create traffic while P0 performs its tiny critical section. The synchronization mechanism adds a second bottleneck on top of the inherent one. With MCS, the 31 waiters mostly wait on distinct cache lines; the critical path is much closer to “current owner finishes → wake one successor.”

So when a paper calls a lock “scalable,” read it carefully. It usually does not mean the protected work becomes parallel. It means the overhead of managing contention does not explode merely because the queue gets longer.

09The deeper pattern: move from broadcast competition to directed handoff

MCS is useful beyond the code of one lock because it teaches a systems design pattern:

You will see cousins of this idea in per-CPU data structures, sharded counters, distributed queues, ownership protocols, and NUMA-aware designs. The common question is: can I turn a many-to-one coordination hotspot into smaller local interactions?

There is a cost. MCS needs a node per waiter and more bookkeeping than a tiny uncontended spinlock. Under very low contention, a simpler lock may be faster. Scalability is not “always fastest”; it is about how cost evolves as load and concurrency rise.

10Changed assumption: what if the critical section is long?

Everything above assumes spinning is reasonable because the owner will release soon. Now make the critical section 10 ms instead of tens of nanoseconds.

Even a beautifully scalable MCS spinlock can waste CPU time: local spinning fixes coherence contention, not the fact that a waiting core is burning execution resources while making no application progress. At that point the next design question is whether waiters should block, park, or use a hybrid spin-then-sleep strategy.

That gives you the hierarchy:

Different lock designs live at different points in that space.

11One question to carry into synchronization

Suppose an MCS lock has 64 waiters. On one release, why does “64 waiters exist” not imply “64 waiters must observe the unlock”?

If your answer mentions the queue structure, per-waiter spin locations, and predecessor→successor handoff, you have the core idea.

12Primary sources