Concurrent Programming Without Locks

KEIR FRASER

University of Cambridge Computer Laboratory

and

TIM HARRIS

Microsoft Research Cambridge

Mutual exclusion locks remain the de facto mechanism for concurrency control on shared-memory

data structures. However, their apparent simplicity is deceptive: It is hard to design scalable locking

strategies because locks can harbor problems such as priority inversion, deadlock, and convoying.

Furthermore, scalable lock-based systems are not readily composable when building compound

operations. In looking for solutions to these problems, interest has developed in nonblocking systems which have promised scalability and robustness by eschewing mutual exclusion while still

ensuring safety. However, existing techniques for building nonblocking systems are rarely suitable

for practical use, imposing substantial storage overheads, serializing nonconflicting operations, or

requiring instructions not readily available on today’s CPUs.

In this article we present three APIs which make it easier to develop nonblocking implementations of arbitrary data structures. The first API is a multiword compare-and-swap operation

(MCAS) which atomically updates a set of memory locations. This can be used to advance a data

structure from one consistent state to another. The second API is a word-based software transactional memory (WSTM) which can allow sequential code to be reused more directly than with MCAS

and which provides better scalability when locations are being read rather than being updated.

The third API is an object-based software transactional memory (OSTM). OSTM allows a simpler

implementation than WSTM, but at the cost of reengineering the code to use OSTM objects.

We present practical implementations of all three of these APIs, built from operations available

across all of today’s major CPU families. We illustrate the use of these APIs by using them to build

highly concurrent skip lists and red-black trees. We compare the performance of the resulting

implementations against one another and against high-performance lock-based systems. These

results demonstrate that it is possible to build useful nonblocking data structures with performance

comparable to, or better than, sophisticated lock-based designs.

Categories and Subject Descriptors: D.4.1 [Operating Systems]: Process Management—Concurrency, mutual exclusion, synchronization

Read more: MS Research PDF

Posted via email from Jasper-net