Implement Lock-Free Queue (Michael-Scott Queue)

Topic Overview

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.

Your Task

The Michael. Scott queue is the standard lock-free FIFO. It is a linked list with a dummy node, a Head and a Tail. An enqueue links the new node after the last one with a CAS and then swings Tail with a second CAS. Between those two CASes, Tail lags one node behind, so every other thread that notices the lag helps by advancing Tail itself. Simulate the algorithm step by step under explicit interleavings.

Input

cCopy
Loading…

Node #1 is the initial dummy (Head = Tail = #1). New nodes are #2, #3, … and are allocated on an enqueue's first attempt.

Steps

enq V:

• 0: t = Tail.
• 1: next = t.next.
• 2: If t != Tail, retry. Else if next != NULL, the tail is lagging: CAS(Tail, t, next) to help, then retry. Else CAS(t.next, NULL, node): on success go to step 3, otherwise retry.
• 3: CAS(Tail, t, node). If it fails, another thread already helped. Either way the enqueue is done.

deq:

• 0: h = Head, t = Tail.
• 1: next = h.next.
• 2: If h != Head, retry. If h == t: when next is NULL the queue is empty (done), otherwise help CAS(Tail, t, next) and retry. Else read next.value and CAS(Head, h, next): on success return the value (next becomes the new dummy), otherwise retry.

Every retry restarts at step 0 and counts as a retry. A help also counts as a help.

Output

cCopy
Loading…

(lagging) is printed when Tail is not the last node. Other messages follow the Treiber-stack tasks: NAME: finished, schedule: unknown thread NAME, thread NAME: bad operation: TEXT, and EMPTY for an empty dequeue.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Treat the lagging Tail as a normal state, and repair it through helping. Never wait for the enqueuer to finish.
2. Keep the dummy-node discipline: the value is read from Head.next, and that node becomes the new dummy.

Hidden tests cover three enqueuers racing for the same next field, a lagging tail seen by state, a dequeuer that loses the race to another dequeuer, dequeuing until the queue is empty, and schedules that name finished or unknown threads.