Concurrent Data Structures
In the previous two chapters, we covered synchronization primitives (mutex, condition_variable, shared_mutex) and atomic operations (atomic, memory order). Now it is time to put these tools to use — in this chapter, we focus on the design and implementation of concurrent data structures. Concurrent data structures are core components of multithreaded programs: task queues in thread pools, routing caches in servers, and buffers in messaging systems all rely on thread-safe data structures behind the scenes.
We start with the most practical thread-safe queue — it is the cornerstone of the producer-consumer pattern and the best case study for understanding "how to build correct concurrent components using mutex + condition_variable." We then expand to more general concurrent container design, discussing the design and trade-offs of four strategies: coarse-grained locking, fine-grained locking, sharded locking, and copy-on-write. Finally, we enter the realm of lock-free programming — from CAS loops and the ABA problem to SPSC ring buffers and the Michael-Scott MPMC queue, building our ability to design and evaluate lock-free concurrent data structures.