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 threading 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. 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 operation (Ex: Microsoft_Windows - InterlockedCompareExchange) to write back a new value atomically, only if no other thread modified it in the meantime. It keeps doing that in a loop for another attempt to read,add and write back. 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)"