08 - Lock-Free Data Structures: Atomic Operations, Memory Ordering and Compare-and-Swap

When a lock is the problem, and what replaces it

A lock serializes: while one thread works in the critical section the others wait, and if that thread is stopped by the scheduler the others wait along with it. A lock-free structure removes the lock and uses atomic CPU instructions, in particular compare-and-swap (CAS): "write the new value only if memory still holds the value I read". The guarantee you get is precise and weaker than people believe: lock-free means that, at any moment, at least one thread completes its operation even if others are stopped or slowed; it does not mean that every thread advances (that is wait-free) nor that the structure is faster than a lock.

Before building anything it is worth looking at what the standard library already offers, because in practice you almost never write the structures by hand: AtomicInteger, AtomicReference, LongAdder, ConcurrentLinkedQueue. The experiments below serve to understand why they work and where they break. All the Java listings were compiled and run with OpenJDK 21.0.13; the two in C++ with g++ (C++17) on x86-64. The counts are exact, the timings change from one machine to another. For the part on traditional locks see race conditions and deadlocks.

The CAS loop: read, decide, try to write

The CAS loop always has the same shape: read the value, compute the new one, attempt the compareAndSet; if another thread changed the value in the meantime, the attempt fails and you start again. The concrete example is a warehouse with 100,000 items and eight threads attempting 160,000 withdrawals: exactly 100,000 must succeed, and the remainder must be zero. The listing tries it with a plain counter and with the CAS loop.

import java.util.concurrent.*;
import java.util.concurrent.atomic.*;

// 100,000 items in stock, 8 threads trying to withdraw one at a time.
public class Scorta {
    static int semplice = 100_000;                          // get-then-set: NOT atomic
    static final AtomicInteger atomica = new AtomicInteger(100_000);

    // CAS loop: "decrement only if positive"
    static boolean prelevaCas() {
        while (true) {
            int corrente = atomica.get();                   // 1. read
            if (corrente <= 0) return false;                // 2. business condition
            if (atomica.compareAndSet(corrente, corrente - 1)) {
                return true;                                // 3. nobody touched the value: done
            }
            // CAS failed: someone changed the value, reread and retry
        }
    }

    static boolean prelevaSemplice() {
        int corrente = semplice;
        if (corrente <= 0) return false;
        semplice = corrente - 1;                            // other threads may have written in the meantime
        return true;
    }

    public static void main(String[] args) throws Exception {
        for (String modo : new String[] {"plain", "cas"}) {
            AtomicInteger riusciti = new AtomicInteger();
            ExecutorService exec = Executors.newFixedThreadPool(8);
            for (int t = 0; t < 8; t++) {
                exec.submit(() -> {
                    for (int i = 0; i < 20_000; i++) {      // 160,000 attempts on 100,000 items
                        boolean ok = modo.equals("cas") ? prelevaCas() : prelevaSemplice();
                        if (ok) riusciti.incrementAndGet();
                    }
                });
            }
            exec.shutdown();
            exec.awaitTermination(30, TimeUnit.SECONDS);
            int residuo = modo.equals("cas") ? atomica.get() : semplice;
            System.out.printf("%-9s successful withdrawals: %d, remainder: %d, successful + remainder = %d%n",
                modo, riusciti.get(), residuo, riusciti.get() + residuo);
        }
    }
}

// Output:
// plain     successful withdrawals: 160000, remainder: 27118, successful + remainder = 187118
// cas       successful withdrawals: 100000, remainder: 0, successful + remainder = 100000

With the plain int the successful withdrawals are 160,000 out of 100,000 available items and the remainder stays 27,118: the sum "successful + remainder" should have been 100,000, and it is 187,118. The program sold more than it had, and also left some behind. With the CAS loop the sum comes out right: 100,000 successful withdrawals, remainder zero. The business condition ("only if positive") is always in the loop before the compareAndSet, and the CAS checks that the condition still holds when you write. An AtomicInteger.decrementAndGet() would not be enough, because it cannot refuse to go below zero.

Treiber stack: one pointer, one CAS

The classic lock-free stack keeps a single pointer, top. For push you create the node, make it point to the current top and attempt the CAS on top; for pop you read top and try to move it to the next node. The algorithm is attributed to R. K. Treiber (IBM report RJ 5118, April 1986, cited in the paper by Michael and Scott). The listing subjects it to four producers and four consumers with a million items and checks that nothing is lost or duplicated by comparing the sums.

