Atomics and lock-free structures

Why it matters

Locks are simple and usually fast enough, but they have failure modes no amount of care removes: a thread preempted while holding a lock stalls everyone behind it, and a heavily contended lock serialises cores. Atomic operations and lock-free structures avoid those, which is why they sit under concurrent queues, reference counting, metrics counters, memory allocators and every lock implementation. They are also notoriously easy to get subtly wrong, so knowing their guarantees and pitfalls matters more than knowing how to write one.

The idea

An atomic operation reads and updates a memory location as one indivisible step that no other core can interleave with: atomic add, exchange, and the universal building block, compare-and-swap (CAS): "if this word still equals expected, set it to new and report success; otherwise report the current value." The hardware guarantees it by holding the cache line exclusively for the duration.

The CAS loop

Any update to a single word can be made atomic with a loop: read the current value, compute the new value from it, CAS from old to new, and if another thread changed it in the meantime, retry with the fresh value. No thread ever blocks; a failed CAS means someone else made progress.

Progress guarantees

Lock-free does not mean faster. Under heavy contention, CAS loops retry repeatedly and bounce the cache line between cores just like a contended lock. The benefit is robustness: no thread can block the system by being descheduled at the wrong moment, which matters in kernels, real-time paths and signal handlers.

Memory ordering

Atomics also carry ordering guarantees about surrounding memory operations, because compilers and CPUs reorder freely. Sequentially consistent atomics (the default in C++ and Java's volatile) behave as if all threads see one global order; simplest and slightly slower. Release on a write and acquire on the matching read create a happens-before edge: everything written before the release is visible after the acquire, which is exactly what publishing an initialised object needs. Relaxed atomics guarantee only atomicity of that variable, fine for a statistics counter and wrong for a flag guarding other data. Getting ordering wrong produces bugs that appear only on some CPU architectures (ARM reorders more than x86).

Classic pitfalls

1. 1

   The ABA problem

   A thread reads A, is delayed, another thread changes the value to B and back to A, and the first thread's CAS succeeds even though the structure changed underneath (for example, a stack node was popped, freed and reused). Fixes: tag the pointer with a version counter that changes on every update, or use memory reclamation that prevents reuse while a thread may still hold a reference.
2. 2

   Safe memory reclamation

   In a lock-free list, a thread may be reading a node another thread just removed. Freeing it immediately is a use-after-free. Garbage-collected languages handle this for you; elsewhere you need hazard pointers, epoch-based reclamation or RCU.
3. 3

   Multi-word updates

   CAS covers one word. Invariants spanning several fields need a lock, a copy-on-write swap of a pointer to an immutable object, or careful multi-step protocols.
4. 4

   False sharing

   Atomics on different variables in the same 64-byte cache line contend as if they were one. Pad hot atomics to separate lines.

When atomics beat locks

Single-variable state: counters, flags, sequence numbers, reference counts, an atomic pointer to an immutable snapshot (readers load it, writers build a new one and swap). Highly contended counters do best when striped: per-core or per-thread cells summed on read (Java's LongAdder, per-CPU counters in the kernel), which turns one hot line into many cold ones. For anything more complex, use a well-tested library structure (concurrent queues, maps, skip lists) rather than writing your own.

Trade-offs

Atomics and lock-free structures give non-blocking progress and excellent uncontended performance, and cost complexity, subtle ordering bugs, ABA and reclamation problems, and no guaranteed speedup under contention. Locks are easier to reason about and often just as fast. Reach for atomics for single words and published snapshots; reach for libraries for anything larger.

In an interview

Pick the simplest correct tool: "Request counts per endpoint are striped atomic counters summed by the metrics scraper, so 64 threads incrementing never contend on one cache line. Configuration is an atomic reference to an immutable object: readers load it without locking, the reloader builds a new one and swaps it in. Everything else uses the language's concurrent collections."