Locking without Blocking: Making Lock Based Concurrent Data Structure Algorithms Nonblocking.

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

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.

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

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]

...