import java.util.concurrent.*;
import java.util.concurrent.atomic.*;

public class Treiber {
    static class Nodo<T> {
        final T valore;
        Nodo<T> next;
        Nodo(T valore) { this.valore = valore; }
    }

    static class Pila<T> {
        private final AtomicReference<Nodo<T>> top = new AtomicReference<>();

        void push(T v) {
            Nodo<T> nuovo = new Nodo<>(v);
            while (true) {
                Nodo<T> vecchio = top.get();
                nuovo.next = vecchio;                         // the new one points to the old top
                if (top.compareAndSet(vecchio, nuovo)) return;
            }
        }

        T pop() {
            while (true) {
                Nodo<T> vecchio = top.get();
                if (vecchio == null) return null;
                if (top.compareAndSet(vecchio, vecchio.next)) return vecchio.valore;
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Pila<Integer> pila = new Pila<>();
        int produttori = 4, perProduttore = 250_000;
        AtomicLong sommaPush = new AtomicLong(), sommaPop = new AtomicLong();
        AtomicInteger contati = new AtomicInteger();
        ExecutorService exec = Executors.newFixedThreadPool(8);
        CountDownLatch fine = new CountDownLatch(produttori);

        for (int p = 0; p < produttori; p++) {
            final int base = p * perProduttore;
            exec.submit(() -> {
                for (int i = 1; i <= perProduttore; i++) {
                    pila.push(base + i);
                    sommaPush.addAndGet(base + i);
                }
                fine.countDown();
            });
        }
        for (int c = 0; c < 4; c++) {
            exec.submit(() -> {
                while (fine.getCount() > 0 || contati.get() < produttori * perProduttore) {
                    Integer v = pila.pop();
                    if (v != null) { sommaPop.addAndGet(v); contati.incrementAndGet(); }
                }
            });
        }
        exec.shutdown();
        exec.awaitTermination(60, TimeUnit.SECONDS);
        System.out.println("inserted: " + produttori * perProduttore + ", extracted: " + contati.get());
        System.out.println("sum inserted = " + sommaPush.get() + ", sum extracted = " + sommaPop.get());
        System.out.println("stack empty at the end: " + (pila.pop() == null));
    }
}

// Output:
// inserted: 1000000, extracted: 1000000
// sum inserted = 500000500000, sum extracted = 500000500000
// stack empty at the end: true

A million inserted, a million extracted, identical sum (500,000,500,000): conservation holds. This does not prove correctness, because a concurrent test can pass by chance, but it is a sensible check for finding losses and duplications. Note the use of a new node for each push: in Java the garbage collector prevents a node from being reused while anyone references it, and that is why in this implementation the following problem does not arise.

The ABA problem

CAS checks the value of top, not its history. If between the read and the CAS the value goes from A to B and back to A, the CAS succeeds even though the structure underneath has changed. It happens when nodes are reused (a pool, or an allocator that returns the same address), typically in C and C++. The paper by Michael and Scott defines it this way, and proposes as a common solution a modification counter attached to the pointer; it specifies that the counter does not guarantee the absence of ABA (it can wrap around) but makes it extremely unlikely.

import java.util.*;
import java.util.concurrent.atomic.*;

// ABA reproduced deterministically: the "threads" are simulated by running the steps by hand
// in the problematic order. The stack REUSES nodes (pool), as in C/C++ without a garbage collector.
public class Aba {
    static class Nodo {
        final String nome;
        Nodo next;
        Nodo(String nome) { this.nome = nome; }
    }

    static final AtomicReference<Nodo> top = new AtomicReference<>();
    static final AtomicStampedReference<Nodo> topStamp = new AtomicStampedReference<>(null, 0);

