Non-blocking algorithm: Difference between revisions

Revision as of 18:48, 18 July 2018

Revision as of 23:36, 16 February 2019

Line 26:

== 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). Until recently, 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|last=Harris|first=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|last=Harris|first=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-94|pages=48–60|url=http://doi.acm.org/10.1145/1065944.1065952|chapter=Composable memory transactions|date=June 15–17, 2005|doi=10.1145/1065944.1065952}}</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.

Line 67:

But in practice these lower bounds do not present a real barrier as spending a cache line or exclusive reservation granule (up to 2&nbsp;KB on ARM) of store per thread in the shared memory is not considered too costly for practical systems (typically the amount of store logically required is a word, but physically CAS operations on the same cache line will collide, and LL/SC operations in the same exclusive reservation granule will collide, so the amount of store physically required{{citation needed|date=June 2014}} is greater).

Wait-free algorithms were rare until 2011, both in research and in practice. However, in 2011 Kogan and [[Erez Petrank|Petrank]]<ref name=wf-queue>{{cite conference |last1=Kogan |first1=Alex |last2=Petrank |first2=Erez |conference=Proc. 16th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) |year=2011 |isbn=978-1-4503-0119-0 |pages=223–234 |doi=10.1145/1941553.1941585 |title=Wait-free queues with multiple enqueuers and dequeuers}}</ref> presented a wait-free queue building on the [[Compare-and-swap|CAS]] primitive, generally available on common hardware. Their construction expanded the lock-free queue of Michael and Scott,<ref name=lf-queue>{{cite conference |last1=Michael |first1=Maged |last2=Scott |first2=Michael |conference=Proc. 15th Annual ACM Symp. on Principles of Distributed Computing (PODC) |year=1996 |isbn=0-89791-800-2 |pages=267–275 |doi=10.1145/248052.248106 |title=Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms}}</ref> which is an efficient queue often used in practice. A follow-up paper by Kogan and [[Erez Petrank|Petrank]]<ref name=wf-fpsp>{{cite conference |last1=Kogan |first1=Alex |last2=Petrank |first2=Erez |conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) |year=2012 |isbn=978-1-4503-1160-1 |pages=141–150 |doi=10.1145/2145816.2145835 |title=A method for creating fast wait-free data structures}}</ref> provided a method for making wait-free algorithms fast and used this method to make the wait-free queue practically as fast as its lock-free counterpart. A subsequent paper by Timnat and [[Erez Petrank|Petrank]]<ref name=wf-simulation>{{cite conference |last1=Timnat |first1=Shahar |last2=Petrank |first2=Erez |conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) |year=2014 | isbn=978-1-4503-2656-8 | pages = 357-368357–368 | doi=10.1145/2692916.2555261 | title= A Practical Wait-Free Simulation for Lock-Free Data Structures}}</ref> provided an automatic mechanism for generating wait-free data structures from lock-free ones. Thus, wait-free implementations are now available for many data-structures.

== Lock-freedom ==