Non-blocking algorithm: Difference between revisions

Content deleted Content added
m "2005 Article", clicking on PPoPP I see full date.
add reference, etc.
Line 46:
 
== 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 This property is critical for real-time systems and is always nice to have as long as the performance cost is not too high.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}}</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.
Line 57 ⟶ 63:
 
== Lock-freedom ==
 
Lock-freedom allows individual threads to starve but guarantees system-wide throughput. An algorithm is lock-free if it satisfies that when the program threads are run sufficiently long at least one of the threads makes
progress (for some sensible definition of progress). All wait-free algorithms are lock-free.
 
An algorithm is lock free if every operation has a bound on the number of steps before one of the threads operating on a data structure completes its operation.<ref name="awilliams" />
 
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 67 ⟶ 76:
 
== Obstruction-freedom ==
Obstruction-freedom is possibly the weakest natural 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.<ref name="awilliams" /> 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 the task of a contention manager.