multithreading · advanced

Concurrency: Lock-Free Queue — Michael-Scott CAS Loop, ABA, Memory Hazards

The Michael-Scott queue is the canonical lock-free MPMC queue. Structure: singly-linked list with sentinel dummy node; atomic<Node*> head and tail. Enqueue: 1) alloc new node; 2) CAS tail->next (null→new, release); 3) CAS tail forward (best-effort; other threads help). Dequeue: 1) load h=head, next=h->next; 2) if next==null: empty; 3) read value from next; 4) CAS head (h→next, release); 5) delete old sentinel. Cooperative: if tail lags (tail->next != null), advance tail before own operation. ABA problem: ptr=A freed, reallocated at same addr=A; CAS(A→B) succeeds on recycled A. Fix: tagged pointer (ptr + version counter, 128-bit CAS) or hazard pointers (C++26) or epoch-based reclamation. Lock-free ≠ wait-free: a thread can spin forever under high contention. In production: use tbb::concurrent_queue, folly::MPMCQueue, or Boost.Lockfree.

🔑 Key line

Michael-Scott lock-free queue: sentinel dummy node; atomic<Node*> head/tail; enqueue = CAS tail->next (null→new); dequeue = CAS head (sentinel→next); ABA problem: tagged pointer or hazard pointers; use tbb/folly in production.

The code

// Michael-Scott lock-free queue — MPMC, wait-free enqueue attempt, ABA hazard
template <typename T>
class LockFreeQueue {
    struct Node {
        T val;
        atomic<Node*> next{nullptr};
    };
    atomic<Node*> head, tail;

public:
    LockFreeQueue() {
        head = tail = new Node{};
    } // sentinel (dummy)

    void enqueue(T val) {
        auto* n = new Node{val};
        Node *t, *next;
        while (true) {
            t = tail.load(acquire);
            next = t->next.load(acquire);
            if (t != tail.load(acquire))
                continue; // snapshot stale
            if (next == nullptr) {
                // tail->next is null: link new node
                if (t->next.compare_exchange_weak(next, n, release, relaxed)) {
                    tail.compare_exchange_strong(t, n, release, relaxed);
                    return;
                }
            } else {
                // tail is lagging — help advance it
                tail.compare_exchange_strong(t, next, release, relaxed);
            }
        }
    }

    optional<T> dequeue() {
        Node *h, *t, *next;
        while (true) {
            h = head.load(acquire);
            t = tail.load(acquire);
            next = h->next.load(acquire);
            if (h != head.load(acquire))
                continue;
            if (next == nullptr)
                return nullopt; // empty
            if (h == t) {
                tail.compare_exchange_strong(t, next, release);
                continue;
            }
            T val = next->val;
            // try to advance head
            if (head.compare_exchange_weak(h, next, release, relaxed)) {
                delete h; // reclaim old dummy  ← HAZARD: ABA, use-after-free risk
                return val;
            }
        }
    }
};

What this lesson walks through

01Lock-free queue overview — sentinel + atomic head/tail
02Enqueue — CAS loop to link new node at tail
03Enqueue — CAS succeeds, tail advanced
04Dequeue — CAS to advance head past sentinel
05ABA problem — the lock-free memory hazard
06Full implementation and when to use lock-free queues

The Michael-Scott queue is the classic lock-free MPMC queue. It uses a singly-linked list with a sentinel (dummy) node. head points to the sentinel; the next node after the sentinel is the oldest element. tail points to the last node. Both head and tail are atomic<Node*>. Enqueue links a new node at tail; dequeue advances head past the sentinel.

See it animated — step by step, at your own pace

Unlock the full interactive walkthrough of Concurrency: Lock-Free Queue — Michael-Scott CAS Loop, ABA, Memory Hazards and 100+ animated C++ interview lessons.

Start free →Already a member? Log in →