Beyond Locks: Atomics and Lock-Free Data Structures

Why a lock is sometimes the problem

Across this rung you have leaned on locks and semaphores to tame shared data: wrap the critical section, take a mutex, and only one thread touches the data at a time. It works, and most of the time you should just do it. But a lock has a quiet cost that the dining philosophers already hinted at. While one thread holds a lock, every other thread that wants it can only wait — and if the holder is unlucky enough to be paused by the scheduler mid-update (its time quantum expired, or a page fault sent it to disk), everyone else is blocked on a thread that is not even running. The lock turned a delay in one thread into a delay for all of them.

Worse, locks invite the whole family of bugs you have already met — deadlock when locks are taken in conflicting orders, priority inversion when a low-priority holder blocks a high-priority waiter, and starvation when one thread keeps losing the race for the lock. So a natural question arises: could threads update shared data correctly without ever holding a lock at all? The surprising answer is yes — but it requires help from the hardware, in the form of a single instruction that does several things as one indivisible step.

The one instruction that makes it possible: compare-and-swap

Recall the deepest lesson from the synchronization rung: a race condition happens because an innocent-looking 'add one to the counter' is really three steps — read the value, add one, write it back — and another thread can slip in between them. A lock fixed this by forbidding anyone else from running during those three steps. The hardware offers a different fix: an atomic operation that does the dangerous bit as one uninterruptible move that no thread can ever observe half-finished. The most important one is compare-and-swap (CAS).

CAS takes three arguments and means: 'Look at this memory location. If it still holds the value I expected, replace it with my new value; otherwise leave it alone. Tell me which happened.' The entire check-and-replace is one atomic step. Why does that one trick suffice? Because it lets a thread say, in effect, 'I will only commit my update if nobody changed the data behind my back.' If someone did, CAS reports failure, and the thread simply re-reads the fresh value and tries again. This read-modify-CAS-retry pattern is the beating heart of lock-free code.

  // Atomically add 1 to a shared counter, no lock at all.
  // CAS(address, expected, new) returns true on success.

  retry:
    old = counter            // 1. read the current value
    new = old + 1            // 2. compute the value we want
    if CAS(&counter, old, new):   // 3. commit ONLY if unchanged
        done                 //    success: nobody slipped in
    else:
        goto retry           //    someone changed it: re-read, redo

Walk the loop with two threads racing to increment a counter holding 5. Both read old = 5 and compute new = 6. Thread A's CAS runs first: the location still holds 5, so it succeeds and the counter becomes 6. Thread B's CAS now checks the location — it expected 5 but finds 6, so CAS fails, B has lost the race harmlessly. B loops, reads the fresh 6, computes 7, and its CAS succeeds. No lock was ever taken, no thread ever blocked another, and the final value is a correct 7. Note the honest catch: under heavy contention a thread can lose the race many times in a row, so it is never blocked but it is not guaranteed a bounded number of tries either.

Lock-free, wait-free, and the promises they make

That last catch is exactly where the precise vocabulary earns its keep. A lock-free data structure guarantees that the SYSTEM as a whole always makes progress: at every moment, at least one thread will complete its operation, even if others keep failing their CAS and retrying. No single paused thread can freeze everyone — which was the very problem with locks. But it does not promise fairness to any one thread: an unlucky thread could, in principle, keep losing the race and retrying for a long time.

A wait-free data structure makes the stronger promise: EVERY thread finishes its operation in a bounded number of its own steps, no matter what the others do. No thread can ever be starved or made to retry indefinitely. That is a wonderful guarantee for real-time systems where a deadline must be met — but it is much harder to design and often slower in the common case, so wait-free structures are rarer and reserved for where the guarantee genuinely matters. The honest hierarchy is: blocking (locks) is easiest, lock-free is harder and stronger, wait-free is hardest and strongest.

The ABA trap: when 'unchanged' is a lie

CAS rests on one assumption that turns out to be subtly false: 'if the value I read is still here, nothing important changed.' But a value can change and change back. Suppose a thread reads a pointer A from the top of a lock-free stack, gets paused, and while it sleeps another thread pops A off, pops the next node, then pushes a recycled node that happens to sit at the SAME address A. Our thread wakes, runs its CAS, sees A is still there — success! — and happily swaps in a stale view of a stack that has been completely rearranged underneath it. The value matched, but the world did not. This is the ABA problem, named for the value going A, then B, then back to A.

1. A thread reads the stack top and sees node A (sitting above nodes X then Y), then is paused by the scheduler before its CAS.
2. Another thread pops A, then pops X, so the top is now Y — the structure our sleeper remembers has been gutted.
3. A's memory is recycled and a node at the SAME address A is pushed back on top, so the top once again reads as A.
4. The sleeper wakes and its CAS(top, expected A, new X) succeeds because A matches — but X was already freed, so it links the stack to garbage. The value matched; the world did not.

The standard cures all amount to making 'unchanged' mean what we wanted. A tagged pointer (or version counter) glues a counter to the value and bumps it on every change, so A-with-tag-7 and A-with-tag-9 no longer compare equal — the CAS now notices the round trip. Alternatively, safe memory reclamation schemes such as hazard pointers or read-copy-update (RCU) simply guarantee that a node is never freed and reused while any thread might still be looking at it, so the address cannot be recycled out from under you. The deeper lesson is humbling: lock-free code is correct only when you reason about not just values but their entire history and memory lifetime.

Memory order, transactions, and choosing your tool

There is one more layer of honesty owed here. On a modern multicore machine, the CPU and compiler reorder memory operations for speed, so the order in which one thread WRITES is not necessarily the order another thread SEES — this is governed by the machine's memory consistency model. Lock-based code is shielded from this because acquiring and releasing a lock acts as a memory barrier that pins the ordering for you. Lock-free code has no such umbrella: you must place the right barriers (often called acquire/release fences) by hand, or your CAS loop can be perfectly atomic and yet still see a neighbor's writes in a scrambled, impossible-looking order. This is a large part of why hand-written lock-free code is so notoriously hard to get right.

Because reasoning about a single CAS is already this delicate, people have long wished for something that composes — a way to mark a whole block as 'all-or-nothing' the way a database transaction does. That wish is transactional memory: you declare a region atomic, the system runs it speculatively, and if no other thread touched the same data it commits in one shot; if there was a conflict it aborts and retries, just like a CAS loop scaled up to many locations at once. It is a beautiful idea, and hardware support exists, but it comes with real limits — transactions can abort for reasons beyond your control, and large or I/O-touching transactions do not fit — so it complements locks and atomics rather than replacing them.

So where does this leave you? The honest default is still a lock: simple, composable, and fast enough almost everywhere. Reach for raw atomics and a CAS loop for one tiny hot counter or flag where lock-free progress genuinely pays off, and reach for a battle-tested lock-free LIBRARY (not your own from scratch) when you need a concurrent queue or map under heavy contention. And if a problem feels like it is fighting shared mutable memory at every turn, that is often a sign you should stop sharing memory altogether — which is exactly the road the next guide takes, where threads coordinate not by locking shared data but by sending each other messages down a channel.