Locks, Atomics, Lock-Free Systems and High-Performance Concurrent Software
- Introduction
Chapter 1: Concurrency vs Parallelism: Defining the Problem
- What Concurrency Actually Means
- Concurrency Without Parallelism
- The Cost of Getting It Wrong
- Why Modern Hardware Demands Concurrency
- The Trade-off Landscape
Chapter 2: Processes, Threads and the Operating System
- The Unix Process Model
- Kernel Threads and User Threads
- Context Switching and Its True Cost
- Scheduling Policies and Predictability
- M:N Thread Models and Goroutines
Chapter 3: Inside the CPU: Cores, Caches and Coherence
- CPU Cores and Hardware Threads
- The Memory Hierarchy and Cache Lines
- MESI and Cache Coherence Protocols
- NUMA Architectures and Their Consequences
- Memory Buses and Interconnect Latencies
Chapter 4: False Sharing, Contention and Cache Thrashing
- The Anatomy of False Sharing
- Detecting False Sharing in Practice
- Memory Allocation Under Concurrency
- Cache Thrashing and Its Symptoms
- Designing for Cache-Line Awareness
Chapter 5: How CPUs Reorder Memory Access
- Why CPUs Reorder Instructions
- The x86-64 Memory Model
- ARM and Weakly Ordered Architectures
- Compiler Reordering vs Hardware Reordering
- What This Means for Correct Code
Chapter 6: The Happens-Before Relation
- Defining Happens-Before
- Program Order and Sequential Execution
- Synchronization Order and Atomic Operations
- Visibility Guarantees and Their Limits
- Reasoning About Correctness with Happens-Before
Chapter 7: Consistency Models: From Sequential to Linearizable
- Sequential Consistency and Its Promise
- Why Sequential Consistency Is Expensive
- Linearizability and Its Real-Time Guarantees
- Relaxed Consistency and When It Is Safe
- Choosing the Right Consistency Model
Chapter 8: Atomic Primitives and Memory Ordering
- Atomicity and What It Actually Guarantees
- Sequentially Consistent Atomics
- Acquire and Release Semantics
- Relaxed Atomics and Their Danger Zones
- Memory Fences and Barrier Instructions
Chapter 9: Compare-and-Swap and Read-Modify-Write Operations
- How Compare-and-Swap Works
- CAS at the Hardware Level
- Fetch-and-Add and Other RMW Operations
- The ABA Problem in Detail
- Tagged Pointers and Version Counters
Chapter 10: Language-Level Memory Models: C/C++, Java, Rust, Go
- The C11/C++11 Memory Model
- Java’s Happens-Before Semantics
- Rust’s Approach to Concurrency
- Go’s Simpler Memory Guarantees
- Mapping Between Language Models
Chapter 11: Progress Guarantees and Fairness
- What It Means for a System to Make Progress
- Lock-Based (Blocking) Algorithms
- Lock-Free Algorithms
- Wait-Free Algorithms
- Fairness and Starvation
- Priority Inversion
- Deadlock, Livelock and Starvation
- Choosing Progress Guarantees
Chapter 12: Mutexes and Futexes
- What a Mutex Actually Does
- Futexes: How Modern Mutexes Work
- Spinlocks
- Recursive Mutexes
- Mutex Performance and Scalability
Chapter 13: Read-Write Locks, Barriers and Condition Variables
- Read-Write Locks
- Condition Variables
- Barriers
- Semaphores
- Monitors
- When to Use Which Primitive
Chapter 14: Specialized Locks: Ticket Locks, MCS Locks and Seqlocks
- Why Specialized Locks Exist
- Ticket Locks
- MCS Locks
- Q-locks and CLH Locks
- Seqlocks
- Choosing a Lock for High Contention
Chapter 15: Lock-Free Programming Fundamentals
- When Lock-Free Is Worth It
- The CAS Loop Pattern
- Lock-Free vs Wait-Free vs Blocking
- ABA in Lock-Free Structures
- Memory Ordering in Lock-Free Code
Chapter 16: Reference Counting and Atomic Pointers
- Why Reference Counting Matters in Concurrency
- Atomic Reference Counting
- Optimized Reference Counting
- Control Blocks and Shared State
- Reference Counting and Lock-Free Structures
Chapter 17: Lock-Free Stacks, Queues and Ring Buffers
- The Treiber Stack
- The Michael-Scott Queue
- Single-Producer Single-Consumer Ring Buffer
- Multi-Producer Multi-Consumer Ring Buffer
- When to Use Which Structure
Chapter 18: Memory Reclamation: Hazard Pointers, EBR and RCU
- The Memory Reclamation Problem
- Hazard Pointers
- Epoch-Based Reclamation (EBR)
- RCU (Read-Copy-Update)
- Comparing Memory Reclamation Techniques
Chapter 19: Concurrent Hash Maps and Scalable Data Structures
- Why Hash Maps Are Hard in Concurrency
- Lock-Striped Hash Map
- Java’s ConcurrentHashMap
- C++ and the Lack of Standard Concurrent Containers
- Immutable and Copy-on-Write Maps
- When to Use Which Approach
Chapter 20: Diagnosing Data Races and Visibility Bugs
- Why Data Races Are Insidious
- Symptoms of Data Races
- ThreadSanitizer (TSan)
- Java ThreadSanitizer Alternatives
- Rust’s Compile-Time Prevention
- Go’s Race Detector
- Lockset Algorithms
- Static Analysis for Races
- Best Practices for Race Detection
Chapter 21: Debugging Deadlocks, Livelocks and Starvation
- Deadlock Detection in Production
- Thread Dump Analysis
- Deadlock Detection Algorithms
- Preventing Deadlock
- Livelock Detection
- Starvation Detection
- Tools for Debugging Liveness Bugs
Chapter 22: Concurrency Testing and Verification
- Why Normal Testing Is Not Enough
- Stress Testing
- Property-Based Testing for Concurrency
- Model Checking
- Deterministic Concurrency Testing
- Fuzzing for Concurrency Bugs
- Verification for Lock-Free Algorithms
- Testing Checklist
Chapter 23: Performance Profiling and Analysis
- Measuring What Matters
- Flame Graphs for Concurrent Code
- Per-Thread and Per-Core Analysis
- Cache Performance Analysis
- Lock Contention Analysis
- Context Switch and Scheduler Analysis
- Tools Summary
Chapter 24: Benchmarking Methodology for Concurrent Systems
- Why Benchmarking Concurrent Code Is Hard
- Controlling Environmental Variables
- Measuring Distributions, Not Averages
- Scalability Testing
- Avoiding Benchmark Artifacts
- Comparing Synchronization Strategies
- Benchmarking Checklist
Chapter 25: Concurrency Design Patterns and Trade-Offs
- Thread Pools
- Work Stealing
- Futures and Promises
- Message Passing and Channels
- Sharding and Partitioning
- Choosing the Right Pattern
Chapter 26: Production Architectures and Case Studies
- High-Throughput Web Servers
- Database Concurrency: MVCC and Latching
- Redis: Single-Threaded with Clustering
- Kafka: Partitioned Log with Concurrent Consumers
- Go Runtime: M:N Scheduling
- Lessons from Production
Chapter 27: Advanced Topics and Language-Specific Patterns
- C++ Concurrency Best Practices
- Rust Concurrency Best Practices
- Go Concurrency Best Practices
- Java Concurrency Best Practices
- Real-Time and Safety-Critical Concurrency
- Emerging Trends
Chapter 28: Design Principles and Anti-Patterns
- Principles for Reliable Concurrent Systems
- Common Anti-Patterns
- Decision Framework
- The Lock-Free Decision
- Final Wisdom
Chapter 29: Conclusion: Building Production-Ready Concurrent Systems
- The Journey from Fundamentals to Production
- The Hierarchy of Concurrency Solutions
- Correctness Before Performance
- Embracing Complexity Responsibly
- The Role of Hardware
- A Lasting Perspective
- References