Non-blocking algorithm: Difference between revisions

Revision as of 14:42, 30 April 2006

Revision as of 10:51, 23 May 2006

Line 1:

In [[computer science]], '''non-blocking synchronization''' ensures that [[thread (software engineering)|thread]]s competing for a shared [[resource (computer science)|resource]] do not have their [[execution (computers)|execution]] indefinitely postponed by [[mutual exclusion]]. Literature up to the turn of the century used "non-blocking" synonymously with ''lock-free'': an algorithm thatwith wasguaranteed freesystem-wide from [[deadlock]] and [[livelock]]progress. However, since 2003 {{ref|obs-free}}, the term has been weakened to deny only deadlockprevent progress-blocking interactions with a [[Computer multitasking|preemptive scheduler]].

In modern usage, therefore, an algorithm is ''non-blocking'' if the suspension of one or more threads will not stop the potential progress of the remaining threads.

Line 24:

== Wait-freedom ==

Wait-freedom is the strongest non-blocking guarantee of progress, combining livelockguaranteed system-freedomwide 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 [[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.

Line 30:

== Lock-freedom ==

Lock-freedom allows individual threads to starve but deniesguarantees livelocksystem-wide throughput. An algorithm is lock-free if every step taken achieves global progress (for some sensible definition of progress). All wait-free algorithms are lock-free.

In general, a lock-free algorithm can run in four phases: completing one's own operation, assisting an obstructing operation, aborting an obstructing operation, and waiting. Completing one's own operation is complicated by the possibility of concurrent assistance and abortion, but is invariably the fastest path to completion.

Line 40:

== Obstruction-freedom ==

Obstruction-freedom deniesis onlythe deadlockweakest non-blocking progress guarantee. An algorithm is obstruction-free if at any point, a single thread executed in isolation (i.e. with all obstructing threads suspended) for a bounded number of steps will complete its operation. All lock-free algorithms are obstruction-free.

Obstruction-freedom demands only that any partially-completed operation can be aborted and the changes made rolled back. Dropping concurrent assistance can often result in much simpler algorithms that are easier to validate. Preventing the system from continually [[livelock|live-locking]] is once again the task of a contention manager.

Recent research {{ref|polka}} has yielded a promising practical contention manager, whimsically named ''Polka'', combining [[exponential backoff]] with "priority accumulation". As an operation progresses, it gains "priority"; when an operation is obstructed by another with higher priority, it will back off, with backoff intervals increasing exponentially. Each backoff increases the operation's priority; only when its priority is greater than that of its obstructor will it abort it. Aborted operations retain their former priority, giving their next attempt a greater chance of success.