Editing Non-blocking algorithm (section)

== Implementation ==
With few exceptions, non-blocking algorithms use [[Linearizability|atomic]] [[read-modify-write]] primitives that the hardware must provide, the most notable of which is [[Compare-and-swap|compare and swap (CAS)]]. [[Critical section]]s are almost always implemented using standard interfaces over these primitives (in the general case, critical sections will be blocking, even when implemented with these primitives). In the 1990s all non-blocking algorithms had to be written "natively" with the underlying primitives to achieve acceptable performance. However, the emerging field of [[software transactional memory]] promises standard abstractions for writing efficient non-blocking code.<ref name=lightweight-transactions>{{cite journal|last1=Harris|first1=Tim|last2=Fraser|first2=Keir|title=Language support for lightweight transactions|journal=ACM SIGPLAN Notices|date=26 November 2003|volume=38|issue=11|pages=388|doi=10.1145/949343.949340|url=http://research.microsoft.com/en-us/um/people/tharris/papers/2003-oopsla.pdf|citeseerx=10.1.1.58.8466}}</ref><ref name=composable-memory-transactions>{{cite book|last1=Harris|first1=Tim|last2=Marlow|first2=S.|last3=Peyton-Jones|first3=S.|last4=Herlihy|first4=M.|title=Proceedings of the 2005 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '05 : Chicago, Illinois|publisher=ACM Press|location=New York, NY|isbn=978-1-59593-080-4|pages=48–60|chapter=Composable memory transactions|date=June 15–17, 2005|doi=10.1145/1065944.1065952|s2cid=53245159 }}</ref>

Much research has also been done in providing basic [[data structure]]s such as [[stack (data structure)|stacks]], [[Queue (data structure)|queues]], [[Set (computer science)|sets]], and [[hash table]]s.  These allow programs to easily exchange data between threads asynchronously.

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>
 [http://libcds.sourceforge.net/ libcds] - C++ library of lock-free containers and safe memory reclamation schema
</ref><ref>
 [https://www.liblfds.org/ liblfds] - A library of lock-free data structures, written in C
</ref><ref>
 [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 name="A_FALSE_SENSE_OF_SECURITY">Herb Sutter. {{cite web | url=http://www.drdobbs.com/article/print?articleId=210600279&siteSectionName=cpp | title=Lock-Free Code: A False Sense of Security | archive-url=https://web.archive.org/web/20150901211737/http://www.drdobbs.com/article/print?articleId=210600279&siteSectionName=cpp | archive-date=2015-09-01 |url-status=dead}}</ref><ref name="A_CORRECTED_QUEUE">Herb Sutter. {{cite web | archive-url=https://web.archive.org/web/20081205072023/http://www.ddj.com/cpp/210604448 | title=Writing Lock-Free Code: A Corrected Queue | archive-date=2008-12-05 | url-status=dead | url=http://www.ddj.com/cpp/210604448 }}</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"].
</ref>

Non-blocking algorithms generally involve a series of read, read-modify-write, and write instructions in a carefully designed order.
Optimizing compilers can aggressively re-arrange operations.
Even when they don't, many modern CPUs often re-arrange such operations (they have a "weak [[consistency model]]"),
unless a [[memory barrier]] is used to tell the CPU not to reorder.
[[C++11]] programmers can use <code>std::atomic</code> in <code>&lt;atomic&gt;</code>,
and [[C11 (C standard revision)|C11]] programmers can use <code>&lt;stdatomic.h&gt;</code>,
both of which supply types and functions that tell the compiler not to re-arrange such instructions, and to insert the appropriate memory barriers.<ref>
Bruce Dawson.
[https://randomascii.wordpress.com/2020/11/29/arm-and-lock-free-programming/ "ARM and Lock-Free Programming"].
</ref>