C++ Lock-Free Programming: CAS, ABA, Memory Order, Queues [#34-3]

Introduction: mutex contention

Queues under heavy load

Worker pools hammering a mutex-protected queue spend time waiting. Lock-free algorithms use compare-exchange loops so some thread always progresses (lock-free progress guarantee).

Topics: basics, CAS, stack/queue examples, memory_order, ABA, hazards (hazard pointers, epoch reclamation), benchmarks, production cautions.

---

Lock-free vs wait-free

Lock-free: system-wide progress; some threads may starve in retry loops. Wait-free: per-thread bounded steps—much harder; rare outside simple atomics.

---

Atomics & CAS

compare_exchange_weak in loops for Treiber stack-style structures. Use acquire/release (or acq_rel) to pair publishes and consumes.

Full LockFreeStack / Michael–Scott listings use acquire/release atomics—copy them carefully so instruction order matches the published algorithms.

---

Memory order

• relaxed: counters
• acquire/release: publish/consume pointers
• seq_cst: default if unsure (slower)

---

ABA & reclamation

ABA: node address reused while another thread still thinks it’s valid. Mitigations: hazard pointers, epoch-based reclamation, tagged pointers, or GC integrations—never delete pop’d nodes naively in lock-free pop without a safe reclamation scheme.

---

Benchmarks

Compare mutex vs lock-free vs SPSC specialized queues on your workload.

---

Production

Prefer battle-tested libraries (Folly, moodycamel, boost::lockfree) before hand-rolling complex structures.

Keywords

lock-free, compare_exchange, memory_order, ABA, atomic, queue