Non-blocking algorithm: Difference between revisions

Revision as of 21:11, 31 December 2020

Revision as of 00:54, 17 January 2021

Line 33:

Additionally, some non-blocking data structures are weak enough to be implemented without special atomic primitives. These exceptions include:

* a single-reader single-writer [[Circular buffer|ring buffer]] [[FIFO (computing and electronics)|FIFO]], with a size which evenly divides the overflow of one of the available unsigned integer types, can unconditionally be [[Producer–consumer problem#Without semaphores or monitors|implemented safely]] using only a [[memory barrier]]

* [[Read-copy-update]] with a single writer and any number of readers. (The readers are wait-free; the writer is usually lock-free, until it needs to reclaim memory).

* [[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>