Content deleted Content added
m →Motivation: leave people out of this |
→Implementation: just using non-blocking primitives does not make critical sections non-blocking |
||
Line 30:
== 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}}</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|year=2005|publisher=ACM Press|___location=New York, NY|isbn=1-59593-080-9|pages=48–60|url=http://doi.acm.org/10.1145/1065944.1065952|chapter=Composable memory transactions|date=June 15–17, 2005}}</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.
| |||