Lock-free algorithms

(5 intermediate revisions by the same user not shown)

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.

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==

Line 5:

Line 12:

* 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

Lock-free algorithms: Difference between revisions

Dank (talk | contribs)

@@ 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.
+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==
@@ Line 5: / Line 12: @@
 * 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