Study notes · 9% of the exam

Atomics, CAS and Lock-Free Programming

Lock-free programming builds shared data structures from atomic operations, mainly compare-and-swap, so some thread always makes progress without locks. Interviews test CAS loop correctness, ABA and memory reclamation, progress guarantees, memory ordering on publish, and when lock-free is (and isn't) faster.

Key points

1
A correct CAS loop re-reads the current value, computes the new value from it, and CASes against that same value on every iteration.
2
Progress guarantees form a hierarchy: blocking < obstruction-free < lock-free (some thread progresses) < wait-free (every thread progresses in bounded steps).
3
ABA happens when a value returns after intermediate changes, usually via memory reuse. Fix it with tagged/stamped pointers, hazard pointers, epoch-based reclamation or garbage collection.
4
compare_exchange_weak may fail spuriously and belongs in loops; use compare_exchange_strong for one-shot attempts whose failure has meaning.
5
Publishing data through an atomic pointer needs release on the store and acquire on the load, or a reader can see the pointer before the data.
6
Contention, not the instruction, is the cost: every RMW needs exclusive ownership of a cache line. False sharing, striping (LongAdder) and back-off are about reducing that traffic.
7
Lock-free is a progress guarantee, not a speed guarantee: at low contention a mutex is often as fast or faster.

Common traps

Computing the new value from one read and CASing against a fresh get() silently loses updates.
Java's AtomicReference.compareAndSet compares by identity (==), not equals().
Atomics only work on integer typed arrays in JavaScript; Float64Array throws a TypeError.

Read the source

Test yourself on Atomics, CAS and Lock-Free Programming

Ten questions, with the answer and explanation after each one.