Learn Concurrent and Parallel Programming: Best Books
This curriculum is designed for expert-level engineers who already understand systems programming and want to master concurrent and parallel programming from the ground up — covering threading primitives and locks, then advancing to lock-free data structures, memory models, async runtimes, and finally large-scale multicore and distributed design. Each stage sharpens a distinct layer of the concurrency stack, with later stages building directly on the mental models and vocabulary established earlier.
Threads, Locks, and the Classical Model
IntermediateSolidify a rigorous, low-level understanding of POSIX threads, mutexes, condition variables, semaphores, and classical synchronization patterns — the vocabulary every later stage assumes.
▸ Study plan for this stage
Pace: 8–10 weeks, ~40–50 pages/day (Butenhof first: ~6 weeks for core chapters 1–7; Downey second: ~2–3 weeks for all chapters)
- POSIX thread lifecycle: creation, attributes, joining, detachment, and cancellation semantics
- Mutex fundamentals: mutual exclusion, lock acquisition/release, deadlock, and priority inversion
- Condition variables: signaling, waiting, spurious wakeups, and the wait-notify pattern
- Semaphores: binary and counting variants, initialization, and their role as synchronization primitives
- Classical synchronization problems: producer-consumer, reader-writer, dining philosophers, and barrier patterns
- Memory visibility and happens-before relationships in concurrent code
- Lock ordering, resource allocation graphs, and deadlock prevention strategies
- Semaphore-based solutions to classical problems and their correctness proofs
- What is the difference between a detached thread and a joinable thread, and when should you use each?
- Explain why condition variables require a mutex and what problem spurious wakeups create.
- How do binary and counting semaphores differ, and what synchronization problems is each suited for?
- What are the four necessary conditions for deadlock, and which ones can be broken to prevent it?
- Describe the producer-consumer problem and how to solve it using mutexes and condition variables.
- What is the difference between a semaphore and a mutex, and why can't a semaphore always replace a mutex?
- How does the reader-writer problem differ from producer-consumer, and what additional synchronization challenges does it present?
- Implement a thread-safe queue using POSIX mutexes and condition variables; test with multiple producers and consumers to verify no data loss or deadlock occurs.
- Write a program that creates N threads, each incrementing a shared counter 1,000,000 times without synchronization, then with a mutex; measure and explain the performance difference.
- Solve the classic dining philosophers problem using semaphores; verify your solution prevents deadlock by running it for extended periods with multiple philosophers.
- Implement a barrier synchronization primitive using mutexes and condition variables; test that all threads block until the barrier count is reached.
- Create a reader-writer lock using semaphores and mutexes; verify that multiple readers can proceed concurrently while writers have exclusive access.
- Build a bounded buffer (circular queue) with separate semaphores for empty slots and full slots; test with varying producer/consumer speeds to confirm correctness.
Next up: This stage establishes the foundational vocabulary and mental models (threads, locks, signaling, classical patterns) that all advanced concurrency topics—lock-free programming, memory models, distributed consensus, and higher-level abstractions—build upon and often optimize around.
The definitive reference on pthreads; establishes precise mental models for thread lifecycle, synchronization primitives, and cancellation that underpin everything else in this curriculum.
Works through classical synchronization puzzles (dining philosophers, readers-writers, etc.) systematically, building strong intuition for reasoning about correctness before moving to harder models.
Memory Models and the Hardware Reality
ExpertUnderstand CPU memory models, cache coherence, reordering, and the C++ and Java memory models — the physical foundation that explains why lock-free programming is hard.
▸ Study plan for this stage
Pace: 4–5 weeks, ~40–50 pages/day, focusing on Chapters 5–6 of "C++ Concurrency in Action" (Memory Models and Synchronization Primitives)
- CPU memory hierarchies: L1/L2/L3 caches, main memory, and how they affect visibility of writes across threads
- Cache coherence protocols (MESI/MOESI) and their role in maintaining consistency across cores
- Memory reordering: compiler optimizations and CPU out-of-order execution that violate sequential consistency
- Happens-before relationships and synchronizes-with semantics as the foundation of the C++ memory model
- Atomic operations and memory ordering guarantees (memory_order_relaxed, acquire-release, sequential consistency)
- The distinction between data races, race conditions, and well-defined concurrent behavior
- Why lock-free programming requires explicit memory ordering: the cost of implicit synchronization vs. explicit ordering
- Practical implications: false sharing, cache line alignment, and performance consequences of memory model choices
- Explain how a write to a variable on one CPU core becomes visible to another core, and why this visibility is not instantaneous
- What is the difference between a data race and a race condition, and why does the C++ standard make data races undefined behavior?
- Describe the memory ordering guarantees provided by memory_order_acquire, memory_order_release, and memory_order_seq_cst, and give an example where each is necessary
- Why can a compiler or CPU reorder memory operations, and what does a happens-before relationship prevent?
- What is false sharing, how does it degrade performance, and how can you mitigate it?
- Explain why a simple spin-lock without explicit memory ordering is broken, and what memory ordering it needs to be correct
- Write a simple multi-threaded program that demonstrates a data race (e.g., two threads incrementing a shared counter), compile with and without optimizations, and observe how the compiler reorders operations using assembly inspection (objdump or godbolt.org)
- Implement a broken spin-lock without memory ordering, then fix it by adding memory_order_acquire/release to atomic loads and stores; measure the performance difference and explain why the fix is necessary
- Create a false-sharing example: two threads each incrementing their own counter on the same cache line vs. on different cache lines; measure and explain the performance gap
- Write a producer-consumer pattern using std::atomic with different memory orderings (relaxed, acquire-release, sequential consistency) and verify correctness with ThreadSanitizer (tsan); document the performance trade-offs
- Analyze the assembly output of a simple atomic operation (e.g., std::atomic<int> x; x.load(memory_order_acquire)) on your target architecture to understand what CPU instructions enforce the ordering guarantee
- Implement a simple lock-free queue using atomic operations with explicit memory ordering; test it with multiple producers and consumers, and document which orderings are necessary at each synchronization point
Next up: This stage provides the theoretical and practical foundation for understanding why lock-free data structures work (or fail), preparing you to design and reason about lock-free algorithms and patterns in the next stage.
The canonical reference for the C++11/14/17/20 memory model, atomics, and the happens-before relation; read after McKenney to see how the hardware model maps to a portable language model.
Lock-Free and Wait-Free Data Structures
ExpertDesign and analyze lock-free stacks, queues, hash maps, and other structures using atomics and CAS; understand progress guarantees (obstruction-free, lock-free, wait-free) and the ABA problem.
▸ Study plan for this stage
Pace: 6–8 weeks, ~40–50 pages/day (focusing on Chapters 9–11 and selected sections from Part III of "The Art of Multiprocessor Programming")
- Compare-and-swap (CAS) as the fundamental atomic primitive and its role in lock-free algorithms
- Progress guarantees: obstruction-free, lock-free, and wait-free definitions and their practical implications
- The ABA problem and detection strategies (versioning, hazard pointers, epoch-based reclamation)
- Lock-free stack design using CAS: Treiber's stack and its correctness proof
- Lock-free queue design: Michael-Scott queue and handling of head/tail pointer races
- Lock-free hash map construction: open addressing, chaining, and resizing challenges
- Memory ordering and visibility guarantees: sequential consistency vs. acquire-release semantics
- Performance analysis of lock-free vs. lock-based structures under contention
- What is the ABA problem and why does it occur in lock-free algorithms? Describe at least two techniques to detect or prevent it.
- Compare and contrast obstruction-free, lock-free, and wait-free progress guarantees. Which is strongest and why?
- Explain how Treiber's stack works and prove that it is lock-free. What happens if CAS fails?
- Describe the Michael-Scott queue algorithm. Why is managing the tail pointer more complex than the head pointer?
- How do hazard pointers work to solve the ABA problem and memory reclamation in lock-free structures?
- What are the trade-offs between lock-free and lock-based data structures in terms of performance, complexity, and scalability?
- Implement Treiber's lock-free stack in your language of choice (C++, Java, or Rust) using atomic CAS operations; test it under high contention with multiple threads.
- Implement the Michael-Scott lock-free queue and verify correctness by running concurrent push/pop operations; measure throughput vs. a mutex-based queue.
- Manually trace through the ABA problem scenario in a lock-free stack: show how versioning (e.g., tagged pointers) prevents the issue.
- Design and implement a simple lock-free hash map using open addressing and CAS; handle collisions and measure performance under read-heavy and write-heavy workloads.
- Write a detailed analysis comparing the progress guarantees of three data structures: a mutex-protected list, Treiber's stack, and a wait-free queue; include pseudocode and correctness arguments.
- Implement memory reclamation for a lock-free linked list using epoch-based reclamation or hazard pointers; verify that no memory leaks occur under concurrent access.
Next up: This stage equips you with the theoretical foundations and practical skills to design scalable concurrent data structures; the next stage will likely extend these techniques to real-world systems (e.g., concurrent memory allocators, lock-free logging, or specialized domain structures) and explore advanced synchronization patterns beyond simple atomics.
The definitive academic text on concurrent data structures and synchronization theory; covers linearizability, consensus numbers, and a full catalog of lock-free algorithms with formal proofs.
Async, Futures, and Modern Runtime Models
ExpertMaster asynchronous programming models — event loops, futures/promises, async/await, and work-stealing schedulers — and understand how they relate to and differ from thread-based concurrency.
▸ Study plan for this stage
Pace: 8–10 weeks, ~40–50 pages/day. Start with Java Concurrency in Practice (weeks 1–5: ~300 pages covering threads, locks, and task execution), then Programming Rust (weeks 6–10: ~250 pages on async/await, futures, and runtime models).
- Thread-based concurrency fundamentals: threads, locks, monitors, and memory visibility (from Java Concurrency in Practice)
- Task execution frameworks and thread pools: ExecutorService, work queues, and thread lifecycle management
- Futures and promises as abstractions for deferred computation and composability
- Event-driven and async/await models: how they differ from thread-per-task approaches and reduce context-switching overhead
- Rust's ownership and borrow checker as enablers of safe concurrent code without garbage collection
- Work-stealing schedulers and task-based parallelism: efficient work distribution and load balancing
- Bridging thread-based and async models: when to use each, trade-offs in latency, throughput, and resource consumption
- Runtime models: green threads, OS threads, and async runtimes (tokio, async-std) in Rust
- What are the key differences between thread-based concurrency and event-driven async models, and when is each appropriate?
- How do futures and promises enable composable asynchronous computation, and what advantages do they offer over callback-based approaches?
- Explain how Java's ExecutorService and thread pools manage task execution, and contrast this with Rust's async/await and work-stealing schedulers.
- What role does Rust's ownership system play in enabling safe concurrent code, and how does this differ from Java's approach with locks and memory visibility?
- How do work-stealing schedulers improve performance in task-parallel workloads, and what trade-offs exist compared to thread-pool-based execution?
- What is the relationship between event loops, async runtimes, and OS scheduling, and how do they affect latency and throughput characteristics?
- Implement a thread pool executor in Java using ExecutorService; submit tasks with varying latencies and measure throughput and context-switch overhead.
- Build a multi-threaded producer-consumer system in Java using BlockingQueue and demonstrate synchronization, memory visibility, and deadlock avoidance.
- Write a Java program that uses Future and CompletableFuture to compose asynchronous operations; compare callback-based and future-based approaches side-by-side.
- Implement an async HTTP client in Rust using tokio or async-std; fetch multiple URLs concurrently and measure latency improvements over sequential execution.
- Create a work-stealing task scheduler simulation in Rust: spawn tasks with variable work, implement work-stealing logic, and benchmark against a simple queue-based scheduler.
- Port a multi-threaded Java application to async Rust using futures and async/await; document the refactoring process and compare resource usage (memory, CPU, latency).
Next up: This stage equips you with deep understanding of both thread-based and async concurrency models, positioning you to explore advanced topics like lock-free data structures, distributed systems coordination, and reactive programming frameworks that build on these foundations.
Bridges classical locking with higher-level concurrency utilities (Executor, ForkJoinPool, futures); essential for understanding task-based parallelism before studying async runtimes.
Rust's ownership model enforces data-race freedom at compile time; this book's concurrency and async chapters show how a modern language encodes the memory-model rules from Stage 2 into the type system.
Multicore Architecture and Large-Scale Parallel Design
ExpertSynthesize everything into system-level multicore design: NUMA awareness, scalable algorithms, parallel patterns, and performance engineering on real hardware.
▸ Study plan for this stage
Pace: 8–10 weeks, ~40–50 pages/day with 2–3 days/week for hands-on labs
- Structured parallel programming patterns (task, data, and pipeline parallelism) and when to apply each
- NUMA architecture awareness: memory locality, affinity, and cost of remote memory access in multicore systems
- MPI (Message Passing Interface) for distributed-memory parallelism and process-level scalability
- OpenMP for shared-memory parallelism, work distribution, synchronization, and thread-level optimization
- Scalable algorithm design: identifying bottlenecks, load balancing, and minimizing communication overhead
- Performance engineering on real hardware: profiling, tuning, and adapting code to specific multicore topologies
- Hybrid parallelism: combining MPI and OpenMP for large-scale systems with multiple sockets and many cores per socket
- Parallel design patterns and their implementation trade-offs across different hardware platforms
- How do you choose between task, data, and pipeline parallelism for a given problem, and what are the trade-offs?
- Explain NUMA and why memory affinity matters in multicore systems; how would you optimize a program for NUMA?
- What is the difference between MPI and OpenMP, and when would you use each or both together?
- How do you identify and eliminate communication bottlenecks in a parallel program?
- Describe the process of profiling a parallel program and translating performance data into concrete optimizations
- How do you design a scalable algorithm that maintains efficiency as you increase the number of cores or nodes?
- Implement a data-parallel matrix multiplication using OpenMP; measure speedup and identify load-balancing issues
- Write a task-parallel quicksort using OpenMP tasks; compare performance against a sequential version and a data-parallel sort
- Implement a distributed-memory version of a reduction operation (e.g., sum or max) using MPI; test on 4, 8, and 16 processes
- Create a hybrid MPI+OpenMP program that solves a stencil computation (e.g., 2D Jacobi iteration); profile memory access patterns and optimize for NUMA
- Profile a parallel program using tools like perf, VTune, or TAU; identify hotspots and implement targeted optimizations
- Design and implement a pipeline-parallel algorithm (e.g., image processing pipeline) using OpenMP; measure throughput and latency
Next up: This stage equips you with the architectural understanding and hands-on skills to design and optimize real-world parallel systems; the next stage will likely focus on specialized domains (GPU computing, distributed systems, or advanced performance analysis) or real-world case studies that apply these patterns at scale.
Presents a pattern-based approach (map, reduce, scan, pipeline, stencil) for writing portable, scalable parallel programs; ties algorithmic thinking to hardware topology.
Grounds multicore and distributed parallelism in concrete, measurable implementations; a practical capstone that connects the theoretical and systems knowledge built across all prior stages.
Discussion
Keep reading
Paths that share books, cover the same subject, or open a related topic.
