Skip to main content
Be Bitwise

Lock-Free Programming

Advanced Concurrency · VR Foundations track

7 min read

In this module

Beyond Locks

In Concurrency & Race Conditions, you saw mutexes serialise access to shared data. They work, and they come with a tax. A thread holding a lock can be descheduled at the wrong instant, freezing every other thread that wants in. If the lock-holder crashes or gets killed mid-critical-section, the protected data is left in whatever half-mutated state it happened to be in. Lock-free programming sidesteps these failure modes by riding directly on atomic hardware instructions.

A data structure is lock-free if at least one thread is guaranteed to make progress in a bounded number of steps no matter what the others do. That's a stronger property than mutual exclusion. Threads can stall, crash, or get preempted indefinitely, and the system as a whole still moves forward.

Compare-and-Swap: The Foundation

The workhorse of lock-free programming is the compare-and-swap (CAS) instruction. On x86 it shows up as CMPXCHG. The semantics, in plain English: "If the value at this address still equals what I expected, replace it with this new value. Otherwise leave it alone and tell me you didn't."

c
// Pseudocode for CAS
bool compare_and_swap(int *addr, int expected, int new_val) {
// This entire block executes atomically in hardware
if (*addr == expected) {
*addr = new_val;
return true; // success
}
return false; // someone else changed it
}

The standard idiom is a CAS loop: read the current value, compute what you want it to become, attempt the CAS. If the CAS fails because somebody else got there first, you go back to the top and try again on the new state.

c
void atomic_increment(atomic_int *counter) {
int old_val, new_val;
do {
old_val = atomic_load(counter);
new_val = old_val + 1;
} while (!atomic_compare_exchange_weak(counter, &old_val, new_val));
}

The ABA Problem

CAS only confirms that the value matches what you expected. "Same value" emphatically does not mean "unchanged." Picture a lock-free stack built from a linked list. Thread 1 reads the top node A and gets ready to pop it. Before Thread 1's CAS fires, Thread 2 pops A, pops B, frees B, and then re-pushes A. Thread 1's CAS sees A sitting on top, exactly the expected value, and cheerfully succeeds. But the structure beneath A has shifted entirely. The next pointer Thread 1 grabbed points at the freed B. The stack's new top is now a dangling pointer into reclaimed memory.

That's the ABA problem. The value walked from A to B and back to A, and CAS slept through the round trip.

Here's the same race on a stack that starts as A, B, C:

With a tagged pointer, Thread 1 would have read (A, tag 0). Each successful CAS on top bumps the tag, so after Thread 2's three operations top holds (A, tag 3) and the stale CAS fails, sending Thread 1 round its loop to read the new state.

Solving ABA

The common fixes: tagged pointers pair the pointer with a monotonically increasing counter so a recycled address still looks different. Hazard pointers have each thread publish the addresses it's currently dereferencing, blocking premature frees. Epoch-based reclamation parks freed nodes until every thread has crossed a synchronisation barrier.

Hazard Pointers

Hazard pointers tackle the trickiest piece: safely reclaiming memory in a lock-free world. Each thread maintains a tiny, publicly visible list of pointers it's currently touching. Before dereferencing anything from a shared data structure, it publishes the address there. Before any thread frees a removed node, it sweeps every hazard list in the system. Find the pointer in someone's list and reclamation gets deferred until they're done.

The re-read after the fence is the step that makes this work. Between Thread 1 reading head and its hazard pointer becoming visible, another thread could have removed the node, scanned the lists, found nothing and freed it. Checking that head still holds node_ptr after the publish proves the node was still in the structure at a moment when the hazard pointer was already visible, so any later scan is guaranteed to see it.

The price is scanning every thread's hazard list before each free. In practice you amortise it: batch retired nodes and only scan once the queue reaches a threshold.

Lock-Free Queues and Stacks

The Michael-Scott queue is the classic lock-free FIFO. It runs two CAS operations: one against the tail during enqueue, one against the head during dequeue. The clever bit is a two-step enqueue. First CAS the next pointer of the current tail. Then CAS the tail pointer itself. If a thread stalls between those steps, any other thread that comes along can "help" by completing the second CAS for it.

A lock-free stack is the easier sibling — really just a singly linked list where push and pop both CAS the head. The Treiber stack is the textbook version. Push allocates a new node pointing at the current head and CAS-swaps the head pointer. Pop reads the head, grabs its next pointer, and CAS-swaps the head to that successor.

When to Use Lock-Free Structures

Lock-free programming is not a free upgrade over locks. The code is much harder to write correctly, much harder to reason about, and notoriously painful to debug. CAS loops can also choke on contention. Under heavy load, dozens of threads may keep losing the CAS race and burning CPU on fruitless retries. Every failed CAS means some other thread's CAS succeeded, so the structure as a whole keeps moving, but an unlucky thread can lose over and over. That's starvation, and lock-freedom alone does nothing to prevent it.

The progress guarantees form a ladder, and you should know which rung your structure stands on:

GuaranteeWho is guaranteed to make progress
Obstruction-freeA thread that runs on its own, with the others paused, finishes in a bounded number of steps
Lock-freeAt least one thread finishes in a bounded number of steps, whatever the others do
Wait-freeEvery thread finishes in a bounded number of its own steps

A Treiber stack is lock-free but not wait-free: the system progresses, the individual thread may not.

Reach for lock-free structures when you need progress guarantees (real-time systems, signal handlers), when lock-holder preemption is a real worry (OS kernels), or when profiling pins lock contention as your bottleneck. For most application-level code, fine-grained locks perform just as well and won't have the next maintainer cursing your name.