12. Concurrency and Parallel Programming

Introduction and Context

Modern software rarely performs one activity in isolation. A web server may serve thousands of requests, a scientific application may process independent data sets, and an interactive desktop application must continue responding while it performs expensive computation. Concurrency and parallelism provide the conceptual and technical foundations for such systems.

Concurrency refers to the management of multiple activities whose executions overlap in time. The activities may be interleaved on a single processor or executed simultaneously on multiple processors. Parallelism is the simultaneous execution of portions of a computation, usually to reduce execution time or increase throughput. The distinction matters: a concurrent program may not be parallel, while a parallel program is necessarily concerned with concurrent activities.

C++ provides a rich concurrency library through the standard headers, including threads, mutexes, condition variables, futures, promises, atomics, and parallel algorithms. These facilities are powerful, but they also expose difficult issues. A program that works correctly in a sequential setting may fail when operations are interleaved unpredictably. Data races, deadlocks, visibility errors, starvation, and false sharing can produce failures that are intermittent and difficult to reproduce.

Effective concurrent programming therefore requires more than learning library syntax. It requires a model of execution, an understanding of the C++ memory model, disciplined ownership of shared state, and the ability to select an appropriate synchronization strategy.

Learning Objectives

After completing this chapter, the student should be able to:

1. Distinguish concurrency, parallelism, multitasking, and asynchronous execution.

2. Create and manage threads using the C++ standard library.

3. Explain data races, race conditions, atomicity, visibility, ordering, and the happens-before relationship.

4. Use mutexes, lock guards, unique locks, condition variables, semaphores, and futures appropriately.

5. Apply atomic operations and select suitable memory-ordering constraints.

6. Diagnose and prevent deadlock, livelock, starvation, and false sharing.

7. Design thread-safe classes and reason about safe ownership and lifetime.

8. Use tasks and parallel algorithms in situations where they are more suitable than explicit threads.

9. Evaluate the performance, reliability, and maintainability trade-offs of concurrent designs.

A Model of Concurrent Execution

A thread is an independently schedulable sequence of instructions within a process. Threads in the same process share its address space, including global variables and dynamically allocated objects, but each thread has its own stack, registers, and execution state. Shared address space makes communication efficient, but it also creates the possibility of conflicting access.

A concurrent program can be understood as a set of actions and possible orderings among those actions. If two actions are independent, their order may not affect the result. If they access the same mutable object, their ordering may be significant. For example, the expression `counter++` is conceptually a read followed by an addition and a write. Two threads executing it can both read the same value and subsequently overwrite one another's updates.

Parallel performance is often described by speedup:

`Speedup = sequential execution time / parallel execution time`

The ideal speedup equals the number of processing units, but real systems incur thread creation, scheduling, communication, synchronization, memory, and load-balancing costs. Amdahl's law emphasizes that a sequential fraction limits total acceleration. If a fraction `s` of a program must remain sequential, the maximum speedup on `p` processors is approximately:

`1 / (s + (1-s)/p)`

This model does not capture every practical effect, but it explains why simply adding threads does not guarantee better performance.

Threads and Their Lifetime

The basic thread facility is `std::thread` in the `<thread>` header. A thread can execute a function, lambda expression, or callable object:

```cpp

#include <thread>

#include <iostream>

void report() {

std::cout << "worker running\n";

}

int main() {

std::thread worker(report);

worker.join();

}

```

`join()` blocks the calling thread until the worker completes. A thread object must be joined or detached before it is destroyed; otherwise its destructor calls `std::terminate`. Detaching separates the thread from the controlling object, but it should be used cautiously because the detached thread may outlive objects it references. Explicit ownership and lifetime are generally safer than detached execution.

Modern C++ also provides `std::jthread`, which automatically joins on destruction and supports cooperative cancellation through stop tokens. It is often preferable for scope-bound work:

