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.
Cited by 24 works. doi:10.5555/110382.110466
Authors
References
- Proving the Correctness of Multiprocess Programs
- Solution of a problem in concurrent programming control
- A new solution of Dijkstra's concurrent programming problem
- Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors
- An exercise in proving parallel programs correct
- A methodology for implementing highly concurrent data structures
- A methodology for implementing highly concurrent data structures
- Debugging concurrent processes: a case study
- Operating system data structures for shared memory mimd machines with fetch-and-add