Simple, Fast, and Practical Non-Blocking and
Blocking Concurrent Queue Algorithms
by Maged
M. Michael and Michael L. Scott
This paper appeared in the proceedings of PODC '96.
PDF
file (180KB).
Pseudocode.
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.