MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


A method for implementing lock-free shared data structures

Barnes, Greg

April 1994, 15 pages.

Status: available - back from printing

We are interested in implementing data structures on shared memory multiprocessors. A natural model for these machines is an asynchronous parallel machine, in which the processors are subject to arbitrary delays. On such machines, it is desirable for algorithms to be {\em lock-free}, that is, they must allow concurrent access to data without using mutual exclusion. Efficient lock-free implementations are known for some specific data structures, but these algorithms do not generalize well to other structures. For most data structures, the only previously known lock-free algorithm is due to Herlihy. Herlihy presents a simple methodology to create a lock-free implementation of a general data structure, but his approach can be very expensive. We present a technique that provides the semantics of exclusive access to data without using mutual exclusion. Using this technique, we devise the {\em caching method}, a general method of implementing lock-free data structures that is provably better than Herlihy's methodology for many well-known data structures. The cost of one operation using the caching method is proportional to $T \log T$, where $T$ is the sequential cost of the operation. Under Herlihy's methodology, the cost is proportional to $T + C$, where $C$ is the time needed to make a logical copy of the data structure. For many data structures, such as arrays and {\em well connected} pointer-based structures (e.g., a doubly linked list), the best known value for $C$ is proportional to the size of the structure, making the copying time much larger than the sequential cost of an operation. The new method can also allow {\em concurrent updates} to the data structure; Herlihy's methodology cannot. A correct lock-free implementation can be derived from a correct sequential implementation in a straightforward manner using this method. The method is also flexible; a programmer can change many of the details of the default implementation to optimize for a particular pattern of data structure use.

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Barnes, Greg},
  TITLE = {A method for implementing lock-free shared data structures},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-94-120},
  MONTH = {April},
  YEAR = {1994},
  ISSN = {0946-011X},