Concurrency Models

Before studying solutions, we must understand exactly what can go wrong. A data race occurs when two threads access the same memory location concurrently, at least one access is a write, and there is no synchronization between them. The result is undefined — not just unpredictable, but genuinely undefined by the language specification, which means the compiler and hardware are free to do anything.

Consider a bank account with balance = 100. Thread A reads the balance (100), thread B reads the balance (100), thread A writes balance + 50 = 150, thread B writes balance + 30 = 130. The final balance is 130, not 180. Fifty dollars evaporated. This is a lost update, the canonical race condition.

But races are even subtler than this example suggests. Modern CPUs reorder instructions for performance. Each core has its own cache, and writes may not be immediately visible to other cores. The memory model of a language or architecture defines exactly which reorderings are permitted and what guarantees a program has about visibility. Java's Memory Model (JMM) and C++11's memory model both distinguish sequentially consistent execution (the gold standard: all operations appear in some single global order) from weaker models that allow reorderings for performance.

The critical section is the region of code that accesses shared state and must execute atomically with respect to other threads. The classical tools — mutexes, semaphores, condition variables — serialize access to critical sections. But serialization is a performance bottleneck: while one thread holds the lock, all others wait. The concurrency models in this module are, at heart, different answers to the question: how can we structure programs so that the need for explicit locks is minimized or eliminated?

# Python: a canonical race condition (run with threading)
import threading

balance = 0

def deposit(amount, n):
    global balance
    for _ in range(n):
        # NOT atomic: read, add, write are three separate ops
        balance = balance + amount

t1 = threading.Thread(target=deposit, args=(1, 100_000))
t2 = threading.Thread(target=deposit, args=(1, 100_000))
t1.start(); t2.start()
t1.join();  t2.join()
print(balance)  # Should be 200000, but often isn't
# Fix: use a threading.Lock() around balance = balance + amount

Shared-memory concurrency is the model closest to the hardware. Threads live in the same address space and communicate by reading and writing shared variables. The dominant synchronization primitive is the mutex (mutual exclusion lock): before entering a critical section, a thread acquires the lock; after leaving, it releases it. Only one thread can hold a mutex at a time.

A monitor packages a mutex with the shared data it protects and one or more condition variables, enabling threads to wait for a condition (e.g., 'queue is non-empty') and to signal waiting threads when the condition changes. This is the basis of Java's synchronized blocks and Object.wait()/notify().

Locks suffer from three classical hazards:

1. Deadlock: Thread A holds lock L1 and waits for L2; thread B holds L2 and waits for L1. Both wait forever. Prevention: always acquire locks in a global order.
2. Livelock: Threads continuously change state in response to each other without making progress — like two people in a hallway who keep stepping the same way.
3. Priority inversion: A low-priority thread holds a lock needed by a high-priority thread. The Mars Pathfinder mission famously hit this bug in 1997.

Beyond these hazards, fine-grained locking is hard to get right. The more locks you introduce to reduce contention, the more complex the invariants you must maintain. Lock-free and wait-free data structures use hardware atomic operations (compare-and-swap, fetch-and-add) to eliminate locks entirely, but their correctness proofs are notoriously difficult.

Despite these challenges, shared-memory remains the foundation of most systems software — the Linux kernel, JVM internals, database engines — because it is efficient (no copying of data) and maps directly to what CPUs do.

// C++: mutex protecting a shared counter
#include <mutex>
#include <thread>

std::mutex mtx;
int balance = 0;

void deposit(int amount, int n) {
    for (int i = 0; i < n; ++i) {
        std::lock_guard<std::mutex> lock(mtx); // RAII: releases on scope exit
        balance += amount;
    }
}

int main() {
    std::thread t1(deposit, 1, 100000);
    std::thread t2(deposit, 1, 100000);
    t1.join(); t2.join();
    // balance is guaranteed to be 200000
}

Message-passing concurrency takes the opposite philosophical stance from shared memory: don't share data; instead, send copies of data between isolated processes. This is Rob Pike's famous Go proverb: "Do not communicate by sharing memory; instead, share memory by communicating."

Communicating Sequential Processes (CSP), invented by Tony Hoare in 1978, is the theoretical foundation. CSP models concurrent computation as a collection of sequential processes that synchronize by communicating on named channels. A channel is a typed conduit: a sender blocks until a receiver is ready (synchronous, or rendezvous, communication), and vice versa. This synchronization-by-communication replaces mutual exclusion as the core primitive.

