Locking is the easy answer to concurrency: a mutex makes parallel code sequential at the critical section. The price is scalability under contention — every locked thread waits. Lock-free algorithms make progress guarantees: at least one thread makes progress in a bounded number of steps, even if others are descheduled. Wait-free algorithms guarantee that every thread makes progress in a bounded number of steps. The cost is code complexity and a deep understanding of the hardware’s memory model.

This topic is the algorithmic frontier — what your compiler and CPU can guarantee, and how to use it to write software that scales where locks cannot.

Memory Ordering

Threads communicate through shared memory, but a CPU core does not necessarily see writes from another core in the order they occurred. The memory-model rules govern what reorderings are permitted, and what the programmer must specify.

C++11 / Rust classify atomic operations with five orderings (Java has equivalents: volatile alone is not enough):

Two axioms that recur:

• Acquire-release is enough for almost everything. Reads from a struct with acquire-loaded pointer see the writes that happened before the corresponding release. The single pairing covers the cross-thread synchronisation.
• seq_cst is the “I give up reasoning” mode. Use it when portability matters more than micro-optimisation; pay the cost on every platform; free your brain.

The most common bug in lock-free code: assuming relaxed is enough for reads whose values are read by other threads. If thread A publishes a struct’s pointer with relaxed and thread B reads it with relaxed, B may see the pointer but see stale contents for the pointed-to struct (or even see half-updated contents due to memory tearing). Acquire-release is the minimum safe model.

Compare-and-Swap and the ABA Problem

A compare-and-swap (CAS) is an atomic operation: “if *ptr == expected, set *ptr to desired and return true; otherwise, do nothing and return false”. The lock-free idiom:

do {
  expected = *ptr
  // compute new_value from expected
} while (!CAS(ptr, &expected, new_value))

A lock-free counter is the simplest possible CAS-loop:

fn increment(ptr) {
  loop {
    old = *ptr
    if CAS(ptr, &old, old + 1) { return }
    // else another thread won — retry
  }
}

Each thread retry-loops on contention. The progress guarantee is lock-free: at least one thread makes progress in O(1) CAS attempts per concurrent thread.

The ABA Problem

The hazard of CAS-based pointers: between reading old and executing CAS, the pointer can be popped, freed, and a new value coincidentally written to the same address — the pointer looks identical (same address), CAS succeeds, but the value semantically changed.

Thread 1 reads p = A → next = B
Thread 2 pops A, frees A
Thread 2 pushes a new value onto the same memory (B happens to be reused)
Thread 1 CAS(p, A, B) succeeds — but the B it now sees is a different list!

Three solutions:

• Tagged pointers: pack a version counter into the high bits of the pointer; CAS includes both. Memory addresses have unused high bits; reuse them.
• Hazard pointers / epoch-based reclamation: never free a node that might be referenced — see below.
• Hazard-protected atomic primitives (std::atomic_shared_ptr<T>, Java’s AtomicReference with compareAndSet): the language runtime protects against ABA at the cost of extra atomic operations.

Lock-Free Stack (Treiber)

The Treiber stack (1986) is the canonical lock-free structure: a singly-linked list where top is an atomic pointer. Push pops once; each pushes via CAS on top.

push(node):
  loop {
    node->next = top
    if CAS(&top, &node->next, node) { return }
  }

pop():
  loop {
    old = top
    if old == null { return null }
    next = old->next
    if CAS(&top, &old, next) { return old->value }
    // ABA protection: tag top with a counter; CAS compares both
  }

A Treiber stack is lock-free: under arbitrary contention, at least one thread completes its operation in O(1) retries. It is not wait-free: a thread can lose CAS races indefinitely while others make progress.

Lock-Free Queue (Michael-Scott)

The Michael-Scott queue (1996) is the standard lock-free FIFO: a head pointer and a tail pointer, both atomic, with CAS-based coordination. The trickiest case: empty-to-non-empty transition (tail is behind head), which the queue handles with a “logically removed” sentinel.