```cpp

#include <thread>

#include <chrono>

void work(std::stop_token token) {

while (!token.stop_requested()) {

// Perform one small unit of work.

std::this_thread::sleep_for(std::chrono::milliseconds(10));

}

}

int main() {

std::jthread worker(work);

// Destruction requests stopping and joins the thread.

}

```

Cancellation is cooperative, not forced. The worker must periodically inspect the token and reach a cancellation point. This design avoids abruptly terminating a thread while it holds a lock or is modifying an invariant.

Shared State, Race Conditions, and Data Races

A race condition occurs when the result depends on the relative timing of operations. Not every race condition is formally a data race, but every unsynchronized conflicting access to ordinary shared memory is dangerous in C++.

A data race occurs when two threads access the same memory location concurrently, at least one access is a write, and the accesses are not properly synchronized. In C++, a data race produces undefined behavior. This is stronger than merely obtaining an unexpected value: the compiler is permitted to assume that data races do not occur and may transform the program in ways that make its behavior unpredictable.

Consider:

```cpp

int counter = 0;

void increment() {

++counter; // unsafe when called by multiple threads

}

```

The operation is not atomic. A mutex can protect it:

```cpp

#include <mutex>

int counter = 0;

std::mutex counter_mutex;

void increment() {

std::lock_guard<std::mutex> lock(counter_mutex);

++counter;

}

```

`std::lock_guard` follows the RAII principle. It acquires the mutex during construction and releases it during destruction, including when the protected block exits through an exception. `std::unique_lock` provides more flexibility: it can be deferred, unlocked and relocked, and moved. That flexibility carries a greater responsibility to maintain correct ownership.

Thread safety can be classified in useful ways. A function is thread-compatible if it may be called concurrently only when each caller supplies separate objects. It is thread-safe if concurrent calls on shared objects are safe. It is reentrant when execution can safely be interrupted and called again, although reentrancy and thread safety are not identical. Documentation should state the intended guarantee rather than leaving clients to infer it.

The C++ Memory Model

The C++ memory model defines how evaluations in different threads relate to one another. It separates three issues that are often confused:

• Atomicity: whether an operation is indivisible with respect to other threads.
• Visibility: whether one thread can observe another thread's completed write.
• Ordering: the permitted arrangement of operations as observed by threads.

A mutex provides mutual exclusion and establishes synchronization. An unlock operation on a mutex synchronizes with a later successful lock of the same mutex. Consequently, writes made before unlocking become visible to the thread that subsequently locks it.

The memory model also defines a happens-before relationship. If operation A happens-before operation B, the effects of A are ordered before B and can be relied upon according to the language rules. Sequenced-before applies within a thread; synchronization operations connect executions across threads. Correct concurrent programs are usually designed by establishing clear happens-before relationships rather than relying on timing assumptions.

The `std::atomic` template provides indivisible operations on suitable types:

```cpp

#include <atomic>

std::atomic<int> requests{0};

void record_request() {

requests.fetch_add(1, std::memory_order_relaxed);

}

```

A relaxed atomic operation guarantees atomicity but does not establish an ordering relationship for unrelated memory. It is appropriate for independent counters when only the count matters. Stronger orders include acquire, release, and sequential consistency. A release store can publish preceding writes; an acquire load can observe those writes when it reads the corresponding value. Sequential consistency provides a single global order consistent with each thread's order, making reasoning easier but sometimes restricting optimization.

Memory ordering should be selected from a proof of the communication protocol, not from performance speculation. If the synchronization requirement is unclear, a mutex or the default sequentially consistent ordering is often a safer choice.

Mutual Exclusion and Coordination

A mutex protects an invariant: a condition that must remain true whenever the protected object is observed. Locking only individual statements is insufficient if a complete transaction requires several operations. For example, removing an item from a queue may require checking emptiness, reading the front item, and removing it as one protected operation.

When several mutexes must be acquired, inconsistent acquisition order can cause deadlock. `std::scoped_lock` can lock multiple mutexes using a deadlock-avoidance algorithm:

```cpp

std::scoped_lock lock(account_a_mutex, account_b_mutex);

transfer_balance();

```

