Hardware Primitives & Lock-Free Programming

Let us open the black box. A lock, at its simplest, is a single integer in memory shared by all threads: 0 means free, 1 means held. To acquire it you check whether it is 0, and if so you set it to 1 and enter. To release it you set it back to 0. Written in the obvious way, acquiring the lock is a read followed by a write. That looks atomic when you read the source, but the CPU sees two distinct memory operations with a gap between them.

int lock = 0;               /* 0 = free, 1 = held */

void acquire(void) {
    while (lock != 0)       /* 1. read: wait until it looks free */
        ;                   /*    (another core can change it here) */
    lock = 1;               /* 2. write: claim it */
}                           /*    <-- steps 1 and 2 are NOT one action */

void release(void) {
    lock = 0;
}

Now run it on two cores at once. Core A reads lock, sees 0, and is about to write 1. Before it does, core B also reads lock, still 0, because A has not written yet. Both cores now believe the lock is free. Both write 1. Both enter the critical section together. The lock did exactly nothing. This is the same read-modify-write race from ch14, except the variable we are racing on is the lock itself — so there is no outer lock to protect it. It is turtles all the way down until something breaks the recursion.

You might hope a cleverer arrangement of ordinary reads and writes could dodge this. For decades computer scientists tried, and there are beautiful results — Dekker’s algorithm and Peterson’s algorithm achieve mutual exclusion using only plain loads and stores. But they assume every core sees memory operations in the exact order they were written, which real CPUs do not guarantee (we will see why in section 5), and they scale poorly and burn cycles. They are teaching tools, not the foundation of a real kernel’s locks.

The oldest hardware answer is test-and-set. It is a single machine instruction that does two things as one indivisible action: it writes 1 into a memory location, and it returns whatever was there before. No other core can touch that location between the read and the write — on older machines the CPU literally locked the memory bus for the duration. Because it is one instruction, there is no gap and no window.

The return value is the whole trick. If test-and-set returns 0, the lock was free and you just claimed it — you are in. If it returns 1, the lock was already held (you harmlessly rewrote 1 over 1) and you did not get it, so you try again. A lock built this way is a spinlock: a thread that fails to acquire simply loops, "spinning" on the instruction until it succeeds.

#include <stdatomic.h>

atomic_flag lock = ATOMIC_FLAG_INIT;   /* the simplest atomic: set or clear */

void acquire(void) {
    /* atomic_flag_test_and_set: set the flag, return its OLD value. */
    while (atomic_flag_test_and_set(&lock))
        ;              /* it was already set -> spin and retry */
}                      /* it returned 0 (was clear) -> we hold the lock */

void release(void) {
    atomic_flag_clear(&lock);          /* back to free */
}

A close cousin is the atomic exchange (often called swap or xchg): it writes a new value into a location and returns the old one, indivisibly. Test-and-set is really just atomic exchange with the fixed new value 1. Both belong to the family of read-modify-write instructions — a single op that reads, transforms, and writes back atomically. That family is the hardware bedrock every lock in your operating system rests on.

Test-and-set

One instruction that stores 1 into a location and returns the previous value, indivisibly. Returns 0 = you acquired it; returns 1 = someone else holds it.

Atomic exchange (swap)

Write a new value, return the old value, as one step. Test-and-set is exchange with new value 1.

Spinlock

A lock whose waiters loop (spin) on an atomic instruction instead of sleeping. Great for very short critical sections, wasteful for long ones.

Read-modify-write (RMW)

The family of atomic instructions that read a location, change it, and write it back with no window in between.

Test-and-set gives you a lock, but it is blunt: it always writes 1. The instruction that changed everything is compare-and-swap, universally abbreviated CAS. Conceptually it takes three arguments — an address, an expected value, and a desired value — and does this atomically: if the memory at the address still equals expected, replace it with desired and report success; otherwise change nothing and report the value it actually found. In one indivisible step it asks "is this still what I last saw? If so, here is my update; if not, tell me what it really is."