    public static void main(String[] args) {
        Nodo a = new Nodo("A"), b = new Nodo("B"), c = new Nodo("C");
        a.next = b; b.next = c;
        top.set(a);
        topStamp.set(a, 0);

        // Thread 1 starts pop(): reads top and top.next, then is suspended
        Nodo visto = top.get();                 // A
        Nodo prossimo = visto.next;             // B
        int[] bollo = new int[1];
        Nodo vistoStamp = topStamp.get(bollo);  // A, stamp 0
        int bolloVisto = bollo[0];

        // Thread 2: pop A, pop B, push A (same object, reused)
        top.set(b);                             // pop A
        top.set(c);                             // pop B  (B leaves the stack: nobody uses it anymore)
        a.next = c;                             // push A reusing the node
        top.set(a);                             // stack: A -> C
        topStamp.set(a, 3);                     // with the stamp, each of the three changes increments it: now it is 3

        // Thread 1 resumes: CAS(top, A, B)
        boolean riuscito = top.compareAndSet(visto, prossimo);
        System.out.println("without stamp: CAS succeeded = " + riuscito + ", top = " + top.get().nome
            + "  <- B had already been extracted: the state is corrupted");

        boolean riuscitoStamp = topStamp.compareAndSet(vistoStamp, prossimo, bolloVisto, bolloVisto + 1);
        System.out.println("with stamp:    CAS succeeded = " + riuscitoStamp + ", top = " + topStamp.getReference().nome
            + "  <- the stamp has changed, the CAS fails and the thread rereads");
    }
}

// Output:
// without stamp: CAS succeeded = true, top = B  <- B had already been extracted: the state is corrupted
// with stamp:    CAS succeeded = false, top = A  <- the stamp has changed, the CAS fails and the thread rereads

Here the threads are simulated: I run by hand, in the problematic order, the steps the interleaving produces. Thread 1 has read top = A and A.next = B and is suspended. Meanwhile thread 2 pops A, pops B and reinserts A (the same object), so the stack is A→C. Thread 1 resumes and does CAS(top, A, B): it succeeds, and top becomes B, a node already extracted. With AtomicStampedReference, which pairs the reference with an integer (the "stamp"), the CAS compares the reference and the stamp: the stamp went from 0 to 3, and the attempt fails. The more sophisticated alternatives are hazard pointers and epoch-based reclamation (the mechanism of the Rust crate crossbeam-epoch): I did not try them here.

Michael and Scott queue: two pointers and mutual help

A queue has two ends, so a single CAS is not enough: insertion must first link the new node after the last one, then move tail, and between the two steps another thread can arrive. The solution of Michael and Scott (1996) is that whoever finds tail lagging advances it themselves: the mutual help is what makes the algorithm lock-free. The documentation of ConcurrentLinkedQueue says it uses a non-blocking algorithm based on that paper. The listing is a teaching implementation, with the same conservation check and one more control: FIFO order per producer.

import java.util.concurrent.*;
import java.util.concurrent.atomic.*;

public class CodaMs {
    static class Nodo<T> {
        volatile T valore;
        final AtomicReference<Nodo<T>> next = new AtomicReference<>();
        Nodo(T valore) { this.valore = valore; }
    }

    static class Coda<T> {
        private final AtomicReference<Nodo<T>> head, tail;

        Coda() {
            Nodo<T> sentinella = new Nodo<>(null);
            head = new AtomicReference<>(sentinella);
            tail = new AtomicReference<>(sentinella);
        }

        void enqueue(T v) {
            Nodo<T> nuovo = new Nodo<>(v);
            while (true) {
                Nodo<T> ultimo = tail.get();
                Nodo<T> dopo = ultimo.next.get();
                if (ultimo != tail.get()) continue;           // tail has changed: reread
                if (dopo == null) {
                    if (ultimo.next.compareAndSet(null, nuovo)) {   // link the node
                        tail.compareAndSet(ultimo, nuovo);          // move tail (if it fails, someone else takes care of it)
                        return;
                    }
                } else {
                    tail.compareAndSet(ultimo, dopo);         // tail is lagging: help it advance
                }
            }
        }

