A method for implementing lock-free shared-data structures

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 desuable for algorithms to be loclc-free, that is, they must allow concurrent access to data without using mutual exclusion. Eflicient lock-free implementations are known ror some specific data structures, but these algorithms do not generalize weIl to other structures. For most data structures, the only previously known lock-free algorithm is due to Herlihy [12]. Herlihy presents a simple methodology to create a lock-free implementation of a general data structure, but his approach can be very expensive.