Lock-free and wait-free algorithms

In contrast to algorithms that protect access to shared data with locks, lock-free and wait-free algorithms are specially designed to allow multiple threads to read and write shared data concurrently without corrupting it. "Lock-free" refers to the fact that no synchronization primitives such as mutexes or semaphores are involved. "Wait-free" refers to the fact that a thread can complete any operation in a finite number of steps, regardless of the actions of other threads. It is possible for an algorithm to be lock-free but not wait-free.

Contents

1 Motivation 2 The lock-free approach 3 Implementation 4 See also 5 External links

Motivation

The traditional approach to multi-threaded programming is to use locks to synchronize access to shared resources. Synchronization primitives such as mutexes, semaphores, and critical sections are all mechanisms by which a programmer can ensure that certain sections of code do not execute concurrently if doing so would corrupt shared memory structures. If one thread attempts to acquire a lock that is already held by another thread, the thread will block until the lock is free.

Blocking a thread is undesirable for many reasons. An obvious reason is that while the thread is blocked, it cannot accomplish anything. If the blocked thread is performing a high-priority or real-time task, it is highly undesirable to halt its progress. Other problems are less obvious. Certain interactions between locks can lead to error conditions such as deadlock, livelock, and priority inversion. Using locks also involves a trade-off between coarse-grained locking which can significantly reduce opportunities for parallelism, and fine-grained locking which requires more careful design and is more prone to bugs.

The lock-free approach

Writing a program that uses lock-free data structures is not a matter of rewriting the algorithms you would normally protect with a mutex to be lock-free. Because lock-free algorithms are so difficult to write, researchers focus on writing lock-free versions of basic data structures such as stacks, queues, sets, and hash tables. These allow programs to easily exchange data between threads asynchronously.

For example, consider a banking program where each thread represents a virtual teller. A lock-based approach to making a deposit could be to have one teller lock an account to make a deposit, so that two tellers don't try to deposit into the same account simultaneously. To make the process lock-free, rather than designing a lock-free "deposit" algorithm you might have the teller submit a "deposit" request asynchronously to a centralized thread that handled all deposits.

Implementation

Lock-free and wait-free algorithms are written using atomic primitives that the hardware must provide. The most notable of these is "compare and swap" (often notated "CAS"), which takes three arguments: a memory address, an old value, and a new value. If the address contains the old value, it is replaced with the new value, otherwise it is unchanged. Critically, the hardware guarantees that this "comparison and swap" operation is executed atomically. The success of this operation is then reported back to the program. This allows an algorithm to read a datum from memory, modify it, and write it back only if no other thread modified it in the meantime.

For example, consider a different implementation of the a banking program where each thread represents a virtual teller. The teller reads the current value of the account (old value), adds an amount and uses CAS to attempt to update the account balance. If no other thread has modified the account balance in the intervening period, the CAS will succeed, and account balance will be updated. However, if a concurrent modification has occurred, the CAS will fail, and the teller will retry the update (by first fetching the new account balance). Each teller will perform this CAS operation in a loop, retrying until they are successful. This algorithm is lock-free but not wait-free, since other threads may keep writing new values and make our teller go for another try.

See also

• Deadlock
• Real-time
• Starvation
• Contention
• Synchronization
• Mutual exclusion
• Priority inversion
• Concurrency control
• Pre-emptive multitasking
• Non-blocking synchronization
• Lock (software engineering)
• Room synchronization
• Read-copy-update
• Memory barrier

External links

• Survey "Some Notes on Lock-Free and Wait-Free Algorithms (http://www.audiomulch.com/~rossb/code/lockfree/)" by Ross Bencina
• Citations from CiteSeer (http://citeseer.org/cs?q=lock-free+wait-free)
• "Scalable Lock-Free Dynamic Memory Allocation (http://www.research.ibm.com/people/m/michael/pldi-2004.pdf)" and Selected Publications - Journal and Conference Papers (http://www.research.ibm.com/people/m/michael/pubs.htm) by Maged M. Michael
• Package java.util.concurrent.atomic (http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/atomic/package-summary.html) - supports lock-free and thread-safe programming on single variables
• The Jail-Ust Container Library (http://jail-ust.sourceforge.net/index.php?section=3&page=1)
• Practical lock-free data structures (http://www.cl.cam.ac.uk/Research/SRG/netos/lock-free/)
• Thesis "Efficient and Practical Non-Blocking Data Structures (http://www.cs.chalmers.se/~phs/phd.pdf)" (1414 KB) by Håkan Sundell
• WARPing - Wait-free techniques for Real-time Processing (http://www.cs.chalmers.se/~phs/warp/project.html)
• Non-blocking Synchronization: Algorithms and Performance Evaluation. (http://www.cs.chalmers.se/~yzhang/thesis.pdf) (1926 KB) by Yi Zhang
• Lock-free Lockless-MiniSPLASH2 Application Benchmark (http://www.cs.chalmers.se/~dcs/miniSplash2.html)
• "Aynchronous Data Sharing in Multiprocessor Real-Time Systems Using Process Consensus (http://citeseer.ist.psu.edu/114960.html)" by Jing Chen and Alan Burns
• Discussion "lock-free versus lock-based algorithms (http://groups.google.de/groups?group=comp.programming.threads&threadm=ec1c3924.0410171103.568fa38a%40posting.google.com)"
• Atomic Ptr Plus Project (http://atomic-ptr-plus.sourceforge.net/) - collection of various lock-free synchronization primitives
• AppCore: A Portable High-Performance Thread Synchronization Library (http://appcore.home.comcast.net/) - An Effective Marriage between Lock-Free and Lock-Based Algorithms
• Practical Lock Freedom (http://www.cl.cam.ac.uk/users/kaf24/lockfree.html) - research and MCAS and STM implementations for all major platforms by Keir Fraser
• LeapHeap (http://www.leapheap.com/) - lock-free memory manager
• WaitFreeSynchronization (http://c2.com/cgi/wiki?WaitFreeSynchronization) and LockFreeSynchronization (http://c2.com/cgi/wiki?LockFreeSynchronization) at the Portland Pattern Repository