Non-blocking algorithm - Revision history

BalinKingOfMoria: Add uncited quote tags

2024-11-05T18:21:20Z

Add uncited quote tags

← Previous revision		Revision as of 18:21, 5 November 2024
Line 4:		Line 4:
	In [[computer science]], an [[algorithm]] is called '''non-blocking''' if failure or [[Scheduling (computing)\|suspension]] of any [[thread (computing)\|thread]] cannot cause failure or suspension of another thread;<ref>{{cite book\|last1=Göetz\|first1=Brian\|last2=Peierls\|first2=Tim\|last3=Bloch\|first3=Joshua\|last4=Bowbeer\|first4=Joseph\|last5=Holmes\|first5=David\|last6=Lea\|first6=Doug\|title=Java concurrency in practice\|date=2006\|publisher=Addison-Wesley\|location=Upper Saddle River, NJ\|isbn=9780321349606\|page=[https://archive.org/details/javaconcurrencyi00goet/page/41 41]\|url-access=registration\|url=https://archive.org/details/javaconcurrencyi00goet/page/41}}</ref> for some operations, these algorithms provide a useful alternative to traditional [[lock (computer science)\|blocking implementations]]. A non-blocking algorithm is '''lock-free''' if there is guaranteed system-wide [[Resource starvation\|progress]], and '''wait-free''' if there is also guaranteed per-thread progress. "Non-blocking" was used as a synonym for "lock-free" in the literature until the introduction of obstruction-freedom in 2003.<ref name=obs-free>{{cite conference\|last1=Herlihy\|first1=M.\|last2=Luchangco\|first2=V.\|last3=Moir\|first3=M.\|title=Obstruction-Free Synchronization: Double-Ended Queues as an Example\|conference=23rd [[International Conference on Distributed Computing Systems]]\|year=2003\|pages=522\|url=http://www.cs.brown.edu/people/mph/HerlihyLM03/main.pdf}}</ref>		In [[computer science]], an [[algorithm]] is called '''non-blocking''' if failure or [[Scheduling (computing)\|suspension]] of any [[thread (computing)\|thread]] cannot cause failure or suspension of another thread;<ref>{{cite book\|last1=Göetz\|first1=Brian\|last2=Peierls\|first2=Tim\|last3=Bloch\|first3=Joshua\|last4=Bowbeer\|first4=Joseph\|last5=Holmes\|first5=David\|last6=Lea\|first6=Doug\|title=Java concurrency in practice\|date=2006\|publisher=Addison-Wesley\|location=Upper Saddle River, NJ\|isbn=9780321349606\|page=[https://archive.org/details/javaconcurrencyi00goet/page/41 41]\|url-access=registration\|url=https://archive.org/details/javaconcurrencyi00goet/page/41}}</ref> for some operations, these algorithms provide a useful alternative to traditional [[lock (computer science)\|blocking implementations]]. A non-blocking algorithm is '''lock-free''' if there is guaranteed system-wide [[Resource starvation\|progress]], and '''wait-free''' if there is also guaranteed per-thread progress. "Non-blocking" was used as a synonym for "lock-free" in the literature until the introduction of obstruction-freedom in 2003.<ref name=obs-free>{{cite conference\|last1=Herlihy\|first1=M.\|last2=Luchangco\|first2=V.\|last3=Moir\|first3=M.\|title=Obstruction-Free Synchronization: Double-Ended Queues as an Example\|conference=23rd [[International Conference on Distributed Computing Systems]]\|year=2003\|pages=522\|url=http://www.cs.brown.edu/people/mph/HerlihyLM03/main.pdf}}</ref>

	The word "non-blocking" was traditionally used to describe [[telecommunications network]]s that could route a connection through a set of relays "without having to re-arrange existing calls" (see [[Clos network]]). Also, if the telephone exchange "is not defective, it can always make the connection" (see [[nonblocking minimal spanning switch]]).		The word "non-blocking" was traditionally used to describe [[telecommunications network]]s that could route a connection through a set of relays "without having to re-arrange existing calls"{{Quote without source\|date=November 2024}} (see [[Clos network]]). Also, if the telephone exchange "is not defective, it can always make the connection"{{Quote without source\|date=November 2024}} (see [[nonblocking minimal spanning switch]]).

	== Motivation ==		== Motivation ==

BalinKingOfMoria: /* Wait-freedom */ Try to cleanup style

2024-10-31T17:37:19Z

Wait-freedom: Try to cleanup style

← Previous revision		Revision as of 17:37, 31 October 2024
Line 77:		Line 77:
	Wait-free algorithms were rare until 2011, both in research and in practice. However, in 2011 Kogan and [[Erez Petrank\|Petrank]]<ref name=wf-queue>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 16th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2011 \|isbn=978-1-4503-0119-0 \|pages=223–234 \|doi=10.1145/1941553.1941585 \|title=Wait-free queues with multiple enqueuers and dequeuers\|url=http://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf}}</ref> presented a wait-free queue building on the [[Compare-and-swap\|CAS]] primitive, generally available on common hardware. Their construction expanded the lock-free queue of Michael and Scott,<ref name=lf-queue>{{cite conference \|last1=Michael \|first1=Maged \|last2=Scott \|first2=Michael \|conference=Proc. 15th Annual ACM Symp. on Principles of Distributed Computing (PODC) \|year=1996 \|isbn=0-89791-800-2 \|pages=267–275 \|doi=10.1145/248052.248106 \|title=Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms\|doi-access=free }}</ref> which is an efficient queue often used in practice. A follow-up paper by Kogan and Petrank<ref name=wf-fpsp>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2012 \|isbn=978-1-4503-1160-1 \|pages=141–150 \|doi=10.1145/2145816.2145835 \|title=A method for creating fast wait-free data structures}}</ref> provided a method for making wait-free algorithms fast and used this method to make the wait-free queue practically as fast as its lock-free counterpart. A subsequent paper by Timnat and Petrank<ref name=wf-simulation>{{cite conference \|last1=Timnat \|first1=Shahar \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2014 \| isbn=978-1-4503-2656-8 \| pages = 357–368 \| doi=10.1145/2692916.2555261 \| title= A Practical Wait-Free Simulation for Lock-Free Data Structures}}</ref> provided an automatic mechanism for generating wait-free data structures from lock-free ones. Thus, wait-free implementations are now available for many data-structures.		Wait-free algorithms were rare until 2011, both in research and in practice. However, in 2011 Kogan and [[Erez Petrank\|Petrank]]<ref name=wf-queue>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 16th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2011 \|isbn=978-1-4503-0119-0 \|pages=223–234 \|doi=10.1145/1941553.1941585 \|title=Wait-free queues with multiple enqueuers and dequeuers\|url=http://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf}}</ref> presented a wait-free queue building on the [[Compare-and-swap\|CAS]] primitive, generally available on common hardware. Their construction expanded the lock-free queue of Michael and Scott,<ref name=lf-queue>{{cite conference \|last1=Michael \|first1=Maged \|last2=Scott \|first2=Michael \|conference=Proc. 15th Annual ACM Symp. on Principles of Distributed Computing (PODC) \|year=1996 \|isbn=0-89791-800-2 \|pages=267–275 \|doi=10.1145/248052.248106 \|title=Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms\|doi-access=free }}</ref> which is an efficient queue often used in practice. A follow-up paper by Kogan and Petrank<ref name=wf-fpsp>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2012 \|isbn=978-1-4503-1160-1 \|pages=141–150 \|doi=10.1145/2145816.2145835 \|title=A method for creating fast wait-free data structures}}</ref> provided a method for making wait-free algorithms fast and used this method to make the wait-free queue practically as fast as its lock-free counterpart. A subsequent paper by Timnat and Petrank<ref name=wf-simulation>{{cite conference \|last1=Timnat \|first1=Shahar \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2014 \| isbn=978-1-4503-2656-8 \| pages = 357–368 \| doi=10.1145/2692916.2555261 \| title= A Practical Wait-Free Simulation for Lock-Free Data Structures}}</ref> provided an automatic mechanism for generating wait-free data structures from lock-free ones. Thus, wait-free implementations are now available for many data-structures.

	Under reasonable assumptions, Alistarh, Censor-Hillel, and Shavit showed that lock-free algorithms are practically wait-free.<ref name=lf-wf>{{cite conference \|last1=Alistarh \|first1=Dan \|last2=Censor-Hillel \|first2=Keren \|last3=Shavit \|first3=Nir \|conference=Proc. 46th Annual ACM Symposium on Theory of Computing (STOC’14) \| year=2014 \| isbn=978-1-4503-2710-7 \| pages = 714–723 \| doi=10.1145/2591796.2591836 \| title=Are Lock-Free Concurrent Algorithms Practically Wait-Free?\|arxiv=1311.3200 }}</ref> So the ~~added~~ ~~algorithmic~~ ~~complexity~~ ~~of a~~ wait-free ~~algorithm~~ ~~might~~ not be worth the ~~effort,~~ if ~~there~~ ~~are not hard deadlines to be~~ ~~met~~.		Under reasonable assumptions, Alistarh, Censor-Hillel, and Shavit showed that lock-free algorithms are practically wait-free.<ref name=lf-wf>{{cite conference \|last1=Alistarh \|first1=Dan \|last2=Censor-Hillel \|first2=Keren \|last3=Shavit \|first3=Nir \|conference=Proc. 46th Annual ACM Symposium on Theory of Computing (STOC’14) \| year=2014 \| isbn=978-1-4503-2710-7 \| pages = 714–723 \| doi=10.1145/2591796.2591836 \| title=Are Lock-Free Concurrent Algorithms Practically Wait-Free?\|arxiv=1311.3200 }}</ref> Thus, in the absence of hard deadlines, wait-free algorithms may not be worth the additional complexity that they introduce.

	== Lock-freedom ==		== Lock-freedom ==

BalinKingOfMoria: /* Wait-freedom */ Try to cleanup style

2024-10-31T17:35:52Z

Wait-freedom: Try to cleanup style

← Previous revision		Revision as of 17:35, 31 October 2024
Line 73:		Line 73:
	Several papers have investigated the difficulty of creating wait-free algorithms. For example, it has been shown<ref name=cond-sync>{{cite conference \|last1=Fich \|first1=Faith\|author1-link=Faith Ellen \|last2=Hendler \|first2=Danny \|last3=Shavit \|first3=Nir \|conference=Proc. 23rd Annual ACM Symp.on Principles of Distributed Computing (PODC) \|year=2004 \|isbn=1-58113-802-4 \|pages=80–87 \|doi=10.1145/1011767.1011780 \|title=On the inherent weakness of conditional synchronization primitives}}</ref> that the widely available atomic ''conditional'' primitives, [[Compare-and-swap\|CAS]] and [[Load-link/store-conditional\|LL/SC]], cannot provide starvation-free implementations of many common data structures without memory costs growing linearly in the number of threads.		Several papers have investigated the difficulty of creating wait-free algorithms. For example, it has been shown<ref name=cond-sync>{{cite conference \|last1=Fich \|first1=Faith\|author1-link=Faith Ellen \|last2=Hendler \|first2=Danny \|last3=Shavit \|first3=Nir \|conference=Proc. 23rd Annual ACM Symp.on Principles of Distributed Computing (PODC) \|year=2004 \|isbn=1-58113-802-4 \|pages=80–87 \|doi=10.1145/1011767.1011780 \|title=On the inherent weakness of conditional synchronization primitives}}</ref> that the widely available atomic ''conditional'' primitives, [[Compare-and-swap\|CAS]] and [[Load-link/store-conditional\|LL/SC]], cannot provide starvation-free implementations of many common data structures without memory costs growing linearly in the number of threads.

	~~But in practice~~ these lower bounds do not present a real barrier as spending a cache line or exclusive reservation granule (up to 2 KB on ARM) of store per thread in the shared memory is not considered too costly for practical systems ~~(typically~~ the amount of store logically required is a word, but physically CAS operations on the same cache line will collide, and LL/SC operations in the same exclusive reservation granule will collide, so the amount of store physically required{{citation needed\|date=June 2014}} is greater).		However, these lower bounds do not present a real barrier in practice, as spending a cache line or exclusive reservation granule (up to 2 KB on ARM) of store per thread in the shared memory is not considered too costly for practical systems. Typically, the amount of store logically required is a word, but physically CAS operations on the same cache line will collide, and LL/SC operations in the same exclusive reservation granule will collide, so the amount of store physically required{{citation needed\|date=June 2014}} is greater.{{Clarification needed\|date=October 2024\|reason=Does this imply that there actually is a barrier in practice?}}

	Wait-free algorithms were rare until 2011, both in research and in practice. However, in 2011 Kogan and [[Erez Petrank\|Petrank]]<ref name=wf-queue>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 16th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2011 \|isbn=978-1-4503-0119-0 \|pages=223–234 \|doi=10.1145/1941553.1941585 \|title=Wait-free queues with multiple enqueuers and dequeuers\|url=http://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf}}</ref> presented a wait-free queue building on the [[Compare-and-swap\|CAS]] primitive, generally available on common hardware. Their construction expanded the lock-free queue of Michael and Scott,<ref name=lf-queue>{{cite conference \|last1=Michael \|first1=Maged \|last2=Scott \|first2=Michael \|conference=Proc. 15th Annual ACM Symp. on Principles of Distributed Computing (PODC) \|year=1996 \|isbn=0-89791-800-2 \|pages=267–275 \|doi=10.1145/248052.248106 \|title=Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms\|doi-access=free }}</ref> which is an efficient queue often used in practice. A follow-up paper by Kogan and Petrank<ref name=wf-fpsp>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2012 \|isbn=978-1-4503-1160-1 \|pages=141–150 \|doi=10.1145/2145816.2145835 \|title=A method for creating fast wait-free data structures}}</ref> provided a method for making wait-free algorithms fast and used this method to make the wait-free queue practically as fast as its lock-free counterpart. A subsequent paper by Timnat and Petrank<ref name=wf-simulation>{{cite conference \|last1=Timnat \|first1=Shahar \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2014 \| isbn=978-1-4503-2656-8 \| pages = 357–368 \| doi=10.1145/2692916.2555261 \| title= A Practical Wait-Free Simulation for Lock-Free Data Structures}}</ref> provided an automatic mechanism for generating wait-free data structures from lock-free ones. Thus, wait-free implementations are now available for many data-structures.		Wait-free algorithms were rare until 2011, both in research and in practice. However, in 2011 Kogan and [[Erez Petrank\|Petrank]]<ref name=wf-queue>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 16th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2011 \|isbn=978-1-4503-0119-0 \|pages=223–234 \|doi=10.1145/1941553.1941585 \|title=Wait-free queues with multiple enqueuers and dequeuers\|url=http://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf}}</ref> presented a wait-free queue building on the [[Compare-and-swap\|CAS]] primitive, generally available on common hardware. Their construction expanded the lock-free queue of Michael and Scott,<ref name=lf-queue>{{cite conference \|last1=Michael \|first1=Maged \|last2=Scott \|first2=Michael \|conference=Proc. 15th Annual ACM Symp. on Principles of Distributed Computing (PODC) \|year=1996 \|isbn=0-89791-800-2 \|pages=267–275 \|doi=10.1145/248052.248106 \|title=Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms\|doi-access=free }}</ref> which is an efficient queue often used in practice. A follow-up paper by Kogan and Petrank<ref name=wf-fpsp>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2012 \|isbn=978-1-4503-1160-1 \|pages=141–150 \|doi=10.1145/2145816.2145835 \|title=A method for creating fast wait-free data structures}}</ref> provided a method for making wait-free algorithms fast and used this method to make the wait-free queue practically as fast as its lock-free counterpart. A subsequent paper by Timnat and Petrank<ref name=wf-simulation>{{cite conference \|last1=Timnat \|first1=Shahar \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2014 \| isbn=978-1-4503-2656-8 \| pages = 357–368 \| doi=10.1145/2692916.2555261 \| title= A Practical Wait-Free Simulation for Lock-Free Data Structures}}</ref> provided an automatic mechanism for generating wait-free data structures from lock-free ones. Thus, wait-free implementations are now available for many data-structures.

Citation bot: Altered pages. Formatted dashes. | Use this bot. Report bugs. | Suggested by Abductive | Category:Synchronization | #UCB_Category 13/80

2024-09-24T06:07:34Z

Altered pages. Formatted dashes. | Use this bot. Report bugs. | Suggested by Abductive | Category:Synchronization | #UCB_Category 13/80

← Previous revision		Revision as of 06:07, 24 September 2024
Line 77:		Line 77:
	Wait-free algorithms were rare until 2011, both in research and in practice. However, in 2011 Kogan and [[Erez Petrank\|Petrank]]<ref name=wf-queue>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 16th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2011 \|isbn=978-1-4503-0119-0 \|pages=223–234 \|doi=10.1145/1941553.1941585 \|title=Wait-free queues with multiple enqueuers and dequeuers\|url=http://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf}}</ref> presented a wait-free queue building on the [[Compare-and-swap\|CAS]] primitive, generally available on common hardware. Their construction expanded the lock-free queue of Michael and Scott,<ref name=lf-queue>{{cite conference \|last1=Michael \|first1=Maged \|last2=Scott \|first2=Michael \|conference=Proc. 15th Annual ACM Symp. on Principles of Distributed Computing (PODC) \|year=1996 \|isbn=0-89791-800-2 \|pages=267–275 \|doi=10.1145/248052.248106 \|title=Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms\|doi-access=free }}</ref> which is an efficient queue often used in practice. A follow-up paper by Kogan and Petrank<ref name=wf-fpsp>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2012 \|isbn=978-1-4503-1160-1 \|pages=141–150 \|doi=10.1145/2145816.2145835 \|title=A method for creating fast wait-free data structures}}</ref> provided a method for making wait-free algorithms fast and used this method to make the wait-free queue practically as fast as its lock-free counterpart. A subsequent paper by Timnat and Petrank<ref name=wf-simulation>{{cite conference \|last1=Timnat \|first1=Shahar \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2014 \| isbn=978-1-4503-2656-8 \| pages = 357–368 \| doi=10.1145/2692916.2555261 \| title= A Practical Wait-Free Simulation for Lock-Free Data Structures}}</ref> provided an automatic mechanism for generating wait-free data structures from lock-free ones. Thus, wait-free implementations are now available for many data-structures.		Wait-free algorithms were rare until 2011, both in research and in practice. However, in 2011 Kogan and [[Erez Petrank\|Petrank]]<ref name=wf-queue>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 16th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2011 \|isbn=978-1-4503-0119-0 \|pages=223–234 \|doi=10.1145/1941553.1941585 \|title=Wait-free queues with multiple enqueuers and dequeuers\|url=http://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf}}</ref> presented a wait-free queue building on the [[Compare-and-swap\|CAS]] primitive, generally available on common hardware. Their construction expanded the lock-free queue of Michael and Scott,<ref name=lf-queue>{{cite conference \|last1=Michael \|first1=Maged \|last2=Scott \|first2=Michael \|conference=Proc. 15th Annual ACM Symp. on Principles of Distributed Computing (PODC) \|year=1996 \|isbn=0-89791-800-2 \|pages=267–275 \|doi=10.1145/248052.248106 \|title=Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms\|doi-access=free }}</ref> which is an efficient queue often used in practice. A follow-up paper by Kogan and Petrank<ref name=wf-fpsp>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2012 \|isbn=978-1-4503-1160-1 \|pages=141–150 \|doi=10.1145/2145816.2145835 \|title=A method for creating fast wait-free data structures}}</ref> provided a method for making wait-free algorithms fast and used this method to make the wait-free queue practically as fast as its lock-free counterpart. A subsequent paper by Timnat and Petrank<ref name=wf-simulation>{{cite conference \|last1=Timnat \|first1=Shahar \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2014 \| isbn=978-1-4503-2656-8 \| pages = 357–368 \| doi=10.1145/2692916.2555261 \| title= A Practical Wait-Free Simulation for Lock-Free Data Structures}}</ref> provided an automatic mechanism for generating wait-free data structures from lock-free ones. Thus, wait-free implementations are now available for many data-structures.

	Under reasonable assumptions, Alistarh, Censor-Hillel, and Shavit showed that lock-free algorithms are practically wait-free.<ref name=lf-wf>{{cite conference \|last1=Alistarh \|first1=Dan \|last2=Censor-Hillel \|first2=Keren \|last3=Shavit \|first3=Nir \|conference=Proc. 46th Annual ACM Symposium on Theory of Computing (STOC’14) \| year=2014 \| isbn=978-1-4503-2710-7 \| pages = ~~714-723~~ \| doi=10.1145/2591796.2591836 \| title=Are Lock-Free Concurrent Algorithms Practically Wait-Free?\|arxiv=1311.3200 }}</ref> So the added algorithmic complexity of a wait-free algorithm might not be worth the effort, if there are not hard deadlines to be met.		Under reasonable assumptions, Alistarh, Censor-Hillel, and Shavit showed that lock-free algorithms are practically wait-free.<ref name=lf-wf>{{cite conference \|last1=Alistarh \|first1=Dan \|last2=Censor-Hillel \|first2=Keren \|last3=Shavit \|first3=Nir \|conference=Proc. 46th Annual ACM Symposium on Theory of Computing (STOC’14) \| year=2014 \| isbn=978-1-4503-2710-7 \| pages = 714–723 \| doi=10.1145/2591796.2591836 \| title=Are Lock-Free Concurrent Algorithms Practically Wait-Free?\|arxiv=1311.3200 }}</ref> So the added algorithmic complexity of a wait-free algorithm might not be worth the effort, if there are not hard deadlines to be met.

	== Lock-freedom ==		== Lock-freedom ==

Onel5969: Disambiguating links to Deadlock (link changed to Deadlock (computer science); link changed to Deadlock (computer science)) using DisamAssist.

2024-08-20T21:18:39Z

Disambiguating links to Deadlock (link changed to Deadlock (computer science); link changed to Deadlock (computer science)) using DisamAssist.

← Previous revision		Revision as of 21:18, 20 August 2024
Line 13:		Line 13:
	Blocking a thread can be undesirable for many reasons. An obvious reason is that while the thread is blocked, it cannot accomplish anything: if the blocked thread had been performing a high-priority or [[real-time computing\|real-time]] task, it would be highly undesirable to halt its progress.		Blocking a thread can be undesirable for many reasons. An obvious reason is that while the thread is blocked, it cannot accomplish anything: if the blocked thread had been performing a high-priority or [[real-time computing\|real-time]] task, it would be highly undesirable to halt its progress.

	Other problems are less obvious. For example, certain interactions between locks can lead to error conditions such as [[deadlock]], [[livelock]], and [[priority inversion]]. Using locks also involves a trade-off between coarse-grained locking, which can significantly reduce opportunities for [[parallel computing\|parallelism]], and fine-grained locking, which requires more careful design, increases locking overhead and is more prone to bugs.		Other problems are less obvious. For example, certain interactions between locks can lead to error conditions such as [[Deadlock (computer science)\|deadlock]], [[livelock]], and [[priority inversion]]. Using locks also involves a trade-off between coarse-grained locking, which can significantly reduce opportunities for [[parallel computing\|parallelism]], and fine-grained locking, which requires more careful design, increases locking overhead and is more prone to bugs.

	Unlike blocking algorithms, non-blocking algorithms do not suffer from these downsides, and in addition are safe for use in [[interrupt handler]]s: even though the [[Pre-emptive multitasking\|preempted]] thread cannot be resumed, progress is still possible without it. In contrast, global data structures protected by mutual exclusion cannot safely be accessed in an interrupt handler, as the preempted thread may be the one holding the lock. While this can be rectified by masking interrupt requests during the critical section, this requires the code in the critical section to have bounded (and preferably short) running time, or excessive interrupt latency may be observed.<ref name="monit">{{cite journal \| doi = 10.1145/358818.358824 \| url = http://research.microsoft.com/lampson/23-ProcessesInMesa/Abstract.html \| title = Experience with Processes and Monitors in Mesa \| author = Butler W. Lampson \| author-link = Butler W. Lampson \|author2=David D. Redell \|author2-link=David D. Redell \| journal = Communications of the ACM \| volume = 23 \| issue = 2 \| pages = 105–117 \|date=February 1980\| citeseerx = 10.1.1.142.5765 \| s2cid = 1594544 }}</ref>		Unlike blocking algorithms, non-blocking algorithms do not suffer from these downsides, and in addition are safe for use in [[interrupt handler]]s: even though the [[Pre-emptive multitasking\|preempted]] thread cannot be resumed, progress is still possible without it. In contrast, global data structures protected by mutual exclusion cannot safely be accessed in an interrupt handler, as the preempted thread may be the one holding the lock. While this can be rectified by masking interrupt requests during the critical section, this requires the code in the critical section to have bounded (and preferably short) running time, or excessive interrupt latency may be observed.<ref name="monit">{{cite journal \| doi = 10.1145/358818.358824 \| url = http://research.microsoft.com/lampson/23-ProcessesInMesa/Abstract.html \| title = Experience with Processes and Monitors in Mesa \| author = Butler W. Lampson \| author-link = Butler W. Lampson \|author2=David D. Redell \|author2-link=David D. Redell \| journal = Communications of the ACM \| volume = 23 \| issue = 2 \| pages = 105–117 \|date=February 1980\| citeseerx = 10.1.1.142.5765 \| s2cid = 1594544 }}</ref>
Line 102:		Line 102:

	== See also ==		== See also ==
	* [[Deadlock]]		* [[Deadlock (computer science)\|Deadlock]]
	* [[Java ConcurrentMap#Lock-free atomicity]]		* [[Java ConcurrentMap#Lock-free atomicity]]
	* [[Liveness]]		* [[Liveness]]

193.165.236.120: /* Motivation */

2024-07-12T17:56:36Z

Motivation

← Previous revision		Revision as of 17:56, 12 July 2024
Line 15:		Line 15:
	Other problems are less obvious. For example, certain interactions between locks can lead to error conditions such as [[deadlock]], [[livelock]], and [[priority inversion]]. Using locks also involves a trade-off between coarse-grained locking, which can significantly reduce opportunities for [[parallel computing\|parallelism]], and fine-grained locking, which requires more careful design, increases locking overhead and is more prone to bugs.		Other problems are less obvious. For example, certain interactions between locks can lead to error conditions such as [[deadlock]], [[livelock]], and [[priority inversion]]. Using locks also involves a trade-off between coarse-grained locking, which can significantly reduce opportunities for [[parallel computing\|parallelism]], and fine-grained locking, which requires more careful design, increases locking overhead and is more prone to bugs.

	Unlike blocking algorithms, non-blocking algorithms do not suffer from these downsides, and in addition are safe for use in [[interrupt handler]]s: even though the [[Pre-emptive multitasking\|preempted]] thread cannot be resumed, progress is still possible without it. In contrast, global data structures protected by mutual exclusion cannot safely be accessed in an interrupt handler, as the preempted thread may be the one holding the ~~lock—but~~ this can be rectified ~~easily~~ by masking ~~the~~ interrupt ~~request~~ during the critical section.<ref name="monit">{{cite journal \| doi = 10.1145/358818.358824 \| url = http://research.microsoft.com/lampson/23-ProcessesInMesa/Abstract.html \| title = Experience with Processes and Monitors in Mesa \| author = Butler W. Lampson \| author-link = Butler W. Lampson \|author2=David D. Redell \|author2-link=David D. Redell \| journal = Communications of the ACM \| volume = 23 \| issue = 2 \| pages = 105–117 \|date=February 1980\| citeseerx = 10.1.1.142.5765 \| s2cid = 1594544 }}</ref>		Unlike blocking algorithms, non-blocking algorithms do not suffer from these downsides, and in addition are safe for use in [[interrupt handler]]s: even though the [[Pre-emptive multitasking\|preempted]] thread cannot be resumed, progress is still possible without it. In contrast, global data structures protected by mutual exclusion cannot safely be accessed in an interrupt handler, as the preempted thread may be the one holding the lock. While this can be rectified by masking interrupt requests during the critical section, this requires the code in the critical section to have bounded (and preferably short) running time, or excessive interrupt latency may be observed.<ref name="monit">{{cite journal \| doi = 10.1145/358818.358824 \| url = http://research.microsoft.com/lampson/23-ProcessesInMesa/Abstract.html \| title = Experience with Processes and Monitors in Mesa \| author = Butler W. Lampson \| author-link = Butler W. Lampson \|author2=David D. Redell \|author2-link=David D. Redell \| journal = Communications of the ACM \| volume = 23 \| issue = 2 \| pages = 105–117 \|date=February 1980\| citeseerx = 10.1.1.142.5765 \| s2cid = 1594544 }}</ref>

	A lock-free data structure can be used to improve performance.		A lock-free data structure can be used to improve performance.

WikiCleanerBot: v2.05b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation)

2024-06-19T06:26:11Z

v2.05b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation)

← Previous revision		Revision as of 06:26, 19 June 2024
Line 77:		Line 77:
	Wait-free algorithms were rare until 2011, both in research and in practice. However, in 2011 Kogan and [[Erez Petrank\|Petrank]]<ref name=wf-queue>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 16th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2011 \|isbn=978-1-4503-0119-0 \|pages=223–234 \|doi=10.1145/1941553.1941585 \|title=Wait-free queues with multiple enqueuers and dequeuers\|url=http://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf}}</ref> presented a wait-free queue building on the [[Compare-and-swap\|CAS]] primitive, generally available on common hardware. Their construction expanded the lock-free queue of Michael and Scott,<ref name=lf-queue>{{cite conference \|last1=Michael \|first1=Maged \|last2=Scott \|first2=Michael \|conference=Proc. 15th Annual ACM Symp. on Principles of Distributed Computing (PODC) \|year=1996 \|isbn=0-89791-800-2 \|pages=267–275 \|doi=10.1145/248052.248106 \|title=Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms\|doi-access=free }}</ref> which is an efficient queue often used in practice. A follow-up paper by Kogan and Petrank<ref name=wf-fpsp>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2012 \|isbn=978-1-4503-1160-1 \|pages=141–150 \|doi=10.1145/2145816.2145835 \|title=A method for creating fast wait-free data structures}}</ref> provided a method for making wait-free algorithms fast and used this method to make the wait-free queue practically as fast as its lock-free counterpart. A subsequent paper by Timnat and Petrank<ref name=wf-simulation>{{cite conference \|last1=Timnat \|first1=Shahar \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2014 \| isbn=978-1-4503-2656-8 \| pages = 357–368 \| doi=10.1145/2692916.2555261 \| title= A Practical Wait-Free Simulation for Lock-Free Data Structures}}</ref> provided an automatic mechanism for generating wait-free data structures from lock-free ones. Thus, wait-free implementations are now available for many data-structures.		Wait-free algorithms were rare until 2011, both in research and in practice. However, in 2011 Kogan and [[Erez Petrank\|Petrank]]<ref name=wf-queue>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 16th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2011 \|isbn=978-1-4503-0119-0 \|pages=223–234 \|doi=10.1145/1941553.1941585 \|title=Wait-free queues with multiple enqueuers and dequeuers\|url=http://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf}}</ref> presented a wait-free queue building on the [[Compare-and-swap\|CAS]] primitive, generally available on common hardware. Their construction expanded the lock-free queue of Michael and Scott,<ref name=lf-queue>{{cite conference \|last1=Michael \|first1=Maged \|last2=Scott \|first2=Michael \|conference=Proc. 15th Annual ACM Symp. on Principles of Distributed Computing (PODC) \|year=1996 \|isbn=0-89791-800-2 \|pages=267–275 \|doi=10.1145/248052.248106 \|title=Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms\|doi-access=free }}</ref> which is an efficient queue often used in practice. A follow-up paper by Kogan and Petrank<ref name=wf-fpsp>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2012 \|isbn=978-1-4503-1160-1 \|pages=141–150 \|doi=10.1145/2145816.2145835 \|title=A method for creating fast wait-free data structures}}</ref> provided a method for making wait-free algorithms fast and used this method to make the wait-free queue practically as fast as its lock-free counterpart. A subsequent paper by Timnat and Petrank<ref name=wf-simulation>{{cite conference \|last1=Timnat \|first1=Shahar \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2014 \| isbn=978-1-4503-2656-8 \| pages = 357–368 \| doi=10.1145/2692916.2555261 \| title= A Practical Wait-Free Simulation for Lock-Free Data Structures}}</ref> provided an automatic mechanism for generating wait-free data structures from lock-free ones. Thus, wait-free implementations are now available for many data-structures.

	Under reasonable assumptions, Alistarh, Censor-Hillel, and Shavit showed that lock-free algorithms are practically wait-free<ref name=lf-wf>{{cite conference \|last1=Alistarh \|first1=Dan \|last2=Censor-Hillel \|first2=Keren \|last3=Shavit \|first3=Nir \|conference=Proc. 46th Annual ACM Symposium on Theory of Computing (STOC’14) \| year=2014 \| isbn=978-1-4503-2710-7 \| pages = 714-723 \| doi=10.1145/2591796.2591836 \| title=Are Lock-Free Concurrent Algorithms Practically Wait-Free?\|arxiv=1311.3200 }}</ref>. So the added algorithmic complexity of a wait-free algorithm might not be worth the effort, if there are not hard deadlines to be met.		Under reasonable assumptions, Alistarh, Censor-Hillel, and Shavit showed that lock-free algorithms are practically wait-free.<ref name=lf-wf>{{cite conference \|last1=Alistarh \|first1=Dan \|last2=Censor-Hillel \|first2=Keren \|last3=Shavit \|first3=Nir \|conference=Proc. 46th Annual ACM Symposium on Theory of Computing (STOC’14) \| year=2014 \| isbn=978-1-4503-2710-7 \| pages = 714-723 \| doi=10.1145/2591796.2591836 \| title=Are Lock-Free Concurrent Algorithms Practically Wait-Free?\|arxiv=1311.3200 }}</ref> So the added algorithmic complexity of a wait-free algorithm might not be worth the effort, if there are not hard deadlines to be met.

	== Lock-freedom ==		== Lock-freedom ==

OAbot: Open access bot: arxiv updated in citation with #oabot.

2024-06-10T05:53:53Z

Open access bot: arxiv updated in citation with #oabot.

← Previous revision		Revision as of 05:53, 10 June 2024
Line 77:		Line 77:
	Wait-free algorithms were rare until 2011, both in research and in practice. However, in 2011 Kogan and [[Erez Petrank\|Petrank]]<ref name=wf-queue>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 16th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2011 \|isbn=978-1-4503-0119-0 \|pages=223–234 \|doi=10.1145/1941553.1941585 \|title=Wait-free queues with multiple enqueuers and dequeuers\|url=http://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf}}</ref> presented a wait-free queue building on the [[Compare-and-swap\|CAS]] primitive, generally available on common hardware. Their construction expanded the lock-free queue of Michael and Scott,<ref name=lf-queue>{{cite conference \|last1=Michael \|first1=Maged \|last2=Scott \|first2=Michael \|conference=Proc. 15th Annual ACM Symp. on Principles of Distributed Computing (PODC) \|year=1996 \|isbn=0-89791-800-2 \|pages=267–275 \|doi=10.1145/248052.248106 \|title=Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms\|doi-access=free }}</ref> which is an efficient queue often used in practice. A follow-up paper by Kogan and Petrank<ref name=wf-fpsp>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2012 \|isbn=978-1-4503-1160-1 \|pages=141–150 \|doi=10.1145/2145816.2145835 \|title=A method for creating fast wait-free data structures}}</ref> provided a method for making wait-free algorithms fast and used this method to make the wait-free queue practically as fast as its lock-free counterpart. A subsequent paper by Timnat and Petrank<ref name=wf-simulation>{{cite conference \|last1=Timnat \|first1=Shahar \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2014 \| isbn=978-1-4503-2656-8 \| pages = 357–368 \| doi=10.1145/2692916.2555261 \| title= A Practical Wait-Free Simulation for Lock-Free Data Structures}}</ref> provided an automatic mechanism for generating wait-free data structures from lock-free ones. Thus, wait-free implementations are now available for many data-structures.		Wait-free algorithms were rare until 2011, both in research and in practice. However, in 2011 Kogan and [[Erez Petrank\|Petrank]]<ref name=wf-queue>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 16th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2011 \|isbn=978-1-4503-0119-0 \|pages=223–234 \|doi=10.1145/1941553.1941585 \|title=Wait-free queues with multiple enqueuers and dequeuers\|url=http://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf}}</ref> presented a wait-free queue building on the [[Compare-and-swap\|CAS]] primitive, generally available on common hardware. Their construction expanded the lock-free queue of Michael and Scott,<ref name=lf-queue>{{cite conference \|last1=Michael \|first1=Maged \|last2=Scott \|first2=Michael \|conference=Proc. 15th Annual ACM Symp. on Principles of Distributed Computing (PODC) \|year=1996 \|isbn=0-89791-800-2 \|pages=267–275 \|doi=10.1145/248052.248106 \|title=Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms\|doi-access=free }}</ref> which is an efficient queue often used in practice. A follow-up paper by Kogan and Petrank<ref name=wf-fpsp>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2012 \|isbn=978-1-4503-1160-1 \|pages=141–150 \|doi=10.1145/2145816.2145835 \|title=A method for creating fast wait-free data structures}}</ref> provided a method for making wait-free algorithms fast and used this method to make the wait-free queue practically as fast as its lock-free counterpart. A subsequent paper by Timnat and Petrank<ref name=wf-simulation>{{cite conference \|last1=Timnat \|first1=Shahar \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2014 \| isbn=978-1-4503-2656-8 \| pages = 357–368 \| doi=10.1145/2692916.2555261 \| title= A Practical Wait-Free Simulation for Lock-Free Data Structures}}</ref> provided an automatic mechanism for generating wait-free data structures from lock-free ones. Thus, wait-free implementations are now available for many data-structures.

	Under reasonable assumptions, Alistarh, Censor-Hillel, and Shavit showed that lock-free algorithms are practically wait-free<ref name=lf-wf>{{cite conference \|last1=Alistarh \|first1=Dan \|last2=Censor-Hillel \|first2=Keren \|last3=Shavit \|first3=Nir \|conference=Proc. 46th Annual ACM Symposium on Theory of Computing (STOC’14) \| year=2014 \| isbn=978-1-4503-2710-7 \| pages = 714-723 \| doi=10.1145/2591796.2591836 \| title=Are Lock-Free Concurrent Algorithms Practically Wait-Free?}}</ref>. So the added algorithmic complexity of a wait-free algorithm might not be worth the effort, if there are not hard deadlines to be met.		Under reasonable assumptions, Alistarh, Censor-Hillel, and Shavit showed that lock-free algorithms are practically wait-free<ref name=lf-wf>{{cite conference \|last1=Alistarh \|first1=Dan \|last2=Censor-Hillel \|first2=Keren \|last3=Shavit \|first3=Nir \|conference=Proc. 46th Annual ACM Symposium on Theory of Computing (STOC’14) \| year=2014 \| isbn=978-1-4503-2710-7 \| pages = 714-723 \| doi=10.1145/2591796.2591836 \| title=Are Lock-Free Concurrent Algorithms Practically Wait-Free?\|arxiv=1311.3200 }}</ref>. So the added algorithmic complexity of a wait-free algorithm might not be worth the effort, if there are not hard deadlines to be met.

	== Lock-freedom ==		== Lock-freedom ==

Sttaft: /* Wait-freedom */ Include reference to paper by Alistarh, Censor-Hillel, and Shavit that showed that under reasonable assumptions, lock-free algorithms are wait free.

2024-06-03T22:38:40Z

Wait-freedom: Include reference to paper by Alistarh, Censor-Hillel, and Shavit that showed that under reasonable assumptions, lock-free algorithms are wait free.

← Previous revision		Revision as of 22:38, 3 June 2024
Line 76:		Line 76:

	Wait-free algorithms were rare until 2011, both in research and in practice. However, in 2011 Kogan and [[Erez Petrank\|Petrank]]<ref name=wf-queue>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 16th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2011 \|isbn=978-1-4503-0119-0 \|pages=223–234 \|doi=10.1145/1941553.1941585 \|title=Wait-free queues with multiple enqueuers and dequeuers\|url=http://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf}}</ref> presented a wait-free queue building on the [[Compare-and-swap\|CAS]] primitive, generally available on common hardware. Their construction expanded the lock-free queue of Michael and Scott,<ref name=lf-queue>{{cite conference \|last1=Michael \|first1=Maged \|last2=Scott \|first2=Michael \|conference=Proc. 15th Annual ACM Symp. on Principles of Distributed Computing (PODC) \|year=1996 \|isbn=0-89791-800-2 \|pages=267–275 \|doi=10.1145/248052.248106 \|title=Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms\|doi-access=free }}</ref> which is an efficient queue often used in practice. A follow-up paper by Kogan and Petrank<ref name=wf-fpsp>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2012 \|isbn=978-1-4503-1160-1 \|pages=141–150 \|doi=10.1145/2145816.2145835 \|title=A method for creating fast wait-free data structures}}</ref> provided a method for making wait-free algorithms fast and used this method to make the wait-free queue practically as fast as its lock-free counterpart. A subsequent paper by Timnat and Petrank<ref name=wf-simulation>{{cite conference \|last1=Timnat \|first1=Shahar \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2014 \| isbn=978-1-4503-2656-8 \| pages = 357–368 \| doi=10.1145/2692916.2555261 \| title= A Practical Wait-Free Simulation for Lock-Free Data Structures}}</ref> provided an automatic mechanism for generating wait-free data structures from lock-free ones. Thus, wait-free implementations are now available for many data-structures.		Wait-free algorithms were rare until 2011, both in research and in practice. However, in 2011 Kogan and [[Erez Petrank\|Petrank]]<ref name=wf-queue>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 16th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2011 \|isbn=978-1-4503-0119-0 \|pages=223–234 \|doi=10.1145/1941553.1941585 \|title=Wait-free queues with multiple enqueuers and dequeuers\|url=http://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf}}</ref> presented a wait-free queue building on the [[Compare-and-swap\|CAS]] primitive, generally available on common hardware. Their construction expanded the lock-free queue of Michael and Scott,<ref name=lf-queue>{{cite conference \|last1=Michael \|first1=Maged \|last2=Scott \|first2=Michael \|conference=Proc. 15th Annual ACM Symp. on Principles of Distributed Computing (PODC) \|year=1996 \|isbn=0-89791-800-2 \|pages=267–275 \|doi=10.1145/248052.248106 \|title=Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms\|doi-access=free }}</ref> which is an efficient queue often used in practice. A follow-up paper by Kogan and Petrank<ref name=wf-fpsp>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2012 \|isbn=978-1-4503-1160-1 \|pages=141–150 \|doi=10.1145/2145816.2145835 \|title=A method for creating fast wait-free data structures}}</ref> provided a method for making wait-free algorithms fast and used this method to make the wait-free queue practically as fast as its lock-free counterpart. A subsequent paper by Timnat and Petrank<ref name=wf-simulation>{{cite conference \|last1=Timnat \|first1=Shahar \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2014 \| isbn=978-1-4503-2656-8 \| pages = 357–368 \| doi=10.1145/2692916.2555261 \| title= A Practical Wait-Free Simulation for Lock-Free Data Structures}}</ref> provided an automatic mechanism for generating wait-free data structures from lock-free ones. Thus, wait-free implementations are now available for many data-structures.

			Under reasonable assumptions, Alistarh, Censor-Hillel, and Shavit showed that lock-free algorithms are practically wait-free<ref name=lf-wf>{{cite conference \|last1=Alistarh \|first1=Dan \|last2=Censor-Hillel \|first2=Keren \|last3=Shavit \|first3=Nir \|conference=Proc. 46th Annual ACM Symposium on Theory of Computing (STOC’14) \| year=2014 \| isbn=978-1-4503-2710-7 \| pages = 714-723 \| doi=10.1145/2591796.2591836 \| title=Are Lock-Free Concurrent Algorithms Practically Wait-Free?}}</ref>. So the added algorithmic complexity of a wait-free algorithm might not be worth the effort, if there are not hard deadlines to be met.

	== Lock-freedom ==		== Lock-freedom ==

Sbmeirow: Reverted edit by 166.181.248.60 (talk) to last version by Tea2min

2024-02-12T01:32:12Z

Reverted edit by 166.181.248.60 (talk) to last version by Tea2min

← Previous revision		Revision as of 01:32, 12 February 2024
Line 5:		Line 5:

	The word "non-blocking" was traditionally used to describe [[telecommunications network]]s that could route a connection through a set of relays "without having to re-arrange existing calls" (see [[Clos network]]). Also, if the telephone exchange "is not defective, it can always make the connection" (see [[nonblocking minimal spanning switch]]).		The word "non-blocking" was traditionally used to describe [[telecommunications network]]s that could route a connection through a set of relays "without having to re-arrange existing calls" (see [[Clos network]]). Also, if the telephone exchange "is not defective, it can always make the connection" (see [[nonblocking minimal spanning switch]]).

	Note:edited in 2024 w/no lock

	== Motivation ==		== Motivation ==

← Previous revision		Revision as of 17:35, 31 October 2024
Line 73:		Line 73:
	Several papers have investigated the difficulty of creating wait-free algorithms. For example, it has been shown<ref name=cond-sync>{{cite conference \|last1=Fich \|first1=Faith\|author1-link=Faith Ellen \|last2=Hendler \|first2=Danny \|last3=Shavit \|first3=Nir \|conference=Proc. 23rd Annual ACM Symp.on Principles of Distributed Computing (PODC) \|year=2004 \|isbn=1-58113-802-4 \|pages=80–87 \|doi=10.1145/1011767.1011780 \|title=On the inherent weakness of conditional synchronization primitives}}</ref> that the widely available atomic ''conditional'' primitives, [[Compare-and-swap\|CAS]] and [[Load-link/store-conditional\|LL/SC]], cannot provide starvation-free implementations of many common data structures without memory costs growing linearly in the number of threads.		Several papers have investigated the difficulty of creating wait-free algorithms. For example, it has been shown<ref name=cond-sync>{{cite conference \|last1=Fich \|first1=Faith\|author1-link=Faith Ellen \|last2=Hendler \|first2=Danny \|last3=Shavit \|first3=Nir \|conference=Proc. 23rd Annual ACM Symp.on Principles of Distributed Computing (PODC) \|year=2004 \|isbn=1-58113-802-4 \|pages=80–87 \|doi=10.1145/1011767.1011780 \|title=On the inherent weakness of conditional synchronization primitives}}</ref> that the widely available atomic ''conditional'' primitives, [[Compare-and-swap\|CAS]] and [[Load-link/store-conditional\|LL/SC]], cannot provide starvation-free implementations of many common data structures without memory costs growing linearly in the number of threads.

	~~But in practice~~ these lower bounds do not present a real barrier as spending a cache line or exclusive reservation granule (up to 2 KB on ARM) of store per thread in the shared memory is not considered too costly for practical systems ~~(typically~~ the amount of store logically required is a word, but physically CAS operations on the same cache line will collide, and LL/SC operations in the same exclusive reservation granule will collide, so the amount of store physically required{{citation needed\|date=June 2014}} is greater).		However, these lower bounds do not present a real barrier in practice, as spending a cache line or exclusive reservation granule (up to 2 KB on ARM) of store per thread in the shared memory is not considered too costly for practical systems. Typically, the amount of store logically required is a word, but physically CAS operations on the same cache line will collide, and LL/SC operations in the same exclusive reservation granule will collide, so the amount of store physically required{{citation needed\|date=June 2014}} is greater.{{Clarification needed\|date=October 2024\|reason=Does this imply that there actually is a barrier in practice?}}

	Wait-free algorithms were rare until 2011, both in research and in practice. However, in 2011 Kogan and [[Erez Petrank\|Petrank]]<ref name=wf-queue>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 16th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2011 \|isbn=978-1-4503-0119-0 \|pages=223–234 \|doi=10.1145/1941553.1941585 \|title=Wait-free queues with multiple enqueuers and dequeuers\|url=http://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf}}</ref> presented a wait-free queue building on the [[Compare-and-swap\|CAS]] primitive, generally available on common hardware. Their construction expanded the lock-free queue of Michael and Scott,<ref name=lf-queue>{{cite conference \|last1=Michael \|first1=Maged \|last2=Scott \|first2=Michael \|conference=Proc. 15th Annual ACM Symp. on Principles of Distributed Computing (PODC) \|year=1996 \|isbn=0-89791-800-2 \|pages=267–275 \|doi=10.1145/248052.248106 \|title=Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms\|doi-access=free }}</ref> which is an efficient queue often used in practice. A follow-up paper by Kogan and Petrank<ref name=wf-fpsp>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2012 \|isbn=978-1-4503-1160-1 \|pages=141–150 \|doi=10.1145/2145816.2145835 \|title=A method for creating fast wait-free data structures}}</ref> provided a method for making wait-free algorithms fast and used this method to make the wait-free queue practically as fast as its lock-free counterpart. A subsequent paper by Timnat and Petrank<ref name=wf-simulation>{{cite conference \|last1=Timnat \|first1=Shahar \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2014 \| isbn=978-1-4503-2656-8 \| pages = 357–368 \| doi=10.1145/2692916.2555261 \| title= A Practical Wait-Free Simulation for Lock-Free Data Structures}}</ref> provided an automatic mechanism for generating wait-free data structures from lock-free ones. Thus, wait-free implementations are now available for many data-structures.		Wait-free algorithms were rare until 2011, both in research and in practice. However, in 2011 Kogan and [[Erez Petrank\|Petrank]]<ref name=wf-queue>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 16th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2011 \|isbn=978-1-4503-0119-0 \|pages=223–234 \|doi=10.1145/1941553.1941585 \|title=Wait-free queues with multiple enqueuers and dequeuers\|url=http://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf}}</ref> presented a wait-free queue building on the [[Compare-and-swap\|CAS]] primitive, generally available on common hardware. Their construction expanded the lock-free queue of Michael and Scott,<ref name=lf-queue>{{cite conference \|last1=Michael \|first1=Maged \|last2=Scott \|first2=Michael \|conference=Proc. 15th Annual ACM Symp. on Principles of Distributed Computing (PODC) \|year=1996 \|isbn=0-89791-800-2 \|pages=267–275 \|doi=10.1145/248052.248106 \|title=Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms\|doi-access=free }}</ref> which is an efficient queue often used in practice. A follow-up paper by Kogan and Petrank<ref name=wf-fpsp>{{cite conference \|last1=Kogan \|first1=Alex \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2012 \|isbn=978-1-4503-1160-1 \|pages=141–150 \|doi=10.1145/2145816.2145835 \|title=A method for creating fast wait-free data structures}}</ref> provided a method for making wait-free algorithms fast and used this method to make the wait-free queue practically as fast as its lock-free counterpart. A subsequent paper by Timnat and Petrank<ref name=wf-simulation>{{cite conference \|last1=Timnat \|first1=Shahar \|last2=Petrank \|first2=Erez \|conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) \|year=2014 \| isbn=978-1-4503-2656-8 \| pages = 357–368 \| doi=10.1145/2692916.2555261 \| title= A Practical Wait-Free Simulation for Lock-Free Data Structures}}</ref> provided an automatic mechanism for generating wait-free data structures from lock-free ones. Thus, wait-free implementations are now available for many data-structures.