Chapter 7: Chapter 7. Designing lock-free concurrent data structures

Introduction

The introduction motivates lock-free data structures, identifies atomic memory ordering as their foundation, and previews the chapter’s definitions, examples, memory-management techniques, and guidelines.

• Motivation and difficulty of lock freedom: Explain why a concurrent data structure might avoid locks despite their usefulness, and why a lock-free design requires particular care.
  Why it matters: This frames both the potential benefits of lock-free structures and the difficulty of making them correct.
• Atomic foundation and chapter path: Describe how the chapter proposes to build lock-free data structures using atomic operations’ memory-ordering properties, and outline the topics it will cover.
  Why it matters: The later examples depend on understanding atomic memory ordering, not merely on removing mutexes.

Key terms: mutexes, deadlock, granularity of locking, lock-free data structure, atomic operations, memory-ordering properties, lock-free data structures, managing memory

7.1 Definitions and consequences

This section distinguishes blocking from nonblocking data structures and explains what happens when a thread makes a blocking call.

• Blocking and nonblocking distinction: Distinguish data structures that use blocking library calls, such as mutex, condition-variable, or future operations, from those that do not. State that nonblocking does not necessarily mean lock-free.
  Why it matters: This distinction sets up the different kinds of nonblocking data structures discussed next.
• Blocked thread suspension: Explain that a blocked thread cannot progress until another thread performs the needed action, and that the OS typically suspends it and gives its time slices to another thread.
  Why it matters: It makes clear what a blocking call costs the waiting thread and what releases it.

Key terms: blocking data structures and algorithms, blocking calls, nonblocking, lock-free, blocked thread, time slices, unlocking a mutex, notifying a condition variable, making a future ready

7.1.1 Types of nonblocking data structures

The section distinguishes merely avoiding blocking calls from guaranteeing progress, using a spin lock to introduce obstruction-free, lock-free, and wait-free data structures.

• Spin locks and nonblocking code: Explain why the std::atomic_flag spin lock is nonblocking but not lock-free: lock() repeatedly calls test_and_set() rather than a blocking function, yet the mutex can still be held by only one thread at a time.
  Why it matters: A loop that never makes a blocking call does not, by itself, guarantee that threads make progress.
• Three bounded progress guarantees: Distinguish obstruction-free, lock-free, and wait-free by whose operation must finish in a bounded number of steps and under what conditions. Explain why the section treats obstruction-freedom as a limited guarantee.
  Why it matters: These terms specify different progress guarantees that the broad word “nonblocking” does not convey.

Key terms: std::atomic_flag, spin lock, test_and_set(), nonblocking, lock-free, obstruction-free, wait-free, bounded number of steps

7.1.2 Lock-free data structures

This section defines lock-free progress, explains why compare/exchange retry loops can qualify, and distinguishes lock-free from wait-free behavior.

• Lock-free progress requirement: Explain that a lock-free data structure permits concurrent access by more than one thread, though it need not support the same operation concurrently, and that other threads can complete operations if one thread is suspended midway.
  Why it matters: This is the test for whether a concurrent data structure is actually lock-free.
• Compare-exchange retries and progress: Explain why a compare/exchange operation may need a retry loop after another thread changes the data, and why that loop can remain lock-free rather than acting as a spin lock.
  Why it matters: A retry loop is not automatically a lock; its progress behavior determines the distinction.
• Starvation versus wait-free progress: Distinguish a lock-free algorithm, in which one thread can continually retry while another makes progress, from a wait-free one that avoids this starvation.
  Why it matters: Progress for the data structure does not guarantee progress for every individual thread.

Key terms: lock-free, concurrently, suspended, compare/exchange, retry, spin lock, starvation, wait-free

7.1.3 Wait-free data structures

This section defines wait-freedom, explains why retry-based lock-free operations do not qualify, and notes the difficulty of achieving the stronger guarantee.

• Bounded progress for every thread: Distinguish wait-free from merely lock-free data structures: every thread must be able to finish an operation within a bounded number of steps, regardless of what other threads do. Explain why an unbounded compare-exchange retry loop is not wait-free.
  Why it matters: Lock-free progress does not guarantee a bound on how much work any particular thread must do.
