Chapter 6: Chapter 6. Designing lock-based concurrent data structures

Introduction

The chapter introduces why data structures need deliberate design for concurrent access and previews lock-based examples before a later chapter turns to lock-free designs.

• Concurrent access design choices: Explain that a data structure shared by threads can avoid synchronization if it is completely immutable; if it changes, those changes must be correctly synchronized, either through external locking or by designing the structure for concurrent access.
  Why it matters: This distinction is the starting point for deciding how shared data should be protected.
• Lock-based chapter roadmap: Describe the chapter’s progression from general design guidelines to data structures built with locks and condition variables, and distinguish that approach from chapter 7’s use of atomic operations to build structures without locks.
  Why it matters: The roadmap separates this chapter’s lock-based designs from the lock-free designs that follow.

Key terms: immutable, synchronization, external locking, concurrent access, locks, condition variables, atomic operations, lock-free

6.1 What does it mean to design for concurrency?

Defines thread safety for a concurrent data structure and explains why designing for concurrency also means limiting serialization.

• Operation-specific thread safety: Explain that a thread-safe data structure gives concurrent users self-consistent views, preserves data and invariants, and avoids problematic races. Describe how the operations that can safely overlap depend on the data structure.
  Why it matters: Thread safety is a promise about particular patterns of access, not a guarantee that every operation can run alongside every other one.
• Serialization and protected-region size: Explain that a mutex keeps threads out of its protected data one at a time, serializing access. Describe why smaller protected regions serialize fewer operations and offer more opportunity for true concurrency.
  Why it matters: Preventing races is not enough if the locking design unnecessarily makes threads take turns.

Key terms: thread-safe, self-consistent view, invariants, problematic race conditions, mutex, mutual exclusion, serialization, protected region, true concurrent access

6.1.1 Guidelines for designing data structures for concurrency

This section gives designers a checklist for making concurrent data structures safe while allowing as much simultaneous access as their operations permit.

• Thread safety design checks: Explain how to keep a concurrent data structure safe: hide states with broken invariants, provide complete operations rather than race-prone steps, preserve invariants when exceptions occur, and limit deadlock risks by keeping locks narrow and avoiding nested locks where possible.
  Why it matters: A data structure is not thread-safe merely because its data is guarded by a mutex.
• Concurrent operation contract: Describe how the designer must specify which functions callers may use concurrently. Explain that users must exclude access before construction finishes or after destruction starts, while the designer must decide whether assignment, swap, and copy construction require exclusive access even if ordinary operations do not.
  Why it matters: Callers need to know which combinations of operations the data structure actually supports safely.
• Opportunities for genuine concurrency: Explain that safe access should not unnecessarily serialize every operation: consider shorter lock scopes, separate mutexes for separate parts, different protection for different operations, and structural changes that preserve operational semantics. Describe how readers may run together while a writer needs exclusive access, or different operations may overlap while identical ones are serialized.
  Why it matters: Reducing unnecessary serialization lets threads make progress at the same time rather than merely taking turns safely.

Key terms: invariants, race conditions inherent in the interface, exceptions, deadlock, nested locks, constructors, destructors, assignment, swap(), copy construction

6.2 Lock-based concurrent data structures

This section introduces the safety and concurrency tradeoffs in lock-based data structures before examining a stack and other simple examples.

• Mutex protection and lock duration: Explain that a lock-based data structure must hold the right mutex whenever protected data is accessed, while keeping the lock held for as little time as possible. Describe why locking alone does not fix race conditions inherent in an interface.
  Why it matters: These are the checks used to judge whether the coming designs are both thread-safe and capable of concurrency.
• Multiple mutex design risks: Explain that protecting separate parts of a data structure with separate mutexes compounds the access and interface-safety problems and can introduce deadlock when an operation needs more than one lock.
  Why it matters: More locks may create opportunities for concurrency, but they also make correctness harder to maintain.
• Stack as initial design test: Describe the section’s plan to apply the guidelines from section 6.1.1 to simple mutex-protected data structures, starting with the single-mutex stack from chapter 3. State that the stack will be judged both for thread safety and for how much true concurrency it permits.
  Why it matters: The stack gives a simple starting point for comparing correctness with opportunities for concurrent access.

Key terms: lock-based concurrent data structures, mutex, race conditions inherent in the interface, thread-safe, separate mutexes, deadlock, multiple mutexes, stack, single mutex, true concurrency

6.2.1 A thread-safe stack using locks