enqueue(node):
  loop {
    tail = this.tail
    next = tail.next
    if tail != this.tail { continue }  // check tail still current
    if next == null {                  // tail is the actual last
      if CAS(&tail.next, &next, node) {
        CAS(&this.tail, &tail, node)   // try to advance tail — failure OK
        return
      }
    } else {                           // tail lagged; help advance
      CAS(&this.tail, &tail, next)
    }
  }

The pattern (CAS-and-help) shows up in every lock-free linked structure: if you see inconsistency, help the other thread fix it. The cost: more CAS operations in the contended case, but unbounded threads make progress.

Safe Memory Reclamation

The bug in every lock-free structure: the lock-free algorithm frees a node when another thread might still be reading it. Locks serialize access; lock-free code cannot. Three solutions:

Epoch-Based Reclamation

Each thread declares its “epoch”. Nodes freed in an epoch are held in a tombstone list; they are physically freed when no thread is reading in an earlier epoch. The data structure writes a try_advance_epoch in normal code paths and reclaims retired nodes when all threads are in the current epoch.

• Pros: very low overhead in the read path.
• Cons: a thread that stalls (GC pause, page fault, pre-empted in scheduler) blocks reclamation. Memory may grow until the thread reschedules.

Hazard Pointers

Each thread declares up to K hazard slots pointing to nodes it is currently reading. The reclaim code frees a node only when no hazard pointer is pointing to it.

• Pros: deterministic reclamation; the read path is fast.
• Cons: K hazard slots per thread limits the structure’s read complexity; reclaim overhead is O(retired_count * thread_count) worst case.

RCU (Read-Copy-Update)

A Linux-kernel favourite: every reader enters an RCU read-side critical section with rcu_read_lock(); writers publish a new version by replacing the pointer atomically (with release semantics); old versions are reclaimed after a quiescent state — a period during which no reader was in a critical section.

• Pros: zero overhead in the read path; proven in the Linux kernel for millions of readers.
• Cons: requires a quiescent-state detection mechanism — in the kernel, it’s “context switch”; in userspace, it requires a library (userspace-rcu or crossbeam-epoch).

For “read-mostly” data (config tables, routing tables, the kernel’s dcache) where reads are 10⁶× more frequent than writes, RCU is the gold standard.

Seqlock

A seqlock is the simplest wait-free read pattern: a sequence counter protects a writer; readers read the counter, then the data, then the counter again; if either counter read is odd (write in progress) or the sequence numbers differ (write completed between reads), the reader retries.

• Pros: writes are O(1), reads are wait-free — they make progress in bounded steps regardless of writers.
• Cons: every reader must be retryable (no side-effects during the read); the data must fit in a small, writeable region.

The Linux kernel uses seqlock for jiffies, xtime, the dcache. A std::shared_mutex-equivalent in Java is the closest userland approximation, but true seqlocks are the canonical wait-free pattern.

When Lock-Free Beats Locking

The honest take: locks are the default; lock-free is the optimisation. A mutex-wrapped critical section of O(50ns) and O(10k) acquisitions per second is 0.0005 seconds per second of contended time — fine on a single core, fine on 8. Lock-free becomes relevant at a hundred cores with millions of operations per second on a hot path, and even then only after measurement shows the lock is the bottleneck.

The deeper discipline: understand the memory model, then reach for primitives that match the workload. The right granularity of “lock” varies from “single atomic increment” to “RCU replacement of a 4MB data structure” — and the engineering decision is the same at every scale.

Practice Trajectory

1. Implement a lock-free counter using std::atomic<int>::fetch_add and a CAS loop. Compare the throughput against a std::mutex-protected counter on a 32-thread stress test.
2. Build a Treiber stack with tagged pointers to defeat ABA. Test by popping every value concurrently; verify the output sequence matches a known push order.
3. Implement a Michael-Scott queue; verify with a stress test that every pushed value is dequeued exactly once and never lost.
4. Pick a lock-free structure and apply epoch-based reclamation. Measure the memory-usage plateau under churn; compare with naive free() (which crashes) and with hazard pointers.
5. In a system where locks dominate hot-path time, identify a candidate. Sketch the lock-free version. Calculate whether the simplification is worth the memory-ordering reasoning cost.

When It’s the Right Tool