A deadlock generally requires four conditions: mutual exclusion, hold and wait, no pre-emption, and circular wait. Prevention strategies include imposing a global lock order, acquiring all required locks together, reducing lock scope, and replacing nested locks with message passing or higher-level abstractions.

A condition variable allows a thread to sleep until a shared condition becomes true rather than repeatedly polling:

```cpp

std::mutex mutex;

std::condition_variable condition;

std::queue<int> queue;

int consume() {

std::unique_lock<std::mutex> lock(mutex);

condition.wait(lock, [] { return !queue.empty(); });

int value = queue.front();

queue.pop();

return value;

}

```

A producer modifies the queue while holding the mutex and then calls `notify_one()` or `notify_all()`. The predicate form of `wait` is essential because condition variables may experience spurious wake-ups. Notification is not the condition; the protected state is the condition.

C++20 also supplies counting semaphores, binary semaphores, latches, and barriers. A latch is a one-use countdown mechanism, useful when a group of operations must complete before continuation. A barrier supports repeated phases in which threads arrive, synchronize, and proceed together. These abstractions express intent more clearly than manually implemented counters and condition variables.

Tasks, Futures, and Asynchronous Results

Explicit threads are appropriate when long-lived execution or precise control is required. For a unit of computation that produces a result, `std::async` and futures are often simpler:

```cpp

#include <future>

std::future<long> result = std::async(std::launch::async, [] {

return expensive_calculation();

});

long value = result.get();

```

A future represents a result that may become available later. `get()` waits if necessary and transfers the result; if the asynchronous function throws, the exception is rethrown by `get()`. A promise provides the producer side of a future and is useful when a result is produced by an independently managed thread.

The launch policy matters. `std::launch::async` requests asynchronous execution, whereas the default policy may choose between deferred and asynchronous execution. Deferred execution can cause the callable to run in the thread calling `get()`. Explicit policy is preferable when execution behavior affects correctness or performance.

Tasks encourage a separation between what must be computed and how execution is scheduled. Production systems commonly use thread pools rather than creating an operating-system thread for every small task. A pool bounds resource consumption, reuses worker threads, and supports queueing and load balancing.

Designing Thread-Safe Objects

A thread-safe class should define its synchronization boundary and ownership rules. One common design protects all mutable state with one mutex. This is easy to reason about but may limit concurrency. Another design uses finer-grained locks, which can improve throughput but increases the risk of deadlock and inconsistent snapshots.

Const member functions are not automatically safe. A logically const operation may update a cache or statistics, and two concurrent readers may still conflict if the implementation mutates ordinary state. Conversely, immutable objects are naturally easier to share. Immutability, ownership transfer, thread confinement, and message passing are often preferable to sharing mutable state.

The lifetime of referenced objects is a major source of defects. Capturing a local variable by reference in a task that outlives the local scope creates a dangling reference. Similarly, a detached thread may access an object after its owner has been destroyed. Safe designs use value captures, `std::shared_ptr` where shared lifetime is genuinely required, or explicit join and cancellation protocols.

Parallel Algorithms and Data-Oriented Design

The standard algorithms library supports execution policies:

```cpp

#include <algorithm>

#include <execution>

std::sort(std::execution::par, values.begin(), values.end());

```

`std::execution::seq` requests sequential execution, `std::execution::par` permits parallel execution, and `std::execution::par_unseq` permits parallel and unsequenced execution subject to stricter requirements. A callable used in a parallel algorithm should avoid unsynchronized shared mutation, blocking synchronization, and assumptions about invocation order. The algorithm may invoke operations concurrently or in an unspecified order.

Parallelism is most effective when work is sufficiently large, independent, and balanced. Small ranges can lose performance because scheduling overhead exceeds useful computation. Data layout also matters. Contiguous data improves cache locality, while unrelated threads repeatedly modifying values on the same cache line may suffer false sharing. Padding or redesigning per-thread storage can reduce this effect.

