Concurrency, Synchronization & Deadlock Questions

Direct answer

The Michael-Scott queue (a multi-producer multi-consumer, MPMC, queue) is a singly linked list with a permanent dummy node (a placeholder node holding no real item, so head and tail are never null), a head that points at the dummy and a tail that points at (or one node behind) the last node. Enqueue links a new node after the last node with a CAS (compare-and-swap, an atomic "write only if still equal to what I read") on that node's next, then tries to swing tail. Dequeue reads the node after the dummy and CASes head forward so that node becomes the new dummy. The operations help each other: whoever notices tail lagging behind a linked node moves it forward before doing its own work, so no thread ever waits for another to finish. The linearization point (the single instant at which the operation appears to take effect) is the successful link CAS for enqueue and the successful head CAS for a non-empty dequeue. ABA (a CAS succeeds because the value looks unchanged although it was changed and changed back) and memory reclamation (when it is safe to free a removed node) are solved either by version-counted links over a recycled pool (shown below), by hazard pointers or epochs, or by a garbage collector (GC).

How it works

1. Invariants. head always points at the dummy. tail is either the last node or exactly one node behind it. Nodes are only ever added at the end and removed at the front.
2. Enqueue. Read tail and tail->next. If next is null, CAS tail->next from null to the new node (linearization point). Then CAS tail to the new node; if that fails, someone already helped. If next is not null, tail is lagging: CAS tail to next (helping) and retry.
3. Dequeue. Read head, tail and head->next. If head == tail and next is null, the queue is empty (it linearizes at the read of next that returned null; the re-check that head is unchanged, made right after that read, confirms the read saw the current dummy). If head == tail and next is not null, help move tail. Otherwise read the value from next before the CAS (afterwards the node may be recycled), then CAS head from the old dummy to next (linearization point); the old dummy is released.
4. Why helping matters. Without it, a thread stalled between its link CAS and its tail swing would block every other enqueuer: that is lock-based behaviour in disguise. With it the algorithm stays lock-free: a failed CAS means somebody else's CAS succeeded.

A traced example: helping with a lagging tail

Start with an empty queue: one dummy node D, head -> D, tail -> D, D.next = null.

