Non-blocking algorithm: Difference between revisions

Revision as of 19:14, 24 September 2006

Revision as of 22:03, 24 September 2006

Line 24:

== 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 interval on the number of steps it will take before completing.

It was shown in the 1980s 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 naive blocking designs. It has also been shown {{ref|cond-sync}} that the widely-available [[Linearizability|atomic]] ''conditional'' primitives, [[compare-and-swap]] and [[LL/SC]], cannot provide starvation-free implementations of many common data structures without memory costs growing linearly in the number of threads. Wait-free algorithms are therefore rare, both in research and in practice.