Concurrent Data Structures

Over the past two chapters we sorted out synchronization primitives (mutex, condition_variable, shared_mutex) and atomic operations (atomic, memory order). Now it's time to put those tools to work — this chapter focuses on designing and implementing concurrent data structures. They are the core components of multithreaded programs: the task queue inside a thread pool, the routing cache in a server, the buffer of a messaging system — behind all of them you need data structures that are safe for concurrent access.

We'll start with the most practical one, the thread-safe queue — it's the cornerstone of the producer-consumer pattern, and the best case study for understanding "how to build a correct concurrent component with mutex + condition_variable". Then we'll widen the scope to concurrent container design in general, discussing the design and trade-offs of four strategies: coarse-grained locking, fine-grained locking, sharded locking, and copy-on-write. Finally we step into the territory of lock-free programming — from CAS loops and the ABA problem to the SPSC ring buffer and the Michael-Scott MPMC queue — building up your ability to design and reason about lock-free concurrent data structures.

In This Chapter

STARTFINISHThread-Safe Queue→STARTFINISHThread-Safe Container Design→STARTFINISHLock-Free Programming Fundamentals→STARTFINISHSPSC and MPMC Queues→