View source for Lock-free algorithms

Herlihy, Luchangco and Moir's 2003 paper, "[http://www.cs.brown.edu/people/mph/HerlihyLM03/main.pdf Obstruction-Free Synchronization: Double-Ended Queues as an Example]" pretty much revolutionized the field and is mandatory reading. Techniques like [[transactional memory|speculative lock elision]] (SLE) can abrogate much of the cost of uncontested locks, and threading implementations like [[NPTL]] handle uncontested mutexes entirely in userspace.

==Taxonomy==
* ''lock-free'' - guaranteed system-wide progress
* ''wait-free'' - guaranteed per-thread progress

==Architectural Primitives==
* Fich, Hendler, and Shavit's 2004 "[http://www.cs.tau.ac.il/~afek/Handler-conditionals.pdf On the Inherent Weakness of Conditional Synchronization Primites]" shows that CAS and LL/SC cannot provide starvation-free implementations of many common data structures without O(N) space on N threads.

==See Also==
* LWN's [http://lwn.net/Articles/300992/ 2008-09-30] and [http://lwn.net/Articles/339641/ 2009-07-08] articles on lockless ring buffers in the Linux kernel
* Bencina, "[http://www.audiomulch.com/~rossb/code/lockfree/ Some Notes on Lock-Free Algorithms]"
* "[http://www.cl.cam.ac.uk/research/srg/netos/lock-free/ Practical Lock-Free Algorithms]" at Cambridge's Computer Laboratory's Systems Research Group
* Section 5.2, "[http://jno.glas.net/data/prog_books/lin_kern_2.6/0596005652/understandlk-CHP-5-SECT-2.html Synchronization Primitives]", in <i>[http://jno.glas.net/data/prog_books/lin_kern_2.6/0596005652/main.html Understanding the Linux Kernel</i>, Third Edition]
* [http://www.rdrop.com/users/paulmck/scalability/paper/ordering.2007.09.19a.pdf "Memory Ordering in Modern Microprocessors"] by Paul McKenney.
* [[High Performance Parallel Computing]] page