That conditional quality is what makes CAS the workhorse of concurrency. It lets you update shared data optimistically: read the current value, compute the new value you want, then CAS it in. If nobody else touched the location in between, the CAS succeeds and you are done. If someone did, the CAS fails, hands you the up-to-date value, and you simply recompute and try again. No lock is held at any point — threads only retry when they actually collided, which under low contention is almost never.

#include <stdatomic.h>

void atomic_increment(atomic_int *counter) {
    int old = atomic_load(counter);           /* 1. read current value */
    while (!atomic_compare_exchange_weak(     /* 3. try to swap it in */
               counter, &old, old + 1)) {     /*    expected=old, desired=old+1 */
        /* CAS failed: someone changed *counter first.
           compare_exchange has already reloaded `old`
           with the real current value, so just loop and
           retry with the fresh value. */
    }
}

Read the loop carefully, because it is the shape of almost every lock-free algorithm. We snapshot old. We ask CAS to move counter from old to old + 1. If it works, great — we incremented exactly once, atomically, with no lock. If it fails, it is because another thread got there first; and the C library’s compare_exchange helpfully writes the real current value back into old for us, so the next iteration computes old + 1 from correct, freshly-observed data. The loop can spin under heavy contention, but it never blocks and never deadlocks.

One caution before you fall in love with CAS: the ABA problem. CAS only checks whether the value equals expected — it cannot tell whether the value changed and changed back while you were not looking. Suppose you read A, and before your CAS another thread changes the location A to B and back to A. Your CAS sees A, concludes "nothing changed", and succeeds — but the world did move, and for pointer-based structures that can mean reusing memory that was freed and reallocated. For a plain counter ABA is harmless; for lock-free stacks and queues it is a real hazard, defused with version tags (a counter bumped on every change) or careful memory reclamation.

Compare-and-swap (CAS)

Atomic: if *addr == expected, store desired and succeed; else report the actual value and fail. The conditional RMW that underlies most lock-free code.

Optimistic update

Read, compute a new value, CAS it in; retry only if you collided. Cheap when contention is low, because you never hold a lock.

compare_exchange_weak vs strong

The C11 forms of CAS. weak may fail spuriously (even when values match) but is cheaper in a loop; strong never fails spuriously — use it when you are not already retrying.

ABA problem

A value changes A -> B -> A between your read and your CAS; CAS sees A and wrongly assumes nothing happened. Fixed with version counters or safe reclamation.

You rarely hand-write CAS loops in day-to-day code, and you almost never write the raw instructions. Modern languages expose atomics directly. In C, the C11 standard added <stdatomic.h>: mark a variable _Atomic (or use the atomic_int typedef) and ordinary-looking operations on it become atomic. The compiler emits the right hardware instruction — a locked add, a CAS loop, whatever the target CPU needs — and guarantees the operation is indivisible.

Recall the racy counter from ch14: ten threads each incrementing a shared int a million times, and a final total stubbornly short of ten million because counter++ is really load, add, store, and updates get lost when two threads interleave. Here is that program fixed with one keyword and one function call — no mutex, no lock, no critical section.

#include <stdatomic.h>
#include <pthread.h>

atomic_int counter = 0;          /* was: int counter (the racy version) */

void *worker(void *arg) {
    for (int i = 0; i < 1000000; i++)
        atomic_fetch_add(&counter, 1);   /* indivisible: load+add+store as one */
    return NULL;
}

int main(void) {
    pthread_t t[10];
    for (int i = 0; i < 10; i++) pthread_create(&t[i], NULL, worker, NULL);
    for (int i = 0; i < 10; i++) pthread_join(t[i], NULL);
    printf("%d\n", counter);     /* always exactly 10000000 */
    return 0;
}

atomic_fetch_add is the key line. It performs the entire load-add-store as one indivisible hardware operation, so no increment can ever be lost, no matter how the ten threads interleave. The total is now exactly ten million, every run. The whole family works this way: atomic_fetch_add, atomic_fetch_sub, atomic_fetch_or, atomic_exchange, atomic_load, atomic_store, and the compare_exchange functions from the previous section.