The section examines how a mutex-protected stack handles races, exceptions, and concurrent access, then explains its deadlock risks and limitations under contention or when callers need to wait for data.

• Mutex protection and pop interface: Explain how locking each stack member function protects its invariants and why each pop operation checks for emptiness under the lock and returns the removed item in the same call.
  Why it matters: Thread safety depends on both protecting the data and avoiding an interface that splits a dependent operation across calls.
• Exception-safe stack operations: Trace why push and both pop overloads leave the stack safe if copying, moving, assignment, allocation, or locking throws. Distinguish the potentially throwing work from the later, nonthrowing removal of an item.
  Why it matters: An exception must not remove an item before the caller can successfully receive it or leave the mutex locked.
• User code and object lifetime: Describe the remaining deadlock risk from running item-copying, moving, assignment, or allocation code while holding the stack lock, and state when other threads may safely begin and cease accessing the stack.
  Why it matters: Locking member functions does not make arbitrary user code under the lock or concurrent construction and destruction safe.
• Serialization and missing item waits: Explain why this stack can perform poorly under contention and why callers that need to wait for an item require polling, repeated empty-stack exceptions, or external notification instead of a built-in wait.
  Why it matters: A correct thread-safe stack is not necessarily an efficient fit for contended workloads or producer-consumer waiting.

Key terms: mutex, std::lock_guard<>, empty(), pop(), top(), invariants, std::make_shared, std::shared_ptr, empty_stack, data.push()

6.2.2 A thread-safe queue using locks and condition variables

This section explains how a mutex-and-condition-variable queue handles empty queues, where its exception-safety and concurrency limits arise, and how storing shared pointers changes those trade-offs.

• Empty queue operation behavior: Distinguish the queue’s try_pop() and wait_and_pop() operations: try_pop() reports that an empty queue has no value, whereas wait_and_pop() waits for an entry instead of requiring repeated empty() checks.
  Why it matters: The choice between trying and waiting determines how a caller handles an empty queue.
• Protected condition variable wait: Explain why wait_and_pop() can remove an entry safely after waiting: the condition-variable wait does not proceed until the queue has an element, and the mutex still protects the data.
  Why it matters: The wait must preserve the queue’s invariants as well as avoid busy-waiting.
• Notification and exception trade-offs: Explain how notify_one() can leave an entry unclaimed if its one awakened waiter throws, and describe the section’s alternatives for addressing that case.
  Why it matters: Waking one waiter is efficient, but an exception can prevent another waiting thread from trying the available entry.
• Shared pointer storage trade-offs: Describe how storing std::shared_ptr<> instances changes the pop functions and moves allocation to push() outside the lock, reducing time spent holding the mutex.
  Why it matters: Where allocation occurs affects both exception safety and how long other threads must wait for the mutex.
• Whole queue locking limit: Explain why protecting the entire std::queue<> with one mutex permits only one thread to work on the queue at a time, and why controlling the implementation enables finer-grained locking.
  Why it matters: A thread-safe queue can still offer little concurrency if every operation needs the same lock.

Key terms: try_pop(), wait_and_pop(), empty(), condition variable, data_cond.wait(), mutex, invariants, data_cond.notify_one(), data_cond.notify_all(), std::shared_ptr<>

6.2.3 A thread-safe queue using fine-grained locks and condition variables

This section builds a fine-grained, lock-based queue and explains how its dummy node, mutexes, and condition variable preserve correctness while allowing concurrent pushes and pops.

• Dummy node queue layout: Explain why a singly linked queue with separate head and tail locks needs a dummy node, and describe how pushing and popping use it.
  Why it matters: The dummy node separates the parts of the list that push and pop modify.
• Head and tail lock ordering: Trace which mutexes protect push and pop, and explain why pop must read the tail while holding the head mutex.
  Why it matters: The lock order and the timing of the tail read keep the list valid and its data accesses ordered.
• Short critical sections and concurrency: Explain how the queue keeps costly work outside short critical sections and what operations can consequently overlap.
  Why it matters: Correct fine-grained locking is most useful when it also reduces time spent blocking other threads.
• Condition variable pop waiting: Describe how wait_and_pop waits for a nonempty queue using the head lock, and how push notifies a waiting thread.
  Why it matters: Waiting must preserve the queue's locking rules rather than reintroduce a race around the empty check.
• Exception safe value removal: Explain why the overload that assigns a popped item to a caller-supplied value must perform potentially throwing assignment before removing the node, and summarize why the other push and pop paths are exception-safe.
  Why it matters: Removing an item before a throwing assignment could lose that item permanently.
