Concurrent operations on priority queues
- 1 January 1989
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 32 (1) , 132-137
- https://doi.org/10.1145/63238.63249
Abstract
Among the fastest priority queue implementations, skew heaps have properties that make them particularly suited to concurrent manipulation of shared queues. A concurrent version of the top down implementation of skew heaps can be produced from previously published sequential versions using almost mechanical transformations. This implementation requires O (log n) time to enqueue or dequeue an item, but it allows new operations to begin after only O(1) time on a MIMD machine. Thus, there is potential for significant concurrency when multiple processes share a queue. Applications to problems in graph theory and simulation are discussed in this article.Keywords
This publication has 9 references indexed in Scilit:
- An empirical comparison of priority-queue and event-set implementationsCommunications of the ACM, 1986
- Self-Adjusting HeapsSIAM Journal on Computing, 1986
- Concurrent simulationPublished by Association for Computing Machinery (ACM) ,1986
- Analysis of tree algorithms for the simulation event listActa Informatica, 1985
- Parallel graph algorithmsACM Computing Surveys, 1984
- Concurrency control mechanisms and the serializability of concurrent tree algorithmsPublished by Association for Computing Machinery (ACM) ,1984
- Self-adjusting binary treesPublished by Association for Computing Machinery (ACM) ,1983
- Efficient locking for concurrent operations on B-treesACM Transactions on Database Systems, 1981
- A data structure for manipulating priority queuesCommunications of the ACM, 1978