Non-blocking algorithm: Difference between revisions

Revision as of 20:12, 26 March 2006

Revision as of 06:06, 11 April 2006

Line 18:

== Implementation ==

Non-blocking algorithms use [[AtomicityAtomic operation|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|critical sections]] 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]], [[queue|queues]], [[set|sets]], and [[hash table|hash tables]]. These allow programs to easily exchange data between threads asynchronously.