Concurrency & Parallelism in Software

A process is the OS's unit of isolation. It has its own virtual address space, file descriptor table, signal handlers, and security context. When you fork a process, the OS gives the child a copy of the parent's memory (via copy-on-write pages). Inter-process communication (IPC) — pipes, sockets, shared memory — must cross this isolation boundary explicitly. The isolation is the whole point: a bug in one process cannot corrupt another's memory.

A thread is the OS's unit of execution within a process. Threads share the process's address space — the heap, global variables, file descriptors, and code segment are all shared. Each thread has only its own stack, stack pointer, program counter, and register file. Creating a thread is cheaper than forking a process (no address space copy, typically 10–100× less overhead), and communication between threads is trivially fast (they read and write the same memory). The price is that the isolation is gone: a thread that writes to the wrong address can corrupt another thread's stack.

In the Linux kernel (and POSIX generally), both processes and threads are implemented as tasks — clone() is the underlying system call for both. fork() is clone() with no sharing flags; pthread_create() is clone() with sharing flags for memory, file descriptors, and signal handlers. This unification is elegant and worth knowing.

The GIL (Global Interpreter Lock) in CPython is a famous complication: even with multiple OS threads, CPython allows only one thread to execute Python bytecode at a time, releasing the GIL only during I/O and C extension calls. For CPU-bound parallelism in Python, multiprocessing (separate processes) or NumPy/C extensions are required. This is why Python's concurrent.futures.ProcessPoolExecutor exists.

import os, threading

# Fork: child gets a COPY of parent's memory
pid = os.fork()
if pid == 0:
    x = 99  # child modifies its own copy — parent's x is unchanged
    os._exit(0)

# Thread: shares the same memory
results = []
def worker():
    results.append(42)  # modifies the SHARED list

t = threading.Thread(target=worker)
t.start()
t.join()
print(results)  # [42]

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 enforcing an ordering between them. Data races are undefined behavior in C/C++ (the compiler may produce any output) and produce non-deterministic results in every language.

The classic example is incrementing a shared counter. counter++ looks atomic but compiles to three machine instructions: LOAD the value into a register, ADD 1, STORE back. If two threads interleave these operations, one increment can be silently lost. This is called a lost update.

The correct mental model is the happens-before relation from Leslie Lamport (1978), formalized in the C++11 and Java memory models. A memory model defines which writes are guaranteed to be visible to which reads. Without explicit synchronization, the compiler and CPU are allowed to reorder instructions, keep values in registers, and use cache-coherent but non-sequentially-consistent memory orders. A data race breaks the memory model and takes you outside the language's guarantees entirely.

Thread sanitizer (TSan) is a compile-time/runtime instrumentation tool (available in GCC and Clang) that detects data races reliably by tracking memory accesses. Always run TSan on concurrent code during testing.

// C — classic lost-update data race
#include <pthread.h>
#include <stdio.h>
static long counter = 0;

void *increment(void *arg) {
    for (int i = 0; i < 1000000; i++)
        counter++;  // NOT atomic: LOAD, ADD, STORE
    return NULL;
}

int main() {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, increment, NULL);
    pthread_create(&t2, NULL, increment, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("%ld\n", counter);  // Prints ~1,100,000 — not 2,000,000!
}

The fundamental solution to data races is mutual exclusion: ensuring that at most one thread executes the critical section — the code that accesses shared state — at a time. The hardware primitive enabling this is the test-and-set or compare-and-swap (CAS) atomic instruction, which reads a memory location and writes a new value in a single, non-interruptible machine instruction.

Built on top of these hardware primitives, a mutex (mutual exclusion lock) is the workhorse synchronization object. A mutex is either locked or unlocked. lock() atomically acquires it (blocking if already held); unlock() releases it. The OS scheduler parks blocked threads in a wait queue, avoiding busy-waiting.