        T dequeue() {
            while (true) {
                Nodo<T> primo = head.get();
                Nodo<T> ultimo = tail.get();
                Nodo<T> dopo = primo.next.get();
                if (primo != head.get()) continue;
                if (primo == ultimo) {
                    if (dopo == null) return null;            // empty
                    tail.compareAndSet(ultimo, dopo);         // tail is lagging
                } else {
                    T v = dopo.valore;
                    if (head.compareAndSet(primo, dopo)) return v;
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Coda<Long> coda = new Coda<>();
        int produttori = 4, perProduttore = 200_000;
        AtomicLong sommaPop = new AtomicLong();
        AtomicInteger contati = new AtomicInteger();
        AtomicInteger fuoriOrdine = new AtomicInteger();
        ExecutorService exec = Executors.newFixedThreadPool(8);
        CountDownLatch fine = new CountDownLatch(produttori);

        for (int p = 0; p < produttori; p++) {
            final long id = p;
            exec.submit(() -> {
                for (long i = 1; i <= perProduttore; i++) coda.enqueue(id * 1_000_000L + i);
                fine.countDown();
            });
        }
        for (int c = 0; c < 4; c++) {
            exec.submit(() -> {
                long[] ultimoPerProduttore = new long[produttori];
                while (fine.getCount() > 0 || contati.get() < produttori * perProduttore) {
                    Long v = coda.dequeue();
                    if (v == null) continue;
                    sommaPop.addAndGet(v);
                    contati.incrementAndGet();
                    int p = (int) (v / 1_000_000L);
                    if (v < ultimoPerProduttore[p]) fuoriOrdine.incrementAndGet(); // FIFO per producer, as seen by this consumer
                    ultimoPerProduttore[p] = v;
                }
            });
        }
        exec.shutdown();
        exec.awaitTermination(60, TimeUnit.SECONDS);

        long atteso = 0;
        for (long p = 0; p < produttori; p++)
            for (long i = 1; i <= perProduttore; i++) atteso += p * 1_000_000L + i;
        System.out.println("extracted: " + contati.get() + " out of " + produttori * perProduttore);
        System.out.println("expected sum = " + atteso + ", extracted sum = " + sommaPop.get());
        System.out.println("out-of-order extractions per producer: " + fuoriOrdine.get());
    }
}

// Output:
// extracted: 800000 out of 800000
// expected sum = 1280000400000, extracted sum = 1280000400000
// out-of-order extractions per producer: 0

The 800,000 items inserted by four producers all come out, the sum matches (1,280,000,400,000) and, for each consumer, the items from the same producer always come out in increasing order: zero inversions. The sentinel (an initial empty node) avoids the special case of the empty queue in the two pointers. In production use ConcurrentLinkedQueue, already verified and optimized: the exercise serves to see where each compareAndSet is indispensable.

Memory ordering: why atomicity is not enough

An atomic operation guarantees that you never see a half-written value; it does not guarantee when other threads see the other writes. CPUs and compilers reorder accesses, and the language's memory model says which reorderings are allowed. In Java the pillar is the happens-before relation: the language specification says a read may see a write if no happens-before ordering prevents it. The listing shows the most concrete consequence, the visibility of a flag.

public class Visibilita {
    static boolean semplice = false;            // no visibility guarantee
    static volatile boolean volatile_ = false;  // writes and reads synchronized

    static String prova(boolean usaVolatile) throws Exception {
        semplice = false; volatile_ = false;
        Thread t = new Thread(() -> {
            if (usaVolatile) { while (!volatile_) { } }
            else { while (!semplice) { } }       // the JIT may hoist the read out of the loop
        });
        t.setDaemon(true);
        t.start();
        Thread.sleep(300);                      // give the JIT time to compile the loop
        if (usaVolatile) volatile_ = true; else semplice = true;
        t.join(2000);
        return t.isAlive() ? "STILL IN THE LOOP after 2 s" : "terminated";
    }

    public static void main(String[] args) throws Exception {
        System.out.println("volatile field:     " + prova(true));
        System.out.println("non-volatile field: " + prova(false));
    }
}

// Output:
// volatile field:     terminated
// non-volatile field: STILL IN THE LOOP after 2 s

With volatile the loop ends as soon as the flag changes. Without it, the thread was still looping two seconds later: the JIT compiler removed the read from the loop, because in the absence of synchronization nothing forbids it from reading the field just once. It is not a defect of HotSpot: the program has no happens-before between the write and the read, and the result is allowed by the specification. The outcome depends on the JIT and the machine: I observed the hang, but it is not guaranteed to happen everywhere, and that is the nature of the bug.

Languages like C++ and Rust offer finer control, with five levels: Relaxed (atomicity only), Release (a write that publishes everything preceding it), Acquire (a read that sees what the matching release published), AcqRel (the two together, for read-modify-write operations) and SeqCst (also a single total order). The Rust documentation specifies that its orderings are those of C++20. The C++ listing publishes a non-atomic piece of data with a release/acquire pair.

#include <atomic>
#include <cstdio>
#include <thread>

int main() {
    int dato = 0;                                // NON-atomic data, published through the flag
    std::atomic<bool> pronto{false};
    int visto = -1;

    std::thread produttore([&] {
        dato = 42;                                                 // 1. write the data
        pronto.store(true, std::memory_order_release);             // 2. publish: "everything before this is visible"
    });
    std::thread consumatore([&] {
        while (!pronto.load(std::memory_order_acquire)) { }        // 3. wait for the publication
        visto = dato;                                              // 4. the data is guaranteed visible
    });
    produttore.join();
    consumatore.join();
    printf("the consumer sees dato = %d\n", visto);
}

// Output:
// $ g++ -std=c++17 -O2 -pthread Pubblica.cpp && ./a.out
// the consumer sees dato = 42
//
// $ ... -fsanitize=thread, with release/acquire: no report
// $ ... -fsanitize=thread, with memory_order_relaxed instead of release: "WARNING: ThreadSanitizer: data race"

The normal output is 42, but it proves nothing: on x86-64, where writes are not reordered among themselves by the CPU, even the wrong version often gives 42 (I tried a store buffering test with 2,000,000 iterations and observed no anomalous outcome, so I do not report it). The useful check is ThreadSanitizer: with release/acquire it reports nothing; replacing release with relaxed, it reports a data race on the variable dato. The tool checks the formal ordering, not the behavior of a particular CPU.

When lock-free pays off (and when it does not)

The case where the atomic wins clearly is the heavily contended counter. The listing compares AtomicLong and LongAdder, which splits the total across several cells to reduce contention, with eight threads and five million increments each.

import java.util.concurrent.*;
import java.util.concurrent.atomic.*;

public class Adder {
    static long misura(Runnable incremento, int thread, int perThread) throws Exception {
        long t0 = System.nanoTime();
        ExecutorService exec = Executors.newFixedThreadPool(thread);
        for (int t = 0; t < thread; t++) {
            exec.submit(() -> { for (int i = 0; i < perThread; i++) incremento.run(); });
        }
        exec.shutdown();
        exec.awaitTermination(60, TimeUnit.SECONDS);
        return (System.nanoTime() - t0) / 1_000_000;
    }

    public static void main(String[] args) throws Exception {
        int thread = 8, perThread = 5_000_000;
        for (int giro = 0; giro < 2; giro++) {                 // the first round warms up the JIT
            AtomicLong atomico = new AtomicLong();
            LongAdder adder = new LongAdder();
            long a = misura(atomico::incrementAndGet, thread, perThread);
            long b = misura(adder::increment, thread, perThread);
            if (giro == 1) {
                System.out.println("AtomicLong: " + a + " ms, total " + atomico.get());
                System.out.println("LongAdder:  " + b + " ms, total " + adder.sum());
            }
        }
    }
}

// Output:
// AtomicLong: 538 ms, total 40000000
// LongAdder:  20 ms, total 40000000

The result is identical (40,000,000), but the LongAdder takes 20 ms against 538 ms, about 27 times less on this machine. The documentation recommends it when many threads update a common sum, for example for statistics; the price is that sum() is not an atomic snapshot if there are concurrent writes. The ratio depends on the number of cores and on the hardware: the figure is a single measurement, not a benchmark.

Lock-free is not the default. It introduces complexity (ABA, orderings, memory to reclaim), and it is not automatically faster than a lock when contention is low. The operating rule is: start from the standard library classes (ConcurrentLinkedQueue, ConcurrentHashMap, LongAdder), measure the bottleneck with a profiler and only then consider a structure of your own, knowing that you will need tests like the ones above and a tool like ThreadSanitizer.

What you can do now

You can write a CAS loop with a business condition, you know why a Treiber stack in Java does not suffer from ABA and how you would reproduce it with reused nodes, you can read a Michael and Scott queue, and you can tell atomicity from visibility. You know that a flag without volatile can stay invisible forever and that ThreadSanitizer shows you the difference between release and relaxed.

The next article moves to an application problem: backpressure and flow control, that is, what to do when the producer is faster than the consumer. For the concurrency models compared, see the first article in the series. For the same question between machines instead of between threads, see distributed systems.

The counts (160,000, 27,118, 1,000,000, 800,000) and the timings (20 ms against 538 ms) come from single runs on one x86-64 machine; the conservation counts are exact, the warehouse remainder without CAS and the timings change with every run.