Locking without blocking: Making lock based concurrent data structure algorithms nonblocking

John Turek, Dennis Shasha, Sundeep Prakash

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 possibility of deadlock (e.g. because of a well-ordering among the lock requests). In contrast to 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.

Original languageEnglish (US)
Title of host publicationProceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
Editors Anon
PublisherPubl by ACM
Pages212-222
Number of pages11
ISBN (Print)0897915194
StatePublished - 1992
EventProceedings of the 11th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems - San Diego, CA, USA
Duration: Jun 2 1992Jun 4 1992

Publication series

NameProceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

Other

OtherProceedings of the 11th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
CitySan Diego, CA, USA
Period6/2/926/4/92

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Locking without blocking: Making lock based concurrent data structure algorithms nonblocking'. Together they form a unique fingerprint.

Cite this