Concurrency

---

Both Amdahl’s Law and Gustafson’s Law formalise the limits on parallel speedup. The former says that if a fraction $f$ of a program is sequential, the maximum speedup is $\lim_{p \to \infty} 1/(f + (1-f)/p) = 1/f$, so even 5% sequential code caps speedup at 20×. The latter counters that problem size often scales with available processors, making parallelisation more effective in practice.

I

---

1.1. Thread-per-Connection

If concurrency is the logical simultaneity of multiple tasks making progress through interleaved executions, and parallelism is their physical simultaneity on different processing units at the same instant, then concurrency predated parallelism, spanning from batch processing and time-sharing (i.e. Multics-UNIX) to GUI responsiveness (i.e. UI thread). Later, two developments led the former into the foreground of software design: i) networked services drove concurrent connections into the tens of thousands, exposing thread-per-connection limits; ii) clock speeds plateaued and the shift to multi-core processors demanded explicit restructuring of programs.

The growth of the World Wide Web in the 90s exposed the first point at scale, while I/O-bound workloads (e.g. network requests, disk reads, database queries) spend most of their time waiting for external resources. The initial solution assigned a thread per connection, but each kernel thread costs 1-8 MB of user-space stack memory and associated kernel bookkeeping (including a 16 KB kernel stack per thread), yet significant portions sit idle in a blocking read() syscall. Dan Kegel in 1999 coined the term C10K problem: at 10,000 concurrent connections, unbounded thread creation exhausts memory and the OS scheduler spends more time context-switching than doing useful work.

I/O models are sometimes characterised by two orthogonal axes, blocking vs non-blocking (i.e. whether the call suspends the thread or returns immediately) and synchronous vs asynchronous (i.e. whether the I/O operation completes before the call returns or the call returns immediately and completion is signalled later), forming the $2 \times 2$ matrix $M$ below (rows: blocking/non-blocking; columns: synchronous/asynchronous). Given that the thread-per-connection model sits on $M_{00}$ (blocking + synchronous): each thread blocks on its own read(), the insight was that threads are the wrong abstraction for waiting, and the solution was to move to $M_{01}$ (blocking + asynchronous), where one thread blocks on a single notification call that watches thousands of file descriptors at once.

• [src]

1.2. Event Loops

The shift from thread-per-connection to event-driven architectures required change on both sides: applications restructured around event loops, and the kernel evolved new syscalls to make the pattern efficient. An event loop runs in a single thread, blocking efficiently in the kernel’s multiplexing interface (epoll_wait(), kevent()) until one or more file descriptors are ready, then dispatching the corresponding handlers. It registers interest in I/O readiness, timers, and callbacks, enabling high concurrency for I/O-bound workloads without thread-per-connection overhead. A single thread suffices because I/O-bound work spends almost no CPU time per connection, but it is also bound to a single core. Nginx and Uvicorn solve this by spawning multiple worker processes (§2.1), each running its own event loop, so multi-core scaling is achieved through multiprocessing rather than multithreading.

I/O multiplexing is the kernel-side mechanism that lets many file descriptors share a single thread by letting the kernel watch them on behalf of the application. Its implementations (i.e. syscall API) evolved from select() (fixed fd limit, copies entire fd set to kernel on every call) $\to$ poll() (dynamic, but still $O(n)$ scanning) $\to$ epoll() (Linux 2.5.44, 2002, registers fds once via epoll_ctl and returns only ready fds, achieving $O(1)$ per event) and kqueue() (BSD/macOS), with io_uring (Linux 5.1, 2019) providing fully asynchronous non-blocking I/O for disk, network, and other I/O operations. In particular, epoll() supports two notification modes.

Level-triggered (default) reports a file descriptor as ready whenever data is available in its buffer, so the application can read partially and be reminded on the next epoll_wait call. Edge-triggered (EPOLLET) reports a file descriptor only when its state changes (e.g. new data arrives), requiring the application to drain the entire buffer in a loop until EAGAIN or risk missing data. Edge-triggered mode generates fewer notifications under high throughput and is used by Nginx, an event-driven reverse proxy and web server, for network I/O. However, regular file reads on Linux do not integrate with epoll (they always report ready, but the actual read() blocks on disk latency), so Nginx offloads blocking disk I/O (e.g. serving large video files) to a thread pool (§2.2) to keep the event loop responsive. Level-triggered mode is the default in Python’s selectors module (underlying asyncio) and most event loop libraries (e.g. libuv, Go’s netpoller) for its forgiving semantics.

