Chapter 9: Lock-Free and Wait-Free Programming Basics

Why this matters

Locks solve concurrency hazards reliably, but they carry real, sometimes significant costs: a thread blocked on a lock is doing no useful work, contention on a popular lock can bottleneck an entire system, and — worst of all — a thread holding a lock that crashes, hangs, or is descheduled at an inopportune moment (companion OS book, Chapter 4's scheduling) can block every other thread waiting on it indefinitely. Lock-free programming exists specifically to avoid these costs, at the price of significantly increased implementation complexity and subtlety.

The core mechanism: compare-and-swap (CAS)

[BEGINNER] Nearly all lock-free algorithms are built on a single hardware-level atomic primitive: compare-and-swap (CAS) — an instruction that atomically checks whether a memory location currently holds an expected value, and if so, updates it to a new value, all as one indivisible hardware operation. If the value has changed since it was last read (because another thread modified it), the CAS fails, and the calling code retries.

import threading

class LockFreeCounter:
    """Illustrating the CAS-based lock-free pattern conceptually in Python
    (which doesn't expose a real hardware CAS primitive directly, but the
    ALGORITHM SHAPE is exactly what a true lock-free implementation follows)."""
    def __init__(self):
        self._value = 0

    def increment(self):
        while True:
            current = self._value           # read the current value
            new_value = current + 1
            # In a language with real atomics (Java's AtomicInteger.compareAndSet,
            # C++'s std::atomic::compare_exchange), this next line would be ONE
            # indivisible hardware instruction:
            if self._compare_and_swap(current, new_value):
                break  # succeeded -- no other thread changed the value in between
            # else: another thread updated it first -- RETRY with the new current value

    def _compare_and_swap(self, expected, new_value):
        # Illustrative only -- a real implementation needs actual hardware CAS support,
        # which Python doesn't expose directly.
        if self._value == expected:
            self._value = new_value
            return True
        return False

The shape of every CAS-based algorithm: read the current state, compute a new state based on it, attempt to atomically swap old-for-new — and if another thread beat you to it, retry from the beginning with the now-current value, rather than blocking and waiting. No thread ever waits for another thread to release anything; every thread is always either making progress or immediately retrying.

Lock-free vs. wait-free: a precise distinction

[SENIOR INSIGHT] These terms are often used loosely interchangeably, but they make a precise, meaningful distinction:

• Lock-free: guarantees that the system as a whole always makes progress — at least one thread is always successfully completing operations, even though any individual thread might retry indefinitely under sustained contention (in principle, an unlucky thread could keep losing every CAS race forever, even while the system overall keeps moving).
• Wait-free: the stronger guarantee that every individual thread completes its operation in a bounded number of steps, regardless of what any other thread is doing — no thread can be starved indefinitely, even in principle.

Wait-free algorithms are significantly harder to design and implement correctly than lock-free ones, and are comparatively rare in practice outside specialized, high-assurance systems — most "lock-free" data structures found in mainstream standard libraries are lock-free, not wait-free, and this distinction is worth stating precisely rather than treating the terms as synonyms.

The real trade-offs: why this isn't a strictly better default choice

[SENIOR INSIGHT] Lock-free programming avoids a specific set of lock-related costs (blocking, priority inversion, a crashed lock-holder freezing everyone else), but it isn't a free upgrade over locks:

• The ABA problem — a classic, subtle lock-free bug: a thread reads value A, gets preempted, another thread changes it to B and back to A before the first thread resumes; the first thread's CAS succeeds (the value IS A again) even though the underlying state actually changed in between, potentially violating an invariant the algorithm depended on. Solving this typically requires additional bookkeeping (versioned pointers/tags alongside the value), adding real complexity.
• Retry storms under high contention — with many threads simultaneously CAS-retrying against the same memory location, the total amount of wasted, repeated work can, in pathological cases, exceed what a well-designed lock-based approach would have cost — lock-free isn't automatically faster under all contention levels.
• Vastly higher implementation complexity and subtlety — correctly reasoning about every possible interleaving in a lock-free algorithm is significantly harder than with lock-based code, and a subtle bug in a lock-free implementation can be extraordinarily difficult to reproduce and diagnose.

[IN PRACTICE] Because of this complexity, most application-level code should use existing, well-tested lock-free data structures (many languages' standard/concurrent libraries provide these) rather than implementing new lock-free algorithms from scratch — this is a much stronger version of Chapter 6's "prefer queue.Queue over hand-rolling" advice, since lock-free bugs are considerably more subtle and dangerous than lock-based ones.

Common mistakes

1. Treating "lock-free" as synonymous with "always faster." Under high contention, retry storms can make a lock-free approach perform worse than a well-designed lock-based one — the performance benefit is real but conditional, not universal.
2. Confusing "lock-free" and "wait-free" as interchangeable terms — lock-free guarantees only system-wide progress; wait-free guarantees every individual thread's bounded progress, a meaningfully stronger and rarer property.
3. Implementing a custom lock-free algorithm without accounting for the ABA problem, introducing a subtle correctness bug that's extremely difficult to reproduce and diagnose after the fact.
4. Reaching for a hand-rolled lock-free implementation as a default optimization, when the actual measured bottleneck doesn't come from lock contention at all — this adds substantial complexity and risk for a problem that may not exist yet (this book's recurring premature-optimization theme, applied at its highest-complexity-cost point).

Discussion / interview questions

1. "What is compare-and-swap, and how do lock-free algorithms use it?" Strong answer: An atomic hardware instruction that checks whether a memory location holds an expected value and, if so, updates it to a new value in one indivisible step; lock-free algorithms use it in a read-compute-attempt-swap-retry-on-failure loop, so threads never block waiting for another thread, only retry if their attempted update was beaten by a concurrent one.

2. "What's the precise difference between lock-free and wait-free?" Strong answer: Lock-free guarantees the system as a whole always makes progress (some thread is always succeeding), but an individual thread could in principle retry indefinitely under sustained contention; wait-free guarantees every individual thread completes in a bounded number of steps regardless of other threads' behavior — a strictly stronger, rarer, harder-to-achieve guarantee.

3. "What is the ABA problem in lock-free programming?" Strong answer: A thread reads value A, is preempted, another thread changes the value to B and back to A before the first thread resumes — the first thread's compare-and-swap succeeds because the value IS A again, even though the underlying state genuinely changed in between, which can violate an invariant the algorithm depended on; typically solved with versioned tags alongside the value.

4. "Is lock-free programming always a better choice than using locks?" Strong answer: No — it avoids specific lock-related costs (blocking, a crashed holder freezing others) but introduces its own risks (retry storms under high contention, the ABA problem, dramatically higher implementation complexity); most application code should prefer existing, well-tested lock-free data structures over hand-implementing new lock-free algorithms, and should only consider it at all in response to a measured, real lock-contention bottleneck.

Chapter summary / cheat sheet

• Compare-and-swap (CAS): the atomic hardware primitive underlying nearly all lock-free algorithms — read, compute, attempt an atomic swap, retry on failure, never block.
• Lock-free: system-wide progress guaranteed, individual threads may retry indefinitely in principle. Wait-free: every individual thread's progress is bounded — a stronger, rarer guarantee.
• Real trade-offs: avoids blocking/priority-inversion/crashed-holder risks, but introduces the ABA problem, potential retry storms under high contention, and significantly higher implementation complexity.
• Prefer existing, well-tested lock-free data structures over hand-rolling new lock-free algorithms; reach for this approach only in response to a measured, real lock-contention bottleneck, not as a default optimization.

---