Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms
📜 Abstract
Drawing ideas from previous authors, we present a new non-blocking concurrent queue algorithm and a new two-lock queue algorithm in which one enqueue and one dequeue can proceed concurrently. Both algorithms are simple, fast, and practical; we were surprised not to find them in the literature. Experiments on a 12-node SGI Challenge multiprocessor indicate that the new non-blocking queue consistently outperforms the best known alternatives; it is the clear algorithm of choice for machines that provide a universal atomic primitive (e.g. compare and swap or load linked/store conditional). The two-lock concurrent queue outperforms a single lock when several processes are competing simultaneously for access; it appears to be the algorithm of choice for busy queues on machines with non-universal atomic primitives (e.g. test and set). Since much of the motivation for non-blocking algorithms is rooted in their immunity to large, unpredictable delays in process execution, we report experimental results both for systems with dedicated processors and for systems with several processes multiprogrammed on each processor.
✨ Summary
Summary
The paper introduces two concurrent FIFO queue algorithms. The primary contribution is a linked-list, lock-free queue using compare-and-swap or load-linked/store-conditional primitives, dummy nodes, modification counters, and helping-style advancement of the tail pointer. The algorithm is linearizable and non-blocking: repeated interference causes another enqueue or dequeue to complete rather than allowing a delayed process to block system-wide progress. The paper also presents a simpler two-lock queue in which separate head and tail locks permit an enqueue and a dequeue to proceed concurrently.
The experiments on a 12-processor SGI Challenge found that the new non-blocking algorithm generally outperformed the alternatives tested, including under multiprogrammed workloads. The two-lock algorithm improved on a single-lock queue under high contention on dedicated processors, but was less suitable when processes could be unpredictably preempted.
Influence
The non-blocking algorithm became widely known as the Michael–Scott queue and has served as a foundational design for subsequent lock-free queue research. The authors’ research group later published corrected and optimized versions, including adaptations using modern memory-reclamation techniques such as hazard pointers, epoch-based reclamation, and interval-based reclamation. (cs.rochester.edu)
The design also influenced production libraries. Java’s ConcurrentLinkedQueue documentation states that its implementation uses an efficient non-blocking algorithm based on the algorithm described in this paper. (docs.oracle.com)
Subsequent research addressed the correctness and verification of the algorithm. Doherty, Groves, Luchangco, and Moir formally verified a slightly optimized version using simulation proofs and the PVS theorem prover, establishing its linearizability. (researchgate.net) More recent work has continued to model-check both the algorithm and the OpenJDK queue implementation based on it. (doi.org)