|
|
|
@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}
}
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:
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.
