A data structure organizes data to support particular operations. When multiple threads access one, it must either remain immutable or synchronize changes correctly. section 6.0
Designing a data structure for concurrent access involves two goals:
- Keep operations safe: preserve invariants, provide complete operations rather than exposing steps, account for exceptions, and reduce deadlock risks. section 6.1.1
- Allow genuine concurrency: consider whether locks can be limited to parts of an operation or different parts of the structure. section 6.1.1
- Specify which operations may run concurrently, including whether assignment, swapping, or copying requires exclusive access. section 6.1.1
Mutexes and condition variables can support lock-based designs; atomic operations can also be used to build data structures without locks. section 6.0 section 6.4
Common concurrent structures
Stacks, queues, hash maps, and linked lists illustrate how locks can protect data and prevent data races. section 6.4
