Lock-free algorithms: Difference between revisions

Revision as of 14:42, 12 July 2009

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. Nonetheless,

Fich, Hendler, and Shavit's 2004 "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.

@@ 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. Nonetheless,
+==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==