Go implements a practical version of CSP with goroutines (lightweight cooperatively-scheduled threads, typically 2–8 KB stack, vs. megabytes for OS threads) and channels. Channels can be buffered (asynchronous up to capacity) or unbuffered (synchronous). The select statement lets a goroutine wait on multiple channels simultaneously, taking the first one that is ready.

The key insight is that no data is shared: each goroutine owns its local state, and values sent on channels are conceptually passed by value (or by transferring ownership). This makes the concurrency structure explicit in the program's communication topology, rather than hidden in which variables are accessed where.

Process calculi like CSP and the pi-calculus (which extends CSP with dynamic channel creation and mobility) provide formal semantics for message-passing programs, enabling mathematical proofs of deadlock-freedom and behavioral equivalence. This is the algebraic beauty of the CSP world.

// Go: pipeline pattern — three stages connected by channels
package main

import "fmt"

func generate(nums ...int) <-chan int {
    out := make(chan int)
    go func() {
        for _, n := range nums { out <- n }
        close(out)
    }()
    return out
}

func square(in <-chan int) <-chan int {
    out := make(chan int)
    go func() {
        for n := range in { out <- n * n }
        close(out)
    }()
    return out
}

func main() {
    c := generate(2, 3, 4, 5)
    out := square(square(c))  // composed pipeline
    for v := range out {
        fmt.Println(v)  // 16, 81, 256, 625
    }
}

The Actor model, introduced by Carl Hewitt in 1973 and later independently developed by Agha, models computation as a collection of actors — the fundamental units of concurrent computation. Each actor has:

• A mailbox (message queue)
• Local private state (not accessible by any other actor)
• A behavior function: given a message, what to do next (including: update state, create new actors, send messages)

Critically, actors never share state. All interaction is via asynchronous message passing to actor addresses (references). This makes actors inherently safe: no locks are needed because no data is shared.

Erlang (designed for telecom at Ericsson in the 1980s) built an entire ecosystem around this model. Erlang processes are incredibly lightweight (~300 bytes), and a single machine can run millions of them. The 'let it crash' philosophy combined with supervision trees provides fault tolerance: if an actor fails, its supervisor detects this and restarts it. WhatsApp ran 2 million simultaneous connections per server with this model.

The difference between the Actor model and CSP is subtle but important:

• CSP channels are first-class; processes are identified by channels, not by identity. Communication is synchronous (rendezvous) by default. The structure of the program is its channel topology.
• Actor model actors are first-class; they have addresses (references). Communication is asynchronous. Actors can dynamically discover and message each other.

In CSP, the channel is the locus of synchronization. In the Actor model, the actor's mailbox is. This difference has deep implications for reasoning about ordering and deadlock.

Scala's Akka and Elixir (running on the BEAM/Erlang VM) are prominent modern incarnations. The actor model maps naturally to microservices architectures, where each service is logically an actor.

# Elixir (Erlang VM): a simple counter actor
defmodule Counter do
  # Spawn an actor with initial state
  def start(initial), do: spawn(fn -> loop(initial) end)

  defp loop(count) do
    receive do  # block waiting for a message
      {:increment, by} ->
        loop(count + by)       # recurse with new state
      {:get, sender} ->
        send(sender, count)    # reply to sender
        loop(count)
    end
  end
end

pid = Counter.start(0)
send(pid, {:increment, 5})
send(pid, {:increment, 3})
send(pid, {:get, self()})
receive do n -> IO.puts(n) end  # prints 8

Software Transactional Memory takes inspiration from database transactions and applies it to in-memory concurrent programming. The idea: wrap a block of code in a transaction. The STM runtime executes it optimistically — without acquiring any locks — while logging all reads and writes to a transaction log. When the transaction commits, the runtime checks whether any memory location read during the transaction has been written by another transaction since the read (the conflict check). If not, the writes are committed atomically. If conflict is detected, the transaction is rolled back and retried.

The result is atomicity and isolation (the ACI of ACID) for arbitrary memory operations, without the programmer ever acquiring a lock. This eliminates entire classes of bugs: no deadlock (no locks to deadlock on), no priority inversion, no forgotten unlocks.

Haskell's STM library (in the Control.Concurrent.STM module) is the canonical production implementation, using Haskell's type system to enforce that transactional code (STM a) cannot perform arbitrary I/O — you cannot print inside a transaction, because the transaction might be retried multiple times. This is a beautiful example of using types to capture semantic constraints.

retry is STM's killer feature: if a transaction discovers a precondition is not met (e.g., a queue is empty), it can call retry, which blocks the current thread until any variable read in the transaction changes, then retries automatically. This replaces condition variables entirely.

orElse provides an alternative: if the first transaction retries, try the second. This enables composable blocking operations — a remarkable feature impossible with locks.