• Difficulty of wait-free design: Explain why writing a correct wait-free data structure is especially hard: operations must complete in a single pass without another thread's steps causing them to fail, which can make the algorithms considerably more complex.
  Why it matters: The stronger progress guarantee carries a design cost that must be justified by its benefit.

Key terms: wait-free data structure, lock-free data structure, compare_exchange_weak, compare_exchange_strong, single pass, bounded number of steps, wait-free data structures

7.1.4 The pros and cons of lock-free data structures

This section weighs the progress and robustness benefits of lock-free data structures against their correctness challenges, livelock risk, and possible performance costs.

• Concurrency and failure resilience: Explain why lock-free data structures can allow more concurrency than mutex-protected ones and why other threads can continue if a thread dies during an operation. Distinguish lock-free progress by some thread from wait-free progress by every thread.
  Why it matters: These are the main reasons to consider a lock-free design in the first place.
• Atomic ordering and invariants: Explain why removing locks makes correctness harder: operations must preserve suitable data-structure invariants, use atomic modifications to avoid data races, and make changes visible to other threads in the right order.
  Why it matters: Atomic operations alone do not make a lock-free data structure correct.
• Livelock versus wait-free progress: Distinguish the absence of deadlock in lock-free structures from the possibility of livelock, where competing threads repeatedly force each other to retry. Explain why a wait-free operation cannot livelock.
  Why it matters: Avoiding locks does not mean retries are harmless or that an individual operation will finish promptly.
• Measured performance tradeoffs: Justify why greater concurrency and shorter individual waits need not improve overall performance: lock-free designs may use more, slower atomic operations and incur synchronization or cache ping-pong. Describe comparing the performance measures that matter for the application against a lock-based version.
  Why it matters: The right choice depends on measured costs and the performance outcome you actually need.

Key terms: lock-free, wait-free, mutex lock, maximum concurrency, invariants, atomic operations, data race, ordering constraints, deadlock, live lock

7.2 Examples of lock-free data structures

The section introduces lock-free data-structure examples, beginning with a stack, and explains how memory ordering and platform behavior affect their design.

• Ordering in lock-free examples: Explain that the examples use atomic operations and memory-ordering guarantees to make data visible to other threads in the right order. Describe why they begin with the default memory_order_seq_cst ordering and later consider weaker orderings.
  Why it matters: This explains the starting point for the lock-free implementations and why their atomic operations can later be refined.
• Practical lock-free implementation choices: Distinguish code that uses no mutex directly from code guaranteed not to use locks internally. Explain why requirements and profiling should guide the choice between an apparently lock-free implementation and a simpler lock-based one.
  Why it matters: A lock-free-looking implementation is not necessarily lock-free on every platform or the best choice for an application.

Key terms: atomic operations, memory-ordering guarantees, memory_order_seq_cst, memory_order_acquire, memory_order_release, memory_order_relaxed, std::atomic_flag, locks internal to the C++ Standard Library implementation, requirements, profile

7.2.1 Writing a thread-safe stack without locks

This section builds a lock-free stack with atomic compare/exchange, then shows why safe popping, exception safety, and node reclamation require more than an atomic head pointer.

• Atomic publication during push: Explain how push prepares a new node before publishing it and uses compare_exchange_weak in a retry loop to prevent a concurrent change to head from being lost.
  Why it matters: A node must be ready for another thread to read the moment it becomes the head.
• Exclusive removal during pop: Trace how pop uses compare/exchange to ensure that only one thread removes and returns a given head node, and explain why that success does not make immediate deletion safe.
  Why it matters: Winning the removal race does not prove that other threads have stopped accessing the old node.
• Empty and exception safe results: Describe why pop checks for an empty head before dereferencing it and returns a std::shared_ptr to data allocated during push, rather than copying a value or allocating it after removal.
  Why it matters: A successful removal should not lose a value because producing the result throws an exception.
• Progress and reclamation limits: Distinguish this stack's lock-free progress from wait-free progress, and state why the presented version leaks removed nodes without a way to reclaim them safely.
  Why it matters: Removing locks does not guarantee that each operation finishes or that removed memory is safely reclaimed.

Key terms: head, next, compare_exchange_weak(), push(), pop(), compare/exchange, dangling pointer, nullptr, std::shared_ptr<>, exception safety

7.2.2 Stopping those pesky leaks: managing memory in lock-free data structures

