Lock-free algorithms - revision history

Dank at 11:47, 29 January 2010

2010-01-29T11:47:37Z

← Older revision		Revision as of 11:47, 29 January 2010
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==

Dank at 11:46, 29 January 2010

2010-01-29T11:46:28Z

← Older revision		Revision as of 11:46, 29 January 2010
Line 10:		Line 10:
	* 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.		* [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

Dank at 10:08, 4 September 2009

2009-09-04T10:08:48Z

← Older revision		Revision as of 10:08, 4 September 2009
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.

Dank at 15:34, 12 July 2009

2009-07-12T15:34:39Z

← Older revision		Revision as of 15:34, 12 July 2009
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

Dank at 14:43, 12 July 2009

2009-07-12T14:43:18Z

← Older revision		Revision as of 14:43, 12 July 2009
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.

	==Architectural Primitives==		==Architectural Primitives==

Dank at 14:42, 12 July 2009

2009-07-12T14:42:43Z

← Older revision		Revision as of 14:42, 12 July 2009
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==		==See Also==

Dank at 14:37, 12 July 2009

2009-07-12T14:37:33Z

← Older revision		Revision as of 14:37, 12 July 2009
Line 4:		Line 4:
	* LWN's [http://lwn.net/Articles/300992/ 2008-09-30] and [http://lwn.net/Articles/339641/ 2009-07-08] articles on lockless ring buffers in the Linux kernel		* LWN's [http://lwn.net/Articles/300992/ 2008-09-30] and [http://lwn.net/Articles/339641/ 2009-07-08] articles on lockless ring buffers in the Linux kernel
	* 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

Dank at 14:36, 12 July 2009

2009-07-12T14:36:14Z

← Older revision		Revision as of 14:36, 12 July 2009
Line 3:		Line 3:
	==See Also==		==See Also==
	* LWN's [http://lwn.net/Articles/300992/ 2008-09-30] and [http://lwn.net/Articles/339641/ 2009-07-08] articles on lockless ring buffers in the Linux kernel		* LWN's [http://lwn.net/Articles/300992/ 2008-09-30] and [http://lwn.net/Articles/339641/ 2009-07-08] articles on lockless ring buffers in the Linux kernel
			* Bencina, "[http://www.audiomulch.com/~rossb/code/lockfree/ Some Notes on Lock-Free Algorithms]"

Dank at 09:59, 12 July 2009

2009-07-12T09:59:15Z

← Older revision		Revision as of 09:59, 12 July 2009
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.

			==See Also==
			* LWN's [http://lwn.net/Articles/300992/ 2008-09-30] and [http://lwn.net/Articles/339641/ 2009-07-08] articles on lockless ring buffers in the Linux kernel

Dank: Created page with '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 m...'

2009-07-12T09:56:49Z

Created page with '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 m...'

New page

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.