Concurrent and Parallel Programming

Choose a model based on CPU work, I/O, runtime behavior, memory isolation, and platform.

11.1 Concurrency versus parallelism

Concurrency: multiple tasks are in progress during overlapping time periods.

Parallelism: multiple tasks execute at the same instant, often on different cores.

A program can be concurrent without running in parallel.

Parallelism is useful for independent computation but adds coordination and overhead.

11.2 Threads and processes

Thread: execution path within a process; threads commonly share process memory.

Process: separate execution environment with its own address space, subject to operating-system facilities.

Task/future: abstraction representing work and its eventual result.

Worker pool: bounded set of workers used to control resource consumption.

Choose a model based on CPU work, I/O, runtime behavior, memory isolation, and platform.

11.3 Race conditions

A race occurs when behavior depends on an uncontrolled ordering of operations. A data race is a more specific condition involving conflicting concurrent memory accesses without adequate synchronization in models that define it.

Conceptual example:

Without synchronization, one update can overwrite the other. Use a lock, atomic operation, transaction, or single-owner message model depending on the system.

Try it: provoke the lost update The race-condition lab below (shared with the Concurrency & Async Programming course) lets you choose which thread runs each step, then explores every possible schedule. With no protection, most schedules lose an update; a mutex or an atomic operation removes the bad outcomes.

shared_balance = 100

Thread A: read balance; add 10; write balance
Thread B: read balance; subtract 20; write balance

11.4 Locks and deadlocks

A mutex protects a critical section. Deadlock can occur when tasks wait cyclically for resources.

Prevention techniques:

Establish a consistent lock ordering.

Hold locks for short periods.

Avoid calling unknown callbacks while holding a lock.

Use timeouts or cancellation where appropriate.

Prefer higher-level concurrent collections or message passing.

Document lock ownership and invariants.

11.5 Atomic operations and memory ordering

Atomic operations prevent selected operations from being observed as partially updated and may establish ordering guarantees. Memory ordering is subtle: acquire/release and sequential consistency have different guarantees. Use language documentation and established synchronization patterns rather than inventing low-level lock-free algorithms without a strong reason.

11.6 Parallel map/reduce

This code is sequential Python. A parallel implementation would distribute independent mapping work across workers and combine results. Parallel overhead can exceed benefits for small inputs; shared mutable state and non-associative reductions can cause incorrect results.

# Conceptual example: map each independent item, then combine results.
squared = [x * x for x in values]
total = sum(squared)

11.7 Structured concurrency

Structured concurrency organizes concurrent tasks within a lexical or logical scope, making cancellation, failure propagation, and lifetime easier to reason about. APIs vary by language. Prefer task groups or equivalent structured mechanisms when available.

11.8 Distributed concurrency

Distributed systems add network delays, partial failures, duplicate delivery, clock differences, and uncertain outcomes. Do not assume a timeout means an operation did not occur. Use idempotency, durable state, correlation IDs, retries with backoff, and explicit consistency semantics.

11.9 Common concurrency patterns

Thread/task pools Reader–writer locks Futures and promises Barriers and latches Actor/message passing Immutable shared data Bulkheads and bounded work queues Producer–consumer with a bounded queue

Text equivalent: producers add work to a queue with a fixed capacity and consumers remove it. When the queue is full the producer must wait, drop work or receive an error — that is backpressure. The lab below lets you change the rates, the capacity and the policy (a simulation; the numbers are a model, not a benchmark).

flowchart LR
  P1[Producer 1] -->|put| Q[(Bounded queue: capacity N)]
  P2[Producer 2] -->|put| Q
  Q -->|get| C1[Consumer 1]
  Q -->|get| C2[Consumer 2]
  Q -.->|full: block, drop or reject| P1

Exercise

Implement a producer–consumer queue with bounded capacity. Define shutdown behavior, backpressure, cancellation, and tests for full/empty queue conditions.

Quiz

? A program interleaves two tasks on a single core. Is it concurrent, parallel, or both?
+ Concurrent, but not parallel. :: Progress overlaps in time, but nothing runs at the same instant.
- Parallel, but not concurrent. :: One core cannot execute two tasks at the same instant.
- Both. :: Parallelism needs simultaneous execution.
- Neither. :: Overlapping progress is concurrency.

? Which techniques help prevent deadlock? (select all that apply)
+ A consistent global lock order :: A wait cycle cannot form.
+ Holding locks briefly and not calling unknown callbacks while holding them :: Reduces the chance of nested acquisition.
+ Timeouts or cancellation :: A waiter can give up.
- Adding more threads :: More threads do not remove cycles.

? Why might a parallel map/reduce give a wrong total?
+ The reduction is not associative, or workers share mutable state. :: Both break the assumption that partial results can be combined in any order.
- Parallel code always returns the same result as sequential code. :: Only if the reduction is associative and there is no shared mutation.
- Because Python lists are immutable. :: Python lists are mutable.
- Because map must run before filter. :: Ord
…