The one instruction that makes lock-free possible
The previous guide promised a way to coordinate threads without ever holding a lock, and left an honest question open: if no thread can stop the others, how does any thread ever change shared state safely? The answer is a single hardware operation called compare-and-swap, almost always written CAS. It is the heartbeat of nearly every lock-free algorithm, so it is worth understanding precisely, not approximately.
CAS takes three things: an address, a value you expect to find there, and a value you want to put there. As one indivisible step it checks whether the memory still holds the expected value; if it does, it writes the new value and reports success; if it does not, it changes nothing and reports failure, handing you back what it actually found. The whole point is the conditional write. You are not blindly storing; you are saying "store this, but only if nobody changed it out from under me since I last looked." Because the check-and-write happens as a single read-modify-write that no other core can split, two threads can never both believe they won.
Read it as one uninterruptible step: `if (*addr == expected) { *addr = desired; return true; } else return false;` — but with the whole if-and-store fused so no other core can interleave between the test and the write. The portable C spelling is atomic_compare_exchange_weak(&head, &expected, desired): it returns true or false, and on failure it rewrites your expected variable with what it actually found, which is exactly what you need for the loop in the next section.
The retry loop: how you actually use CAS
A single CAS that fails is not an error — it is normal, expected, and the whole reason the technique works. You almost never call CAS once. You wrap it in a CAS retry loop: read the current value, compute what you want the new value to be, then CAS. If it succeeds you are done; if it fails, someone beat you to it, so you take the fresh value CAS just handed back, recompute against that, and try again. The loop is the lock-free analogue of "wait for the lock" — except instead of blocking, you spin forward and re-attempt.
Concretely, to atomically increment a shared counter you would write: int old = atomic_load(&counter); then while (!atomic_compare_exchange_weak(&counter, &old, old + 1)) ; with an empty loop body. Each time the CAS fails, the call has already reloaded old with the current value, so the next attempt computes old + 1 against the freshest number — and when it finally succeeds the counter moved by exactly one, with no lost update. That tiny loop is the whole pattern; everything fancier is the same shape with a more interesting "compute the new value" step in the middle.
Look closely at why this is lock-free and not just clever. A CAS only fails when some other thread succeeded — when the value changed, it changed because a competitor made progress. So the system as a whole never stalls: every failed attempt is the shadow of someone else's win. That is precisely the lock-free guarantee from guide 1. But be honest about the cost it does not buy: your particular thread can lose the race over and over while others keep winning, so a single unlucky thread can starve. If failures pile up under heavy contention and the whole system thrashes without anyone finishing, you have a livelock — progress for the system, but a thread spinning forever. Guide 5 returns to why taming this is genuinely hard.
CAS has a sibling: load-linked / store-conditional
x86 gives you CAS directly, as the cmpxchg instruction. But ARM, RISC-V, and POWER take a different route to the same goal, and you will meet it the moment you read disassembly on a phone or a server chip. It is a pair of instructions called load-linked / store-conditional, usually abbreviated LL/SC. Load-linked reads an address and quietly tells the hardware to start watching it. Store-conditional then tries to write back — but it succeeds only if nothing at all has touched that address since the matching load-linked. If anything did, the store-conditional fails and you loop, exactly like a CAS retry.
There is a deep and beautiful difference hiding here, and it matters for the rest of this guide. CAS compares values: it asks "is the number still 42?" LL/SC watches the location: it asks "has this address been written at all?" Those are not the same question. A value can leave 42 and come back to 42, and CAS would happily call it unchanged. LL/SC would not — any write to the watched address, even one that restored the old value, breaks the link and fails the store. Hold onto that distinction; it is the seed of the whole problem this guide is named after.
The ABA problem: when nothing changed, but everything did
Now the trap. Because CAS only compares values, it can be fooled by a value that left and came back. This is the ABA problem, and the name is the whole story: a memory location holds A, you read A, then while you are mid-computation another thread changes it to B and then back to A. When your CAS finally runs, it sees A, matches your expected A, and reports success — but the world is not the world you read. The pointer is the same number; the thing it points to may be entirely different. CAS cannot tell the difference between "never changed" and "changed twice and changed back."
The classic place this bites is a lock-free stack — the Treiber stack you will build in guide 3. To pop, a thread reads the head pointer (call it node A), reads A's next field to find the new head, then CAS-es head from A to that next. Imagine the thread reads head = A, plans to set head to A's next, then pauses. Another thread pops A, pops the node after it, frees A, then pushes a brand-new node that the allocator happens to place at the same address A. Head is once again the pointer value A — but A is now a different node with a different next. The paused thread wakes, CAS-es head from A to its stale, long-gone next pointer, and succeeds. The stack is now corrupt, pointing into freed or wrong memory.
thread 1 (popping) thread 2
---------------------- --------------------------------
old = head; // = A
next = A->next; // = X
... paused ... pop A; pop X; free(A);
push(new); // malloc reuses A's address!
// head == A again, but A->next is now Y
CAS(&head, A, X) // SUCCEEDS — sees A, writes X
// head now points at X, which was freed. corruption.Fixing ABA: tags, LL/SC, and the deeper problem underneath
The most direct fix is to make the value carry its own history so A-then-A no longer looks identical. You pair the pointer with a counter — a version stamp — and CAS the pair as one unit. Every successful modification bumps the counter, so even if the pointer returns to A, the counter has moved from, say, 7 to 9, and the CAS of (A, 7) against the current (A, 9) correctly fails. This is the tagged pointer or versioned pointer trick. To CAS two words at once, ABA-prone code reaches for a double-width CAS such as x86's cmpxchg16b, packing pointer and counter into 16 bytes.
Two honest caveats on the counter trick. First, a counter is finite: at 0x7fffffff it wraps back to 0, so in principle ABA can recur if exactly that many modifications slip between your read and your CAS. In practice 32 or 64 bits makes this astronomically unlikely, but "astronomically unlikely" is not "impossible," and an honest engineer files it under known limits. Second, recall the sibling instruction: LL/SC is naturally immune to ABA, because store-conditional fails on any write to the watched address, A-back-to-A included. That elegance is real — but spurious failures and the rule that you can do almost nothing between the load-linked and the store-conditional make LL/SC its own kind of fiddly.
Step back and hold the shape of it. CAS is a conditional, indivisible write — the atom from which lock-free algorithms are assembled. Its one blind spot is that it compares values, not histories, so a value that returns to its old self slips past the check; that is ABA. You can blunt ABA with a version counter or sidestep it with LL/SC, but the deepest cause is almost always premature reuse of freed memory, which is really a reclamation question in disguise. Carry those three ideas — conditional write, value-blindness, reclamation underneath — into the next guides, where you finally build the stacks and queues these instructions were made for.