Hardware Synchronization
Coherence and consistency let threads see each other's data. But seeing is not enough: two threads
that both run \texttt{count = count + 1} can each read the same old value, each
add one, and each write back — and one increment simply vanishes. This is the
synchronization
problem, and it cannot be solved by ordinary loads and stores alone. It needs a new kind of instruction the
hardware must provide: an atomic read-modify-write.
An atomic RMW reads a memory location, computes a new value, and writes it back as one
indivisible step — no other core can sneak in between the read and the write. Every lock, every
mutex, every lock-free data structure in existence is built on a handful of these primitives. This lesson is
about what they are, how they are built on the coherence machinery you already know, and why they are so
surprisingly expensive.
The three primitives
Almost every ISA offers one or more of these atomic building blocks:
- Test-and-set (TAS) — atomically write 1 to a location and
return its old value. If you got 0, you just acquired the lock;
1 means someone else holds it;
- Compare-and-swap (CAS) — atomically: if the location equals an expected
value, replace it with a new value; return whether it succeeded. The universal primitive — you can build
any other from it;
- Load-linked / store-conditional (LL/SC) — LL reads and "tags" a location; SC writes
back only if nothing touched it since the LL, else it fails and you retry. RISC-style
(ARM, RISC-V, POWER) — it builds CAS without a single fused instruction.
CAS is the workhorse. Its power is that it lets you attempt an update and find out
whether you were beaten to it — the foundation of every optimistic, lock-free algorithm.
Building a spinlock from CAS
A spinlock is the simplest lock there is: to acquire it, keep trying CAS to flip the lock
word from "free" (0) to "held" (1) until you win; to release it, store 0. The loop "spins" — burns CPU —
until it succeeds. Here it is, with a simulated cell you can CAS. The demo also shows the lost-update bug
that CAS prevents:
// An atomic memory cell: compareAndSwap is the one indivisible operation.
class AtomicCell {
private v: number;
constructor(init: number) { this.v = init; }
load(): number { return this.v; }
store(x: number): void { this.v = x; }
// Atomically: if current == expected, set to next and return true.
compareAndSwap(expected: number, next: number): boolean {
if (this.v === expected) { this.v = next; return true; }
return false;
}
}
// --- A CAS spinlock ---
const lock = new AtomicCell(0); // 0 = free, 1 = held
function acquire(): number {
let spins = 0;
while (!lock.compareAndSwap(0, 1)) { spins++; } // spin until we flip 0 -> 1
return spins;
}
function release(): void { lock.store(0); }
acquire();
console.log(`lock acquired, held = ${lock.load()}`);
release();
console.log(`lock released, held = ${lock.load()}`);
// --- Why atomicity matters: a CAS-retry counter never loses an update ---
const counter = new AtomicCell(0);
function atomicInc(): void {
let old: number;
do { old = counter.load(); } while (!counter.compareAndSwap(old, old + 1)); // retry on interference
}
for (let i = 0; i < 5; i++) atomicInc();
console.log(`counter after 5 atomic increments = ${counter.load()}`); // exactly 5, never fewer
Why atomics are expensive: the cache-line ping-pong
Here is the sting. A CAS or test-and-set must write the lock word, and by
MESI a write
demands the block in Modified state — the only copy. So every core that even attempts
the lock must pull that cache line to itself in M, invalidating everyone else. When many cores spin on one
lock, its cache line ping-pongs between them, and each bounce is a full coherence transaction
across the interconnect. The cores spend more time shuttling the lock line than doing useful work.
The classic fix is test-and-test-and-set (TTAS): before doing the expensive atomic write,
spin on an ordinary read of the lock (which lets every core keep the line in cheap
Shared state), and only attempt the CAS when the read says the lock looks free. That
collapses the traffic from "everyone writes constantly" to "everyone reads quietly, one writes when it's
worth trying." Beyond that, real systems use back-off, queue locks (MCS), or ticket locks to tame the
contention entirely.
LL/SC: the same idea without a fused instruction
CISC machines like x86 have a single fused atomic (\texttt{LOCK CMPXCHG}). RISC
machines dislike fusing a read and a write into one instruction, so they split it:
load-linked reads the word and quietly records a reservation on that address;
store-conditional writes back only if the reservation is still intact — that is,
if no other core wrote the line since the LL. If someone did, SC fails, returns a flag, and you loop. It is
CAS assembled from two half-instructions, and the coherence protocol itself supplies the "did anyone touch
it?" signal, since a remote write to the line already had to invalidate your copy.
| Primitive | What it does atomically | Style / ISA |
|---|
| Test-and-set | set to 1, return old value | simplest; older machines |
| Compare-and-swap | if == expected, swap in new; report success | x86 LOCK CMPXCHG |
| LL / SC | read+reserve, then write-only-if-untouched | ARM, RISC-V, POWER |
CAS checks a value, not a history. Suppose CAS expects the pointer A.
Between your read and your CAS, another thread changes it to B and then back to
A — perhaps freeing and reusing that very address. Your CAS sees
A, thinks nothing changed, and succeeds — even though the world moved underneath
it. This is the notorious ABA problem in lock-free code, and it can corrupt a data
structure silently. Fixes include tagged pointers (a version counter bumped on every change, so
A never looks identical twice) or hazard pointers. LL/SC sidesteps
ABA entirely: it fails if the line was touched at all, regardless of whether the value ended up the
same — it checks history, not equality.
Beginners see \texttt{lock.compareAndSwap(...)} as a single, presumably cheap,
operation. It is one instruction but potentially hundreds of cycles: it must obtain the
cache line in Modified state (invalidating every other copy across the machine), it often acts as a memory
fence
that stalls the pipeline, and under contention it triggers the cache-line ping-pong. A single uncontended CAS
might cost tens of cycles; a hotly contested one can cost thousands in wasted coherence traffic. This is why
"just use a lock-free algorithm" is not automatically faster — the atomics themselves are the bottleneck.