A useful pattern is reduction: each worker computes a local result, and partial results are combined. This avoids frequent contention on one shared accumulator. The combination operation should be associative, and floating-point reductions may produce slightly different rounding results because the grouping of operations changes.

Applied Case: A Concurrent Image-Analysis Service

Background

Consider an illustrative image-analysis service that receives photographs, divides each image into regions, computes feature statistics, and stores a summary. The initial implementation creates one thread per request and increments a global counter as regions are processed.

Problem

Under load, the service exhibits inconsistent counts, occasional crashes during shutdown, and declining throughput. Investigation shows that the counter is updated without synchronization, a shared result vector is modified by all workers, and worker threads may still access a request object after the request handler returns.

Analysis

The counter update constitutes a data race. The result vector has unsynchronized concurrent mutation and may reallocate while another thread accesses it. The lifetime error arises because worker lambdas capture the request by reference. One-thread-per-request also creates excessive scheduling and memory overhead. Finally, a long-held mutex around image processing would eliminate races but serialize the expensive computation.

Strategy and Solution

The service is redesigned as follows:

1. A bounded thread pool accepts analysis tasks, preventing unbounded thread creation.

2. Each task receives an owning value or a shared immutable image object rather than a reference to a temporary request.

3. Each worker writes to a private result structure. A completion step combines results after all tasks finish.

4. The total-request statistic uses an atomic counter with relaxed ordering because it is independent telemetry, not a publication mechanism.

5. A future represents completion and transports exceptions to the request coordinator.

6. Shutdown uses cooperative cancellation and joins all workers before shared resources are destroyed.

7. Metrics distinguish queue delay, computation time, synchronization time, and failed tasks.

Outcome

The redesigned service eliminates the data races and lifetime defect while reducing synchronization contention. Its performance can be evaluated under different pool sizes rather than assumed from the number of processor cores. Correctness tests use tools such as ThreadSanitizer where available, while stress tests vary timing and workload distribution.

Learning Points

The central lesson is architectural: concurrency is easier when shared mutable state is minimized. Atomics solve specific communication problems but do not make a compound data structure safe. A thread pool manages execution resources, futures express completion and failure, and ownership rules prevent lifetime errors. Performance measurement remains necessary because more parallelism may increase contention or memory pressure.

Failure Modes, Risks, and Professional Practice

Deadlock is not the only synchronization failure. Starvation occurs when a thread repeatedly fails to obtain required resources. Livelock occurs when threads remain active but make no progress, often because they repeatedly respond to one another. Priority inversion occurs when a high-priority task waits for a lock held by a lower-priority task. Excessive lock duration causes contention, while excessive lock fragmentation makes correctness difficult to prove.

Common mistakes include protecting a check but not the subsequent action, publishing a pointer before the pointed-to object is fully initialized, using `volatile` as if it were a synchronization primitive, ignoring exceptions in worker threads, and assuming that a successful test run proves correctness. `volatile` may affect compiler interaction with special memory or hardware, but it does not provide atomicity or inter-thread synchronization.

Concurrency also has governance and ethical implications. A server that creates unbounded tasks can exhaust system resources and deny service to other users. Shared logs and telemetry may contain personal information and must follow applicable privacy and retention policies. Reproducibility is important in scientific and machine-learning systems because nondeterministic execution can change results. Systems should document synchronization assumptions, cancellation behavior, failure handling, and resource limits.

Testing should combine code review, deterministic unit tests for components, stress and soak tests, race detectors, deadlock monitoring, and production telemetry. Static analysis can identify suspicious locking and lifetime patterns, but no tool replaces a clear correctness argument.

Contemporary Developments

C++20 and later standards continue moving concurrency toward higher-level abstractions. `std::jthread` and stop tokens make cancellation and lifetime safer. Semaphores, latches, and barriers express common coordination patterns directly. Parallel algorithms expose implementation-level parallelism without requiring application code to manage every worker.