• [src]

1.3. Coroutines (in Python)

Coroutines (Conway, 1963), generalised functions that can suspend execution at explicit points (yield, await) and resume from exactly where they left off, are applied in modern languages as an abstraction over event loops and callbacks. While event loops solved the C10K problem at the cost of raw callbacks, which are error-prone and deeply nested (i.e. callback hell), coroutines restore sequential-looking control flow over the same event loop machinery. Coroutines are also cooperative, yielding control explicitly rather than being interrupted, unlike threads that are preemptively scheduled by the OS.

The Global Interpreter Lock (GIL), a mutual exclusion lock (mutex) allowing only one thread to execute CPython bytecode at a time, was a reasonable design choice when Python was created (1991) on single-core machines where threads could never run in parallel anyway. With multi-core CPUs (mid-2000s), the GIL became a bottleneck, preventing threads from exploiting multiple cores and making async I/O the primary concurrency model for I/O-bound Python. Python’s asyncio module (3.4, 2014) provides an event loop wrapping the kernel’s multiplexing interface, initially repurposing generator delegation (yield from, PEP 380) as coroutine syntax. Python 3.5 (2015, PEP 492) replaced this with native async / await keywords, so coroutines were no longer disguised generators.

• [src]

The entire arc of Section I is visible in Python web frameworks. Web Server Gateway Interface (WSGI) frameworks (Flask, Django) run on synchronous servers (Gunicorn, uWSGI) that follow the blocking model from 1.1, assigning a thread or process per request. Asynchronous Server Gateway Interface (ASGI) frameworks (FastAPI, Django Channels) run on asynchronous servers (Uvicorn, Hypercorn) that follow the event-loop model from 1.2, running requests on asyncio with the coroutine syntax from 1.3. The choice between them reduces to whether the workload is I/O-bound at scale (ASGI) or low-concurrency and CPU-bound (WSGI).

• [src]

II

---

2.1. Multiprocessing

CPU-bound workloads (numerical computation, encryption, image processing) saturate the processor and benefit from true parallelism across multiple cores. Event loops solved the waiting problem, but computation needs real CPU time, and when single-core clock speeds plateaued (2004), exploiting multiple cores required distributing work across multiple execution contexts. Two approaches exist: multiprocessing and multithreading. Most real systems are hybrid, with I/O stages feeding CPU stages in a pipeline (e.g. fetch data → transform → write), and the bottleneck shifts depending on load and data volume.

Multiprocessing runs parallel work in separate processes, each with its own isolated address space. Because no memory is shared, there are no race conditions by construction, and a crash in one process cannot corrupt another. The trade-off is overhead: each process requires its own page table, file descriptor table, and kernel bookkeeping, and communication between processes requires explicit IPC. Python’s multiprocessing module and ProcessPoolExecutor use this approach to bypass the GIL for CPU-bound work, spawning worker processes that communicate results via serialisation (pickle). Fork-based multiprocessing is also how traditional web servers (Apache prefork) and database engines (PostgreSQL) achieve parallelism.

• …

2.2. Multithreading

Multithreading runs parallel work in threads within the same process. Since all threads share the same address space, they read and write the same heap (dynamically allocated memory) and share the process’s code, data/BSS segments, and kernel resources (file descriptor table, signal handlers) without any IPC mechanism, making communication fast but demanding synchronisation. Thread pools pre-create a fixed number of threads and reuse them across tasks, avoiding the repeated syscall and stack allocation cost of per-task thread creation while matching thread count to core count. Python 3.13 (2024) introduced an experimental free-threaded mode (PEP 703) that disables the GIL entirely, enabling true multithreaded parallelism for CPU-bound CPython code for the first time.

A function or data structure is thread-safe if it can be called from multiple threads concurrently without producing incorrect results. Thread safety is achieved either by avoiding shared mutable state entirely (immutability, thread-local storage) or by protecting it with synchronisation primitives. The standard threading API on Unix-like systems is POSIX Threads (pthreads), which provides pthread_create, pthread_join, pthread_mutex_lock, and related functions. Most languages wrap pthreads into higher-level APIs (Python’s threading, Java’s java.lang.Thread, C++’s std::thread).

