DCAS-based concurrent deques
- 9 July 2000
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 35 (3), 349-386
- https://doi.org/10.1145/341800.341817
Abstract
The computer industry is currently examining the use of strong synchronization operations such as double compare-and-swap (DCAS) as a means of supporting non-blocking synchronization on tomorrow's multiprocessor machines. However, before such a strong primitive will be incorporated into hardware design, its utility needs to be proven by developing a body of effective non-blocking data structures using DCAS.As part of this effort, we present two new linearizable non-blocking implementations of concurrent deques using the DCAS operation. The first uses an array representation, and improves on former algorithms by allowing uninterrupted concurrent access to both ends of the deque while correctly handling the difficult boundary cases when the deque is empty or full. The second uses a linked-list representation, and is the first non-blocking unbounded-memory deque implementation. It too allows uninterrupted concurrent access to both ends of the deque.Keywords
This publication has 12 references indexed in Scilit:
- Effective fine-grain synchronization for automatically parallelized programs using optimistic synchronization primitivesACM Transactions on Computer Systems, 1999
- Atomic Snapshots in O (n log n) OperationsSIAM Journal on Computing, 1998
- Thread scheduling for multiprogrammed multiprocessorsPublished by Association for Computing Machinery (ACM) ,1998
- Software transactional memoryDistributed Computing, 1997
- The synergy between non-blocking synchronization and operating system structurePublished by Association for Computing Machinery (ACM) ,1996
- Universal operationsPublished by Association for Computing Machinery (ACM) ,1996
- Are wait-free algorithms fast?Journal of the ACM, 1994
- A methodology for implementing highly concurrent data objectsACM Transactions on Programming Languages and Systems, 1993
- Wait-free synchronizationACM Transactions on Programming Languages and Systems, 1991
- Linearizability: a correctness condition for concurrent objectsACM Transactions on Programming Languages and Systems, 1990