A methodology for implementing highly concurrent data objects
Maurice P. Herlihy · ACM Transactions on Programming Languages and Systems · 1993
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, nonfaulty processes will be unable to progress. By contrast, a concurrent object implementation is lock free 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 lock-free 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 atutomatically transformed into a lock-free 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 atomic read, write, load_linked, and store_conditional operations to a shared memory.
Cited by 469 works. doi:10.1145/161468.161469 Open-access PDF
Authors
References
- Introduction to Algorithms
- Ethernet
- Ethernet
- Impossibility of distributed consensus with one faulty process
- The C Programming Language
- The C programming language
- How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs
- The NYU Ultracomputer—Designing an MIMD Shared Memory Parallel Computer
- On optimistic methods for concurrency control
- Consensus in the presence of partial synchrony