Some notes on lock-free and wait-free algorithms

Ross Bencina
home page email
Page last updated 11 May 2006

Over the past two decades the research community has developed a body of knowledge concerning "Lock-Free" and "Wait-Free" algorithms and data structures. These techniques allow concurrent update of shared data structures without resorting to critical sections protected by operating system managed locks. A number of wait-free and lock free algorithms for simple data structures such as LIFO stacks and FIFO queues have been published. Lock-free algorithms for more complex data structures such as priority queues, hash tables, sets, and red-black trees are also known.

Some of the most commonly stated benefits of lock-free synchronisation are:

A significant benefit of lock (or wait)-freedom for real-time systems is that by avoiding locks the potential for priority inversion is avoided. Solutions for avoiding priority inversion usually involve special real-time process schedulers. On platforms where a real-time scheduler is not present, lock-free data structures provide an opportunity to sidestep the hazards of interlocking with the scheduler.

With the exception of a uniprocessor implementation of a single-reader single-writer ring buffer FIFO, all the lock-free algorithms which I have encountered require the use of special atomic processor instructions such as CAS (compare and swap) or LL/SC (load linked/store conditional). Furthermore, the correct implementation of these algorithms also requires an understanding of the use of memory barriers to force the order of some memory reads and writes on SMP systems. This is because memory controllers may reorder reads and writes as observed by other processors on an SMP system (or by prehipherals on a uniprocessor system).

Lock free structures in computer music

One example of a context which can benefit from lock-free synchronisation is the desktop digital audio domain. Commodity operating systems such as Microsoft Windows and Macintosh OS-X do not provide real-time schedulers, yet there is often a requirement for concurrent access to shared data structures accross separate threads maintaining a GUI, performing real-time audio rendering, and performing disk and network i/o.

Lock-free data structures are not unknown in the computer music world. For example the venerable single-reader single-writer atomic ring buffer FIFO is found in many systems including PortAudio, PortMidi, and SuperCollider. More complex data structures such as node-based lock free queues are found in MidiShare (see also post to LAD). JACK also cites some lock-free publications although it is not clear if it uses them. Serpent uses lock-free data structures. JSyn uses lock-free FIFOs and singly-linked-lists.

Ken Greenbaum informs me that the SGI AL implementation uses the single-reader, single-writer ring buffer algorithm, and successfully implements this on symmetric MP machines.

In search of an open source library

It would be useful to have a cross-platform library of lock-free primitives for implementing real-time applications on desktop operating systems. Such a library would include implementations of queues and stacks, low level atomic update operations and memory barriers. It may also be useful to include higher level infrastructure, such as a robust implementation of deferred C++ function calls (for example see the single reader, single writer prototype code here). The present author is seeking to find or develop a library released under a permissive open source license allowing use in closed-source applications. These requirements can be summarised as follows:

Thus far a library which fulfills the above requirements has not been identified. If you know of such a library, or are interested in contributing to the development of one, please let me know.

NEWSFLASH!: a group of interested developers has formed a working group to create the lock-free data structures library. Why not join us?

Existing source code and libraries.

The following is a list of open-source libraries which provide implementations of lock-free data structures. If you know of one which isn't listed here, please let me know.

Brief literature survey

This is not an exhaustive list, but the hope is that enough core articles are linked to give a good introduction to the field. Most of the resources here can be turned up on google or citeseer with search terms such as "lock free", "lock-free", "wait free", "lock free queue", "non-blocking", "atomic fifo", etc.

Other possibly relevant links