Concurrent data structure: Difference between revisions

Revision as of 19:06, 23 April 2010

Latest revision as of 18:32, 9 August 2025

(45 intermediate revisions by 33 users not shown)

Line 1:

{{Refimprove|date=NovemberUse 2009}}dmy {{Cleanupdates|date=NovemberAugust 20092020}}

{{Refimprove|date=November 2009}}

In [[computer science]], a '''concurrent data structure''' (also called '''shared data structure''') is a data structure designed for access and modification by multiple computing [[Thread (computer science)|threads]] (or [[process (computing)|processes]] or nodes) on a computer, for example concurrent [[Message queue|queues]], concurrent [[Stack (abstract data type)|stacks]] etc. The concurrent data structure is typically considered to reside in an abstract storage environment known as shared memory, which may be physically implemented as either a tightly coupled or a distributed collection of storage modules. <ref>{{Cite book |title=A VLSI Architecture for Concurrent Data Structures |isbn=9781461319955 |last1=Dally |first1=J. W. |date=6 December 2012 |publisher=Springer }}</ref><ref>{{Cite book |title=23nd International Symposium on Distributed Computing, DISC |publisher=Springer Science & Business Media |year=2009}}</ref>

In [[computer science]], a '''concurrent data structure''' is a

particular way of storing and organizing [[data]] for access by

multiple computing [[threads]] (or [[process (computing)|processes]]) on a [[computer]].

==Basic principles==

Historically, such data structures were used on [[uniprocessor]]

machines with [[operating systems]] that supported multiple

computing threads (or [[process (computing)|processes]]). The term [[concurrency (computer science)|concurrency]] captured the

[[multiplexing]]/[[interleaving]] of the threads' operations on the

data by the operating system, even though the processors never

issued two operations that accessed the data simultaneously.

Today, as [[multiprocessor]] computer architectures that provide

[[parallelism]] become the dominant computing platform (through the

proliferation of [[multi-core]] processors), the term has come to

stand mainly for data structures that can be accessed by multiple

threads which may actually access the data simultaneously because

they run on different processors that communicate with one another.

The concurrent data structure (sometimes also called a [[shared data structure]]) is usually considered to reside in an abstract storage

environment called [[shared memory]], though this memory may be

physically implemented as either a "tightly coupled" or a

[[distributed]] collection of storage modules.

==Basic principles==

Concurrent data structures, intended for use in

parallel or distributed computing environments, differ from

"sequential" data structures, intended for use on a uniprocessoruni-processor

machine, in several ways.<ref name="sahni">

<ref name="sahni">

{{cite book

| author = Mark Moir and |author2=[[Nir Shavit]]

| title = 'Handbook of Data Structures and Applications'

| chapter = ''Concurrent Data Structures''

|chapter-url=http://www.cs.tau.ac.il/~shanir/concurrent-data-structures.pdf

| edition = 1st

|archive-url=https://web.archive.org/web/20110401070433/http://www.cs.tau.ac.il/~shanir/concurrent-data-structures.pdf

| editor = Dinesh Metha and [[Sartaj Sahni]]

|archive-date=2011-04-01

| editor = Dinesh Metha and |editor2=[[Sartaj Sahni]]

| publisher = Chapman and Hall/CRC Press

| year = 2007

| pages = 47-14 — 4714–47-30

}}

</ref>. Most notably, in a sequential environment

one specifies the data structure's properties and checks that they

are implemented correctly, by providing '''safety properties'''. In

Line 50 ⟶ 32:

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 64 ⟶ 45:

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.

In order toTo 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_synchronizationHardware 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 synchronization algorithm| non-blocking]]. There is a wide body

of theory on the design of concurrent data structures (see

bibliographical references).

==Design and Implementationimplementation==

Concurrent data structures are significantly more difficult to design

Line 94 ⟶ 74:

various elements of the multiprocessor architecture all influence performance.

Furthermore, there is a tension between correctness and performance: algorithmic enhancements that seek to improve performance often make it more difficult to design and verify a correct

data structure implementation.<ref>

{{cite conference

| title=More than you ever wanted to know about synchronization: Synchrobench, measuring the impact of the synchronization on concurrent algorithms

| author=Gramoli, V.

| book-title=Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

| pages=1–10

| year=2015

| publisher=ACM

| url=http://sydney.edu.au/engineering/it/~gramoli/doc/pubs/gramoli-synchrobench.pdf

| archive-url=https://web.archive.org/web/20150410030004/http://sydney.edu.au/engineering/it/~gramoli/doc/pubs/gramoli-synchrobench.pdf

| archive-date=10 April 2015

}}</ref>