Research and industry practice increasingly emphasize structured concurrency: child tasks have well-defined lifetimes, failures propagate predictably, and a scope does not finish while its work is silently running elsewhere. Executors and senders/receivers are important directions for standard asynchronous composition, although exact facilities depend on the language standard and implementation in use. Heterogeneous systems also combine CPU threads with GPUs and other accelerators, making data movement and synchronization costs central design concerns.

Best-Practice Framework

A disciplined design process can be summarized as follows:

• Prefer local state, immutable data, ownership transfer, and message passing before introducing shared mutable state.
• Define the invariant protected by each mutex and keep lock scopes short but complete.
• Establish a lock order or use multi-lock facilities when several mutexes are required.
• Use atomics only when the communication protocol and memory ordering are understood.
• Prefer tasks, futures, pools, and structured lifetimes for ordinary asynchronous work.
• Make cancellation cooperative and ensure every resource has a clear owner.
• Measure speedup, contention, memory use, and tail latency rather than relying on thread count.
• Test under stress and use race-detection and profiling tools.

Chapter Summary

Concurrency enables overlapping activities, while parallelism uses simultaneous execution to improve throughput or reduce elapsed time. C++ supports these goals through threads, `jthread`, mutexes, condition variables, atomics, futures, promises, semaphores, barriers, latches, and parallel algorithms. Correctness depends on preventing data races and establishing appropriate happens-before relationships under the C++ memory model.

Mutexes protect invariants; RAII wrappers make lock ownership exception-safe; condition variables coordinate state changes; atomics provide specialized lock-free or low-overhead communication; and futures express asynchronous results and exception propagation. Explicit threads are not always the best abstraction: task systems and thread pools usually manage resource limits more effectively. Good designs minimize shared mutable state, control object lifetime, prevent deadlock, support cancellation, and validate performance through measurement and testing.

Key Terms

Concurrency: The overlapping management of multiple activities.

Parallelism: Simultaneous execution of computational activities.

Thread: An independently schedulable execution sequence within a process.

Data race: Conflicting unsynchronized accesses to the same memory location, producing undefined behavior in C++.

Race condition: Behavior whose result depends on the timing or ordering of concurrent operations.

Atomic operation: An indivisible operation on a shared object.

Mutex: A mutual-exclusion synchronization object protecting shared state.

RAII: Resource Acquisition Is Initialization; ownership is tied to object lifetime.

Condition variable: A mechanism allowing threads to sleep until a state predicate may be satisfied.

Happens-before: A memory-model relationship that establishes ordering between evaluations.

Memory ordering: Rules governing visibility and ordering of atomic operations.

Future: An object representing a result that may become available later.

Promise: A producer-side object used to supply a future's result or exception.

Deadlock: Permanent waiting caused by circular or otherwise incompatible resource dependencies.

Starvation: Indefinite postponement because a thread cannot obtain required resources.

Livelock: Repeated activity without meaningful progress.

False sharing: Performance degradation caused by independent variables sharing a cache line.

Thread pool: A bounded collection of reusable worker threads executing queued tasks.

Structured concurrency: A model in which task lifetimes, completion, and failure are scoped and explicitly managed.

Review Questions

Short Answer Questions

1. Distinguish concurrency from parallelism.

2. Why is `counter++` unsafe when performed concurrently on an ordinary integer?

3. What guarantee does a relaxed atomic operation provide, and what does it not provide?

4. Why should a condition-variable wait normally test a predicate?

5. State two advantages of using `std::jthread` over an unmanaged detached thread.

Long Answer Questions

1. Explain the C++ memory model using atomicity, visibility, ordering, and happens-before relationships.

2. Compare `std::mutex`, `std::lock_guard`, `std::unique_lock`, and `std::scoped_lock` in terms of purpose and flexibility.

3. Discuss the causes of deadlock and develop a design strategy for preventing it in a multi-resource system.

4. Explain how futures, promises, `std::async`, and thread pools support task-based concurrency.

5. Analyze the design principles required for a thread-safe class with mutable shared state.

Analytical / Application Questions

