John Turek
Dennis Shasha
ABSTRACT
Nonblocking algorithms for concurrent data structures guarantee that a data structure is always accessible. This is in contrast to blocking algorithms in which a slow or halted process can render part or all of the data structure inaccessible to other processes.
This paper proposes a technique that can convert most existing lock-based blocking data structure algorithms into nonblocking algorithms with the same functionality. Our instruction-by-instruction transformation can be applied to any algorithm having the following properties:
•Interprocess synchronization is established solely through the use of locks.
•There is no possiblity of deadlock (e.g. because of a well-ordering among the lock requests).
In contrast to a previous work, our transformation requires only a constant amount of overhead per operation and, in the absence of failures, it incurs no penalty in the amount of concurrency that was available in the original data structure.
The techniques in this paper may obviate the need for a wholesale reinvention of techniques for nonblocking concurrent data structure algorithms.
- BS77.Bayer, M. and Scholnick. Concurrency of Operations on B-Trees. Acta Informatica, 9:1-21, 1977.Google Scholar
Digital Library
- CBDW91.A. Colbrook, E.A. Brewer, C.N. Dellarocas, and W.E. Weihl. An algorithm for concurrent search trees.In Proceedzngs of the #Oth International Conference on Parallel Processing, pages III138-III141, 1991.Google Scholar
- Her88.Herlihy, Maurice. Impossibility and Universality Results for Wait-Free Synchronization. In Proceedsngs of the Seventh Annual A CM Symposzum on Prsnciples of Distrsbuted Computing, pages 276-290, Toronto, Ontario, Canada, August 1988. Google ScholarDigital Library
- IBM83.IBM. IBM 370 Pmnc#ples of Operation, May 1983. Publication GA22-7000.Google Scholar
- JS90.Johnson, T. and D. Shasha. A Framework for the Performance Analysis of Concurrent B-Tree Algorithms. In 9th A CM SIGA CT-SIGMOD Conference on Pmncspies of Database Systems, pages 273-287, April 1990. Google ScholarDigital Library
- KL80.Kung, H. and P. Lehman. Concurrent Manipulation of Binary Search Trees. A CM- TODS, 5(3):339-353, 1980. Google ScholarDigital Library
- LS81.Lehman, P. and Yao. S. Efficient Locking for Concurrent Operations on B-Trees. A CMTODS, 6(4):650-670, December 1981. Google ScholarDigital Library
- PLJ91.Prakash, S., Y. H. Lee, and T. Johnson. A Non-Blocking Algorithm for Shared Queues Using Compare-and-Swap. In Internatzonal Conference on Parallel Processing, 1991.Google Scholar
- Plo89.Plotkin, S. Sticky Bits and Universality of Consensus. In Proceedsngs of the E#ghth Annual A CM Sympossum on Prznczples of Dzs. tributed Computing, pages 159-t75, 1989. Google ScholarDigital Library
- SC91.V. Srinivasan and M. Carey Performance of B-tree concurrency control algorithms. In Proceedings of the 1991 A CM SIGMOD Int'l Conference on Management of Data, pages 461-425. ACM, 1991. Google ScholarDigital Library
- SG88.Shasha, D. and N. Goodman. Concurrent Search Structure Algorithms. ACM Transactions on Database Systems, 13(1):53-90, Marcia 1988. Google ScholarDigital Library
- Sto90.Stone, J.M. A Simple and Correct Shared-Queue Algorithm Using Compareand-Swap. In Proceedings of the IEEE Computer Soczety and A CM S#gArch Supercomputzug '90 Conference, November 1990. Google ScholarDigital Library
- Ten81.Tennent, I:t Principles of Programming Languages. International Series in Computer Science. Prentice-Hall, 1981. Google ScholarDigital Library
- WW90.W.E. Weihl and P. Wang. Multi-version memory: Software cache management for concurrent B-trees. In Proceedsngs of the 2nd IEEE Sympossum on Parallel and Dsstmbuted Process,ng, pages 650-655, 1990.Google ScholarDigital Library
Recommendations
A method for implementing lock-free shared-data structures
SPAA '93: Proceedings of the fifth annual ACM symposium on Parallel Algorithms and ArchitecturesSimple, fast, and practical non-blocking and blocking concurrent queue algorithms
PODC '96: Proceedings of the fifteenth annual ACM symposium on Principles of distributed computingLock-free locks revisited
PPoPP '22: Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel ProgrammingThis paper presents a new and practical approach to lock-free locks based on helping, which allows the user to write code using fine-grained locks, but run it in a lock-free manner. Although lock-free locks have been suggested in the past, they are ...
Comments