Locking without Blocking: Making Lock Based Concurrent Data Structure Algorithms Nonblocking.
John Turek, Dennis Shasha, Sundeep Prakash:
Locking without Blocking: Making Lock Based Concurrent Data Structure Algorithms Nonblocking.
PODS 1992: 212-222@inproceedings{DBLP:conf/pods/TurekSP92,
author = {John Turek and
Dennis Shasha and
Sundeep Prakash},
title = {Locking without Blocking: Making Lock Based Concurrent Data Structure
Algorithms Nonblocking},
booktitle = {Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems, June 2-4, 1992, San Diego,
California},
publisher = {ACM Press},
year = {1992},
isbn = {0-89791-519-4},
pages = {212-222},
ee = {http://doi.acm.org/10.1145/137097.137873, db/conf/pods/TurekSP92.html},
crossref = {DBLP:conf/pods/92},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
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
mount 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.
Copyright © 1992 by the ACM,
Inc., used by permission. Permission to make
digital or hard copies is granted provided that
copies are not made or distributed for profit or
direct commercial advantage, and that copies show
this notice on the first page or initial screen of
a display along with the full citation.
Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98.
and ...
Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings.
and ...
BibTeX
Printed Edition
Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 2-4, 1992, San Diego, California.
ACM Press 1992, ISBN 0-89791-519-4
Contents BibTeX
[Abstract and Index Terms]
[Full Text in PDF Format, 1038 KB]
References
- [BS77]
- Rudolf Bayer, Mario Schkolnick:
Concurrency of Operations on B-Trees.
Acta Inf. 9: 1-21(1977) BibTeX
- [CBDW91]
- ...
- [Her88]
- Maurice Herlihy:
Impossibility and Universality Results for Wait-Free Synchronization.
PODC 1988: 276-290 BibTeX
- [IBM83]
- ...
- [JS90]
- Theodore Johnson, Dennis Shasha:
A Framework for the Performance Analysis of Concurrent B-tree Algorithms.
PODS 1990: 273-287 BibTeX
- [KL80]
- H. T. Kung, Philip L. Lehman:
Concurrent Manipulation of Binary Search Trees.
ACM Trans. Database Syst. 5(3): 354-382(1980) BibTeX
- [LS81]
- Philip L. Lehman, S. Bing Yao:
Efficient Locking for Concurrent Operations on B-Trees.
ACM Trans. Database Syst. 6(4): 650-670(1981) BibTeX
- [PLJ91]
- ...
- [Plo89]
- Serge A. Plotkin:
Sticky Bits and Universality of Consensus.
PODC 1989: 159-175 BibTeX
- [SC91]
- V. Srinivasan, Michael J. Carey:
Performance of B-Tree Concurrency Algorithms.
SIGMOD Conference 1991: 416-425 BibTeX
- [SG88]
- Dennis Shasha, Nathan Goodman:
Concurrent Search Structure Algorithms.
ACM Trans. Database Syst. 13(1): 53-90(1988) BibTeX
- [Sto90]
- ...
- [Ten81]
- ...
- [WW90]
- ...
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:06 2009