Implement Lock-Free Queue (Michael-Scott Queue)

Michael-Scott Lock-Free Queue

The Michael-Scott queue provides FIFO ordering with separate atomic head and tail. Producers CAS the tail forward; consumers CAS the head. It powers many message-passing runtimes where mutex latency spikes under load.

Enqueue and Dequeue Sketch

Allocate a dummy node. Enqueue links new node at tail with CAS retry. Dequeue advances head when the next pointer is non-null.

cCopy
Loading…

• Tail lagging head is normal; help advance tail in enqueue path
• Freeing nodes requires epoch or hazard pointers
• SPSC specialization is simpler and faster (see next tasks)
• Measure against pthread_mutex + std::deque under many producers

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will implement the Michael-Scott lock-free queue in C11 atomics. This exercise requires enqueue/dequeue from multiple threads without losing elements.