The Michael-Scott Lock-Free Queue

Why locks are not always the answer

The traditional way to make a data structure safe for concurrent use is to protect it with a mutex: a thread must acquire the lock before touching the queue and release it afterward. This is simple to reason about, but it has a serious weakness. If the thread currently holding the lock is paused, perhaps preempted by the operating system scheduler, swapped out to disk, or simply slow, every other thread that wants to use the queue must wait. In the worst case, one unlucky scheduling decision can stall an entire system, even though most threads are perfectly capable of running. This is called lock convoying, and it becomes especially painful in real-time systems, operating system kernels, and highly parallel server workloads where predictable throughput matters.A lock-free algorithm offers a different guarantee. It does not promise that any particular thread will finish quickly, but it does promise that the system as a whole always makes progress: at any point in time, at least one thread among those trying to operate on the structure will complete its operation in a finite number of steps. No thread can bring the entire structure to a halt just by being descheduled at an inconvenient moment. This is a weaker guarantee than wait-free, which promises every thread finishes in a bounded number of steps regardless of what others do, but it is dramatically stronger than what a lock provides, and it is far easier to achieve in practice.The Michael-Scott queue achieves this lock-free property by replacing the mutex with the compare-and-swap instruction, often abbreviated CAS, which most modern processors support directly in hardware. Compare-and-swap takes a memory location, an expected old value, and a desired new value. It atomically checks whether the memory location still holds the expected value, and if so, replaces it with the new value, reporting success. If the memory location has changed since the thread last read it, the operation fails and reports that failure, leaving the memory untouched. This single instruction becomes the building block for an entire queue implementation, because it lets a thread attempt an update and immediately know whether it succeeded or must try again.

The linked list skeleton with head and tail pointers

The Michael-Scott queue is built on a singly linked list of nodes, where each node holds a data value and a pointer to the next node. Two shared pointers frame the structure: head, which always refers to a sentinel or dummy node just before the first real element, and tail, which refers to the last node currently known to be in the list. The use of a permanent dummy node at the front is a deliberate design choice. It means the queue is never truly empty at the pointer level, which eliminates a whole class of special-case handling for the transition between zero and one elements, a transition that is notoriously easy to get wrong in concurrent code.Dequeue operations only ever touch the head end of the list. A thread wanting to remove an element reads the current head, looks at the node immediately after it, which holds the actual first item of logical queue, copies out its value, and then attempts to compare-and-swap the head pointer forward to that node. If the compare-and-swap succeeds, the old dummy node is retired, sometimes literally becoming garbage to be reclaimed later, and the node that used to hold the first item becomes the new dummy. If it fails, another thread has already dequeued, and the operation restarts by re-reading the current head.Enqueue operations work at the tail end, but here the design gets more subtle. A naive approach might try to compare-and-swap the tail pointer directly to a new node, but that would be wrong, because the new node also needs to be linked into the existing chain by updating the current last node's next pointer. Two separate pieces of shared state, the last node's next field and the tail pointer itself, need to be updated together, yet compare-and-swap can only touch one memory word at a time. This mismatch between what correctness requires, updating two locations, and what the hardware offers, atomically updating one location, is the central engineering challenge that the algorithm has to solve, and it is the subject of the next section.

The two-step tail-advancing dance

Here is the heart of the algorithm's cleverness. To enqueue a new node, a thread first reads the current tail pointer and looks at that node's next field. Under normal, uncontended conditions, that next field should be empty, meaning the tail pointer genuinely points at the last node in the chain. The thread then attempts a compare-and-swap on that next field, trying to set it from empty to point at the new node. If this succeeds, the new node is now officially part of the linked list, reachable by following next pointers from the head. But notice: the shared tail pointer itself has not been updated yet. It still points at the node that used to be last.The thread that just succeeded then attempts a second compare-and-swap, this time on the tail pointer itself, trying to advance it from the old last node to the newly inserted node. Crucially, the algorithm does not require this second step to succeed for the enqueue to be considered logically complete. As soon as the first compare-and-swap linked the new node into the chain, the enqueue has, in effect, already happened, because any thread traversing the list from the head will reach it. Advancing the tail pointer is bookkeeping that helps future enqueuers find the end of the list quickly, but it is not itself part of the linearization point of the operation.This separation is what makes the algorithm robust against a thread stalling between the two steps. Imagine a thread successfully links its node in but then gets suspended by the scheduler before it can swing the tail pointer forward. The tail pointer is now stale, one node behind reality. Any other thread that comes along to enqueue will detect this: it reads tail, looks at tail's next field, and discovers that field is not empty, meaning someone already inserted a node that tail has not caught up to yet. Rather than giving up, the helping thread performs a compare-and-swap to advance the tail pointer on behalf of the stalled thread, and only then retries its own insertion. This technique is called helping, and it is precisely what preserves the lock-free guarantee: no thread ever needs to wait for the stalled thread to wake up, because any other active thread can finish the stalled thread's cleanup work for it.

