Michael-Scott queue is the standard lock-free MPMC queue (1996), using separate head and tail pointers with a dummy node and a “helping” mechanism where threads help other threads complete stalled tail updates. It provides full multi-producer/multi-consumer safety using only compare-and-swap.

The helping pattern guarantees lock-free progress by forwarding stalled operations when another thread encounters them, rather than waiting.

#include <stdio.h>
#include <stdlib.h>
#include <stdatomic.h>
 
struct node { int val; atomic_intptr_t next; };
struct queue { atomic_intptr_t head, tail; };
 
void enqueue(struct queue* q, int val) {
    struct node* n = malloc(sizeof(*n));
    n->val = val;
    atomic_store(&n->next, 0);
 
    struct node* t;
    do {
        t = (struct node*)atomic_load(&q->tail);
        struct node* next = (struct node*)atomic_load(&t->next);
        if (next) 
            atomic_compare_exchange_weak(&q->tail, &t, next);
        else
            atomic_compare_exchange_weak(&t->next, (void*)&next, n);
    } while (1);
}