Non-blocking algorithm: Difference between revisions

Revision as of 13:15, 5 February 2007

Revision as of 20:22, 17 February 2007

Line 19:

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)]]. Ultimately, all synchronizing algorithms must use these; however, [[critical section]]s are almost always implemented using standard interfaces over 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.

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

== Wait-freedom ==