Non-blocking algorithm: Difference between revisions

Revision as of 20:01, 10 March 2006

Revision as of 20:12, 26 March 2006

Line 20:

Non-blocking algorithms use [[Atomicity|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 (computingdata structure)|stacks]], [[queue|queues]], [[set|sets]], and [[hash table|hash tables]]. These allow programs to easily exchange data between threads asynchronously.

== Wait-freedom ==