The $1 \colon 1$ model maps each user thread directly to a kernel thread. The kernel handles scheduling and can place threads on separate cores for true parallelism, but every thread creation requires a syscall and allocates a kernel stack (16 KB on x86-64 since Linux 3.16), making creation and context switching expensive. The $m \colon 1$ model (green threads, early Java on Solaris) multiplexes many user threads onto a single kernel thread, so creation and switching happen entirely in user space at negligible cost. The trade-off is that the kernel sees only one thread, so no two user threads can run on different cores simultaneously, and a single blocking syscall (e.g. disk I/O) stalls all of them. The $m \colon n$ model (Go goroutines, Erlang processes) multiplexes $m$ user threads onto $n$ kernel threads ($m \gg n$), combining cheap user-space switching with kernel-level parallelism across cores. A user-space runtime scheduler assigns user threads to kernel threads and migrates them on blocking.

• …

2.3. Synchronisation

Multithreading’s shared address space makes communication fast but introduces a fundamental problem. A single source-level statement (e.g. x += 1) compiles to multiple machine instructions (load, add, store), and a timer interrupt can preempt the thread between any of them. The order of interleaved operations is non-deterministic, determined by the OS scheduler and hardware timing rather than the program. Two threads reading and writing the same variable can produce different results on every run, and bugs may only manifest under specific interleavings that are hard to reproduce (Heisenbugs). A critical section is a code region where shared state is accessed and that must execute atomically with respect to other threads. Without proper synchronisation, concurrent access to a critical section produces race conditions where correctness depends on timing, e.g. two threads both reading a balance of 100, then independently writing 150 and 70, losing one update entirely.

Hardware adds a further layer of difficulty. Memory consistency models define ordering guarantees for operations across threads. Sequential consistency ensures a global total order, but most hardware provides relaxed consistency that reorders loads and stores for performance: x86-TSO is relatively strong (only store-load reordering), while ARM weak ordering permits load-load, load-store, and store-store reorderings as well. Memory barriers (fences) are ISA-level instructions (mfence on x86, dmb on ARM, fence on RISC-V) that force ordering, and compilers insert these behind language-level primitives (e.g. std::atomic in C++, volatile in Java). Happens-before relationships formalise which operations are guaranteed visible to other threads.

• …

A mutex (mutual exclusion lock) puts a waiting thread to sleep until the lock is released, while a spinlock keeps the thread running in a tight loop checking repeatedly. Spinlocks avoid the overhead of a context switch and are faster when the lock is held briefly on multicore systems (another core can release the lock while the spinner runs), but waste CPU cycles if the holder is slow or on a single core where spinning prevents the holder from running at all. A reentrant lock (recursive mutex) allows the same thread to acquire the lock multiple times without deadlocking against itself, maintaining an acquisition count. Read-write locks allow concurrent reads but exclusive writes, optimising for read-heavy workloads where writers are rare.

Semaphores generalise mutual exclusion with an integer counter that permits up to $N$ threads to enter a critical section simultaneously, where a binary semaphore ($N = 1$) behaves like a mutex. Condition variables allow a thread to atomically release a lock and sleep until another thread signals that a predicate has changed, and the waiting thread must recheck the predicate in a while loop because of spurious wakeups (the thread may be woken without a signal). Atomic operations such as compare-and-swap (CAS), which atomically checks whether a memory location holds an expected value and replaces it only if it does, provide the building blocks for lock-free data structures that bypass locks entirely for higher throughput under contention.

These primitives are best understood through classical synchronisation problems. The producer-consumer (bounded buffer) problem has producers writing to a fixed-size buffer and consumers reading from it, requiring a mutex to protect the buffer and two semaphores (or condition variables) to block producers when the buffer is full and consumers when it is empty. The readers-writers problem allows multiple concurrent readers but requires exclusive access for writers, typically solved with a read-write lock or a pair of mutexes tracking reader count. Both problems illustrate that correct synchronisation requires choosing the right primitive for the access pattern, not simply wrapping every operation in a lock.

Deadlock occurs when threads are permanently blocked in a circular dependency. The four Coffman conditions must all hold simultaneously, namely mutual exclusion, hold-and-wait, no preemption, and circular wait. The dining philosophers problem (Dijkstra, 1965) illustrates all four: five philosophers share forks with neighbours, each grabs one fork and waits for the other, forming a circular dependency that deadlocks. Breaking any single condition prevents it, e.g. always picking up the lower-numbered fork first eliminates circular wait. Prevention strategies include consistent lock ordering, timeout mechanisms, and deadlock detection algorithms. Livelock (threads continuously change state without making progress) and starvation (a thread perpetually denied access) are related failure modes.

• …

---