Concurrent data structure: Difference between revisions

Revision as of 14:01, 17 October 2018

Latest revision as of 18:32, 9 August 2025

(14 intermediate revisions by 11 users not shown)

Line 1:

{{Use dmy dates|date=August 2020}}

{{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 [[Thread (computer science)|threads]] (or [[process (computing)|processes]]) on a [[computer]].

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

[[parallel computing|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 architecture|shared memory]], though this memory may be

physically implemented as either a "tightly coupled" or a

distributed collection of storage modules.

==Basic principles==

Line 30 ⟶ 11:

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

{{cite book

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

| title = 'Handbook of Data Structures and Applications'

| chapter = ''[http://www.cs.tau.ac.il/~shanir/concurrent-data-structures.pdf 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–47–3047-14–47-30

}}

</ref> Most notably, in a sequential environment

Line 62 ⟶ 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

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 achieved in a blocking manner by using [[Spinlock|locks]], or without locks, in which case it is [[Non-blocking algorithm|non-blocking]]. There is a wide body

Line 77 ⟶ 60:

bibliographical references).

==Design and Implementationimplementation==

Concurrent data structures are significantly more difficult to design

Line 95 ⟶ 78:

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

| author=Gramoli, V.

| conferencebook-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

}}</ref>

| archive-date=10 April 2015

}}</ref>

A key measure for performance is scalability, captured by 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 known as [[Amdahl's law]] and

Line 116 ⟶ 101:

___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

exacerbated by the additional memory traffic associated with

unsuccessful attempts to acquire the lock.

==.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|Java concurrency]] (JSR 166)]]

* [[Java ConcurrentMap]]

Line 137 ⟶ 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

* [httphttps://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.

{{Concurrent computing}}

{{DEFAULTSORT:Concurrent Data Structure}}