Concurrent data structure: Difference between revisions

Revision as of 19:11, 27 September 2010

Revision as of 19:46, 10 November 2010

Line 23:

distributed collection of storage modules.

==Basic principles==

Concurrent data structures, intended for use in

Line 64:

Therefore, many mainstream approaches for arguing the safety properties of a

concurrent data structure (such as [[serializability]], [[linearizability]], [[sequential consistency]], and

quiescent consistency <ref name="sahni" />) specify the structures properties

</ref>) specify the structures properties

sequentially, and map its concurrent executions to

a collection of sequential ones.

Line 71 ⟶ 70:

In order to guarantee the safety and liveness properties, concurrent

data structures must typically (though not always) allow threads to

reach [[consensus (computer science) | consensus]] as to the results

of their simultaneous data access and modification requests. To

support such agreement, concurrent data structures are implemented

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 [[non-blocking synchronization | non-blocking]]. There is a wide body

of theory on the design of concurrent data structures (see

bibliographical references).

Line 108 ⟶ 107:

in which locks control access to memory. In order to

acquire a lock, a thread must repeatedly attempt to modify that

___location. On a [[Cache coherence | cache-coherent]]

multiprocessor (one in which processors have

local caches that are updated by hardware in order to keep them

Line 116 ⟶ 115:

unsuccessful attempts to acquire the lock.

==References==

{{reflist}}

Line 126 ⟶ 125:

==External links==

* [http://www.jcp.org/en/jsr/detail?id=166 JSR 166: Concurrency Utilities][http://g.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html intro page]

{{DEFAULTSORT:Concurrent Data Structure}}

[[Category:Data structures]]

[[Category:Concurrent computing]]