It is worth being precise about what this bought us and what it did not. The atomic version is correct and, for a single counter, faster than taking a mutex around counter++, because there is no lock to acquire and release and no risk of a waiter being put to sleep. But atomics only make individual operations indivisible. The instant your invariant spans two variables — "always credit one account exactly as much as you debit another" — a single atomic op cannot protect the pair, and you are back to needing a lock or a carefully designed lock-free algorithm. Atomics shine for one independent word; they are not a general replacement for mutual exclusion.

Now the subtlety that humbles everyone who writes lock-free code for the first time. You imagine the machine executes your memory operations in the order you wrote them. It does not. Both the compiler (when optimising) and the CPU (when running) freely reorder loads and stores, as long as the result looks identical to a single thread. For one thread that is invisible and wonderful. For several threads sharing memory, it means another core can observe your writes happening in a different order than your source lists them.

The classic trap is the publish pattern. One thread writes some data, then sets a ready flag; another thread waits for the flag, then reads the data. In source order it is airtight. But if the writer’s two stores get reordered, ready=1 can become visible before data=42, and the reader sees the flag, dives in, and reads stale data. Nothing in the code is "wrong" line by line — the ordering assumption is what is wrong.

int data = 0;
atomic_int ready = 0;

void producer(void) {
    data = 42;                                       /* the payload */
    atomic_store_explicit(&ready, 1,                 /* publish it... */
                          memory_order_release);     /* ...release: no store above
                                                         may sink below this point */
}

void consumer(void) {
    while (atomic_load_explicit(&ready,
                          memory_order_acquire) == 0) /* acquire: no load below may
        ;                                            /*   hoist above this point */
    assert(data == 42);   /* guaranteed to see 42, never the stale 0 */
}

The fix is a memory barrier (or fence): an instruction that forbids reordering across it. You rarely place raw fences yourself — instead you tag atomic operations with an ordering. A release store guarantees that every write you did before it is visible to any thread that later performs an acquire load on the same variable. Together, release on the writer and acquire on the reader form a one-way gate: everything the producer did before the release is seen by the consumer after the acquire. That is the acquire/release pair, and it is exactly the handshake a lock performs — unlock() is a release, lock() is an acquire, which is why code inside a critical section never leaks out.

C11 atomics default to the strongest and simplest ordering, sequentially consistent (memory_order_seq_cst): every thread sees all sequentially-consistent operations in one single global order, the way your intuition expects. It is the safe default and what atomic_fetch_add used in the previous section. Weaker orderings like acquire/release and relaxed are faster on some architectures but demand you reason precisely about what may be seen when. This is the point where lock-free programming stops being clever and starts being genuinely hard.

Memory reordering

The compiler and CPU may execute loads/stores out of program order, as long as a single thread cannot tell. Other threads can tell.

Memory barrier / fence

An instruction that forbids reordering of memory operations across it, forcing a defined order that other cores can rely on.

Acquire / release

A one-way gate: a release store publishes all prior writes to any thread doing a matching acquire load. This is what lock/unlock do underneath.

Sequential consistency

The strongest, most intuitive ordering — one global order all threads agree on. The safe default for atomics; sometimes slower than weaker orderings.

With CAS in hand we can define the terms precisely, because they are progress guarantees, not vibes. An algorithm is lock-free if the system as a whole always makes progress: at any moment, at least one thread is guaranteed to complete its operation in a finite number of steps. Individual threads may retry their CAS loop many times — one unlucky thread could keep losing races indefinitely — but the structure as a whole never stalls, and crucially, no thread holds a lock that can freeze everyone else.

Wait-free is the stronger promise: every thread completes its operation in a bounded number of its own steps, regardless of what other threads do. No thread can be starved, ever. Wait-free algorithms exist and are prized in hard-real-time and safety-critical systems, but they are dramatically harder to design and often slower in the common case, so they are rare in practice. Most "lock-free" code you meet in the wild is lock-free but not wait-free.

The appeal is real. A lock-free structure cannot deadlock, because there is no lock to hold in the wrong order. It cannot suffer priority inversion, where a low-priority thread holding a lock blocks a high-priority one (the bug that famously froze the Mars Pathfinder). If a thread is suspended by the scheduler mid-operation — or even crashes — it cannot leave the whole structure locked and unusable, because it was never holding anything. For latency-sensitive systems where an unlucky pause is unacceptable, that resilience is worth a great deal.

