Concurrent operations on priority queues

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.

REFERENCES

• 1: Bayer, R. and Schkolnick, M. Concurrency of operations on B-trees. Acta Informatica 9, I (1977), 1-21.
• 2: Ben Ari , M. Ben-Ari, Principles of Concurrent Programming, Prentice Hall Professional Technical Reference, 1982
• 3: Biswas, J. and Browne, J.C. Simultaneous update of priority structures. In Proceedings of the 1987 International Conference on Parallel Processing. S.K. Sahni, Ed. (University Park, Pa., Aug. 17-21, 1987), pp. 124-131.
• 4: Brown, M.R. The Analysis of a Practical and Nearly Optimal Priority Queue. Tech. Rep. STAN-CS-77-600, Computer Science Dept., Stanford Univ., 1977. (An abridged version appears as Implementation and analysis of bionomial queue algorithms. SIAM J. Computing 7, 3 (Aug. 1978) 298-319.)
• 5: Ray Ford , Jim Calhoun, Concurrency control mechanisms and the serializability of concurrent tree algorithms, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588020]
• 6: Douglas W. Jones, An empirical comparison of priority-queue and event-set implementations, Communications of the ACM, v.29 n.4, p.300-311, April 1986 [doi>10.1145/5684.5686]
• 7: Douglas W. Jones, Concurrent simulation: an alternative to distributed simulation, Proceedings of the 18th conference on Winter simulation, p.417-423, December 08-10, 1986, Washington, D.C., United States [doi>10.1145/318242.318468]
• 8: Jeffrey H. Kingston, Analysis of tree algorithms for the simulation event list, Acta Informatica, v.22 n.1, p.15-33, April 1985 [doi>10.1007/BF00290143]
• 9: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 10: Philip L. Lehman , s. Bing Yao, Efficient locking for concurrent operations on B-trees, ACM Transactions on Database Systems (TODS), v.6 n.4, p.650-670, Dec. 1981 [doi>10.1145/319628.319663]
• 11: Nix, R. An Evaluation of Pagodas. Tech. Rep. 164, Computer Science Dept., Yale Univ., Conn. (no date).
• 12: Michael J. Quinn , Narsingh Deo, Parallel graph algorithms, ACM Computing Surveys (CSUR), v.16 n.3, p.319-348, Sept. 1984 [doi>10.1145/2514.2515]
• 13: Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.235-245, December 1983 [doi>10.1145/800061.808752]
• 14: Daniel Dominic Sleator , Robert Endre Tarjan, Self adjusting heaps, SIAM Journal on Computing, v.15 n.1, p.52-69, Feb. 1986 [doi>10.1137/0215004]
• 15: Jean Vuillemin, A data structure for manipulating priority queues, Communications of the ACM, v.21 n.4, p.309-315, April 1978 [doi>10.1145/359460.359478]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Queueing theory

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Design, Measurement, Performance