1. A program uses an atomic counter with relaxed ordering to count completed jobs, while another thread reads a separately stored result buffer after observing the counter. Is relaxed ordering sufficient? Explain what synchronization is required.

2. Design a producer-consumer queue for a bounded system. Identify its invariant, synchronization operations, shutdown behavior, and response to spurious wake-ups.

3. A parallel algorithm is slower than its sequential version for small input ranges and produces slightly different floating-point totals on each run. Analyze the causes and propose improvements or acceptable policies.

22. Multiple Choice Questions with Answers

Question 1

Which statement best distinguishes concurrency from parallelism?

A. Concurrency always requires multiple processors, while parallelism does not.

B. Concurrency concerns overlapping activities; parallelism concerns simultaneous execution.

C. Concurrency applies only to I/O, while parallelism applies only to computation.

D. They are identical terms in the C++ standard.

Correct Answer: B. Concurrency concerns overlapping activities; parallelism concerns simultaneous execution.

Question 2

What happens when two threads increment the same ordinary int without synchronization?

A. The compiler automatically makes the increment atomic.

B. The final value is guaranteed to equal the number of increments.

C. The program has a data race and its behavior is undefined.

D. The operation is safe if the increment is a single source-code statement.

Correct Answer: C. The program has a data race and its behavior is undefined.

Question 3

Why is the predicate form of condition_variable::wait recommended?

A. It prevents the mutex from ever being released.

B. It handles spurious wake-ups and checks whether the required state exists.

C. It converts the condition variable into an atomic object.

D. It guarantees that notification cannot be missed under any design.

Correct Answer: B. It handles spurious wake-ups and checks whether the required state exists.

Question 4

Which facility is most appropriate for automatically joining a scope-bound thread and supporting cooperative cancellation?

A. std::jthread

B. std::promise

C. std::atomic_flag

D. std::condition_variable_any

Correct Answer: A. std::jthread

Question 5

A relaxed atomic counter is appropriate when the counter is used only for independent telemetry because it provides:

A. Atomicity without ordering unrelated memory operations.

B. A complete lock on every object accessed by the thread.

C. Guaranteed visibility of all preceding non-atomic writes.

D. A total ordering stronger than sequential consistency.

Correct Answer: A. Atomicity without ordering unrelated memory operations.

Question 6

Which practice most directly prevents deadlock when two mutexes are needed by several operations?

A. Acquire them in a globally consistent order or use std::scoped_lock.

B. Detach every thread before acquiring either mutex.

C. Replace both mutexes with volatile variables.

D. Hold the first mutex indefinitely so another thread cannot interfere.

Correct Answer: A. Acquire them in a globally consistent order or use std::scoped_lock.

Question 7

Why can a thread pool improve a one-thread-per-request server?

A. It eliminates the need for synchronization.

B. It bounds resource use and reuses worker threads for queued tasks.

C. It guarantees every task runs simultaneously.

D. It makes all shared objects immutable automatically.

Correct Answer: B. It bounds resource use and reuses worker threads for queued tasks.

Question 8

What is false sharing?

A. Two threads intentionally sharing an immutable object.

B. A cache-related performance problem caused by independent data on one cache line.

C. A compiler error caused by two variables having the same name.

D. A deadlock caused by recursive mutex acquisition.

Correct Answer: B. A cache-related performance problem caused by independent data on one cache line.

Question 9

Which statement about std::async with the default launch policy is correct?

A. It always creates a new operating-system thread immediately.

B. It always executes synchronously before returning a future.

C. The implementation may choose asynchronous or deferred execution.

D. It cannot transport exceptions to the caller.

Correct Answer: C. The implementation may choose asynchronous or deferred execution.

Question 10

In the image-analysis case, why were private per-worker results preferable to one shared result vector?

A. They eliminate the need to combine results.

B. They reduce synchronization and avoid concurrent mutation of one container.

C. They guarantee perfect load balancing regardless of input.

D. They make every operation lock-free by definition.

Correct Answer: B. They reduce synchronization and avoid concurrent mutation of one container.