max planck institut

informatik

informatik

**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.

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.

Acknowledgement:** **

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.pdf | 10635 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |