7 Designing lock-free concurrent data structures

In the last chapter we looked at general aspects of designing data structures for concurrency, with guidelines for thinking about the design to ensure they’re safe. We then examined several common data structures and looked at example implementations that used mutexes and locks to protect the shared data. The first couple of examples used one mutex to protect the entire data structure, but later ones used more than one to protect various smaller parts of the data structure and allow greater levels of concurrency in accesses to the data structure.

7.1   Definitions and consequences

7.1.1   Types of nonblocking data structures

7.1.2   Lock-free data structures

7.1.3   Wait-free data structures

7.1.4   The pros and cons of lock-free data structures

7.2   Examples of lock-free data structures

7.2.1   Writing a thread-safe stack without locks

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

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

7.2.4   Detecting nodes in use with reference counting

7.2.5   Applying the memory model to the lock-free stack

7.2.6   Writing a thread-safe queue without locks

7.3   Guidelines for writing lock-free data structures

7.3.1   Guideline: use std::memory_order_seq_cst for prototyping

7.3.2   Guideline: use a lock-free memory reclamation scheme

7.3.3   Guideline: watch out for the ABA problem

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

7.4   Summary