A simple and correct shared-queue algorithm using compare-and-swap
Janice M. Stone · Conference on High Performance Computing (Supercomputing) · 1990
The shared queue is a paradigm of concurrent processes. Because shared queues are central to many multiprocessor systems, their implementations require correctness and efficiency. We present a Compare-and-Swap shared-queue algorithm that permits concurrent access and is nondelaying, in that no processor need wait for an action by another processor. We present a verification method that analyzes the states of the shared data-structure. By drawing a graph that incorporates in a simple way the effects of multi-processor interleaving, one can quickly find errors in an algorithm or produce a proof of correctness. Since enqueue and dequeue operations may begin at any time, concurrent queue operations are represented by providing, in each state of the shared data-structure, one transition that initiates an enqueue operation and another transition for a dequeue operation. The method is a practical one that is applicable to a variety of algorithms that use shared data-structures.