• Unbounded and bounded queues: Distinguish this unbounded queue from a bounded queue and describe the stated approach to limiting its length.
  Why it matters: A capacity limit can prevent producers from getting too far ahead of consumers.

Key terms: head, tail, dummy node, std::unique_ptr<node>, std::shared_ptr<>, head_mutex, tail_mutex, get_tail(), pop_head(), queue invariants

6.3 Designing more complex lock-based data structures

This section introduces why lock-based designs become harder as data structures support more operations, then points to a lookup table as an example.

• Operation-aware concurrency design: Explain why a data structure with more operations may offer more opportunities for concurrency than a stack or queue, while being harder to protect because its different access patterns must be considered.
  Why it matters: The operations a data structure supports shape how it can be safely accessed by multiple threads.

Key terms: stacks and queues, operations, access patterns, concurrent access, lookup table

6.3.1 Writing a thread-safe lookup table using locks

This section designs a thread-safe lookup table whose revised interface and per-bucket locks allow more concurrent access than a single lock around a standard map.

• Concurrency-safe lookup interface: Explain why the lookup table omits standard associative-container iterators and uses operations such as lookup, add-or-update, and removal instead. Describe how lookup can report a missing key without returning a reference into the container.
  Why it matters: A safe interface must account for other threads changing or deleting entries while an operation is in progress.
• Hash buckets for independent locking: Justify choosing a fixed-bucket hash table over a binary tree or sorted array for fine-grained locking. Explain how a key’s hash identifies a bucket that can have its own lock.
  Why it matters: The choice of underlying structure determines whether operations on different keys can avoid contending for one container-wide lock.
• Per-bucket reading and writing: Describe how the implementation selects a bucket without locking, then uses shared ownership for reads or unique ownership for modifications. Explain that each bucket holds a list of key/value pairs searched before a value is read, updated, inserted, or removed.
  Why it matters: Per-bucket shared mutexes permit readers to overlap while still excluding conflicting changes within a bucket.
• Lookup operation exception safety: Explain why lookup and removal do not leave the table structurally changed by an exception, and why insertion is safe if list push_back throws. Identify replacement-value assignment as dependent on the exception behavior of the user-supplied mapped type.
  Why it matters: Thread safety does not by itself establish what state an operation leaves behind if it throws.
• Consistent whole-table snapshot: Explain why copying the lookup table into a std::map requires locking every bucket, and why acquiring those locks in the same order prevents deadlock.
  Why it matters: A snapshot must represent a consistent state even though normal operations lock only one bucket.

Key terms: iterators, add_or_update_mapping, value_for, default_value, hash table, buckets, hash function, fine-grained locking, std::hash<>, get_bucket()

6.3.2 Writing a thread-safe list using locks

This section builds a thread-safe linked list with per-node locks, explains its operations, and identifies the safety rules and concurrency limits of the design.

• Container-controlled iteration: Explain why the list offers container-controlled operations such as for_each instead of STL-style iterators, and describe the obligations this places on user-supplied functions.
  Why it matters: The list can keep references valid during iteration only if it controls when the relevant locks are held.
• Per-node locking and insertion: Describe the list's per-node mutex design, including its dummy head and how push_front inserts a newly allocated node while holding only the head lock.
  Why it matters: Keeping allocation outside the lock and limiting insertion to one node's lock makes the update short and simple.
• Hand-over-hand list traversal: Trace how for_each and find_first_if traverse by locking the next node before releasing the previous one, and distinguish applying a function to every item from stopping at the first predicate match.
  Why it matters: The lock handoff protects each node and its data while still allowing threads to work on different parts of the list.
• Safe conditional node removal: Trace how remove_if unlinks a matching node and explain why deleting it after unlocking its mutex is safe while the preceding node remains locked.
  Why it matters: Unlinking and destroying a node safely is the hardest part of changing this list during concurrent traversal.
• Concurrency gains and limits: Explain why forward-only lock ordering avoids deadlock for well-behaved callbacks, while per-node locks permit simultaneous work on different nodes but do not let traversing threads pass one another.
  Why it matters: Fine-grained locking improves overlap, but a slow operation on one node can still hold up other traversals.

Key terms: STL-style iterator, for_each, user-supplied code, deadlock, data races, threadsafe_list<>, node, head, push_front(), mutex

6.4 Summary

The summary recaps how the chapter applies concurrency-design guidelines to lock-based data structures and points ahead to lock-free designs using the same guidelines.