Why architecture matters here
Lock-free code is famously subtle. A missed memory barrier lets threads see stale data. ABA problems corrupt intrusive lists. False sharing makes lock-free slower than locked. Cache-line-aware layout requires deep understanding of the hardware.
The architecture matters because most teams should not write lock-free code from scratch; they should use verified library implementations. But reading, tuning, and integrating them requires understanding the pieces.
With the concepts in mind, you can recognize when lock-free helps and when a well-chosen mutex is the right answer.
The architecture: every piece explained
The top strip is the primitive stack. Atomic primitive — CAS (compare-and-swap) or LL/SC — is the hardware building block. Memory ordering — acquire, release, sequentially consistent — controls how loads and stores are observed across cores. Retry loop reads current state, computes new state, attempts CAS, retries on failure. Progress guarantee classifies algorithms: wait-free (bounded steps per thread), lock-free (system-wide progress), obstruction-free (progress when others don't obstruct).
The middle row is the safety machinery. ABA problem: a pointer changes to B then back to A between reads, fooling naive CAS; mitigations include tagged pointers or version counters. Hazard pointers let readers announce which pointers they are using so reclamation waits. RCU defers freeing until all readers have completed grace period. MPMC queues — Michael-Scott, LCRQ — are canonical lock-free structures.
The lower rows are practice. Cache line effects: false sharing kills throughput; pad hot atomics. Verification with TLA+ or model checkers is warranted for critical structures. Ops: measure contention, prefer library primitives, verify when writing new.
End-to-end flow
End-to-end: a task-stealing scheduler uses an MPMC queue based on Michael-Scott. Workers push and pop with CAS + tagged pointers to avoid ABA. Memory ordering is release on push, acquire on pop, ensuring visibility. Hazard pointers manage safe reclamation of popped nodes. False sharing is avoided by cache-line-aligning the queue's head and tail. Under contention, tail latency stays flat where a mutex would spike. The queue's correctness has been TLA+ verified.