This section shows how a lock-free stack can reclaim removed nodes safely, why a simple deferred-deletion scheme works only when pop() has quiet periods, and why heavier use requires another approach.

• Safe node reclamation condition: Explain why a removed stack node cannot be deleted while another pop() might still hold and dereference a pointer to it, and why push() does not create the same reclamation problem.
  Why it matters: This safety condition determines when the stack can free memory without introducing undefined behavior.
• Pop counter and pending nodes: Trace the deferred-reclamation scheme: count threads in pop(), move unsafe-to-delete nodes to a pending list, and delete pending nodes only when the count shows no pop() can still access them. Describe why pop() swaps out the node's data before its deletion is delayed.
  Why it matters: The counter and pending list let the stack avoid both immediate unsafe deletion and permanent leaks when quiet periods occur.
• Claim and recheck sequence: Trace why try_reclaim() atomically claims the pending list when it sees only one thread in pop(), then decrements and rechecks the counter before deleting that list. Explain why it chains claimed nodes back with a compare-exchange loop if another pop() has entered.
  Why it matters: The second check closes a race in which another thread could still be using a node on the claimed list.
• Quiescent period limitation: Explain why counter-based reclamation works when periods occur with no threads in pop(), but can let the pending list grow without bound under sustained activity. State that reclaiming nodes without such periods requires identifying when each particular node is no longer accessed, with hazard pointers introduced as an alternative.
  Why it matters: This limitation explains why the chapter moves from a whole-stack quiet-period test to node-specific reclamation.

Key terms: pop(), push(), node, reclaim, threads_in_pop, to_be_deleted, try_reclaim(), swap(), atomic exchange, compare_exchange_weak

7.2.3 Detecting nodes that can’t be reclaimed using hazard pointers

This section shows how hazard pointers let a lock-free stack defer deletion of nodes that other threads may still access, then examines the cost of a simple implementation and ways to reduce it.

• Hazard pointer reclamation rule: Explain how a thread announces that it may access a node and how that announcement determines whether another thread may delete the node.
  Why it matters: Removing a node from a lock-free structure does not mean no other thread still holds a reference to it.
• Protected stack head validation: Trace how pop() publishes a hazard pointer for the stack head, checks that the head has not changed, and repeats this protection when it reloads the head.
  Why it matters: The gap between reading a pointer and announcing its use is where a concurrent deletion could otherwise occur.
• Per-thread hazard pointer slots: Describe how the example gives each participating thread a reusable hazard-pointer slot and makes that slot visible to other threads.
  Why it matters: Deletion checks work only if threads can find the pointers that other threads have published.
• Deferred node deletion process: Trace how the example records nodes that cannot yet be deleted and later rechecks them without two reclaimers taking the same waiting list.
  Why it matters: A safe pop() needs a way to eventually free nodes whose deletion it postponed.
• Hazard scan performance tradeoffs: Explain why scanning hazards on every pop() is expensive and how batching or thread-local reclamation lists trade memory for less frequent scanning and contention.
  Why it matters: Safe reclamation can still make a lock-free operation costly if its atomic checks are too frequent.

Key terms: hazard pointers, outstanding hazard pointers, reclaim_later(), old_head, head, compare_exchange_strong(), hazard pointer, get_hazard_pointer_for_current_thread(), hp_owner, thread_local

7.2.4 Detecting nodes in use with reference counting

This section shows how reference counting can make node reclamation safe in a lock-free stack, from shared-pointer options to a manual split-count implementation.

• Shared pointer reclamation options: Explain how reference-counted shared pointers can reclaim stack nodes, and why atomic operations on std::shared_ptr<> or std::experimental::atomic_shared_ptr<> do not necessarily make a stack lock-free.
  Why it matters: Atomic access is not enough if the underlying operation uses a lock.
• Split reference count lifecycle: Describe how each node's external count travels with its pointer, how readers transfer their references to the internal count when finished, and why a node can be deleted when its internal count reaches zero after the external pointer is retired.
  Why it matters: The two counts let threads determine when no outstanding access can reach a removed node.
• Counted stack head and push: Describe how push links a new node to the current head and uses compare_exchange_weak() to install a counted pointer with an external count of one and an internal count of zero; explain why the counted pointer must itself be supported by lock-free atomic operations for the stack to remain lock-free.
  Why it matters: An atomic counted head protects the pointer and count together, but platform support determines whether that atomic operation uses a lock.
