M. Herlihy
Abstract
A concurrent object is a data structure shared by concurrent processes. Conventional techniques for implementing concurrent objects typically rely on critical sections: ensuring that only one process at a time can operate on the object. Nevertheless, critical sections are poorly suited for asynchronous systems: if one process is halted or delayed in a critical section, other, non-faulty processes will be unable to progress. By contrast, a concurrent object implementation is non-blocking if it always guarantees that some process will complete an operation in a finite number of steps, and it is wait-free if it guarantees that each process will complete an operation in a finite number of steps. This paper proposes a new methodology for constructing non-blocking and wait-free implementations of concurrent objects. The object's representation and operations are written as stylized sequential programs, with no explicit synchronization. Each sequential operation is automatically transformed into a non-blocking or wait-free operation using novel synchronization and memory management algorithms. These algorithms are presented for a multiple instruction/multiple data (MIMD) architecture in which n processes communicate by applying read, write, and compare&swap operations to a shared memory.
- 1 G.R. Andrews and F.B. Schneider. Concepts and notations for concurrent programming. A CM Computing Surveys, 15(I):3-43, 1983. Google Scholar
Digital Library
- 2 R. Bayer and M. Schkolnick. Concurrency of operations on b-trees. Acta Informa#ica, 1(I):1-21, 1977.Google Scholar
- 3 J. Biswas and J.C. Browne. Simultaneous update of priority structures. In Proceedings of the 1087 International Conference on Parallel Processing, pages t24-131, 1987.Google Scholar
- 4 B. Bloom. Constructing two-writer atomic registers. In Proceedings of the Sizth A CM Symposium on Principles of Distributed Computing, pages 249-259, 1987. Google ScholarDigital Library
- 5 :I.E. Burns and G.L. Peterson. Constructing multireader atomic values from non-atomic values. In Proceedings of the Sizgh A CM Symposium ou Principles of Disgribu#ed Computing, pages 222-231, 1987. Google ScholarDigital Library
- 6 B. Chor, A. Israeli, and M. Li. On processor coordination using asynchronous hardware. In Proceedings of the Sizth A CM Symposium on Principles of Distributed Computing, pages 86-97, 1987. Google ScholarDigital Library
- 7 D. Dolev, C. Dwork, and L Stockmeyer. On the minimal synchronism needed for distributed consensus. Journal of the A C1#I, 34(1):77-97, January 1987. Google ScholarDigital Library
- 8 C. Dwork, N. Lynch, and L Stoekmeyer. Consensus in the presence of partial synchrony. Journal of the ACM, 35(2):228-323, April 1988. Google ScholarDigital Library
- 9 C. Dwork, D. Shmoys, and L. Stockmeyer. Flipping persuasively in constant expected time. In Twengy-Seventh Annual Symposium on Foundations of Computer Science, pages 222-232, October 1986.Google ScholarDigital Library
- 10 C.S. Ellis. Concurrent search and insertion in 2-3 trees. Acga Informatica, 14:63-86, 1980.Google ScholarDigital Library
- 11 M. Fischer, N.A. Lynch, and M.S. Paterson. Impossibility of distributed commit with one faulty process. Journal of the A CM, 32(2), April 1985. Google ScholarDigital Library
- 12 R. Ford and J. Calhoun. Cnncurrency control mechanisms and the serializability of concurrent tree algorithms. In 3rd A CM Symposium on PTiucples of Database Systems, pages 51-60, 1984. Google ScholarDigital Library
- 13 A. Gottlieb, R. Grishman, C.P. Kruskal, K.P. McAuliffe, L. Rudolph, and M. Suit. The nyu ultracomputer -designing an mimd parallel computer. IEEE Transactions on Computers, C- 32(2):175-189, February 1984.Google ScholarDigital Library
- 14 A. Gottlieb, B.D. Lubachevsky, and L. Rudolph. Basic techniques for the efficient coordination of very large numbers of cooperating sequential processors. A CM Transactions on Programming Languages and Systems, 5(2):164-189, April 1983. Google ScholarDigital Library
- 15 L. Guibas and R. Sedgewick. A dichromatic framework for balanced trees. In 19th A CM Symposium on Foundations of Computer Science, pages 8-21, 1978.Google ScholarDigital Library
- 16 R. Halstead. Multilisp: A language for concurrent symbolic computation. A CM Trans. on Prog. Languages and Systems, 7(4):501-538, 1985. Google ScholarDigital Library
- 17 M. Herlihy and 3. Wing. Axioms for concurrent objects. In 14th A CM Symposium on Principles of Programming Languages, pages 13-26, January 1987. Google ScholarDigital Library
- 18 M.P. Herlihy. Impossibility and universality resuits for wait-free synchronization. In Seventh A CM SIGA CT-SIGOPS Symposium on Principles of Distributed Computing, August 1988. Google ScholarDigital Library
- 19 M.P. Herlihy. Wait-free synchronization. Submitted for publication., July 1989.Google Scholar
- 20 IBM. System/370 principles of operation. Order Number GA22-7000.Google Scholar
- 21 D.W. Jones. Concurrent operations on priority queues. Communications of the A CM, 32(1):132- 137, January 1989. Google ScholarDigital Library
- 22 L. Lamport. Concurrent reading and writing. Communications of the ACM, 20(11):806-811, November 1977. Google ScholarDigital Library
- 23 L. Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computers, C- 28(9):690, September 1979.Google ScholarDigital Library
- 24 L. Lamport. Specifying concurrent program modules. A CM Transactions on Programming Languages and Systems, 5(2)'190-222, April 1983. Google ScholarDigital Library
- 25 L. I,amport. On interprocess communication, parts i and it. Distributed Computing, 1"77-101, 1986.Google Scholar
- 26 V. Lanin and D. Shasha. Concurrent set manipulation without locking. In Proceedings of the Seventh A CM Symposium on Principles of Database Systems, pages 211-220, March 1988. Google ScholarDigital Library
- 27 P.L. Lehman and S.B. Yao. Efficient locking for concurrent operations on b-trees. ACM Transactions on Database Systems, 6(4):650-670, December 1981. Google ScholarDigital Library
- 28 R. Newman-Wolfe. A protocol for wait-free, atomic, multi-reader shared variables, in Proceedings of the Sizth A CM Symposium on Principles of Distributed Computing, pages 232-249, 1987. Google ScholarDigital Library
- 29 C.H. Papadimitriou. The setializability of concurrent database updates. Journal of the A CM, 26(4):631-653, October 1979. Google ScholarDigital Library
- 30 G.L. Peterson. Concurrent reading while writing. A CM Transactions orr Programming Lartguages and Systems, 5(1):46-55, January 1983. Google ScholarDigital Library
- 31 G.L. Peterson and J.E. Burns. Concurrent reading while writing ii" the multi-writer case. Technical Report GIT-ICS-86/26, Georgia Institute of Technology, December 1986.Google Scholar
- 32 S.A. Plotkin. Sticky bits and universality of consensus. In Proceedings of the Eighth A CM Symposium on Principles of Distribuled Computing, pages 159-176, 1989. Google ScholarDigital Library
- 33 Y. Sagiv. Concurrent operations on b-trees with overtaking. In A CM Prir#cples of Database Systems, pages 28-37, January 1985. Google Scholar
- 34 A.K. Singh, J.H. Anderson, and M.G. Gouda. The elusive atomic register revisited. In Proceedings of the Sizth A CM Symposium on Principles of Distributed Computing, pages 206-221, 1987. Google ScholarDigital Library
- 35 D.D. Sleator and R.E. Tarjan. Self adjusting binary trees. In Proceedings of the 15th A CM Symposium ou Theory of Computing, pages 52-59, 1983. Google ScholarDigital Library
Index Terms
- A methodology for implementing highly concurrent data structures
Recommendations
A methodology for implementing highly concurrent data objects
A concurrent object is a data structure shared by concurrent processes. Conventional techniques for implementing concurrent objects typically rely on critical sections; ensuring that only one process at a time can operate on the object. Nevertheless, ...
A methodology for implementing highly concurrent data structures
PPOPP '90: Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programmingA concurrent object is a data structure shared by concurrent processes. Conventional techniques for implementing concurrent objects typically rely on critical sections: ensuring that only one process at a time can operate on the object. Nevertheless, ...
Transactional Acceleration of Concurrent Data Structures
SPAA '15: Proceedings of the 27th ACM symposium on Parallelism in Algorithms and ArchitecturesConcurrent data structures are a fundamental building block for scalable multi-threaded programs. While Transactional Memory (TM) was originally conceived as a mechanism for simplifying the creation of concurrent data structures, modern hardware TM ...
Comments