Non-blocking algorithm: Difference between revisions

Revision as of 10:51, 23 May 2006

Revision as of 11:31, 23 May 2006

Line 26:

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 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 [[AtomicityLinearizability|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 ==