And now the honest half. Lock-free data structures — queues, stacks, hash maps — exist, are used in real systems, and are extraordinarily hard to get right. The Treiber stack and the Michael-Scott queue are famous precisely because getting a correct concurrent structure is a publishable result. You must handle the ABA problem, reason about every memory-ordering interleaving from section 5, and solve memory reclamation (when is it safe to free a node another thread might still be reading? — the answer involves hazard pointers or epoch-based reclamation, each a project in itself). Bugs are timing-dependent, rare, and nearly impossible to reproduce in a debugger.

Blocking

Uses locks; if the lock-holder is delayed or descheduled, everyone waiting behind it is stuck. Simple to write, vulnerable to deadlock and priority inversion.

Lock-free

The system as a whole always makes progress — some thread always completes — even though an individual thread may retry indefinitely. No locks, so no deadlock.

Wait-free

Every thread completes in a bounded number of its own steps; no thread can ever be starved. The strongest guarantee, the hardest to build, and rare.

Priority inversion

A high-priority thread stuck waiting on a lock held by a low-priority one. Lock-free code cannot suffer it, since no lock is held.

Step back to where this touches your daily work, because atomics are not an exotic curiosity — you already depend on them constantly. The most pervasive example is reference counting. Every shared_ptr in C++, every Arc in Rust, every reference-counted object in a garbage-collected runtime uses an atomic counter to track how many references point at it. When the count hits zero the object is freed. If that increment and decrement were not atomic, two threads dropping the last two references could both see "not zero yet" and neither would free the memory — or worse, both would, and you get a double-free crash. Atomic refcounts are the quiet reason shared ownership works across threads at all.

The second everyday case is counters and statistics: request counts, bytes served, cache hits, metrics scraped by your monitoring. Dozens of worker threads bump these constantly, and a mutex around each increment would serialise your whole server on a number nobody reads until a dashboard asks. A single atomic_fetch_add is the right tool — one independent word, updated from many threads, no invariant spanning anything else. This is atomics at their best. The third case is the concurrent data structures from the last section: the lock-free queue passing work between a producer and a consumer thread, sitting inside a library you did not write but very much rely on.

So when should you actually reach past a plain mutex? The honest, experience-earned answer is: less often than you think. A mutex is simple to reason about, hard to get subtly wrong, and on modern systems an uncontended lock is remarkably cheap — often just an atomic operation or two under the hood. Atomics win clearly for a single independent variable like a counter or a flag. Lock-free structures win when you have measured a genuine bottleneck, need to eliminate blocking for latency or fault-tolerance reasons, and can use a proven implementation. Everywhere else, the clarity of a mutex is worth more than the theoretical speed of code you cannot confidently debug.

• ▸Reach for an atomic when the shared state is a single independent word — a counter, a flag, a reference count. It is correct, lock-free, and faster than a mutex there.
• ▸Keep the plain mutex from ch15 when your invariant spans several fields, or the critical section does real work. Correctness and readability beat cleverness.
• ▸Only consider a lock-free data structure after profiling proves lock contention is your bottleneck — and then use a library, do not hand-roll it.
• ▸Remember memory ordering: hand-written lock-free code that passes on x86 can still fail on ARM. The safe default ordering exists for a reason.

That completes the picture we opened in ch14 and ch15. Concurrency creates races; locks tame them by enforcing mutual exclusion; and now you know what is under the lock — the atomic read-modify-write instructions, test-and-set, exchange, and compare-and-swap, that the CPU provides because software alone cannot build mutual exclusion. You have seen how language-level atomics fix a race without a lock, why memory reordering makes lock-free code genuinely hard, and where the lock-free trade-off is honestly worth it. Use the sharp tools when the measurement calls for them, respect how easy they are to get wrong, and default to the plain mutex the rest of the time. That judgement — not the cleverest primitive — is what separates engineers who ship correct concurrent systems from those who ship heisenbugs.