1. Enqueuer E1 wants to add item A. It reads tail = D and D.next = null, then CASes D.next from null to A. This succeeded: A is now in the queue (the linearization point), even though tail still points at D. Now E1 is descheduled before it swings tail.
2. Enqueuer E2 wants to add B. It reads tail = D and D.next = A, which is not null, so it knows tail is lagging. It does not wait for E1: it CASes tail from D to A (helping), then loops.
3. E2 reads tail = A, A.next = null, CASes A.next from null to B (E2's linearization point), then CASes tail from A to B.
4. E1 wakes up and tries to CAS tail from D to A. It fails because tail is already B, which is fine: E1 treats a failed swing as "someone helped" and returns. The list is D -> A -> B and the order A then B is the order of the link CASes.
5. A dequeuer reads head = D, D.next = A, reads A's value, then CASes head from D to A. A is now the dummy and the caller gets A's value (that CAS is the dequeue's linearization point).

Empty-queue case: a dequeuer reads head = D, then D.next, and gets null; it then checks that head is still D. Since head is unchanged, D was still the dummy when D.next was read, and a null next at that moment means no item sat after the dummy, so the queue was empty at exactly that read. That read is the linearization point of the failed dequeue. If head had changed in between, the read may describe a stale dummy and the loop retries.

Worked example: a tested C++ implementation

Nodes live in a fixed pool of 4,096. A link is (tag << 32) | node index (a counted link: the index plus a version number); every successful CAS on a link bumps its tag, so a link that came back to the same index is still told apart. Released nodes go to a tagged free list (itself a lock-free stack), so memory is never returned to the allocator while a stale thread may read it. Reading guide: pack/idx_of/tag_of build and split a link; release_node/acquire_node push and pop the free list; enqueue is step 2 of the algorithm above (the else branch is helping, the line after the loop is the optional tail swing); dequeue is step 3 (its first branch handles empty or lagging, its second reads the value then CASes head); main runs the producers and consumers and checks the results. Two producers each enqueue 200,000 numbers tagged with their producer id; two consumers dequeue them; the checks are no loss, no duplicates, and that each consumer sees each producer's numbers in increasing order (per-producer first-in first-out, FIFO, order).

// Michael-Scott queue over a fixed node pool with counted (tagged) links.
// A link is (tag << 32) | node index. Nodes are recycled through a tagged free list,
// so no node is ever returned to the allocator while a stale thread may still read it.
#include <atomic>
#include <cstdint>
#include <cstdio>
#include <thread>
#include <vector>

constexpr uint32_t NIL = 0xFFFFFFFFu;
constexpr uint32_t POOL = 4096;
static uint64_t pack(uint32_t tag, uint32_t idx) { return (uint64_t(tag) << 32) | idx; }
static uint32_t idx_of(uint64_t l) { return uint32_t(l); }
static uint32_t tag_of(uint64_t l) { return uint32_t(l >> 32); }

struct Node {
    std::atomic<uint32_t> value{0};
    std::atomic<uint64_t> next{pack(0, NIL)};
    std::atomic<uint32_t> free_next{NIL};
};

class MSQueue {
    Node nodes_[POOL];
    std::atomic<uint64_t> head_, tail_, free_{pack(0, NIL)};

    void release_node(uint32_t n) {                       // push onto the tagged free list
        uint64_t f = free_.load();
        do { nodes_[n].free_next.store(idx_of(f)); }
        while (!free_.compare_exchange_weak(f, pack(tag_of(f) + 1, n)));
    }
    uint32_t acquire_node() {                             // pop from the tagged free list
        uint64_t f = free_.load();
        for (;;) {
            if (idx_of(f) == NIL) return NIL;
            uint32_t nx = nodes_[idx_of(f)].free_next.load();
            if (free_.compare_exchange_weak(f, pack(tag_of(f) + 1, nx))) return idx_of(f);
        }
    }
public:
    MSQueue() {
        for (uint32_t i = 1; i < POOL; ++i) release_node(i);
        head_ = tail_ = pack(0, 0);                        // node 0 is the dummy
    }
    bool enqueue(uint32_t v) {
        uint32_t n = acquire_node();
        if (n == NIL) return false;                        // pool exhausted
        nodes_[n].value.store(v);
        nodes_[n].next.store(pack(tag_of(nodes_[n].next.load()), NIL));
        uint64_t tail;
        for (;;) {
            tail = tail_.load();
            uint64_t next = nodes_[idx_of(tail)].next.load();
            if (tail != tail_.load()) continue;            // snapshot changed, retry
            if (idx_of(next) == NIL) {
                // LINEARIZATION POINT of enqueue: this CAS links the new node after the last node.
                if (nodes_[idx_of(tail)].next.compare_exchange_weak(next, pack(tag_of(next) + 1, n))) break;
            } else {
                // Tail is lagging: HELP the enqueuer that linked a node but has not swung Tail yet.
                tail_.compare_exchange_weak(tail, pack(tag_of(tail) + 1, idx_of(next)));
            }
        }
        tail_.compare_exchange_strong(tail, pack(tag_of(tail) + 1, n));  // optional swing; others may do it
        return true;
    }
    bool dequeue(uint32_t& out) {
        for (;;) {
            uint64_t head = head_.load(), tail = tail_.load();
            uint64_t next = nodes_[idx_of(head)].next.load();
            if (head != head_.load()) continue;
            if (idx_of(head) == idx_of(tail)) {
                if (idx_of(next) == NIL) return false;     // empty (linearizes at the load of next above)
                tail_.compare_exchange_weak(tail, pack(tag_of(tail) + 1, idx_of(next)));  // HELP
            } else {
                uint32_t v = nodes_[idx_of(next)].value.load();   // read BEFORE the CAS: node may be recycled after it
                // LINEARIZATION POINT of a non-empty dequeue: Head moves past the old dummy.
                if (head_.compare_exchange_weak(head, pack(tag_of(head) + 1, idx_of(next)))) {
                    release_node(idx_of(head));            // old dummy goes back to the pool
                    out = v;
                    return true;
                }
            }
        }
    }
};

int main() {
    constexpr int P = 2, C = 2, PER = 200000;
    static MSQueue q;
    std::atomic<long> consumed{0};
    std::vector<std::vector<uint32_t>> got(C);
    std::vector<std::thread> th;
    for (int p = 0; p < P; ++p)
        th.emplace_back([&, p] {
            for (uint32_t i = 0; i < PER; ++i)
                while (!q.enqueue(uint32_t(p) << 24 | i)) std::this_thread::yield();
        });
    for (int c = 0; c < C; ++c)
        th.emplace_back([&, c] {
            uint32_t v;
            while (consumed.load() < long(P) * PER)
                if (q.dequeue(v)) { got[c].push_back(v); consumed.fetch_add(1); }
        });
    for (auto& t : th) t.join();
    // Checks: every item exactly once, and each consumer sees each producer's items in increasing order.
    std::vector<std::vector<char>> seen(P, std::vector<char>(PER, 0));
    long total = 0; bool order_ok = true, dup = false;
    for (int c = 0; c < C; ++c) {
        uint32_t last[P]; for (auto& l : last) l = 0xFFFFFFFFu;
        for (uint32_t v : got[c]) {
            uint32_t p = v >> 24, i = v & 0xFFFFFF;
            if (last[p] != 0xFFFFFFFFu && i <= last[p]) order_ok = false;
            last[p] = i;
            if (seen[p][i]++) dup = true;
            ++total;
        }
    }
    printf("dequeued %ld of %d, duplicates=%d, per-producer FIFO order kept=%d\n", total, P * PER, dup, order_ok);
}

g++ -std=c++20 -O1 -g -Wall -Wextra -fsanitize=thread msqueue.cpp -o m && ./m (g++ 14.4.0; TSan, the data race detector, reported nothing) and the same program at -O2 run twice without TSan all printed:

dequeued 400000 of 400000, duplicates=0, per-producer FIFO order kept=1

All atomics use the default sequentially consistent order (every thread sees one agreed order of all these operations) to keep the proof obligation small; relaxing to acquire/release on the link CASes and loads is possible but should be done only with a model-checked argument (a tool that explores every interleaving of a small model of the algorithm, rather than trusting a hand proof). Not executed: counter wraparound (see the test plan).

ABA and memory reclamation: the options

For a pointer-passing queue I would take hazard pointers when threads can be preempted for long periods (bounded garbage matters) and epochs when threads are short-lived and the per-operation cost dominates.

The Java version

ConcurrentLinkedQueue in the JDK is documented as based on the Michael and Scott non-blocking algorithm. The same algorithm in plain AtomicReference form needs no tag and no free list: the collector guarantees a node is not reused while referenced, which removes the reclamation half of ABA. AtomicStampedReference (it succeeds only if both the reference and an integer stamp match) is needed only if you recycle node objects yourself. A four-thread run, each thread pushing and enqueuing 100,000 numbers, checked the item count and the sum:

import java.util.concurrent.atomic.AtomicReference;

public class GcLockFree {
    // Treiber stack: nodes are plain garbage-collected objects, never reused by this code.
    static final class TStack<T> {
        private static final class Node<T> { final T item; Node<T> next; Node(T i) { item = i; } }
        private final AtomicReference<Node<T>> head = new AtomicReference<>();
        void push(T item) {
            Node<T> n = new Node<>(item);
            Node<T> h;
            do { h = head.get(); n.next = h; } while (!head.compareAndSet(h, n));
        }
        T pop() {
            Node<T> h;
            do { h = head.get(); if (h == null) return null; } while (!head.compareAndSet(h, h.next));
            return h.item;
        }
    }

    // Michael-Scott queue: same algorithm, no tags, no free list.
    static final class MSQueue<T> {
        private static final class Node<T> { final T item; final AtomicReference<Node<T>> next = new AtomicReference<>(); Node(T i) { item = i; } }
        private final AtomicReference<Node<T>> head, tail;
        MSQueue() { Node<T> d = new Node<>(null); head = new AtomicReference<>(d); tail = new AtomicReference<>(d); }
        void enqueue(T item) {
            Node<T> n = new Node<>(item);
            for (;;) {
                Node<T> t = tail.get(), nx = t.next.get();
                if (t != tail.get()) continue;
                if (nx == null) {
                    if (t.next.compareAndSet(null, n)) { tail.compareAndSet(t, n); return; }  // linearization point
                } else tail.compareAndSet(t, nx);                                              // help
            }
        }
        T dequeue() {
            for (;;) {
                Node<T> h = head.get(), t = tail.get(), nx = h.next.get();
                if (h != head.get()) continue;
                if (h == t) { if (nx == null) return null; tail.compareAndSet(t, nx); }
                else { T v = nx.item; if (head.compareAndSet(h, nx)) return v; }               // linearization point
            }
        }
    }

    public static void main(String[] a) throws Exception {
        final int THREADS = 4, PER = 100_000;
        TStack<Integer> s = new TStack<>();
        MSQueue<Integer> q = new MSQueue<>();
        Thread[] ts = new Thread[THREADS];
        for (int t = 0; t < THREADS; t++) { ts[t] = new Thread(() -> {
            for (int i = 0; i < PER; i++) { s.push(i); q.enqueue(i); } }); ts[t].start(); }
        for (Thread t : ts) t.join();
        long sumS = 0, nS = 0, sumQ = 0, nQ = 0; Integer v;
        while ((v = s.pop()) != null) { sumS += v; nS++; }
        while ((v = q.dequeue()) != null) { sumQ += v; nQ++; }
        long expect = (long) THREADS * ((long) (PER - 1) * PER / 2);
        System.out.println("stack: " + nS + " items, sum " + sumS + "; queue: " + nQ + " items, sum " + sumQ + "; expected " + (THREADS * PER) + " items, sum " + expect);
    }
}

java GcLockFree.java (JDK 21) printed:

stack: 400000 items, sum 19999800000; queue: 400000 items, sum 19999800000; expected 400000 items, sum 19999800000

Related queue designs and where they fit

• Bounded array queue (for example a logging pipeline that must not allocate): each slot carries a sequence number (a counter stored with the slot that tells producers and consumers whose turn it is) saying whether it is ready for a producer or a consumer; a full ring makes enqueue fail or the caller drop or block, and there is no reclamation problem at all.
• Lock-free linked list with deletion: removing a node in the middle needs a "logically deleted" mark in the node's next pointer, set by CAS before the node is physically unlinked, so that no one links a new node after a node being removed.
• Network I/O or mobile (Java/Kotlin) producers: the shape above, with the GC doing the reclamation.
• Use from interrupt and thread context across cores: no GC and no allocator in an interrupt service routine, so use the pooled design with version-tagged CAS; every thread and ISR needs the ordering the CASes provide, and reclamation is the pool plus tag.

Test plan for a lock-free MPMC queue

1. A tiny pool (a few nodes) so recycling happens constantly: the use-after-free and reclamation-lag bugs only show then.
2. A sanitizer build (TSan, and AddressSanitizer for the pointer version) in CI.
3. Invariants checked after the run: every item exactly once, per-producer order, and queue empty at the end.
4. Wraparound: start the tag counters near 0xFFFFFFFF so the wrap happens in the test.
5. Empty and one-element transitions with one enqueuer racing one dequeuer, plus long runs with many yields to vary the interleaving.

Pitfalls

Reading the value after the head CAS; forgetting to help; assuming tail is always the last node; and using a tag too short for the update rate.

What a work-stealing scheduler is. A fork-join pool (Java's ForkJoinPool is the familiar one) runs many small tasks on a fixed set of worker threads. Instead of one shared queue that every worker fights over, each worker owns its own double-ended queue (a "deque", pronounced "deck"). A worker takes work from its own deque and only goes to other workers' deques when its own is empty. That is "stealing". Most of the time a worker touches only its own deque, so there is almost nothing to contend on.

1. What each worker's deque looks like. A circular array of task slots plus two integer indices: bottom (where the owner pushes and pops) and top (where thieves take from). The deque holds the tasks at indices top up to bottom - 1, stored at index mod capacity. top only ever grows (it is a 64-bit long, so wrap-around is not a practical concern), which matters later for the ABA problem (a value that changes A to B and back to A, fooling a compare-and-swap). bottom does not only grow: the owner's pop moves it back down by one each time it takes an item, and only the owner ever writes it.

2. Which end is used by whom.

• The owner pushes new tasks at the bottom and pops from the bottom. That is last-in-first-out (LIFO), like a stack. When a task forks children and then joins them, the owner immediately runs the most recently forked child, which is the one whose data is still in its CPU cache, and the recursion stays depth-first, so the deque stays small.
• Thieves take from the top, the opposite end. That is first-in-first-out for them, and the task at the top is the oldest one, which in divide-and-conquer code is the biggest remaining chunk (the root of the largest unexplored subtree). One steal therefore hands the thief a lot of work, so steals are rare. Using opposite ends also means owner and thief almost never want the same slot.
• The ForkJoinPool documentation confirms the default "locally stack-based" order for a worker's own tasks, and offers an asyncMode flag for local first-in-first-out order for event-style tasks that are never joined.

3. How a steal is made safe without a global lock. The only slot owner and thief can fight over is the very last item. The rules:

• Only the owner writes bottom; only the owner writes slots. Thieves never write bottom and never write slots.
• top is advanced by compare-and-swap (CAS: "set top to t+1 only if it still equals t, atomically"). A thief reads top, reads bottom, reads the slot at top, then CASes top from t to t+1. If the CAS fails, another thief (or the owner) took that task first, so this thief gives up (returns ABORT) and tries elsewhere. Because top never goes backwards, a stale slot value can never be mistaken for a fresh one, so ABA does not arise on top: a thief that read top = 3 can only succeed with a CAS from 3 to 4 while top is still 3, and since the index only grows, 3 can never come back after it has been passed.
• The owner's push writes the slot first, then publishes it by storing bottom + 1 with release semantics (release: everything written before this store is visible to a thread that reads the new value with acquire or stronger). The code below uses seq_cst for this store, which is stronger than release and includes it, so its comment "release: publishes the slot write" names the property this store is relied on for. A thief that sees the new bottom is therefore guaranteed to see the task in the slot.
• The owner's pop is the delicate one. It first stores bottom - 1 (claiming the item), and only then reads top. Both sides do "write my index, then read the other side's index", which is the classic pattern that needs sequentially consistent ordering (seq_cst: all threads agree on one global order of these operations). With anything weaker, each side could read the other's old index, as if the other had not yet written. A hand trace with illustrative numbers: the deque holds two tasks, top = 3 and bottom = 5 (slots 3 and 4). Thief A steals slot 3 (top becomes 4). Thief B reads top = 4 and a stale bottom = 5, so it plans to take slot 4. The owner meanwhile stores bottom = 4 and reads a stale top = 3; since 3 < 4 it concludes there are two or more items and takes slot 4 with no CAS. Both take slot 4. Under seq_cst this cannot happen: B's read of bottom before the owner's store, and the owner's read of top before A's CAS, cannot both hold in one global order, so either B sees bottom = 4 and finds the deque empty, or the owner sees top = 4 and falls into the last-item CAS path. And for the last item itself: with top = 3 and bottom = 4, the owner and a thief both try to move top from 3 to 4 by CAS; only one CAS can succeed, so only one takes the task. If after the claim top is still below bottom, there are at least two items and the owner takes the slot with no CAS at all. If exactly one item remains (top == bottom), the owner must win a CAS on top against any thief; the loser comes away empty-handed. If top > bottom, the deque was already empty.

This design is known as the Chase-Lev deque, after its authors. Here is a fixed-capacity version (no growth), compiled and run with GCC 14.4.0 in a Linux container. The ring size is a power of two, so & (CAP - 1) is the modulo. The code uses seq_cst on the index operations rather than separate fences, because ThreadSanitizer (TSan, the compiler's data-race detector) does not model standalone fences. That is simpler and slightly slower than the hand-tuned acquire/release plus fence version published for this algorithm, which is a different, more delicate design and is not reproduced here.

// Fixed-capacity Chase-Lev work-stealing deque (no resizing), seq_cst on the index operations.
#include <atomic>
#include <thread>
#include <vector>
#include <cstdio>
#include <cstdlib>
constexpr long CAP = 1 << 12;             // power of two; owner must never hold more than CAP items
constexpr int EMPTY = -1, ABORT = -2;
struct Deque {
  std::atomic<long> top{0}, bottom{0};    // thieves advance top; only the owner writes bottom
  std::atomic<int> slot[CAP];
  bool push(int x) {                      // owner only
    long b = bottom.load(std::memory_order_relaxed), t = top.load(std::memory_order_acquire);
    if (b - t >= CAP) return false;       // full: a real pool would grow or run the task inline
    slot[b & (CAP - 1)].store(x, std::memory_order_relaxed);
    bottom.store(b + 1, std::memory_order_seq_cst);   // release: publishes the slot write
    return true;
  }
  int pop() {                             // owner only, LIFO end
    long b = bottom.load(std::memory_order_relaxed) - 1;
    bottom.store(b, std::memory_order_seq_cst);       // announce the claim BEFORE reading top
    long t = top.load(std::memory_order_seq_cst);
    if (t > b) { bottom.store(b + 1, std::memory_order_relaxed); return EMPTY; }
    int x = slot[b & (CAP - 1)].load(std::memory_order_relaxed);
    if (t == b) {                         // last item: race the thieves for it
#ifndef BROKEN
      if (!top.compare_exchange_strong(t, t + 1, std::memory_order_seq_cst)) x = EMPTY;
#endif
      bottom.store(b + 1, std::memory_order_relaxed);
    }
    return x;
  }
  int steal() {                           // any thread, FIFO end
    long t = top.load(std::memory_order_seq_cst);
    long b = bottom.load(std::memory_order_seq_cst);
    if (t >= b) return EMPTY;
    int x = slot[t & (CAP - 1)].load(std::memory_order_relaxed);
    if (!top.compare_exchange_strong(t, t + 1, std::memory_order_seq_cst)) return ABORT;
    return x;
  }
};
int main() {
  const int N = 200000, THIEVES = 3;
  static Deque d;
  static std::atomic<int> seen[N];
  std::atomic<bool> done{false};
  auto take = [&](int x) { if (x >= 0) seen[x].fetch_add(1, std::memory_order_relaxed); };
  std::vector<std::thread> th;
  for (int i = 0; i < THIEVES; i++) th.emplace_back([&] {
    while (!done.load(std::memory_order_acquire)) take(d.steal());
  });
  int next = 0;
  while (next < N) {                       // owner: push a burst, pop part of it, repeat
    for (int k = 0; k < 7 && next < N; k++) if (d.push(next)) next++;
    for (int k = 0; k < 4; k++) take(d.pop());
  }
  for (int x; (x = d.pop()) != EMPTY;) take(x);
  while (true) { int x = d.steal(); if (x == EMPTY) break; take(x); }
  done.store(true, std::memory_order_release);
  for (auto& t : th) t.join();
  long missing = 0, dup = 0;
  for (int i = 0; i < N; i++) { int c = seen[i].load(); if (c == 0) missing++; else if (c > 1) dup++; }
  std::printf("tasks=%d missing=%ld duplicated=%ld\n", N, missing, dup);
  return (missing || dup) ? 1 : 0;
}

What was run and what it showed.

• g++ -std=c++17 -O1 -g -Wall -Wextra -fsanitize=thread deque.cpp -o t, then ./t five times: every run printed tasks=200000 missing=0 duplicated=0 and TSan reported no data race (3 thieves plus the owner, 200,000 task ids, each counted in a per-id array).
• g++ -std=c++17 -O2 -Wall -Wextra deque.cpp -o o, three runs: same line, missing=0 duplicated=0.
• To prove the harness can fail, the same program was compiled with -DBROKEN (which removes the last-item CAS from pop). Over repeated runs of both the -O2 build and the TSan -O1 build the duplicate count was in the thousands and varied widely from run to run, and it was never 0. The exact count is timing-dependent and is not the point; the point is that it was never 0. So the CAS on the last item is the load-bearing line, and the test catches its absence.
• Caveat: this ran natively in an aarch64 Linux container (a weakly ordered CPU, which is a good place to find ordering bugs). Passing tests is evidence, not a proof; a production deque would also get model checking or a long stress run on x86-64 as well.

4. What keeps contention low.

• Owner operations (push, and pop when two or more items remain) never need a compare-and-swap and never wait for another thread, but they are not free: both read top, the line thieves write, and the seq_cst store to bottom that pop depends on compiles with GCC 14 -O2 on x86-64 to an xchg instruction (an implicitly locked read-modify-write, regenerated with g++ -O2 -S), while on AArch64 it is a plain release-store instruction. Production deques avoid that cost with the weaker acquire/release-plus-fence formulation, which the code shown here does not use.
• Thieves are the exception. They only touch another worker's top and bottom, and only when they are idle, so busy workers are not slowed.
• Steal from the oldest end: big chunks, so few steals per unit of work.
• Choose victims (the workers being stolen from) randomly (or try a few random victims, then back off and park the thread, meaning put it to sleep until woken): this spreads thieves across deques instead of all hammering worker 0.
• Keep top and bottom on separate cache lines (pad to 64 bytes on typical x86-64 and arm64 parts; check your target). Otherwise the owner's writes to bottom and thieves' CASes on top bounce one line between cores (false sharing). The fixed-capacity code above declares the two indices side by side and does not add this padding.
• A failed CAS returns ABORT instead of spinning. The thief just moves to another victim.
• A thief that finds every deque empty should not spin forever: after some failed rounds it parks (sleeps on a condition variable or a futex, the Linux kernel primitive that lets a thread sleep on an address until another thread wakes it) and a push wakes it. Waking is the one place a lock or a kernel call re-enters, and it is off the hot path.

5. What this sketch leaves out, and how a production deque handles it.

• Growth: when bottom - top reaches capacity, a production deque allocates a bigger array, copies the live range, and publishes the new array pointer. Old arrays cannot be freed while a thief might still be reading them, so they are retired and freed later (safe memory reclamation: for example epochs, where an array is freed only after every thread has moved past the moment it was retired, or hazard pointers, where a thread announces the address it is reading and the freer skips announced addresses), or the pool simply runs the task inline when the deque is full.
• Task type: slots here are int ids so the slot reads are atomic and TSan-clean. A real pool stores task pointers in std::atomic<Task*> slots for the same reason. A thief reads a slot before its CAS succeeds, so the slot read must be an atomic read, and a result that loses the CAS is discarded.
• Joins: a worker that waits for a child it forked should keep executing other tasks (its own deque first, then steals) instead of blocking, otherwise a small pool can starve itself.
• Fairness and idle handling, plus exceptions inside tasks, are policy layers on top of the deque.

How to say it in an interview. One sentence per decision: per-worker deque so there is no global lock; owner LIFO for cache locality and small depth; thieves FIFO for big chunks and rare steals; only the last element is contended and it is settled by one CAS on top; and the pop-claims-then-reads-top step needs seq_cst. Then offer the failure you tested: remove that CAS and tasks run twice.

What the code does and what can go wrong

// thread A                     // thread B
payload = 42;                   while (flag == 0) {}   // spin
flag = 1;                       use(payload);

The intent: A writes the data, then raises the flag; B waits for the flag, then reads the data. With no ordering constraints, three separate things can break this.

1. Language level: it is a data race. Two threads access payload (and a plain flag) without synchronization and one access is a write. In C and C++ that is undefined behaviour (the program has no defined meaning), regardless of the hardware.
2. The compiler can reorder or hoist. It may move the flag store before the payload store (they are independent as far as one thread can tell), or read a plain flag once and turn the spin into an infinite loop (hoisting the load, that is, moving it out of the loop because nothing in the loop appears to change it). This is the failure on x86 too.
3. The CPU can reorder (Arm). x86 keeps stores in order with other stores and loads in order with other loads (a strongly ordered model, TSO, total store order), so once the compiler behaves, A's two stores become visible in order and B's two loads happen in order. Arm is weakly ordered: A's payload and flag stores can become visible to B in either order, and B's load of payload can execute before its load of flag. B can therefore see flag == 1 and still read the old payload. That is the Arm-versus-x86 difference the question asks about: x86 hides the hardware reordering, Arm does not, so code that "works on my x86 machine" can fail on a phone, a Raspberry Pi or an Apple-silicon machine.

The minimal fix: release on the store, acquire on the load

Make the flag a std::atomic<int>. Store it with memory_order_release and load it with memory_order_acquire. A release store guarantees everything this thread wrote before it is visible to a thread that acquires the same variable and reads the stored value. cppreference puts it: if the acquire load reads the value written by the release store, all writes that happened before the store become visible to the loading thread. payload can stay a plain int: the release/acquire pair orders it. You do not need seq_cst (the strongest, default ordering) or explicit fences here, because one flag between one writer and one reader needs only this pairing.

#include <atomic>
#include <iostream>
#include <thread>

#ifdef BROKEN
constexpr auto STORE_ORDER = std::memory_order_relaxed;
constexpr auto LOAD_ORDER  = std::memory_order_relaxed;
#else
constexpr auto STORE_ORDER = std::memory_order_release;
constexpr auto LOAD_ORDER  = std::memory_order_acquire;
#endif

struct Slot {
    int payload;                       // plain data, written before the flag is raised
    std::atomic<int> ready{0};
};

int main() {
    constexpr int ROUNDS = 20000;
    static Slot slots[ROUNDS];
    std::atomic<int> go{0};
    long bad = 0;
    std::thread writer([&] {
        while (!go.load()) {}
        for (int i = 0; i < ROUNDS; ++i) {
            slots[i].payload = i + 1;                  // 1) write the payload
            slots[i].ready.store(1, STORE_ORDER);      // 2) then raise the flag
        }
    });
    std::thread reader([&] {
        go.store(1);
        for (int i = 0; i < ROUNDS; ++i) {
            while (slots[i].ready.load(LOAD_ORDER) == 0) {}   // spin on the flag
            if (slots[i].payload != i + 1) ++bad;      // 3) read the payload
        }
    });
    writer.join(); reader.join();
    std::cout << "stale payload reads: " << bad << "\n";
}

Run in a gcc:14 container (aarch64) with g++ -std=c++20 -O1 -g -fsanitize=thread -pthread:

• Built with -DBROKEN (both flag operations relaxed, which gives atomicity but no ordering), ThreadSanitizer printed WARNING: ThreadSanitizer: data race with a read of payload in one thread and a previous write of the same address in the other.
• Built without -DBROKEN (release store, acquire load) it printed stale payload reads: 0 and no warning.

Plain (unsanitized) runs of the broken build on this aarch64 VM printed stale payload reads: 0: a weak-ordering failure can be rare or hardware dependent, so a run that does not fail proves nothing. The data-race report from TSan is the evidence, and -DBROKEN shows why the pairing is needed even when the bad value never shows up.

What the compiler emits

Compiled with g++ -std=c++20 -O2 -S (GCC 14.4), these four functions on a global std::atomic<int> flag:

#include <atomic>
std::atomic<int> flag;
void store_relaxed() { flag.store(1, std::memory_order_relaxed); }
void store_release() { flag.store(1, std::memory_order_release); }
void spin_acquire()  { while (flag.load(std::memory_order_acquire) == 0) {} }
void spin_relaxed()  { while (flag.load(std::memory_order_relaxed) == 0) {} }

The table lists the flag access that each function compiles to. The surrounding address setup (adrp/add on AArch64), the loop test and branch (cbz, or testl and je) and ret are left out.

Key to the table: on AArch64, w1 is a 32-bit register and x0 and x1 are 64-bit registers holding addresses, and [x0] means "the memory at the address in x0". str and ldr are the plain store and load, stlr is store-release and ldar is load-acquire. On x86-64, movl is a 32-bit move and flag(%rip) is the flag's address written relative to the instruction pointer.

On Arm, release and acquire turn into dedicated instructions; on x86 they are plain moves because the hardware order already matches, and only the compiler is restricted (cppreference says the same: on strongly ordered systems no extra instructions are issued, the compiler just may not move accesses across the operation). In this tiny function the relaxed and release versions happen to compile identically on x86, but the language rules still differ, and a larger function may be compiled differently.

The same pattern elsewhere

The shape "write the data, then publish with a release store; consume with an acquire load" is the same when an interrupt handler on another core of a system-on-chip sets a ready flag for the main loop, or when a thread builds a new rule table and publishes a pointer to it for packet-processing workers. The same applies to a game: a simulation thread builds the next frame's state (positions, animation data) and publishes a pointer to it with a release store, and the render thread acquire-loads that pointer before drawing from it. In each case publish with release, read with acquire, and never write to the published data again until readers are known to have finished with it.

Direct answer

The ABA problem is a compare-and-swap (CAS) succeeding because a location holds the same value as before, although the structure around it changed in between. Thread 1 reads the top of a lock-free stack as A, is preempted (the scheduler pauses it mid-operation); other threads pop A, pop B, free B and push A back; thread 1's CAS (head == A?) succeeds and installs the stale next pointer (B), which now points at freed memory. Prevent it either by making the value carry history (a version tag packed with the pointer or index, so A-with-tag-3 is not A-with-tag-6) or by never freeing or reusing a node while another thread might still hold a pointer to it; a tag alone leaves the read of a freed node unsafe, so tagged designs over heap nodes also need a fixed pool or a reclamation scheme. The version tag is the core fix for the CAS itself; the table below lists the ways to make freeing safe (hazard pointers, epoch-based reclamation, RCU, a fixed node pool), each explained there.

The pop that breaks

A lock-free stack (a Treiber stack, the standard lock-free stack design) is a singly linked list whose head pointer is updated by CAS. The textbook pop:

old = head
do { if (old == NULL) return NULL; next = old->next; }      // step 1: read next
while (!CAS(&head, &old, next));                             // step 2: swing head from old to next

It is correct only if "head still equals old" implies "old->next is still next". That is false when old can leave the stack and come back.

Starting from a stack a -> b -> c:

The CAS only compared head with a, and a really is at the head again. Everything T1 knew about what follows a is stale. Two failures follow: the stack's head now points at a node that is no longer in the stack, and the next operation reads b->next from freed memory (a use-after-free: reading or writing memory after it was given back to the allocator, where its contents may be anything).

Reproduced deterministically, and the fix, in a Linux container

A real race needs lucky timing, so this program plays the two threads' steps in a fixed order on one thread, using the real atomic operations. Part 2 is the fix (an index plus a tag packed into one 64-bit atomic over a small node array), run through the same interleaving. In part 2 the 64-bit word is the tag in its high 32 bits and the node index in its low 32 bits: pack(tag, idx) shifts the tag left by 32 and ORs in the index, idx_of keeps the low half and tag_of shifts the high half down. For example pack(3, 0) is 3 x 2^32 + 0 = 12,884,901,888, the word T1 reads: tag 3, index 0. T2's two pops and one push each add 1 to the tag (3, then 4, 5, 6) while the index goes 0, then 1, then 2, then 0 again, so the head word becomes pack(6, 0): the same index as before but a different word, and T1's compare with pack(3, 0) fails. Part 1 is the pointer version.

#include <stdatomic.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

/* ---------- Part 1: pointer-based Treiber stack, scripted ABA interleaving ---------- */
typedef struct Node { int val; struct Node *next; } Node;
static _Atomic(Node *) head;

static void push(Node *n) {
    Node *old = atomic_load(&head);
    do { n->next = old; } while (!atomic_compare_exchange_weak(&head, &old, n));
}
static Node *pop(void) {                       /* the textbook pop */
    Node *old = atomic_load(&head), *next;
    do {
        if (!old) return NULL;
        next = old->next;                      /* (1) read next */
    } while (!atomic_compare_exchange_weak(&head, &old, next)); /* (2) CAS */
    return old;
}
static void part1(void) {
    Node *a = malloc(sizeof *a), *b = malloc(sizeof *b), *c = malloc(sizeof *c);
    a->val = 1; b->val = 2; c->val = 3;
    push(c); push(b); push(a);                 /* stack: a -> b -> c */

    /* T1 starts pop: reads old = a, next = b ... then is descheduled before its CAS. */
    Node *t1_old = atomic_load(&head), *t1_next = t1_old->next;
    /* T2 runs to completion: pop a, pop b (and free it), push a back. Stack is now a -> c. */
    Node *x = pop(); Node *y = pop(); free(y); push(x);
    printf("part1: T2 done; head is again a (same address): %s; real stack is a -> c\n", atomic_load(&head) == a ? "yes" : "no");
    /* T1 resumes: head == a, so its CAS succeeds, installing the stale next = b (freed). */
    Node *expected = t1_old;
    int ok = atomic_compare_exchange_strong(&head, &expected, t1_next);
    printf("part1: T1's CAS succeeded: %s; head now points at the freed node b\n", ok ? "yes" : "no");
    Node *p = pop();                           /* next operation reads head->next through the freed node */
    printf("part1: next pop returned %p\n", (void *)p);
}

/* ---------- Part 2: index + tag packed into one 64-bit atomic ---------- */
#define NIL 0xFFFFFFFFu
typedef struct { int val; uint32_t next; } Slot;
static Slot slots[3];
static _Atomic uint64_t top2;                  /* high 32 bits: tag, low 32 bits: index */
static uint64_t pack(uint32_t tag, uint32_t idx) { return ((uint64_t)tag << 32) | idx; }
static uint32_t idx_of(uint64_t v) { return (uint32_t)v; }
static uint32_t tag_of(uint64_t v) { return (uint32_t)(v >> 32); }

static void push2(uint32_t i) {
    uint64_t old = atomic_load(&top2);
    do { slots[i].next = idx_of(old); } while (!atomic_compare_exchange_weak(&top2, &old, pack(tag_of(old) + 1, i)));
}
static int pop2(uint32_t *out) {
    uint64_t old = atomic_load(&top2);
    do {
        if (idx_of(old) == NIL) return 0;
        uint32_t nxt = slots[idx_of(old)].next;
        if (atomic_compare_exchange_weak(&top2, &old, pack(tag_of(old) + 1, nxt))) { *out = idx_of(old); return 1; }
    } while (1);
}
static void part2(void) {
    atomic_store(&top2, pack(0, NIL));
    push2(2); push2(1); push2(0);              /* stack: 0 -> 1 -> 2 */
    uint64_t t1_old = atomic_load(&top2);      /* T1 reads top = (tag 3, idx 0) and next = 1, then stalls */
    uint32_t t1_next = slots[idx_of(t1_old)].next;
    uint32_t x, y; pop2(&x); pop2(&y); push2(x);   /* T2: pop 0, pop 1, push 0 back */
    printf("part2: top index is again %u, but tag went %u -> %u\n", idx_of(atomic_load(&top2)), tag_of(t1_old), tag_of(atomic_load(&top2)));
    uint64_t expected = t1_old;
    int ok = atomic_compare_exchange_strong(&top2, &expected, pack(tag_of(t1_old) + 1, t1_next));
    printf("part2: T1's CAS succeeded: %s\n", ok ? "yes" : "no (stale tag, so T1 must re-read)");
    printf("part2: lock-free? %s\n", atomic_is_lock_free(&top2) ? "yes" : "no");
}
int main(void) { setvbuf(stdout, NULL, _IONBF, 0); part2(); part1(); return 0; }

gcc -O1 -g -Wall -Wextra -fsanitize=address,undefined aba.c -o aba && ./aba in a gcc:14 container (aarch64); the program turns off stdout buffering because AddressSanitizer aborts the process. The part lines and the AddressSanitizer summary:

part2: top index is again 0, but tag went 3 -> 6
part2: T1's CAS succeeded: no (stale tag, so T1 must re-read)
part2: lock-free? yes
part1: T2 done; head is again a (same address): yes; real stack is a -> c
part1: T1's CAS succeeded: yes; head now points at the freed node b
==12==ERROR: AddressSanitizer: heap-use-after-free on address 0x502000000038 ...
SUMMARY: AddressSanitizer: heap-use-after-free /w/aba.c:18 in pop

(The tag went from 3 to 6 because each of the three T2 operations, two pops and a push, adds 1.) With the pointer version the CAS succeeds and the next pop reads old->next from the freed node at line 18. AddressSanitizer is a compiler-inserted memory checker; "heap-use-after-free" is its name for exactly that, an access to heap memory (from malloc) after free. With the tagged version the same interleaving makes T1's CAS fail, and T1 would re-read the head and retry correctly.

In production code the "A comes back" step usually happens without the code doing it deliberately: free(a) then a later malloc returns the same address for a new node, so a new node looks like the old one to a pointer comparison.

Ways to prevent it

A tag stops the corrupting CAS; it does not by itself make freeing a node safe, because T1 may still dereference old->next of a node T2 just freed (reading old->next at step 1 is itself a hazard when nodes are freed). That second problem is safe memory reclamation (deciding when freeing a node can no longer hurt a thread still reading it). The two fixes overlap rather than always stack: a tag-based design needs a never-freed pool or a reclamation scheme to make the old->next read safe, while hazard pointers or epoch-based reclamation used alone also remove the ABA window, because a node that another thread may still reference is never freed and so its address cannot come back as a "new" node. Real implementations therefore choose tag plus index pool, or reclamation without a tag, not necessarily both.

Pitfalls

• Assuming load-linked/store-conditional (LL/SC, the CPU pair used on Arm and POWER instead of CAS: the store succeeds only if nothing wrote the location since the load) is always a way out. It detects any intervening write, so the stack's ABA does not arise on that primitive, but real hardware can fail the store for other reasons, and C++ and Rust code only see the CAS abstraction, so the portable answer is still the tag plus safe reclamation.
• Believing a successful CAS means "nothing changed". It means "the value I compared is the same".
• Tagging with a counter and also reusing freed memory immediately, which fixes the CAS but keeps the use-after-free.
• Skipping a atomic_is_lock_free check on the packed type: a 16-byte (pointer + tag) CAS may not be lock-free on every platform; the index-plus-tag layout above fits in 64 bits (it printed lock-free? yes here).
• Testing with real threads only: a deterministic replay as above is the reliable way to prove a fix handles the interleaving.

Direct answer

An atomic operation is one that other threads can only observe as either not started or fully finished, never half done. A read-modify-write such as counter++ is normally three steps (load, add, store), so two threads can both load the same old value and one update is lost; an atomic increment does all three as one indivisible step. Atomics beat a mutex for a single independent variable (a statistics counter, a flag). They do not help when an invariant spans several variables or a check and an action must be made together.

Primitives a platform typically offers

Compare-and-swap and fetch-and-modify do most of the practical work; the other four are the simplest cases of them or the hardware pieces they are built from.

Compiler built-ins matter on embedded toolchains: GCC documents the __atomic built-ins as approximately matching the requirements of the C++11 memory model and says new code should use them rather than the older __sync built-ins (a family that predates the C++11 memory model). If the hardware has no lock-free instruction for an operation (a single hardware instruction that does the whole operation, with no lock taken behind the scenes), GCC emits a call to an external routine (its libatomic support library) instead, which may be implemented with a lock, so check lock-freedom with std::atomic<T>::is_always_lock_free for your target type.

Where an atomic beats a mutex

A statistics counter incremented by four threads. A mutex works but makes contending threads queue, and a waiting thread may be put to sleep (a context switch: the operating system's scheduler swaps another thread onto the CPU), which is slow if the lock is held only for one addition. An atomic fetch_add never blocks and cannot deadlock.

#include <atomic>
#include <cstdint>
#include <cstdio>
#include <string>
#include <thread>
#include <vector>

constexpr int THREADS = 4, PER_THREAD = 100000;

// (1) A plain counter: the read-modify-write is three steps (load, add, store).
// Run "./atomics plain" for the racy version, "./atomics" for the atomic one.
long plain_counter = 0;
std::atomic<long> atomic_counter{0};

int main(int argc, char** argv) {
    bool use_plain = argc > 1 && std::string(argv[1]) == "plain";
    std::vector<std::thread> ts;
    for (int t = 0; t < THREADS; t++)
        ts.emplace_back([&] {
            for (int i = 0; i < PER_THREAD; i++) {
                if (use_plain) ++plain_counter;                                  // data race
                else atomic_counter.fetch_add(1, std::memory_order_relaxed);     // atomic RMW
            }
        });
    for (auto& t : ts) t.join();
    long got = use_plain ? plain_counter : atomic_counter.load();
    std::printf("%s: expected %d, got %s%ld\n", use_plain ? "plain" : "atomic",
                THREADS * PER_THREAD, got == THREADS * PER_THREAD ? "" : "(lost updates) ", got);
    std::printf("atomic<long> always lock-free: %d\n", (int)std::atomic<long>::is_always_lock_free);

    // Compiler built-in form of the same operation, as used from C or embedded toolchains.
    long builtin = 0;
    __atomic_fetch_add(&builtin, 5, __ATOMIC_RELAXED);
    std::printf("builtin result: %ld\n", builtin);
}

Built with g++ -std=c++20 -O2 -pthread in a GCC 14 container on arm64:

$ ./at plain
plain: expected 400000, got (lost updates) 134335
atomic<long> always lock-free: 1
builtin result: 5
$ ./at
atomic: expected 400000, got 400000
atomic<long> always lock-free: 1
builtin result: 5

The plain count lands far below 400,000 (typically somewhere around 100,000 to 200,000 here) and changes from run to run; the atomic version is exact. Compiling the same file with -fsanitize=thread makes ThreadSanitizer print WARNING: ThreadSanitizer: data race for the plain counter line and nothing for the atomic version. The counter is relaxed (memory_order_relaxed) because it only needs to be counted correctly, with no ordering against other data: the C++ reference describes relaxed operations as guaranteeing atomicity and modification order only.

Where an atomic does not beat a mutex

• A rule that spans two variables. A transfer that moves 50 from checking to savings while keeping their total fixed needs both changes to be visible together. Making each variable atomic still lets another thread see the money gone from one account and not yet in the other, or approve two transfers against the same balance (a check-then-act race). One mutex around both updates, or packing both values into a single atomic word, fixes it.
• A long or blocking critical section. Atomics cannot make a thread wait politely. Spinning on an atomic burns CPU, where a mutex lets the thread sleep.
• Complex structures. Lock-free linked structures bring the ABA problem (a value changes A to B and back to A, so a CAS wrongly succeeds) and memory-reclamation problems. A mutex is far easier to get right.

Cost of choosing atomics in a hot path

Each atomic needs a justified memory order, which says how much ordering it imposes on the other reads and writes around it: relaxed guarantees only that this one operation is atomic; acquire/release is a pair, where a release store publishes everything the thread wrote before it and an acquire load that sees that store also sees those writes; sequentially consistent (seq_cst) adds a single order of all such operations that every thread agrees on. A reviewer must reason about every one of these choices, whereas a mutex gives one simple rule. Recommendation: start with a mutex; use atomics for independent counters and flags, defaulting to the strongest order (seq_cst) unless profiling shows it matters and you can explain why a weaker one is correct. What would flip it: a measured contention problem on a single variable with no invariant tying it to other data.