• Safe pop reference accounting: Trace how pop first atomically increases the head node's external count before dereferencing it, then handles both a successful and a failed attempt to remove that node while releasing references and deleting it only when the count permits.
  Why it matters: Pop is where a thread can otherwise dereference a freed node or reclaim one still in use.

Key terms: std::shared_ptr<>, std::atomic_is_lock_free, std::experimental::atomic_shared_ptr<T>, internal count, external count, counted_node_ptr, std::atomic<counted_node_ptr>, compare_exchange_weak(), double-word-compare-and-swap, compare_exchange_strong()

7.2.5 Applying the memory model to the lock-free stack

The section derives the memory orderings needed for a reference-counted lock-free stack by tracing publication, concurrent updates, and safe node deletion.

• Memory ordering analysis method: Explain how to choose memory orderings by identifying the required happens-before relationships in concrete thread interactions, then using the weakest orderings that provide them.
  Why it matters: This approach lets you relax atomic operations without guessing whether the stack remains correct.
• Push publication and pop acquisition: Trace how push publishes a node and its data with a release compare/exchange, and how a successful acquire compare/exchange in increase_head_count() makes the pop thread’s subsequent access to the node’s non-atomic next field safe. State why failed exchanges and the initial head load can be relaxed.
  Why it matters: The release–acquire connection protects the ordinary node fields that atomics alone do not protect.
• Relaxed removal and release sequences: Explain why pop’s compare/exchange that replaces head with next can be relaxed for access to node data, and why intervening compare/exchange updates to head do not break the publication relationship with a later acquiring thread.
  Why it matters: This distinguishes ordering needed to read a node from ordering that is unnecessary during its removal.
• Reference count deletion ordering: Explain why extracting the data with swap() must happen before another thread deletes the node, and how a release decrement plus an acquire reload only in the thread whose decrement reaches zero provides that ordering while other decrements remain relaxed.
  Why it matters: Correct reference counts are not enough if deletion can race with another thread’s access to node data.
• Optimization and complexity tradeoff: Describe the outcome of the ordering analysis: more relaxed operations improve performance without sacrificing correctness, while memory management makes the finished lock-free pop substantially more complex than the earlier stack examples.
  Why it matters: It sets realistic expectations about the benefit and implementation cost of lock-free structures.

Key terms: happens-before, memory ordering, std::memory_order_relaxed, head, counted_node_ptr, compare_exchange_weak, increase_head_count, compare_exchange_strong, std::memory_order_release, ptr->data

7.2.6 Writing a thread-safe queue without locks

This section develops a lock-free queue from a single-producer, single-consumer design, addressing concurrent updates, safe node reclamation, and stalled pushes.

• Queue ends and concurrent races: Explain why the initial atomic-head-and-tail queue works for one producer and one consumer but fails when multiple producers or consumers operate concurrently. Describe how publishing tail makes the data visible to pop().
  Why it matters: Making the pointers atomic does not, by itself, make every queue operation safe for multiple threads.
• Concurrent push node claims: Describe how a producer can claim a tail node by atomically changing its data pointer from null, retrying if another producer claimed it. Explain why protecting the loaded tail pointer against reclamation is also necessary before dereferencing it.
  Why it matters: Winning the data-pointer exchange prevents competing writes, but it does not keep the node alive.
• Dual-counter node reclamation: Explain how the queue uses internal references and up to two external counters to keep nodes alive, and how pop() claims a head node with compare/exchange. Describe why the counts must be updated together and a node deleted only when both kinds of reference are gone.
  Why it matters: Correct reclamation prevents a concurrent queue operation from using a freed node or deleting one twice.
• Helping stalled queue pushes: Explain why the race-free push() still behaves like a lock when one producer has set the data pointer but not finished the link and tail updates. Describe how another producer can complete those updates using atomic next and compare/exchange, restoring progress if the first producer stalls.
  Why it matters: Avoiding races is not enough for lock freedom if every other producer must wait for one thread to finish.
• Allocation costs in lock-free queues: Explain why frequent node allocation and deletion can limit this queue’s scalability, and state that allocator changes should be evaluated by measurement.
  Why it matters: A lock-free algorithm can still perform poorly when memory allocation is expensive.