A key measure for performance is scalability, captured by the the [[speedup]] of the implementation. Speedup is a measure of how

effectively the application is utilizingusing the machine it is running

on. On a machine with P processors, the '''speedup''' is the ratio of the structures execution time on a single processor to its execution time on TP processors. Ideally, we want linear speedup: we would like to achieve a

speedup of P when using P processors. Data structures whose

speedup grows with P are called '''scalable'''. The extent to which one can scale the performance of a concurrent data structure is captured by a formula knowknown as [[Amdahl's law]] and

more refined versions of it such as [[Gustafson's law]].

A key issue with the performance of concurrent data structures is the level of '''memory contention''': the overhead in traffic to and from memory as a

result of multiple threads concurrently attempting to access the same

locations in memory. This issue is most acute with blocking implementations

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

consistent with the latest values stored) this results in long

waiting times for each attempt to modify the ___location, and is

Line 116 ⟶ 107:

unsuccessful attempts to acquire the lock.

==References.NET==

[[.NET]] have {{Mono|ConcurrentDictionary}},<ref>{{cite web |title=ConcurrentDictionary Class (System.Collections.Concurrent) |url=https://learn.microsoft.com/en-us/dotnet/api/system.collections.concurrent.concurrentdictionary-2?view=net-9.0 |website=learn.microsoft.com |access-date=26 November 2024 |language=en-us}}</ref> {{Mono|ConcurrentQueue}}<ref>{{cite web |title=ConcurrentQueue Class (System.Collections.Concurrent) |url=https://learn.microsoft.com/en-us/dotnet/api/system.collections.concurrent.concurrentqueue-1?view=net-9.0 |website=learn.microsoft.com |access-date=26 November 2024 |language=en-us}}</ref> and {{Mono|ConcurrentStack}}<ref>{{cite web |title=ConcurrentStack Class (System.Collections.Concurrent) |url=https://learn.microsoft.com/en-us/dotnet/api/system.collections.concurrent.concurrentstack-1?view=net-9.0 |website=learn.microsoft.com |access-date=26 November 2024 |language=en-us}}</ref> in the {{Mono|System.Collections.Concurrent}} namespace.

[[File:UML dotnet concurrent.svg|UML class diagram of System.Collections.Concurrent in .NET]]

==Rust==

[[Rust (programming language)|Rust]] instead wraps data structures in {{Mono|Arc}} and {{Mono|Mutex}}.<ref>{{cite web |title=Shared-State Concurrency - The Rust Programming Language |url=https://doc.rust-lang.org/book/ch16-03-shared-state.html |website=doc.rust-lang.org |access-date=26 November 2024}}</ref>

<syntaxhighlight lang="rust">

let counter = Arc::new(Mutex::new(0));

</syntaxhighlight>

==See also==

* [[Thread safety]]

* [[Java concurrency]] (JSR 166)

* [[Java ConcurrentMap]]

==References==

{{reflist}}

==Further reading==

* [[Nancy Lynch]] "Distributed Computing"

* [[Hagit Attiya]] and Jennifer Welch "Distributed Computing: Fundamentals, Simulations And Advanced Topics, 2nd Ed"

* [[Doug Lea]], "Concurrent Programming in Java: Design Principles and Patterns"

* [[Maurice Herlihy]] and [[Nir Shavit]], "The Art of Multiprocessor Programming"

Line 126 ⟶ 135:

==External links==

* [https://web.archive.org/web/20160303215946/http://www.ibm.com/developerworks/aix/library/au-multithreaded_structures1/index.html Multithreaded data structures for parallel computing, Part 1] (Designing concurrent data structures) by Arpan Sen

* [https://web.archive.org/web/20160304000118/http://www.ibm.com/developerworks/aix/library/au-multithreaded_structures2/index.html Multithreaded data structures for parallel computing: Part 2] (Designing concurrent data structures without mutexes) by Arpan Sen

* [https://libcds.sourceforge.net/ libcds] – C++ library of lock-free containers and safe memory reclamation schema

* [https://sites.google.com/site/synchrobench/ Synchrobench] – C/C++ and Java libraries and benchmarks of lock-free, lock-based, TM-based and RCU/COW-based data structures.

[[Category:{{Concurrent computing]]}}

{{DEFAULTSORT:Concurrent Data Structure}}

* [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]

[[Category:DataDistributed data structures]]

[[Category:Data structures]]

[[Category:Concurrent computing]]