Concurrent data structure: Difference between revisions

Revision as of 20:23, 22 March 2024

Revision as of 05:02, 24 November 2024

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}}</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==