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