The monitor pattern (used in Java's synchronized, Python's with lock:, and Rust's Mutex<T>) wraps both the lock and the protected data, making it syntactically hard to access the data without holding the lock. Rust goes further: its borrow checker statically prevents data races at compile time, making them impossible by construction.

Lock granularity matters enormously. A single global lock on a hash table (coarse-grained) eliminates races but serializes all operations. Per-bucket locks (fine-grained) allow operations on different buckets to proceed in parallel. The extreme is lock-free data structures, discussed later.

RAII (Resource Acquisition Is Initialization) is the C++ and Rust pattern where a lock object's destructor automatically releases the lock when it goes out of scope, preventing the common bug of forgetting to unlock on an early return or exception.

import threading

counter = 0
lock = threading.Lock()

def safe_increment():
    global counter
    with lock:          # RAII: automatically releases on exit
        counter += 1    # critical section: only one thread at a time

threads = [threading.Thread(target=safe_increment) for _ in range(1000)]
for t in threads: t.start()
for t in threads: t.join()
print(counter)  # Always exactly 1000

Deadlock is the situation where a set of threads are each waiting for a resource held by another thread in the set, forming a cycle of dependencies that no thread can break. The four Coffman conditions (1971) are necessary and sufficient for deadlock:

1. Mutual exclusion: at least one resource is held in a non-sharable mode.
2. Hold and wait: a thread holds a resource while waiting for another.
3. No preemption: resources cannot be forcibly taken; a thread must release them voluntarily.
4. Circular wait: there is a circular chain T1→R1→T2→R2→T1.

Breaking any one of these four conditions prevents deadlock. In practice, the most common prevention strategy is lock ordering: impose a global total order on all locks and always acquire them in that order. If all threads acquire lock A before lock B, a cycle is impossible.

Livelock is a subtler pathology: threads keep changing state in response to each other but make no progress — like two people in a hallway each stepping aside to let the other pass, indefinitely. Livelock requires randomized back-off or priority mechanisms to resolve.

Starvation occurs when a thread can in principle make progress but is perpetually denied the CPU or a lock because other threads always get scheduled first. Priority scheduling with aging (gradually increasing the priority of waiting threads) is the standard remedy.

Deadlock detection is used in databases: the system maintains a wait-for graph where an edge T1→T2 means T1 is waiting for a lock held by T2. A cycle in this graph signals deadlock; the database kills one transaction (the victim) to break the cycle.

import threading, time

lock_a = threading.Lock()
lock_b = threading.Lock()

def thread1():
    with lock_a:         # acquires A
        time.sleep(0.01) # simulates work
        with lock_b:     # waits for B — but thread2 holds B!
            pass

def thread2():
    with lock_b:         # acquires B
        time.sleep(0.01)
        with lock_a:     # waits for A — deadlock!
            pass

# FIX: always acquire locks in the same global order (a then b)
def thread1_fixed():
    with lock_a:
        with lock_b:   # consistent order
            pass

def thread2_fixed():
    with lock_a:       # consistent order — acquires A first
        with lock_b:
            pass

A semaphore (Dijkstra, 1965) is a generalized synchronization primitive: an integer S that supports two atomic operations, traditionally called P (probeer, Dutch for try — decrements S, blocks if S=0) and V (verhoog, increment — increments S, wakes a blocked thread). A binary semaphore (S ∈ {0,1}) behaves like a mutex. A counting semaphore (S ≥ 0) controls access to a pool of k identical resources (e.g., a bounded buffer with k slots).

Semaphores are powerful enough to implement any synchronization pattern, but they are error-prone: a missing V leaves threads blocked forever; a double P causes deadlock. The classical textbook uses semaphores to prove and solve the producer-consumer, readers-writers, and dining philosophers problems.

Condition variables are a higher-level primitive designed to work alongside a mutex. A condition variable lets a thread atomically release a mutex and block on a condition, and be woken when another thread signals that the condition may now be true. The critical pattern is always to check the condition in a while loop (not an if), because of spurious wakeups — the OS may wake a thread for reasons unrelated to your signal, and another thread may have consumed the resource between the wakeup and re-acquisition of the lock.

The standard idiom in POSIX:

// consumer:
pthread_mutex_lock(&m);
while (queue_empty()) pthread_cond_wait(&cv, &m);  // atomically releases m
item = dequeue();
pthread_mutex_unlock(&m);

// producer:
pthread_mutex_lock(&m);
enqueue(item);
pthread_cond_signal(&cv);  // wake one waiter
pthread_mutex_unlock(&m);

import threading
from collections import deque

buffer = deque()
MAX = 5
lock = threading.Lock()
not_full  = threading.Condition(lock)
not_empty = threading.Condition(lock)

def producer(item):
    with not_full:
        while len(buffer) >= MAX:
            not_full.wait()   # releases lock, blocks
        buffer.append(item)
        not_empty.notify()    # wake a consumer

def consumer():
    with not_empty:
        while not buffer:
            not_empty.wait()  # releases lock, blocks
        item = buffer.popleft()
        not_full.notify()     # wake a producer
        return item

For simple operations — incrementing a counter, publishing a pointer — taking a full mutex lock is costly (a system call, a context switch if contended). Atomic operations are hardware instructions that execute as a single, indivisible step with memory-order guarantees, without requiring a lock.

The key primitive is compare-and-swap (CAS): atomically, if *ptr == expected, set *ptr = desired and return true; otherwise return false. CAS is the foundation of all lock-free algorithms. A lock-free increment looks like:

do {
    expected = atomic_load(&counter);
    desired  = expected + 1;
} while (!atomic_compare_exchange_weak(&counter, &expected, &desired));

This is an optimistic concurrency pattern: we speculatively compute the new value and commit only if no one else changed the data under us. Under low contention, this is far faster than a mutex. Under high contention, CAS loops spin and waste CPU — a problem called contention.

Memory ordering is the subtlest part. Modern CPUs and compilers reorder instructions for performance. C++11 and Java define explicit memory orders:

• relaxed: no ordering guarantees (just atomicity).
• acquire/release: pairs that establish happens-before across threads.
• seq_cst (sequentially consistent): strongest — a global total order; the default in most languages.

ABA problem: a CAS sees value A, another thread changes it to B then back to A; the CAS succeeds even though the state has changed. Solutions include tagged pointers (adding a version counter), or hazard pointers.

Lock-free vs. wait-free: lock-free guarantees system-wide progress (at least one thread always makes progress). Wait-free guarantees per-thread bounded progress (every thread completes in a bounded number of steps). Wait-free algorithms are notoriously complex and only needed in real-time systems.

#include <stdatomic.h>
#include <stdio.h>

atomic_long counter = 0;

// Lock-free increment via CAS loop
void atomic_increment(void) {
    long expected, desired;
    do {
        expected = atomic_load_explicit(&counter, memory_order_relaxed);
        desired  = expected + 1;
    } while (!atomic_compare_exchange_weak_explicit(
                &counter, &expected, &desired,
                memory_order_release,   // success order
                memory_order_relaxed)); // failure order
}

// Simpler: atomic_fetch_add is a single instruction on x86
void fast_increment(void) {
    atomic_fetch_add_explicit(&counter, 1, memory_order_relaxed);
}

Creating and destroying OS threads for every task is expensive — each thread has a kernel object, 1–8 MB of stack, and scheduling overhead. A thread pool amortizes this cost: a fixed set of worker threads are created once, and tasks (functions + arguments) are placed into a shared work queue. Workers continuously dequeue tasks and execute them, then loop back for more.

The Executor abstraction (Java's ExecutorService, Python's concurrent.futures.Executor, C++'s forthcoming std::execution) decouples submission from execution. You submit a callable and get back a Future — a handle to a computation that may not have completed yet. You can get() the future to block until the result is ready, or attach a callback.

Choosing pool size: a common heuristic is N = number of CPU cores for CPU-bound work (so every core is busy without wasted context switches), and N = (number of cores) × (1 + wait ratio) for I/O-bound work, where wait ratio is the fraction of time spent blocked. Brian Goetz's Java Concurrency in Practice contains a precise derivation.

Work stealing: sophisticated thread pools (Java's ForkJoinPool, Go's goroutine scheduler) give each worker its own double-ended queue (deque). A worker pushes and pops from one end (LIFO, cache-friendly). Idle workers steal from the other end of a busy worker's deque (FIFO). This minimizes contention on the shared queue and keeps all cores busy when tasks spawn sub-tasks recursively — the backbone of parallel divide-and-conquer.

from concurrent.futures import ThreadPoolExecutor, as_completed
import urllib.request

URLs = [
    "https://example.com",
    "https://python.org",
    "https://github.com",
]

def fetch(url):
    with urllib.request.urlopen(url, timeout=5) as r:
        return url, len(r.read())

# 4 workers; tasks submitted to the internal work queue
with ThreadPoolExecutor(max_workers=4) as pool:
    futures = {pool.submit(fetch, u): u for u in URLs}
    for f in as_completed(futures):
        url, size = f.result()  # blocks until this future is done
        print(f"{url}: {size} bytes")

Thread-per-connection server architectures break down at ~10,000 simultaneous connections (the C10K problem) because each thread consumes ~1 MB of stack memory and context switching overhead grows. The alternative is event-driven / async programming: a single OS thread runs an event loop that multiplexes thousands of I/O operations using OS primitives like epoll (Linux), kqueue (macOS/BSD), or IOCP (Windows).

The event loop works as follows:

1. Register interest in I/O events (socket readable, timer expired, etc.).
2. Block in epoll_wait() until at least one event fires — this is a single, efficient syscall.
3. Dispatch the callbacks registered for those events.
4. Repeat.

The coroutine is the programming model that makes this ergonomic. A coroutine is a function that can be suspended at an await expression, yielding control back to the event loop while waiting for I/O, and resumed when the I/O completes — without a thread context switch. Python's async def / await, JavaScript's async/await, Rust's async/await, and Go's goroutines (which are coroutines scheduled by the Go runtime) all implement this idea.

The crucial insight: async does not make individual operations faster. A single HTTP request takes the same wall-clock time whether you use threads or async. Async wins when you have many concurrent I/O-bound operations on one thread, avoiding the memory and scheduling overhead of many OS threads. For CPU-bound work, async is counterproductive — it keeps the CPU on one thread while a task burns cycles.

Colored functions (the "function color" problem by Bob Nystrom): in Python/JS, async functions are "colored" differently from regular functions — they can only be await-ed from other async functions, and calling them from sync code requires asyncio.run(). This viral coloring is a known ergonomic drawback.

import asyncio, aiohttp

async def fetch(session, url):
    async with session.get(url) as response:
        # 'await' suspends this coroutine, yields to event loop
        # resumes when response headers are ready
        body = await response.read()
        return url, len(body)

async def main():
    urls = ["https://example.com", "https://python.org"]
    async with aiohttp.ClientSession() as session:
        # asyncio.gather schedules all coroutines concurrently
        # on the SAME thread — no OS thread creation
        results = await asyncio.gather(
            *[fetch(session, u) for u in urls]
        )
    for url, size in results:
        print(f"{url}: {size} bytes")

asyncio.run(main())

Recognizing which pattern your parallel problem fits is more than half the battle. Three patterns cover most cases:

Map-Reduce (Dean & Ghemawat, Google 2004): split a collection into chunks, apply a function independently to each chunk (map), then combine the partial results (reduce). Embarrassingly parallel — zero inter-worker communication during the map phase. Ideal for data-parallel batch processing. multiprocessing.Pool.map() is a single-machine implementation; Hadoop/Spark are distributed implementations.

Fork-Join (the Cilk model): a task can fork (spawn) subtasks, do its own work, then join (wait for) all subtasks. Recursive algorithms — merge sort, quicksort, tree traversals, matrix multiply — fall naturally into this pattern. Java's ForkJoinPool and RecursiveTask, Python's concurrent.futures with recursive submission, and OpenMP's #pragma omp parallel for all implement fork-join. Work stealing (see Thread Pools) is the canonical scheduler for fork-join.

Pipeline: decompose a computation into stages connected by bounded queues. Each stage runs in its own thread, reading from its input queue and writing to its output queue. Like an assembly line. Useful when stages have varying speeds (naturally buffered) and when data must be processed in order. Compilers (lex → parse → semantic analysis → codegen) and multimedia pipelines are canonical examples.

A key concept: Amdahl's Law upper-bounds the speedup from parallelism. If fraction f of a program is serial (cannot be parallelized), then with N processors the maximum speedup is 1/(f + (1−f)/N). As N→∞, speedup → 1/f. A program that is 50% serial cannot be sped up by more than 2×, regardless of how many cores you add. Gustafson's Law provides a more optimistic view: as problem size scales with N, the serial fraction often shrinks, giving near-linear speedup in practice for data-parallel workloads.

from multiprocessing import Pool
import math

def is_prime(n):
    if n < 2: return False
    for i in range(2, int(math.isqrt(n)) + 1):
        if n % i == 0: return False
    return True

# MAP: each worker independently checks a range of numbers
# REDUCE: collect results in the main process
if __name__ == "__main__":
    numbers = range(10_000_000, 10_001_000)
    with Pool() as pool:               # forks one process per CPU core
        results = pool.map(is_prime, numbers)  # map phase
    primes = [n for n, p in zip(numbers, results) if p]  # reduce
    print(f"Found {len(primes)} primes")

Many data structures have a natural asymmetry: reads can proceed concurrently (they do not modify state), but writes require exclusive access. A plain mutex serializes both reads and writes, leaving performance on the table when reads dominate.

The readers-writers lock (RWLock) formalizes this: multiple readers can hold the lock simultaneously; a writer requires exclusive access (no readers, no other writers). There are two classical variants:

• Readers-preference: new readers can always sneak in, potentially starving writers.
• Writers-preference: once a writer is waiting, new readers are queued behind it, preventing writer starvation.

Python's threading.RLock is a recursive mutex (same thread can acquire multiple times); a true RWLock is in concurrent.futures or third-party packages. C++ 17 has std::shared_mutex with std::shared_lock (readers) and std::unique_lock (writers).

RWLocks are appropriate when reads are far more frequent than writes and the critical section is non-trivial in duration. For very short critical sections (a few nanoseconds), the overhead of the RWLock itself can dominate — a plain mutex with fast code can be faster.

Seqlocks (sequence locks, used in the Linux kernel for timekeeping) are an alternative: a writer increments a sequence counter before and after writing; a reader reads the counter before and after the data, and retries if the counters differ (write in progress). Writers never block; readers may retry. This is extremely fast for frequently-read, rarely-written small values.

import threading

class RWLock:
    """Simple readers-preference RWLock using two mutexes."""
    def __init__(self):
        self._read_lock  = threading.Lock()
        self._write_lock = threading.Lock()
        self._readers    = 0

    def acquire_read(self):
        with self._read_lock:
            self._readers += 1
            if self._readers == 1:   # first reader blocks writers
                self._write_lock.acquire()

    def release_read(self):
        with self._read_lock:
            self._readers -= 1
            if self._readers == 0:   # last reader unblocks writers
                self._write_lock.release()

    def acquire_write(self):
        self._write_lock.acquire()   # exclusive

    def release_write(self):
        self._write_lock.release()

A memory model is the contract between the programmer and the hardware+compiler about which writes are visible to which reads and in what order. Without such a contract, you cannot reason about concurrent code at all.

The key relation is happens-before (HB) (Lamport, 1978). Write W happens-before read R means: if W HB R and no other write to the same variable HB R, then R is guaranteed to see the value written by W. HB is established by:

1. Program order: within a single thread, each statement HB the next.
2. Synchronization: mutex.unlock() HB the next mutex.lock() on the same mutex. thread.join() HB everything after it in the joining thread. sem_post() HB the subsequent sem_wait().
3. Transitivity: if A HB B and B HB C, then A HB C.

If two accesses to the same variable (with at least one write) have no HB relationship, there is a data race — undefined behavior in C/C++, a programming error in Java/Go.

Sequential consistency (SC) is the strongest useful memory model: the result of any execution is as if all operations were in some sequential order that respects each thread's program order. Most programmers implicitly assume SC. Modern hardware does not guarantee SC by default — x86 guarantees total store order (TSO), which is close; ARM and POWER are much more relaxed. The C++11 seq_cst fence forces SC behavior at the cost of expensive memory barriers.

The practical takeaway: always use proper synchronization (mutexes, atomics with appropriate ordering, channels). Never "optimize" by dropping synchronization and hoping the hardware will do the right thing — it will not, on all platforms, under all compilers.

// C++11 memory model: acquire-release semantics
#include <atomic>
#include <thread>

std::atomic<int>  data{0};
std::atomic<bool> ready{false};

void producer() {
    data.store(42, std::memory_order_relaxed);
    // release: all prior stores visible to thread that acquires
    ready.store(true, std::memory_order_release);
}

void consumer() {
    // acquire: sees all stores that preceded the release
    while (!ready.load(std::memory_order_acquire))
        ;  // spin
    // guaranteed to see data == 42 (happens-before via acq/rel pair)
    assert(data.load(std::memory_order_relaxed) == 42);
}

Go represents the state of the art in language-integrated concurrency. Its model is based on CSP (Communicating Sequential Processes) (Hoare, 1978): instead of sharing memory, concurrent entities communicate by passing messages through channels. Go's mantra: "Do not communicate by sharing memory; instead, share memory by communicating."

A goroutine is a lightweight green thread managed by the Go runtime. Creating a goroutine is go f() — a single keyword. Goroutines are multiplexed onto a small number of OS threads by the Go scheduler (M:N scheduling). They start with ~2 KB stacks that grow and shrink dynamically, supporting millions of concurrent goroutines.

A channel ch := make(chan int, k) is a typed, synchronized queue of capacity k (0 = unbuffered). Sending ch <- v blocks until a receiver is ready (unbuffered) or the buffer has space. Receiving v := <-ch blocks until a sender sends. Buffered channels act as semaphores counting free slots.

select is the most powerful concurrency construct in Go: it simultaneously waits on multiple channel operations and executes the first one that is ready. This is the idiomatic way to implement timeouts, cancellation, and fan-in patterns.

However, Go does not prevent shared memory races — the sync.Mutex and sync/atomic packages exist and are used extensively in the standard library. The Go race detector (go run -race) is the go-to tool for finding races.

package main

import "fmt"

func producer(ch chan<- int, n int) {
    for i := 0; i < n; i++ {
        ch <- i     // blocks if channel full
    }
    close(ch)      // signal: no more values
}

func consumer(ch <-chan int, done chan<- struct{}) {
    for v := range ch {  // receives until channel closed
        fmt.Println(v)
    }
    done <- struct{}{}
}

func main() {
    ch   := make(chan int, 10)  // buffered channel
    done := make(chan struct{})
    go producer(ch, 100)
    go consumer(ch, done)
    <-done  // wait for consumer to finish
}