Ivan's wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
# 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.

```c
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);
}
```

## Enqueue

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.

```c
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.

## Dequeue

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.

```c
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;
            }
        }
    }
}
```

## ABA and memory reclamation

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|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`.