Non-blocking algorithm: Difference between revisions

Revision as of 13:40, 22 November 2005

Revision as of 18:56, 6 February 2006

Line 25:

Wait-freedom is the strongest non-blocking guarantee of progress, combining livelock-freedom with [[Resource starvation|starvation]]-freedom. An algorithm is wait-free if every operation has a bound on the number of steps it will take before completing.

It was shown in the 1980s that all algorithms can 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 [[Atomicity|atomic]] ''conditional'' primitives, [[compare-and-swap]] and [[Load-Linked/Store-Conditional|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.

== Lock-freedom ==