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
Contributions
The paper presents two FIFO concurrent-queue algorithms. The first is a non-blocking, lock-free linked-list queue using a dummy head node, compare-and-swap operations, modification counters to mitigate the ABA problem, and a non-blocking free list. Its enqueue and dequeue operations are linearizable, and the paper argues that repeated retries imply progress by another concurrent operation. The second algorithm uses separate head and tail locks, allowing an enqueue and a dequeue to proceed concurrently while remaining compatible with simpler atomic primitives such as test-and-set.
Evaluation
Experiments on a 12-processor SGI Challenge compared the algorithms with single-lock, blocking, and earlier non-blocking queues under dedicated and multiprogrammed workloads. The proposed non-blocking queue consistently performed best when at least three processors were active and remained competitive with fewer processors. The two-lock queue improved on a single lock under high contention on dedicated systems, but was less effective than non-blocking alternatives under multiprogramming.
Influence
The algorithm became a foundational design for practical lock-free queues. Oracle’s documentation states that Java’s ConcurrentLinkedQueue uses an efficient non-blocking algorithm based on the paper, while the OpenJDK implementation describes itself as a modification of the Michael–Scott algorithm adapted for garbage-collected memory and interior-node deletion. (docs.oracle.com) Later concurrent-queue research continued to use it as a baseline: a University of Rochester paper describes LCRQ as a major enhancement of the Michael–Scott linked-list queue, replacing individual list elements with fixed-size concurrent ring queues. (cs.rochester.edu) The authors’ research group also maintains corrected pseudocode and notes adaptations using hazard pointers, epoch-based reclamation, and interval-based reclamation for environments where the original memory-management assumptions are unsuitable. (cs.rochester.edu)