Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


A method for implementing lock-free shared data structures

Barnes, Greg

MPI-I-94-120. April 1994, 15 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
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
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.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-94-120.pdfMPI-I-94-120.pdf10635 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
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},