Chapter 7: Data Structures for Concurrency

In the last chapter, we explored, in detail, the synchronization primitives that can be used to ensure the correctness of concurrent programs. We also studied the simplest but useful building blocks for these programs: thread-safe counters and pointers.

In this chapter, we are going to continue the study of data structures for concurrent programs. The aim of this chapter is two-fold: on the one hand, you will learn how to design thread-safe variants of several fundamental data structures. On the other hand, we will point out several general principles and observations that are important for designing your own data structures to be used in concurrent programs, as well as for evaluating the best approaches to organize and store your data.

In this chapter, we're going to cover the following main topics:

• Understanding thread-safe data structures, including sequential containers, stack and queue, node-based containers, and lists...