Editing Non-blocking algorithm (section)

== Wait-freedom ==
Wait-freedom is the strongest non-blocking guarantee of progress, combining guaranteed system-wide throughput with [[Resource starvation|starvation]]-freedom. An algorithm is wait-free if every operation has a bound on the number of steps the algorithm will take before the operation completes.<ref name="awilliams">
Anthony Williams.
[https://www.justsoftwaresolutions.co.uk//files/safety_off.pdf "Safety: off: How not to shoot yourself in the foot with C++ atomics"].
2015.
p. 20.
</ref>
This property is critical for real-time systems and is always nice to have as long as the performance cost is not too high.

It was shown in the 1980s<ref name=imp>{{cite conference |last=Herlihy |first=Maurice P. |conference=Proc. 7th Annual ACM Symp. on Principles of Distributed Computing |isbn=0-89791-277-2 |pages=276–290 |doi=10.1145/62546.62593 |title=Impossibility and universality results for wait-free synchronization |year=1988|doi-access=free }}</ref> that all algorithms can be implemented wait-free, and many transformations from serial code, called ''universal constructions'', have been demonstrated. However, the resulting performance does not in general match even naïve blocking designs. Several papers have since improved the performance of universal constructions, but still, their performance is far below blocking designs.

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.

However, these lower bounds do not present a real barrier in practice, as spending a cache line or exclusive reservation granule (up to 2&nbsp;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.

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.