A nonblocking algorithm for shared queues using compare-and-swap
- 1 May 1994
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 43 (5), 548-559
- https://doi.org/10.1109/12.280802
Abstract
Nonblocking algorithms for concurrent objects guarantee that an object is always accessible, in contrast to blocking algorithms in which a slow or halted process can render part or all of the data structure inaccessible to other processes. A number of algorithms have been proposed for shared FIFO queues, but nonblocking implementations are few and either limit the concurrency or provide inefficient solutions. The authors present a simple and efficient nonblocking shared FIFO queue algorithm with O(n) system latency, no additional memory requirements, and enqueuing and dequeuing times independent of the size of the queue. They use the compare & swap operation as the basic synchronization primitive. They model their algorithm analytically and with a simulation, and compare its performance with that of a blocking FIFO queue. They find that the nonblocking queue has better performance if processors are occasionally slow, but worse performance if some processors are always slower than others.Keywords
This publication has 9 references indexed in Scilit:
- A simple and correct shared-queue algorithm using compare-and-swapPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Locking without blockingPublished by Association for Computing Machinery (ACM) ,1992
- Concurrent search structure algorithmsACM Transactions on Database Systems, 1988
- Impossibility and universality results for wait-free synchronizationPublished by Association for Computing Machinery (ACM) ,1988
- Performance analysis of centralized databases with optimistic concurrency controlPerformance Evaluation, 1987
- Axioms for concurrent objectsPublished by Association for Computing Machinery (ACM) ,1987
- Specifying Concurrent Program ModulesACM Transactions on Programming Languages and Systems, 1983
- Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential ProcessorsACM Transactions on Programming Languages and Systems, 1983
- On optimistic methods for concurrency controlACM Transactions on Database Systems, 1981