Concurrent data structure: Difference between revisions

Revision as of 18:05, 15 September 2011

Revision as of 18:14, 15 September 2011

Line 50:

The type of liveness requirements tend to define the data structure.

The [[method (computer science)|method]] calls can be '''[[Blocking (computing)|blocking''']] or '''[[Non-blocking algorithm|non-blocking''']]. Data structures are not

(see [[non-blocking synchronization]]). Data structures are not

restricted to one type or the other, and can allow combinations

where some method calls are blocking and others are non-blocking

Line 75 ⟶ 74:

using special primitive synchronization operations (see [[Synchronization (computer science)#Process_synchronization|synchronization primitives]])

available on modern [[multiprocessing|multiprocessor machine]]s

that allow multiple threads to reach consensus. This consensus can be reached achieved in a blocking manner by using [[Spinlock|locks]], or without locks, in which case it is [[nonNon-blocking synchronizationalgorithm|non-blocking]]. There is a wide body

of theory on the design of concurrent data structures (see

bibliographical references).