Key terms: head, tail, dummy node, single-producer, single-consumer (SPSC), happens-before, compare_exchange_strong(), std::atomic<T*>, increase_external_count(), internal_count, external_counters

7.3 Guidelines for writing lock-free data structures

The section introduces additional design guidelines drawn from the chapter’s examples because lock-free data structures are difficult to get right.

• Need for lock-free design guidelines: Explain why designing a lock-free data structure calls for guidance beyond the general concurrent-data-structure guidelines: lock-free code is difficult to get right, and the following guidelines are drawn from the chapter’s examples.
  Why it matters: This connects the lock-free examples to the practical guidance that follows.

Key terms: lock-free data structures, concurrent data structures, guidelines

7.3.1 Guideline: use std::memory_order_seq_cst for prototyping

The section recommends starting lock-free data structures with sequentially consistent atomic operations, then considering weaker memory orderings only after the design works and its complete code can be examined.

• Sequentially consistent starting point: Explain why a lock-free data structure should initially use std::memory_order_seq_cst: its atomic operations form a total order, making the design easier to reason about. Describe weaker memory orderings as a later optimization rather than a starting point.
  Why it matters: Starting with the easiest ordering to reason about helps separate basic design problems from memory-ordering problems.
• Conditions for relaxing ordering: Explain that deciding which operations can use weaker ordering generally requires seeing all code that accesses the data structure's internals. State why ordinary successful tests cannot establish correctness under the specified ordering guarantees, unlike a checker that systematically explores permitted thread visibilities.
  Why it matters: A weaker ordering may appear to work in tests while still allowing an incorrect execution.

Key terms: std::memory_order_seq_cst, total order, memory-ordering constraints, memory orderings, thread visibilities, ordering guarantees, algorithm checker

7.3.2 Guideline: use a lock-free memory reclamation scheme

This section explains how lock-free data structures can reclaim memory safely and why reusing nodes introduces a different hazard.

• Safe lock-free memory reclamation: Explain why a lock-free data structure must not delete an object while another thread might still reference it, yet should reclaim it promptly to limit memory use. Describe the three techniques presented for deciding when deletion is safe.
  Why it matters: Safe reclamation prevents dangling references without letting unused objects accumulate indefinitely.
• Garbage collection and node recycling: Describe garbage collection and node recycling as alternatives for managing lock-free nodes. Explain that recycling keeps node memory valid until the structure is destroyed but makes the ABA problem more prevalent.
  Why it matters: Keeping nodes allocated can avoid invalid-memory problems, but it does not eliminate concurrency hazards.

Key terms: lock-free memory reclamation, pending deletion, hazard pointers, reference counting, garbage collector, recycle nodes, ABA problem

7.3.3 Guideline: watch out for the ABA problem

This section explains how a compare/exchange operation can be fooled when a value changes away and back, and how a counter can detect that change.

• ABA failure sequence: Trace how a thread can read A, pause while another thread changes the atomic value to B and then back to A, and wrongly succeed at compare/exchange even though the data associated with A has changed. Explain why recycling nodes makes this problem especially likely.
  Why it matters: An equal atomic value does not necessarily mean the data you originally inspected is still valid.
• ABA counter safeguard: Describe the section's common safeguard: pair the atomic value with a counter, increment it whenever the value is replaced, and compare/exchange the value and counter as one unit.
  Why it matters: The counter lets compare/exchange detect an intervening replacement even when the value returns to A.

Key terms: ABA problem, compare/exchange, free lists, ABA counter

7.3.4 Guideline: identify busy-wait loops and help the other thread

A lock-free queue should let a thread waiting on another operation help finish it instead of wasting CPU time in a busy-wait loop.

• Helping instead of busy-waiting: Explain why a push operation that repeatedly waits for another push is effectively blocking, and how letting the waiting thread complete the unfinished steps removes that wait. Describe the queue example’s use of an atomic data member and compare/exchange to make this possible.
  Why it matters: Helping another thread complete an operation preserves progress rather than merely spinning without getting anywhere.

Key terms: busy-wait loop, blocking operation, atomic variable, compare/exchange operations

7.4 Summary

The section recaps the correctness and progress challenges of lock-free structures, then explains why their scalability and encapsulated synchronization matter to concurrent code.