A data structure is concurrent if it organizes and stores data to be accessed by the multiple computing threads or we can say asynchronous processes on a system. The term “concurrency” is known to define the 2 terms of the operations that are performed simultaneously by the threads up on the data:
1. Multiplexing of the threads and
2. Interleaving of the threads.
– However, the above two issues have not yet been faced simultaneously by the processors while accessing the data.
– Now-a-days, parallelism is more prevalent as more and more multi-processor computer architectures are being developed.
– They are one of the most dominant computing platforms and are achieved through the multi – core processors proliferation.
– However, lately this term has come to refer to the data structures that can be readily accessed by the multiple processes or threads which may tend to access data simultaneously.
– This is because the threads run on different processors which have a communication link between them.
– Concurrent data structures are sometimes known as the shared data structure and usually reside in shared memory (particularly known as the abstract storage environment).
– You have options for implementing this memory in either of the two ways:
1. Tightly coupled collection of the storage modules or
2. Distributed collection of storage modules.
Why were Concurrent Data Structures developed?
– The concurrent data structures were developed with the intention of using them in the distributing computing environments and in parallel computing.
– This makes them different from the usual sequential data structures which are used only on the processor machines in a number of ways.
– It is a thing to be noted that the data structure properties are specified and verified on the implementation part in a sequential environment by means of the safety properties.
– Whereas, in the concurrent environment, the specifications also need to describe live-ness properties which are provided by the implementation.
– The purpose of the safety properties is to state that something bad would never happen.
– On the other hand, the purpose of the live-ness properties is to state that something good keeps happening.
– Linear temporal logic is used to express the above properties.
– The data structure is defined by the type of the live-ness requirements.
– The method calls are of 2 types:
1. Blocking and
2. Non – blocking
– There are many mainstream approaches such as mentioned below which will specify sequentially the structures:
3. Sequential consistency
4. Quiescent consistency
– Also, the concurrent executions are mapped to the sequential ones.
– The concurrent data structures should be powered enough to reach the consensus so as to process the results of their modification requests and simultaneous data access.
– The concurrent data structures are implemented via the special primitive synchronization operations in order to support such agreements.
– These synchronization primitives which are available on the multiprocessor machines using which the multiple threads can reach consensus.
– It is quite difficult to design concurrent data structures when compared to their sequential counterparts.
– The concurrency is at the heart of this difficulty.
– For today’s system, the performance is affected by many factors including the layout of memory, processors etc.
– The key measure of performance of the concurrent data structure is scalability.