Concurrent data structure: Difference between revisions

Revision as of 17:56, 10 March 2022

Latest revision as of 18:32, 9 August 2025

(10 intermediate revisions by 8 users not shown)

Line 2:

{{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 31 ⟶ 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 72 ⟶ 54:

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 96 ⟶ 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

Line 124 ⟶ 106:

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]] (JSR 166)

* [[Java ConcurrentMap]]

Line 140 ⟶ 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}}