STM's weakness is performance: the transaction log has overhead, and high-conflict workloads cause many retries. It shines for low-to-medium contention with complex invariants — exactly the case where lock-based code is most error-prone.

-- Haskell STM: bank transfer with retry
import Control.Concurrent.STM

type Account = TVar Int

transfer :: Account -> Account -> Int -> STM ()
transfer from to amount = do
  bal <- readTVar from
  if bal < amount
    then retry  -- block until 'from' balance changes, then retry
    else do
      writeTVar from (bal - amount)
      modifyTVar to (+ amount)

-- Usage (in IO monad):
main :: IO ()
main = do
  alice <- atomically $ newTVar 100
  bob   <- atomically $ newTVar 50
  atomically $ transfer alice bob 30
  -- atomically: commit or roll back as a unit, never partial
  a <- readTVarIO alice  -- 70
  b <- readTVarIO bob    -- 80

Async/await is a different concurrency model that targets I/O-bound rather than CPU-bound parallelism. The insight: most web server time is spent waiting — for a database query, a network response, a file read. A thread blocked on I/O wastes its OS thread, which is expensive (megabytes of stack, kernel scheduler overhead). If instead we could suspend a computation while it waits and resume it when the I/O completes, we could handle many concurrent operations with far fewer threads.

This is cooperative multitasking: tasks voluntarily yield control at await points. An event loop (like Python's asyncio or Node.js's libuv) manages a queue of ready tasks and a set of pending I/O operations. When a task awaits something, it is suspended and the event loop runs another task. When the I/O completes (detected via OS mechanisms like epoll/kqueue), the suspended task is made ready and eventually resumed.

A function marked async returns a coroutine (Python) or a Promise/Future (JavaScript) — a first-class object representing a computation that may not yet have a value. await expr means: "if expr is not yet done, suspend me here and resume me when it is." This is syntactic sugar over continuation-passing style: the code after the await is packaged into a callback, but you write it as straight-line code.

The crucial limitation: async/await is cooperative, not preemptive. A CPU-bound task that never awaits will block the event loop, starving all other tasks. This is why Python, JavaScript, and Rust's async ecosystems recommend offloading CPU work to thread pools. Async does not give you parallelism; it gives you concurrency. For CPU-bound tasks you still need threads or processes.

Rust's async/await is particularly elegant: futures are zero-cost abstractions compiled to state machines with no heap allocation or runtime overhead, making async Rust competitive with hand-written callback code.

# Python asyncio: concurrent HTTP requests without threads
import asyncio
import aiohttp

async def fetch(session, url):
    async with session.get(url) as resp:  # suspends here while waiting
        return await resp.text()           # suspends here while reading body

async def main():
    urls = [
        "https://example.com",
        "https://httpbin.org/delay/1",
        "https://httpbin.org/delay/1",
    ]
    async with aiohttp.ClientSession() as session:
        # asyncio.gather runs all coroutines CONCURRENTLY
        # Total time ≈ max(latencies), not sum
        results = await asyncio.gather(*[fetch(session, u) for u in urls])
    return results

# asyncio.run(main())
# One thread, three concurrent requests, ~1s total instead of ~3s

No single concurrency model is best in all situations. Each makes different tradeoffs across correctness, performance, expressiveness, and fault tolerance.

Shared-memory with locks is the fastest and most hardware-natural model. Use it for:

• Tight inner loops where cache locality matters
• Systems programming (kernel code, device drivers, databases)
• When you need fine-grained control over memory layout
• When the concurrent data structure is small and well-understood

CSP / channels shine when:

• The program has a natural pipeline or dataflow structure
• You want to reason about communication topology statically
• Goroutines in Go: cheap, structured, with select for fan-in
• You want synchronization-as-communication rather than explicit locks

Actor model is optimal for:

• Large-scale distributed systems (Erlang/Elixir in telecom, messaging)
• Fault-tolerant services where independent failure domains matter
• Systems where the number of concurrent entities is huge (millions)
• When location transparency (local vs. remote actor) is valuable

STM excels when:

• You have complex invariants across multiple shared variables
• Conflict rate is low to moderate
• You want composable atomic operations (orElse is not possible with locks)
• Correctness matters more than peak throughput

Async/await is the right tool for:

• I/O-bound concurrency: web servers, API clients, scrapers
• Environments with expensive threads (Python GIL, browser JS)
• When you want structured concurrency (async with nurseries in Trio/Python)
• Rust: when zero-overhead async matters (embedded, high-frequency trading)