Why a single compare-and-swap cannot do it all

It is worth dwelling on why the two-step approach is necessary rather than just an inefficiency to be optimized away. Some processor architectures offer a double-word compare-and-swap, sometimes called compare-and-swap-two, which can atomically update two adjacent memory words at once. In principle, a queue could use this to update the last node's next pointer and the tail pointer simultaneously. But the Michael-Scott algorithm was designed to work with the single-word compare-and-swap available on essentially all mainstream hardware, which makes it far more portable, and the two-step approach with helping turns out to generalize better to other lock-free structures as well, so it remains the canonical teaching example even where wider atomics exist.The correctness argument rests on identifying the exact moment, called the linearization point, at which an operation appears to take effect instantaneously from the perspective of all other threads. For enqueue, that moment is the successful compare-and-swap that links the new node into the chain by updating the previous last node's next field, not the later compare-and-swap that moves the tail pointer. Because the tail pointer is allowed to lag behind the true end of the list by at most one node, every operation checks for this condition and repairs it opportunistically before proceeding. This is a recurring pattern in lock-free design: rather than forbidding a structure from ever being in an intermediate, slightly inconsistent state, the algorithm defines exactly what those intermediate states can look like and gives every participant the responsibility of noticing and fixing them.This pattern also explains why lock-free algorithms are notoriously hard to invent and even harder to verify by hand. A change that looks like a harmless simplification, such as skipping the check on tail's next field before attempting to insert, can silently break the invariant that the tail pointer never falls more than one node behind, corrupting the queue under just the right interleaving of threads. Formal verification tools and model checkers are frequently used in practice to confirm that queues like this one are correct under every possible thread interleaving, because human intuition about concurrent execution is unreliable at this level of detail.

The ABA problem and memory reclamation

Compare-and-swap has a subtle blind spot known as the ABA problem. Compare-and-swap only checks whether a memory location currently holds the expected value, it has no way of knowing whether that value changed and then changed back in the meantime. Suppose a thread reads a pointer expecting it to still refer to node A, gets paused, and while paused, other threads dequeue node A, free its memory, allocate a brand new node that happens to be placed at the exact same memory address, and link it in. When the original thread wakes up and performs its compare-and-swap, the memory location still equals the address it remembers, so the swap succeeds, even though the actual node identity has completely changed underneath it. This can corrupt the queue's structure in ways that are extremely difficult to reproduce and debug.The original Michael-Scott paper addresses this with a technique involving version tags or counters bundled alongside each pointer, so that even if an address is reused, the paired counter has advanced and the compare-and-swap will correctly fail. Modern implementations often use different strategies for the closely related problem of memory reclamation, deciding when it is safe to actually free a dequeued node's memory, given that another thread might still be in the middle of reading it. Techniques such as hazard pointers, where each thread publishes which nodes it is currently accessing so other threads know not to free them, and epoch-based reclamation, where memory is freed only after every thread has passed a synchronization checkpoint, are common solutions in production-grade lock-free libraries.Java's ConcurrentLinkedQueue sidesteps much of this danger because the Java Virtual Machine provides automatic garbage collection: a node can never be freed and its address reused while any thread still holds a reference to it, which eliminates the ABA problem's most dangerous manifestation for free. This is one reason the Michael-Scott algorithm found such a comfortable home in managed-memory languages, even though the original paper was written with manual memory management in unmanaged languages like C in mind, where the ABA problem and reclamation safety demand much more careful engineering.

Frequently asked questions

Try it live

Everything above runs in your browser — open The Michael-Scott Lock-Free Queue and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.