Item

Abstract

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.