A mature system often combines models: Go uses goroutines + channels for most work but sync.Mutex for hot paths; Erlang actors occasionally use ETS (in-memory shared tables with STM-like semantics); Python uses async/await for the network layer and multiprocessing for CPU-bound workers.

Concurrency bugs come in two families: safety violations (something bad happened, like a data race) and liveness violations (something good never happened, like a deadlock).

Deadlock occurs when a set of processes are each waiting for a resource held by another in the set, forming a cycle. The classical necessary conditions (Coffman, 1971): mutual exclusion, hold-and-wait, no preemption, and circular wait. Eliminating any one condition prevents deadlock. Practical strategies:

• Lock ordering: always acquire locks in a global total order — breaks circular wait
• Timeout and backoff: release locks and retry if waiting too long
• Resource allocation graphs: detect cycles at runtime (used by database systems)

Livelock is subtler: processes are active but making no progress, like two people in a hallway who keep mirroring each other's moves.

Starvation: a process that is perpetually denied a resource it needs, often because other processes are always prioritized.

Formal tools for reasoning about concurrency:

• Temporal Logic (LTL, CTL): express properties like "process A always eventually receives a response" and model-check them automatically
• TLA+ (Leslie Lamport): a specification language used at AWS, Microsoft, and Intel to verify distributed protocols. Has found bugs in published algorithms.
• Session Types: a type system for communication protocols. A typed channel enforces a protocol (e.g., "send an int, then receive a bool"), making protocol violations a compile-time error.
• Linearizability: the gold standard for concurrent data structures. An operation is linearizable if it appears to take effect instantaneously at some point between its invocation and completion. It is the formal definition of "behaves like a sequential object".
• Happens-before (Lamport, 1978): a partial order on events in a concurrent system. Event A happens-before B if A causally precedes B. Memory models are defined in terms of happens-before.

// Deadlock example and the lock-ordering fix
// Two threads, two locks — classic ABBA deadlock pattern

// DEADLOCK version:
void transfer_unsafe(Account& from, Account& to, int amt) {
    lock(from.mutex);       // Thread 1 locks A first
    lock(to.mutex);         // Thread 2 locked B first -> deadlock!
    from.balance -= amt;
    to.balance   += amt;
    unlock(to.mutex);
    unlock(from.mutex);
}

// SAFE version: always lock in address order
void transfer_safe(Account& from, Account& to, int amt) {
    Account* first  = (&from < &to) ? &from : &to;
    Account* second = (&from < &to) ? &to   : &from;
    lock(first->mutex);
    lock(second->mutex);
    from.balance -= amt;
    to.balance   += amt;
    unlock(second->mutex);
    unlock(first->mutex);
}

Classical concurrency — spawning threads or goroutines freely — has a problem: scope. When you spawn a goroutine, it escapes the calling function's scope. The caller returns while the child runs in the background, errors are silently lost, and cancellation becomes an afterthought. This is the concurrent equivalent of goto: powerful but structurally dangerous.

Structured concurrency, a concept formalized by Nathaniel Smith (Trio, 2018) and adopted in Python (asyncio TaskGroup, PEP 654), Kotlin (coroutines structured concurrency), and Swift (async let), imposes a discipline: a task's lifetime is always bounded by the scope of a nursery (task group). You open a nursery with async with, spawn tasks inside it, and the nursery does not exit until all child tasks have completed (or been cancelled). This is the structured equivalent of sequential composition: just as f(); g() means g starts after f ends, a nursery block means the code after the block runs only after all spawned tasks end.

The benefits are profound:

• Automatic cancellation: if one task fails, the nursery cancels all siblings and re-raises the error
• Error propagation: exceptions from child tasks propagate to the parent scope
• No orphaned tasks: leaking a background task is a type error, not a silent bug
• Comprehensible lifetimes: the control flow of a concurrent program becomes a tree, not a graph

This is analogous to how structured programming (if/for/while) tamed goto in the 1960s. Structured concurrency is likely the future default for async programming.

# Python 3.11+ TaskGroup (structured concurrency)
import asyncio

async def fetch_one(url: str) -> str:
    await asyncio.sleep(0.1)  # simulate I/O
    return f"result from {url}"

async def main():
    results = []
    # TaskGroup: all tasks MUST finish before the 'async with' block exits.
    # If any task raises, all siblings are cancelled and the exception
    # propagates out of the 'async with' block.
    async with asyncio.TaskGroup() as tg:
        tasks = [
            tg.create_task(fetch_one(f"https://example.com/{i}"))
            for i in range(5)
        ]
    # Here we are guaranteed all 5 tasks are done (or an exception was raised)
    results = [t.result() for t in tasks]
    print(results)

asyncio.run(main())