Coherence is not enough: the torn update
The previous guides earned us a powerful guarantee: with cache coherence and a protocol like MESI, if one core writes a value to an address, every other core eventually sees that exact value — nobody is left reading a stale photocopy. You might hope that settles parallel programming. It does not. Coherence makes each single read or write to a location land cleanly, but most useful work is not a single access; it is a little dance of read-then-write, and coherence says nothing about what another core may do in between those two steps.
Picture the classic example: two cores each want to add 1 to a shared counter that holds 10. Each core's `counter = counter + 1` is really three steps — read 10 into a register, add 1 to get 11, write 11 back. If the two cores interleave so both read 10 before either writes, both compute 11, both store 11, and one increment silently vanishes. The counter should be 12; it is 11. Nothing was incoherent — every read and write saw a legitimate value — yet the program is wrong. This is a race condition, and the read-modify-write sequence that must not be interrupted is called a critical section.
The cure is to make the dangerous middle step atomic — Greek for 'uncuttable'. We need a way to tell the hardware: 'read this location, decide, and write back, all as one indivisible action that no other core can wedge itself into.' Plain loads and stores cannot promise this, because between them any number of cycles (and other cores' accesses) can slip through. So the ISA must offer special instructions whose whole point is that they cannot be torn apart. Those are the atomic operations, and they are the bedrock everything else in this guide stands on.
The atomic primitives: CAS and LL/SC
Hardware designers settled on a small toolkit of atomic read-modify-write primitives, and almost everything else is built from them. The most famous is compare-and-swap (CAS). CAS takes three things — an address, an expected old value, and a new value — and atomically does: 'if the location still holds the expected value, write the new value and report success; otherwise change nothing and report failure.' The crucial word is still: CAS only commits if nobody else slipped a write in since you read, so it is a one-instruction way to say 'I'll write only if my view of the world hasn't gone stale.'
With CAS, the lost-increment bug dissolves into a tiny retry loop: read the counter (say 10), compute the new value (11), then CAS(address, expected=10, new=11). If another core sneaked an increment in, the location now holds 11 not 10, CAS fails, and you simply loop back, re-read the fresh value, and try again. No update is ever lost, because a write only lands when nobody disturbed the value you based it on. This pattern — read, compute, attempt-to-commit, retry on failure — is the heartbeat of almost all lock-free code.
RISC processors (including RISC-V and Arm) often prefer a two-instruction cousin: load-linked / store-conditional (LL/SC). `LL` reads an address and quietly tells the hardware to watch that line; `SC` then tries to write back, but succeeds only if nothing has touched the watched line since the `LL`. If the coherence machinery saw any other write to that line — exactly the events MESI already tracks — the `SC` fails and returns 0, and you retry the pair. Notice the beautiful reuse: LL/SC piggybacks on the same per-line ownership signals the coherence protocol was already broadcasting, so atomicity costs almost no new hardware beyond a small 'reservation' flag.
Atomic increment, two ways (pseudocode):
-- with compare-and-swap (CAS) --
loop:
old = load(counter) ; read current value
new = old + 1 ; compute off to the side
if CAS(counter, old, new): ; commit only if still == old
break ; success -> done
; else: someone changed it -> loop and retry
-- with load-linked / store-conditional (LL/SC, RISC-V style) --
loop:
old = LL(counter) ; read AND start watching the line
new = old + 1
if SC(counter, new) == 1: ; succeeds only if line untouched
break ; success -> done
; else: line was written by another core -> retryBuilding locks: the spinlock
Atomics are powerful but low-level; programmers usually want something simpler: 'let me grab this resource, do my work undisturbed, and release it.' That is a lock, and the simplest hardware-backed lock is the spinlock (spinlock). It is just one shared variable — 0 means free, 1 means held. To acquire it, a core atomically tries to flip it from 0 to 1; if it wins, it owns the lock and enters the critical section; if it loses, it spins — loops, re-checking — until the lock falls back to 0, then pounces.
- Acquire: atomically attempt to set the lock from 0 to 1 (e.g. with CAS(lock, expected=0, new=1), or an LL/SC pair). If it succeeds you hold the lock; if it fails another core holds it.
- Spin: on failure, loop and keep retrying. A good spinlock first just reads the lock in a tight loop (a cheap cache hit on a Shared copy) and only fires the expensive atomic again once it sees the lock go back to 0 — this avoids hammering the coherence fabric.
- Critical section: once you hold the lock, do your read-modify-write on the shared data, knowing no other core can be inside at the same time.
- Release: write 0 back to the lock (with the proper ordering — more on that next) so a waiting core can win the next round.
The hidden hazard: memory ordering and barriers
There is a subtler trap lurking beneath all of this, and it surprises almost everyone the first time. We have been quietly assuming that memory operations happen in the order the program wrote them. But modern cores reorder loads and stores aggressively — recall out-of-order execution and store buffers from earlier rungs — and a core may make its writes visible to other cores in a different order than it issued them. The rules for what orderings are allowed form the memory consistency model (memory consistency model), and it is a separate contract from coherence: coherence is about the values of a single location, consistency is about the relative order across different locations.
The strictest, most intuitive model is sequential consistency (sequential consistency): all cores' operations appear to interleave into one single global order, and each core's own operations keep their program order within it — exactly the mental model a beginner naturally assumes. The honest catch is that real hardware usually does not give you this for free, because enforcing it would forbid too many of the reorderings that make a fast core fast. Instead, machines like x86 and Arm offer relaxed (weaker) models that allow certain reorderings, and they hand you a tool to forbid them exactly where you need to.
That tool is the memory barrier (or fence, memory barrier). A barrier is an instruction that says 'no memory operation may cross this line': everything before it must become visible to other cores before anything after it does. This is exactly why the spinlock's release step needs care — releasing the lock (writing 0) must not become visible before the writes you made inside the critical section, or another core could grab the lock and read half-finished data. So lock-acquire carries an acquire barrier and lock-release carries a release barrier; conveniently, the atomic instructions on most ISAs can bundle the right ordering in, which is why correctly using the provided lock or atomic library is far safer than rolling your own.
Two traps from the hardware: false sharing and NUMA
Even perfectly correct synchronization can run shockingly slowly because of how coherence works underneath. The first trap is false sharing (false sharing). Recall that coherence tracks whole cache lines (say 64 bytes), not individual variables. Suppose two cores each update a different counter, but those two counters happen to sit in the same 64-byte line — for instance neighbouring slots of an array, `count[0]` and `count[1]`. There is no logical sharing at all, yet every time one core writes its counter, the coherence protocol invalidates the line in the other core's cache, forcing it to refetch before its next write. The line ping-pongs back and forth, and two threads that should run independently crawl as if they were fighting over one variable.
The fix is to pad the data so independently-updated values land on separate cache lines — give each core's counter its own line, even if that wastes a few bytes. False sharing is a textbook example of the broader lesson from the cache rungs: the hardware's granularity is invisible to your source code but very visible in your runtime, and identical results can hide a many-fold slowdown. It is the multicore cousin of the conflict-miss padding trick from the cache guides.
The second trap appears once a machine grows beyond a handful of cores. In a small shared-memory multiprocessor, every core reaches all of memory at roughly the same cost. But big machines stitch several processor packages together, each with its own attached memory, and a core's accesses to its own local memory are faster than reaching across the interconnect to another package's memory. This is NUMA (NUMA), non-uniform memory access. It does not change correctness — coherence and your locks still work everywhere — but it means where a thread's data physically lives now affects speed. Good parallel code tries to keep each thread's hot data in the memory closest to the core running it, lest every access pay the long-haul toll.
Why this is the price of going parallel
Step back and notice the shape of the whole story. The power wall pushed us to thread-level parallelism — many cores instead of one ever-faster core — but the moment threads share data, we inherit races, and to tame races we need atomics, and to make atomics usable we wrap them in locks, and to make locks correct we need barriers, and to make all of it fast we must dodge false sharing and respect NUMA. Each layer earns its keep, but each also adds cost and a chance to get it wrong. Synchronization is not a free add-on to parallelism; it is the tax you pay for sharing.
And that tax has a deeper consequence, which the final guide in this rung will make precise. Every lock you take serializes the cores that contend for it — while one core holds the lock, the others wait, doing nothing useful. That serial fraction does not shrink as you add cores; if anything, more cores fight harder over the same locks. This is the seed of Amdahl's law: the parts of a program that must run one-at-a-time set a hard ceiling on how much speedup any number of cores can ever buy. Synchronization is exactly where that serial fraction is born, which is why the cheapest synchronization is the synchronization you managed to avoid — by not sharing in the first place.