Check out my first novel, midnight's simulacra!

Lock-free algorithms: Difference between revisions

From dankwiki
No edit summary
No edit summary
 
(4 intermediate revisions by the same user not shown)
Line 1: Line 1:
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. Nonetheless,
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==
==Architectural Primitives==
Line 8: Line 12:
* Bencina, "[http://www.audiomulch.com/~rossb/code/lockfree/ Some Notes on Lock-Free Algorithms]"
* 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
* "[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

Latest revision as of 11:47, 29 January 2010

Herlihy, Luchangco and Moir's 2003 paper, "Obstruction-Free Synchronization: Double-Ended Queues as an Example" pretty much revolutionized the field and is mandatory reading. Techniques like 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

See Also