Lock-free queue

A mutex-protected queue is the natural starting point for producer-consumer communication between threads. Under light load it works fine, but under high contention the lock becomes a bottleneck: a thread preempted while holding it stalls every other producer and consumer until it is scheduled again. A lock-free queue avoids the mutex entirely by using compare-and-swap to coordinate. No thread ever holds an exclusive lock, so the worst case is a CAS retry rather than a sleep.

The standard multi-producer multi-consumer lock-free queue is the Michael-Scott queue (1996). It uses two atomic pointers — head and tail — plus a dummy node that simplifies empty-queue handling. head always points to the dummy; the real first element is head->next. tail points to the last node or lags one step behind when two threads enqueue simultaneously.

struct node {
    void                   *data;
    _Atomic(struct node *)  next;
};
 
struct queue {
    _Atomic(struct node *)  head;
    _Atomic(struct node *)  tail;
};
 
void queue_init(struct queue *q) {
    struct node *dummy = calloc(1, sizeof *dummy);
    atomic_store(&q->head, dummy);
    atomic_store(&q->tail, dummy);
}

To enqueue, a thread appends a new node by CASing the tail node's next pointer from NULL to the new node, then swings tail forward. If tail->next is already non-NULL, another thread has appended a node but not yet updated tail; the current thread advances tail on its behalf before retrying. This cooperative helping ensures tail never falls more than one step behind.

void enqueue(struct queue *q, void *data) {
    struct node *node = malloc(sizeof *node);
    node->data = data;
    atomic_store(&node->next, NULL);
 
    for (;;) {
        struct node *tail = atomic_load(&q->tail);
        struct node *next = atomic_load(&tail->next);
        if (next == NULL) {
            if (atomic_compare_exchange_weak(&tail->next, &next, node)) {
                atomic_compare_exchange_weak(&q->tail, &tail, node);
                return;
            }
        } else {
            atomic_compare_exchange_weak(&q->tail, &tail, next);  // help stalled enqueuer
        }
    }
}

atomic_compare_exchange_weak is used inside the retry loop because on LL/SC architectures (ARM, RISC-V) it avoids an extra round-trip that the _strong variant pays to guarantee no spurious failure. The loop handles spurious failures transparently.

To dequeue, a thread reads head->next (the real first element), CASes head forward to that node, and returns the data. The old head node becomes the new dummy and is freed. If head and tail point to the same node and head->next is NULL, the queue is empty. If head->next is non-NULL while head == tail, tail is lagging and is advanced before retrying.

void *dequeue(struct queue *q) {
    for (;;) {
        struct node *head = atomic_load(&q->head);
        struct node *tail = atomic_load(&q->tail);
        struct node *next = atomic_load(&head->next);
 
        if (head == tail) {
            if (next == NULL) return NULL;                          // empty
            atomic_compare_exchange_weak(&q->tail, &tail, next);   // help stalled enqueuer
        } else {
            void *data = next->data;
            if (atomic_compare_exchange_weak(&q->head, &head, next)) {
                free(head);   // reclaim old dummy — see ABA note below
                return data;
            }
        }
    }
}

The free(head) in dequeue is unsafe in the general case. If the freed node is immediately reallocated and enqueued by another thread, it can appear at the same address it held before. A concurrent dequeuer whose CAS on head compares against the old address will then succeed incorrectly — this is the ABA problem. The same issue applies to tail->next in enqueue.

The standard fixes are hazard pointers (publish the pointer you are about to CAS before reading it; reclamation checks all published pointers before freeing) or epoch-based reclamation (defer all frees until every thread has passed a quiescent point). The choice trades implementation complexity against reclamation latency. Most production lock-free queue libraries (Intel TBB's concurrent_queue, folly::MPMCQueue) use one of these schemes rather than immediate free.