Non-blocking algorithm: Difference between revisions

Revision as of 02:39, 6 June 2014

Revision as of 23:14, 11 July 2014

Line 27:

* [[Read-copy-update]] with multiple writers and any number of readers. (The readers are wait-free; multiple writers generally serialize with a lock and are not obstruction-free).

Several libraries internally use lock-free techniques.,<ref>

[http://libcds.sourceforge.net/ libcds] http://www.liblfds.org/ - C++ library of lock-free containers and safe memory reclamation schema

Several libraries internally use lock-free techniques.<ref>

</ref><ref>

[http://libcds.sourceforge.net/ libcds] http://www.liblfds.org/ - C++ library of lock-free containers and safe memory reclamation schema

[http://concurrencykit.org Concurrency Kit] - A C library for non-blocking system design and implementation

But</ref> but it is difficult to write lock-free code that is correct.<ref>

Herb Sutter. [http://www.drdobbs.com/article/print?articleId=210600279&siteSectionName=cpp "Lock-Free Code: A False Sense of Security"].

</ref><ref>

Herb Sutter. [http://www.ddj.com/cpp/184401930 "Writing Lock-Free Code: A Corrected Queue"].

</ref><ref>

Herb Sutter. [http://www.ddj.com/cpp/211601363 "Writing a Generalized Concurrent Queue"].

</ref><ref>

Herb Sutter. [http://www.ddj.com/cpp/184401930 "The Trouble With Locks"].

[http://concurrencykit.org Concurrency Kit] - A C library for non-blocking system design and implementation

</ref>

But it is difficult to write lock-free code that is correct.<ref>

Herb Sutter.

[http://www.drdobbs.com/article/print?articleId=210600279&siteSectionName=cpp "Lock-Free Code: A False Sense of Security"].

Herb Sutter.

[http://www.ddj.com/cpp/184401930 "Writing Lock-Free Code: A Corrected Queue"].

Herb Sutter.

[http://www.ddj.com/cpp/211601363 "Writing a Generalized Concurrent Queue"].

Herb Sutter.

[http://www.ddj.com/cpp/184401930 "The Trouble With Locks"].

</ref>

== Wait-freedom ==

Line 68 ⟶ 64:

== 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. All lock-free algorithms are obstruction-free.