Check out my first novel, midnight's simulacra!
Lock-free algorithms: Difference between revisions
From dankwiki
No edit summary |
No edit summary |
||
| Line 8: | Line 8: | ||
* 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 | * 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. | |||
Revision as of 10:08, 4 September 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.
Architectural Primitives
- 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.
See Also
- LWN's 2008-09-30 and 2009-07-08 articles on lockless ring buffers in the Linux kernel
- Bencina, "Some Notes on Lock-Free Algorithms"
- "Practical Lock-Free Algorithms" at Cambridge's Computer Laboratory's Systems Research Group
- Section 5.2, "Synchronization Primitives", in Understanding the Linux Kernel, Third Edition
- "Memory Ordering in Modern Microprocessors" by Paul McKenney.
