0

Concurrent data structures:

[1] http://www.cs.tau.ac.il/~shanir/concurrent-data-structures.pdf

[2] http://en.wikipedia.org/wiki/Concurrent_data_structure

Are concurrent data structures and thread safe data structures interchangeable terms?

Anton
  • 6,349
  • 1
  • 25
  • 53
Pranjal Mittal
  • 10,772
  • 18
  • 74
  • 99

2 Answers2

2

My understanding differs from @xxa (the answer is: No). Though I have no a regious definition either. Concurrent implies thread-safety. But nowadays, it implies simultaneous access as well. While thread-safety gives no such assumptions. See this quote form the mentioned Wiki-article:

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.

For example, STL containers are claimed to be thread-safe for the given conditions (read-only), moreover, it allows simultaneous reads by a number of threads (STL says them are "as safe as int"), but only one thread can modify them and in absence of readers. Can we name them 'concurrent'? No. While practical concurrent containers (see for example) allow at least two or more threads to work with the container (including modification) at the same time.

And one more point. You could implement std::queue so that methods push() and pop() will not trigger a failure when used by different threads. But does this make it a concurrent_queue? No. Because, queue::front() and queue::pop() do not provide a way to get elements simultaneously by two or more threads without external synchronization. To become a concurrent_queue it needs different interface, which takes care of atomicity by combining pop() with returning the value.

Anton
  • 6,349
  • 1
  • 25
  • 53
  • The distinction you suggest is important, but I am not convinced that the dividing line should be drawn between "thread-safe" and "concurrent". [1] discusses simultaneous access under the terms "non-blocking techniques" vs. "blocking techniques", and further "fine grained locking" in the latter case. But it does not seem to exclude blocking techniques to be used in the case of concurrent data structures. Also `tbb` provides means for mutual exclusion, which explicitly asks for exclusive access. – xxa Oct 15 '14 at 08:32
  • I agree the line is blur but at least, it is accepted among TBB developers. The term 'concurrent container' does not dictate whether a container is non-blocking or fine-grained. It just says that two or more threads can perform operations simultaneously/concurrently at least on two different elements. While thread-safety discloses only that it is safe to access a container from different threads and gives no clue whether the operations are serialized or not. – Anton Oct 15 '14 at 11:03
  • It is interesting how the meaning of "concurrent" evolves in this case because in a similar debate on the meaning of "concurrent" vs. "parallel" (http://stackoverflow.com/questions/1050222/concurrency-vs-parallelism-what-is-the-difference) the consensus seems to be that "concurrent" is a more general term, while "parallel" means that events actually happen simultaneously. It is unfortunate that things go in the opposite direction in relation to data structures. – xxa Oct 15 '14 at 11:42
  • I agree that "concurrency" is wider while "parallelism" gives stronger guarantees. But there is no such a term as "parallel container", it can be only applied to process of execution. – Anton Oct 15 '14 at 11:46
  • So, to summarize, a thread-safe data structure is to be used when processes are executed concurrently, but a concurrent data structure makes sense only when processes are executed in parallel. It is possible to define things this way, but I maintain that this is not entirely a consistent way of using them. – xxa Oct 15 '14 at 13:44
  • As the http://stackoverflow.com/questions/1897993/difference-between-concurrent-programming-and-parallel-programming?lq=1 discusses, concurrency is a property of the program and parallelism is property of machine execution. Thus your definition above does not make much sense to me. I think the problem is misunderstanding of concurrency as strictly interleaved execution, it's definitely not. – Anton Oct 15 '14 at 14:16
0

These terms do not have a rigorous definition, but in general it can be asserted that the answer to your questions is yes. Both refer to data structures that are stored in shared memory (http://en.wikipedia.org/wiki/Shared_memory) and manipulated by several threads or processes.

In fact [1] asserts the same when it refers to threads explicitly:

The primary source of this additional difficulty is concurrency: Because threads are executed concurrently on different processors, ..."

xxa
  • 1,258
  • 9
  • 20