Why architecture matters here
Lock-free architecture matters because at high concurrency, locks limit throughput. A mutex-protected queue caps at maybe 10 million ops per second on modern hardware; a well-designed lock-free queue can hit 100 million. For high-frequency trading, low-latency messaging, and hot-path OS code, this difference matters.
Correctness is where lock-free is famously hard. It looks simple — "just use CAS in a loop" — but the ABA problem, memory ordering, and safe reclamation all silently produce corruption if handled wrong. Bugs are notoriously difficult to reproduce.
Reliability under contention is the real payoff. Locks let a single slow thread block everyone; lock-free algorithms guarantee at least one thread makes progress. Under adversarial scheduling (which OS schedulers occasionally deliver), this is the difference between "sometimes very slow" and "reliably fast."
The architecture: every mechanism explained
Walk the diagram top to bottom.
Application Threads. Multiple threads accessing shared state. No coordination through locks; all coordination through atomic operations on shared memory.
Shared Data Structure. Queue, stack, hashmap, tree — the actual thing being accessed concurrently. Design choices about pointer indirection and memory layout are more consequential in lock-free code than in locked code.
CAS Loop. The workhorse pattern: read current value, compute new value, CAS (compare-and-swap) old to new. If CAS fails, someone else got there first; loop and retry.
Atomic Operations. On x86: LOCK CMPXCHG. On ARM/RISC-V: load-linked/store-conditional (LL/SC). C++ std::atomic and Java's Atomic classes wrap these portably.
Memory Order. Acquire/release semantics prevent CPUs from reordering memory operations across atomic boundaries. Get wrong, and threads see values in impossible orders.
ABA Problem. Thread reads A, sleeps; another thread changes to B then back to A; thread's CAS succeeds thinking nothing changed. Fix: add version tag, use hazard pointers, or use epoch-based GC.
Hazard Pointers. Each thread publishes pointers it's reading. Deleters check hazard list before freeing memory. Ensures no thread reads freed memory.
Epoch-Based GC. Alternative to hazard pointers. Threads announce epoch on entry to critical section; garbage collected only after all threads have advanced past an epoch.
Wait-Free vs Lock-Free. Lock-free: at least one thread makes progress. Wait-free: every thread makes progress in bounded steps. Wait-free is stronger and harder.
Contention Mitigation. Exponential backoff on CAS failures. Elimination arrays let two conflicting operations cancel each other. Reduce contention where possible.
End-to-end queue operation trace
Trace a lock-free queue push. Michael-Scott queue is the classic. Thread T wants to push value V.
Allocate new node with V. Read the queue's tail pointer T. Try to CAS T.next from null to the new node.
If success: try to advance the tail pointer via CAS from T to new node. If this fails, another thread noticed and did it; ok.
If CAS on T.next failed: someone else pushed. Read tail again (may have advanced); help advance if needed. Retry.
Pop: read head H, read H.next, try CAS head from H to H.next. Return the value at H.next.
ABA scenario: T reads head, plans to CAS. Meanwhile another thread pops H, pops H.next, and pushes back what was H. The pointer at head is again H but the internal state has changed. T's CAS succeeds falsely. Hazard pointers prevent this by keeping H alive until T is done.
Under heavy contention, threads accumulate on the tail. Exponential backoff spreads retries; elimination combines conflicting push+pop pairs without touching the queue.