Lock-free algorithms: Difference between revisions
No edit summary |
No edit summary |
||
| (2 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. | 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 | * 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 | |||