Technical Report
Number 579
Computer Laboratory
UCAM-CL-TR-579
ISSN 1476-2986
Practical lock-freedom
Keir Fraser
February 2004
15 JJ Thomson Avenue
Cambridge CB3 0FD
United Kingdom
phone +44 1223 763500
http://www.cl.cam.ac.uk/
c
2004 Keir Fraser
This technical report is based on a dissertation submitted
September 2003 by the author for the degree of Doctor of
Philosophy to the University of Cambridge, King’s College.
Technical reports published by the University of Cambridge
Computer Laboratory are freely available via the Internet:
http://www.cl.cam.ac.uk/TechReports/
Series editor: Markus Kuhn
ISSN 1476-2986
Summary
Mutual-exclusion locks are currently the most popular mechanism for interpro-
cess synchronisation, largely due to their apparent simplicity and ease of imple-
mentation. In the parallel-computing environments that are increasingly com-
monplace in high-performance applications, this simplicity is deceptive: mutual
exclusion does not scale well with large numbers of locks and many concur-
rent threads of execution. Highly-concurrent access to shared data demands a
sophisticated ‘fine-grained’ locking strategy to avoid serialising non-conflicting
operations. Such strategies are hard to design correctly and with good perfor-
mance because they can harbour problems such as deadlock, priority inversion
and convoying. Lock manipulations may also degrade the performance of cache-
coherent multiprocessor systems by causing coherency conflicts and increased
interconnect traffic, even when the lock protects read-only data.
In looking for solutions to these problems, interest has developed in lock-free
data structures. By eschewing mutual exclusion it is hoped that more efficient
and robust systems can be built. Unfortunately the current reality is that most
lock-free algorithms are complex, slow and impractical. In this dissertation I
address these concerns by introducing and evaluating practical abstractions and
data structures that facilitate the development of large-scale lock-free systems.
Firstly, I present an implementation of two useful abstractions that make it easier
to develop arbitrary lock-free data structures. Although these abstractions have
been described in previous work, my designs are the first that can be practically
implemented on current multiprocessor systems.
Secondly, I present a suite of novel lock-free search structures. This is interest-
ing not only because of the fundamental importance of searching in computer
science and its wide use in real systems, but also because it demonstrates the
implementation issues that arise when using the practical abstractions I have
developed.
Finally, I evaluate each of my designs and compare them with existing lock-
based and lock-free alternatives. To ensure the strongest possible competition,
several of the lock-based alternatives are significant improvements on the best-
known solutions in the literature. These results demonstrate that it is possible to
build useful data structures with all the perceived benefits of lock-freedom and
with performance better than sophisticated lock-based designs. Furthermore,
and contrary to popular belief, this work shows that existing hardware primi-
tives are sufficient to build practical lock-free implementations of complex data
structures.
3
4
Table of contents
1 Introduction 7
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Terminology discussion . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5 Pseudocode conventions . . . . . . . . . . . . . . . . . . . . . . . 12
2 Background 13
2.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.1 Lock-freedom . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.2 Wait-freedom . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.3 Obstruction-freedom . . . . . . . . . . . . . . . . . . . . . 15
2.2 Desirable algorithmic features . . . . . . . . . . . . . . . . . . . . 15
2.2.1 Disjoint-access parallelism . . . . . . . . . . . . . . . . . . 16
2.2.2 Linearisability . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.1 Non-blocking primitives . . . . . . . . . . . . . . . . . . . 17
2.3.2 Universal constructions . . . . . . . . . . . . . . . . . . . . 18
2.3.3 Programming abstractions . . . . . . . . . . . . . . . . . . 19
2.3.4 Ad hoc data structures . . . . . . . . . . . . . . . . . . . . 24
2.3.5 Memory management . . . . . . . . . . . . . . . . . . . . 25
2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3 Practical lock-free programming abstractions 29
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2 Multi-word compare-&-swap (MCAS) . . . . . . . . . . . . . . . 30
3.2.1 Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3 Software transactional memory . . . . . . . . . . . . . . . . . . . 34
3.3.1 Programming interface . . . . . . . . . . . . . . . . . . . . 36
3.3.2 Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.3.3 Further enhancements . . . . . . . . . . . . . . . . . . . . 47
5
评论1