Computer Laboratory

Systems Research Group – NetOS

Practical lock-free data structures

Introduction

Through careful design and implementation it's possible to build data structures that are safe for concurrent use without needing to manage locks or block threads. These non-blocking data structures can increase performance by allowing extra concurrency and can improve robustness by avoiding some of the problems caused by priority inversion in local settings, or machine and link failures in distributed systems.

The best overall introduction to our non-blocking algorithms is the paper Concurrent programming without locks, currently under submission, which covers our designs for multi-word compare-and-swap, word-based software transactional memory and object-based software transactional memory.

The papers Language support for lightweight transactions and Exceptions and side-effects in atomic blocks cover the integration of a software transactional memory with a managed run-time environment.

Keir Fraser's dissertation, Practical lock freedom, presents a large number of new designs for concurrent data structures such as skip-lists, red-black trees and binary search trees, including new lock-based designs as well as lock-free versions.

This work is supported by donations from the Intel/Hewlett-Packard IPF University Grants Program and from the Scalable Synchronization Research Group at Sun Labs Massachusetts. We would also like to thank Nick Maclaren for providing access to the Cambridge-Cranfield High Performance Computing Facility.

Source code

Lock-free library (including object-based STM)

A set of lock-free programming abstractions and search structures. Includes an object-based software transactional memory, multi-word compare-and-swap, and a range of search structures (skip lists, binary search trees, red-black trees).

lock-free-lib.tar.gz

That same library under a BSD license: lock-free-lib-bsd.tar.gz

Word-based STM built directly from CAS

An initial source release for our word-based software transactional memory is available. It contains brief programming documentation -- for more details see our OOPSLA 2003 paper.

Note that this initial version lags our internal version in terms of many niceties – for instance many parameters must be specified at compile time and the implementation lacks several optimizations which give important performance improvements. We will be releasing those when we have time to create a new neatly packaged version of the code. Please e-mail Tim Harris if you would like to be kept up to date with future releases.

libstm-v1.tar.gz

Word-based STM using ‘hold’ / ‘release’ operations

A further release of our word-based software transactional memory. This is built over a new internal abstraction which provides revocable exclusive access to salient memory locations used in the algorithm's implementation. We will be reporting on these in more detail in a forthcoming paper, but believe that they provide a convenient abstraction for developing lock-free and obstruction-free algorithms and that they admit a variety of software and hardware implementations.

holdrel-v1.tar.gz

Publications

Concurrent programming without locks
Keir Fraser and Tim Harris
ACM Transactions on Computer Systems, Vol. 25 (2), May 2007
[PDF]

Non-blocking hashtables with open addressing
Chris Purcell and Tim Harris
19th International Symposium on Distributed Computing (DISC), September 2005
Also available as Cambridge University Technical Report UCAM-CL-TR-639
[PDF]

Exceptions and side-effects in atomic blocks
Tim Harris
Workshop on Concurrency and Synchronization in Java Programs
July 2004 (to appear)
[PDF] paper and [PPT] slides of a talk based on this work

Brief announcement: Implementing multi-word atomic snapshots on current hardware
Chris Purcell and Tim Harris
Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC 2004)
[PDF]

Practical lock freedom
Keir Fraser
PhD dissertation, September 2003
Cambridge University Technical Report UCAM-CL-TR-579
[PDF]

Language support for lightweight transactions
Tim Harris and Keir Fraser
Proceedings of the 18th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA-2003)
[PDF]

Design choices for language-based transactions
Tim Harris
Technical Report UCAM-CL-TR-572, August 2003
[PDF]

A Practical Multi-Word Compare-and-Swap Operation
Tim Harris, Keir Fraser and Ian Pratt
Proceedings of the 2002 IEEE Symposium on Distributed Computing
[PDF] [postscript]

A Pragmatic Implementation of Non-Blocking Linked Lists
Tim Harris
Proceedings of the 2001 IEEE Symposium on Distributed Computing
[PDF] [gzipped postscript] also published as part of Volume 2180 of Lecture Notes in Computer Science

People

Tim Harris

Tim Harris