My Computer cs600 699. videos untitled

My Computer

NameSizeTypeDate
23 object(s)
 

604. concurrency

Concurrency

Concurrency, the interleaving of tasks so each advances without any finishing first, arises from two scarcities that appear similar yet demand opposite remedies: i) Waiting, where thousands of idle connections each tie down a thread, calls for event loops; and ii) Computing, where cores are few, calls for spreading work across them and the synchronisation shared memory forces.

I

1.1. Thread-per-Connection

Concurrency is the logical simultaneity of tasks making progress through interleaved executions, whereas parallelism is their physical simultaneity on different processing units (e.g. CPU/GPU). Concurrency appeared first and spanned from batch processing and time-sharing to GUIs (i.e. Multics $\to$ UNIX $\to$ UI thread), but remained as the concern of the OS scheduler and the toolkit’s message loop. Two developments pushed it onto the application programmer, who now composes the kernel’s processes and threads (§603#3.1) rather than leaving them to the scheduler: i) networked services drove connections into the tens of thousands, exposing thread-per-connection limits; and ii) stalled clock speeds and the multi-core turn forced programs to be restructured explicitly.

The former arrived with the web (§605#3.2), whose tasks are predominantly I/O-bound, spending most of their time waiting on the network and other external resources (e.g. disk reads, DB queries). As client connections surged into the thousands, the initial attempt was the thread-per-connection model (e.g. a multithreaded server), which assigns every connection its own kernel thread with a 1-8 MB user-space stack (§603#3.1). However, the model fails at scale because those stacks exhaust memory and the OS scheduler spends more time context-switching than doing useful work. This wall at $10^4$ concurrent connections is known as the C10K problem (Dan Kegel, 1999).

If unbounded threads are the problem, a fixed thread pool bounds resource consumption but not concurrent capacity. A thread blocked in read() consumes no CPU yet still holds one of the pool’s $N$ slots, and $N$ threads serve at most $N$ connections while further arrivals wait for a free slot. In effect, the scarce resource is the thread, not the idle CPU, because each connection pins one for the entire wait. The concurrency bound $N \gtrsim 10^4$ and the system-resource bound $N \ll 10^4$ leave no room for a viable $N$, so neither extreme cures a fault that lies in the I/O model rather than the thread count, and reaching a better one first means surveying the I/O models on offer.

Specifically, two binary choices form the $2 \times 2$ matrix $R$ below. Its row index, {synchronous, asynchronous}, distinguishes whether the I/O completes before the call returns or its completion is signalled later. Whereas, its column index, {blocking, non-blocking}, hinges on whether the call suspends the thread or returns instantly. The thread-per-connection model $R_{00}$ cedes to the event loop $R_{10}$, in which one thread multiplexes many connections while still parking on a single wait. Non-blocking is less favoured since $R_{01}$ squanders CPU busy-polling readiness through repeated $\text{EAGAIN}$ returns and $R_{11}$ awaited io_uring for a general completion interface.

1.2. Event Loops

Serving many connections from one thread demanded change on both sides. The application restructured around an event loop, while the OS evolved new syscalls to wait on many descriptors at once. Such a program is governed by event-driven programming (§602#1.1), a paradigm that organises control flow around reactions to events rather than a fixed instruction sequence. The pattern long predates the C10K problem and appears in the GUI message loop dispatching clicks and keystrokes (§603#1.1). Networking is another instance with the same inversion of control in which the runtime, not the program, invokes the handlers whenever a descriptor becomes ready.

The event loop drives the invocation on a single application thread as a dispatcher rather than a program, running each ready handler to completion before returning to the wait, and thus lets the thread fan out across many connections instead of dedicating itself to one. Mechanically, it blocks on the kernel’s multiplexing interface through a syscall (e.g. Linux: epoll_wait(), BSD: kevent()) until a watched descriptor becomes ready, then dispatches each ready descriptor to its registered handler (i.e. callback). The same call also returns when a timeout set to the nearest scheduled timer elapses, which asyncio finds in $O(1)$ by keeping its timers in a min-heap (i.e. the heapq module) keyed on deadline, so the loop runs due time-based callbacks even when no descriptor fires.

The loop however changed only what the application waits on, not how the I/O itself is performed. That is, the kernel still performs this through device drivers, DMA, and interrupts (§603#3.3), signalling the event loop the moment a descriptor is ready for its read. One main thread then suffices because I/O-bound work spends almost no CPU per connection. It stands in for the thousands that thread-per-connection needed and collapses their blocking waits into a single one. Its one limit is concurrency without parallelism, since a single loop occupies one core and every additional core takes another loop.

Beyond performing the I/O, the kernel must also watch it through I/O multiplexing, which lets many file descriptors (fds) share a single thread by tracking their readiness on the application’s behalf. Its implementations (the syscall API) evolved from select() (4.2BSD, 1983, fixed fd limit, copies the entire fd set to the kernel on every call) $\to$ poll() (System V, 1986, 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() (FreeBSD, 2000). In particular, epoll() supports two notification modes.

Level-triggered (default) reports an fd 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 an fd only when its state changes (e.g. new data arrives), so the application must drain the entire buffer in a loop until EAGAIN or risk missing data. The former is the default in Python’s selectors module and most event loop libraries (e.g. Node.js’s libuv) for its forgiving semantics, whereas the latter generates fewer notifications under high throughput and drives Nginx’s network I/O and Go’s netpoller.

The trigger modes govern network descriptors, yet the loop’s coverage is not total. The readiness model assumes a descriptor can be not ready, which holds for sockets that wait on the network but not for regular files, whose data is deemed always available even when fetching it stalls on disk latency. Hence such reads report ready yet the actual read() blocks, and Nginx offloads blocking disk I/O (e.g. serving large video files) to a thread pool to keep the event loop responsive. Only io_uring (Linux 5.1, 2019) closes this gap, since its completion-based interface reports the finished read rather than a readiness that regular files cannot express. The kernel’s side is thereby complete, leaving the application’s, its logic scattered across callbacks, as the remaining cost.

1.3. Coroutines

Coroutines do not replace the event loop but change its unit of work from a raw callback to a coroutine. A coroutine (Conway, 1963) generalises the ordinary subroutine, which runs from a single entry to completion, into a function that suspends at explicit points (yield, await) with its local state preserved and resumes exactly where it left off. Raw callbacks are error-prone and deeply nested (i.e. callback hell), scattering one connection’s logic across handlers and hand-threaded state, whereas a coroutine keeps that state in its local variables and its logic reads top to bottom as in the blocking style.

The event loop schedules cooperatively, its coroutines yielding control explicitly rather than being preempted. This revives the model the OS abandoned for the timer interrupt (§603#3.1), safe again since one loop’s tasks belong to one program rather than strangers the kernel must referee. Each await on I/O suspends the coroutine and hands its fd to the loop, whose single thread blocks in the epoll_wait() a C programmer would write by hand, making async / await portable across readiness mechanisms. The bargain still binds, since a coroutine that computes or calls a blocking function without reaching an await stalls every other task, so CPU-bound work belongs in the mechanisms that follow.

Switching between coroutines is cheap, nanoseconds against the microseconds an OS thread context switch costs, since it saves only a suspended frame in user space, avoiding the kernel-mode transition a thread switch requires. This keeps a coroutine’s cost in the language runtime rather than the scheduler, which is why one thread can hold far more of them than the machine could hold threads. Coroutines are a language-general construct, reaching C# (5.0, 2012) before Python and the rest (JavaScript, Kotlin, Rust) after, yet Python is the instructive case because its runtime hides the event loop most completely.

Python’s initial coroutine implementation repurposed generators (yield, Python 2.2), which already suspend and resume on demand, and two amendments generalised it by letting a generator: i) receive values (send, PEP 342); and ii) delegate to sub-generators (yield from, PEP 380). The asyncio module (3.4, 2014) later implemented the event loop on this machinery, a while loop that repeatedly runs coroutines and waits for I/O readiness through the selectors module, a thin wrapper over the kernel’s multiplexing syscalls. Python 3.5 (2015, PEP 492) added native async / await keywords, so coroutines became a first-class construct rather than disguised generators, an async def function being a coroutine and each await its yield point.

Yet the syntax alone creates no concurrency since awaiting a coroutine merely runs it inline. Concurrency arises when the loop drives many coroutines at once, each wrapped in a Task, its scheduled form, which the loop places on the ready queue and advances as the awaited fd signals. For example, asyncio.gather launches many Tasks together, thus one thread interleaves thousands of outstanding requests, each parked at its own await. asyncio.TaskGroup (3.11, 2022) was later introduced to provide structured concurrency, which scopes sibling Tasks so that one failure cancels the rest, while gather leaves them a loose bundle that fails independently.

1.4. HTTP Servers

The entire arc (i.e. thread-per-connection $\to$ event loops $\to$ coroutines) resurfaces in Python web frameworks. Historically a Python application was bound to a particular server through CGI or mod_python, until the web server gateway interface (WSGI, 2003) decoupled the two so that any compliant app runs on any compliant server, a contract the asynchronous server gateway interface (ASGI, 2016) later generalised to the asynchronous model. A WSGI framework exposes a single synchronous callable app(environ, start_response) that the server invokes once per request, whereas an ASGI framework exposes an async def app(scope, receive, send) whose receive and send channels stream events across the asyncio loop.

In practice, the ASGI side forms a stack of layers, each wrapping the one beneath. At the bottom, asyncio (2014) is the event loop that drives the socket I/O via the OS (§603#2.2). Uvicorn (2017), the ASGI server above it, runs the loop and turns each HTTP request into a coroutine call (e.g. httptools parses the raw bytes). FastAPI (2018) atop the stack routes and validates the request into the async def handler the loop ultimately drives. Note that ASGI is only a contract between server and app, hence either side substitutes freely (e.g. Uvicorn $\leftrightarrow$ Hypercorn, FastAPI $\leftrightarrow$ Starlette), and even asyncio’s loop engine may become uvloop, built on the same libuv as Node.js.

Within a single worker any request that blocks stalls the rest because they all share the loop’s single thread. One such offender is an ordinary def endpoint, which carries no await and would hold the thread through its whole body unless the framework runs it in a thread pool. The same hazard attends any blocking call reached from a coroutine (e.g. time.sleep instead of asyncio.sleep, a synchronous database driver), thus an async server demands async libraries throughout. CPU-bound work stalls the loop equally but merits a process pool rather than a thread pool, since only processes convert the host’s remaining cores into parallelism.

The loop occupies at most one core, however many the host offers, hence Gunicorn (2010), a pre-fork master descended from Ruby’s Unicorn, calls fork() once per core before any request arrives and supervises the resulting Uvicorn workers, each inheriting the already-bound listening socket so no worker binds a port of its own. The arrangement layers core-level parallelism over each loop’s concurrency. In containerised deployments an orchestrator such as Kubernetes replaces the master and replicates single-worker containers for the same parallelism and resilience (§607#3.1). A reverse proxy such as Nginx (2004, written in C) sits in front of the worker pool, where it terminates TLS and buffers slow clients such that the workers see only complete and fast requests.

II

2.1. Multiprocessing

CPU-bound workloads (e.g. numerical computation, compression, encryption) saturate the processor and benefit from true parallelism across multiple cores. Event loops solved the waiting that came with scaling connections, whereas stalled clock speeds and the multi-core turn are what now bite. Most real systems are hybrid, where I/O stages feed CPU stages in a pipeline (e.g. fetch → transform → write). More specifically, two approaches parallelise the CPU stages, multiprocessing and multithreading. They differ chiefly in whether the parallel work shares memory or stays isolated, hence in whether communication is cheap or synchronisation-free.

In fact, the speedup from adding processors is not automatic but bounded by a program’s sequential fraction, as Amdahl’s Law (1967) and Gustafson’s Law (1988) formalise. The former sets the problem size fixed and says that, if a fraction $f$ of a program is sequential, the maximum speedup on $p$ processors is $1/(f + (1-f)/p) \to 1/f$ as $p \to \infty$ (e.g. $f = 0.05 \Rightarrow 1/f = 20$). The latter instead lets the problem grow with $p$, whereby the parallel part scales with $p$ while the serial part stays fixed, and yields the scaled speedup $f + (1-f)p$, linear in $p$. The two answer different questions: the speed gained on a fixed problem vs. the work gained in equal time.

Multiprocessing runs parallel work in separate processes (§603#3.1), each in its own address space. Because it shares no memory, it rules out data races by construction and isolates crashes, for instance one Chrome tab failing without bringing down the others, at the cost of a per-process page table, fd table, and kernel bookkeeping plus explicit IPC to communicate. Even so, fork-based multiprocessing underlies traditional web servers (Apache prefork), database engines (PostgreSQL, §606#3.3), and modern ASGI deployments (Gunicorn forking one Uvicorn worker per core).

In Python, the multiprocessing module (2.6, 2008) and ProcessPoolExecutor (3.2, 2011) bypass the GIL by giving each worker process its own interpreter, and so its own cores. Each worker returns its result via serialisation (pickle, §605#4.1). A worker pool that maps one operation across partitioned data (Pool.map) is data parallelism, whereas routing distinct pipeline stages to distinct processes is task parallelism, the two ways to decompose parallel work that §608 scales from cores to machines.

2.2. Multithreading

Multithreading trades isolation for a shared address space, partitioning the process’s state such that every thread reads and writes the same regions (e.g. heap, text, data segments) and inherits the same kernel resources (e.g. fd table, signal dispositions), while private to each remain only its register set (PC included) and stack. It is lighter and so faster than multiprocessing, as communication reduces to ordinary memory access rather than IPC, but pays for it in synchronisation. The small private remainder also prices the switch. One between threads of a process leaves invariant the page table and TLB that one between processes must swap and flush (§603#3.1).

Yet the cost has not vanished. A thread reduces to a triple $($register set, stack, scheduler$)$, and whichever layer supplies the triple pays the same bill of creation, storage, and switching. Namely, an application spawns $m$ user threads, each created by its runtime at an allocation and switched at a function call unseen by the kernel. By contrast, the kernel supplies $n$ kernel threads, each at a syscall and a kernel stack, orders of magnitude dearer, for they alone are dispatched onto cores. A threading model that fixes the ratio $m \colon n$ of user to kernel threads is hence a strategy for how much of the bill to pay at kernel prices by trading parallelism against abundance.

The $1 \colon 1$ model (POSIX threads, Windows threads), today’s default, sets $n = m$, backing each user thread with its own kernel thread, as glibc’s native POSIX thread library (NPTL, 2003) does on Linux beneath C, Java, and CPython threads alike. Its virtue is that the runtime does nothing, every user thread being directly schedulable and stalling no other whether it blocks or computes, since the kernel deschedules it on a block and preempts it by the timer interrupt otherwise. Every operation is instead billed at kernel prices, and the cost scales as $O(m)$ in syscalls and memory alike, a clone() and a multi-MB stack per creation plus a kernel entry per block and wake, capping $m$ at the thousands, the earlier C10K wall.

The $m \colon 1$ model (green threads, early Java) drops the kernel’s share to zero. The runtime keeps every triple and multiplexes all user threads onto the process’s main thread, cheap enough to spawn one flow per task. The kernel however sees one thread, so nothing runs in parallel and one blocking syscall (e.g. disk I/O) stalls all $m$. The $m \colon n$ model (Go goroutines, Erlang processes, Java virtual threads) instead splits the bill such that cheapness and parallelism coexist. The runtime keeps the $m$ triples while the kernel carries a constant $n$ of typical kernel threads ($m \gg n$, one per core), and a runtime scheduler migrates user threads across the $n$ on blocking.

In practice, the $1 \colon 1$ default leaves threads too expensive to spawn per task, thus an application pre-creates a fixed number in a thread pool and reuses them across tasks, amortising the creation cost. Specifically, in Python, ThreadPoolExecutor is the explicit pool the application constructs and sizes. Libraries also provision one implicitly, as in i) asyncio.to_thread’s default executor; ii) FastAPI’s $\sim$40-thread pool shielding its loop from def endpoints; and iii) OpenBLAS’s worker threads beneath NumPy’s linear algebra. Either way the size settles at the core count when CPU-bound and diverges as blocking rises when I/O-bound, since a blocked thread holds no core.

The same shared address space that made these threads cheap now threatens their correctness, since communication through common memory equally lets concurrent access corrupt it. A function or data structure is thus thread-safe only if concurrent calls cannot corrupt its result, won either by avoiding shared mutable state (immutability, thread-local storage) or by guarding it with synchronisation primitives. On Unix-like systems those primitives are standardised as POSIX Threads (pthreads, POSIX.1c, 1995), whose pthread_create, pthread_mutex_lock, and related calls most languages wrap into higher-level APIs (Python’s threading, C++’s std::thread).

More specifically, in CPython the Global Interpreter Lock (GIL), a mutex admitting one thread to run bytecode at a time, withholds the parallelism threading’s real $1\colon1$ kernel threads would otherwise deliver. They speed only I/O-bound work, which releases the GIL while blocked in a syscall, never CPU-bound work, which yields it only when forced. That forcing is CPython’s own 5 ms switch interval (sys.getswitchinterval), layered on the OS timer to make a long-running holder release the GIL so waiting threads take turns, one at a time and never in parallel.

The lock exists because even reading an object on the shared heap (§602#1.3) mutates its reference count, so per-object locks would number in the millions, their overhead crippling the single-threaded case Python (1991) was built for. One interpreter-wide lock collapses the millions to one at the price of multicore, a bargain struck by CPython, not the language, on the single-core machines of its day, and one sparing C extensions any change.

Python 3.13 (2024) took the other path, the one Greg Stein’s 1999 patch first tried and was rejected for slowing single-threaded code, now an experimental free-threaded mode (PEP 703) that trades the single lock for per-object locking, at a measurable single-thread overhead and C extensions that must opt in (Py_mod_gil). The removal is staged, as 3.14 (2025, PEP 779) made the build officially supported and restored the specialising interpreter 3.13 had disabled, narrowing the overhead toward the single digits, while 3.15 converges on one free-threaded default build. The trade is worth making only now that idle cores cost more than the GIL ever saved, bringing true CPU-bound parallelism and with it the synchronisation problems that follow.

III

3.1. Race Conditions

Although shared memory makes communication fast, concurrent executions can corrupt whatever they share, and a race condition is any such outcome whose correctness depends on the timing of concurrent operations (e.g. two processes both finding a file absent and both creating it). The root cause is non-atomicity, where a single statement (e.g. x += 1) typically compiles to several instructions ($\text{load}$, $\text{add}$, $\text{store}$), and another execution can interleave in any gap between them, whether by timer preemption (§603#3.1) on a single core or genuine simultaneity across two. The span of code that must execute atomically is formally called the critical section.

Thus, the unprotected critical section is the archetypal site of a race, though not the only one, and three forms recur. i) check-then-act: two actors test a condition and then both act on it, as in the file creation above; ii) lost wakeup: a signal fires before its waiter sleeps; and iii) the data race: two unsynchronised accesses touch one memory location with at least one write (i.e. two concurrent reads never conflict). The first form matters enough in security to carry its own name, time-of-check to time-of-use (TOCTOU), as an attacker who slips a symlink between a program’s access() check and its open() redirects the privileged operation to a file of their choosing.

The first two forms are semantic races, a matter of operations happening in the wrong order, whereas the data race stands apart as a memory-level condition. Despite the popular subset diagram, race condition and data race coincide in neither direction. Two individually atomic withdrawals racing on arrival order form a race condition without a data race, while unsynchronised reads of an approximate counter form a data race that is benign in practice. When a data race does bite, the damage runs deeper than a lost update, since a wide value updated non-atomically (e.g. a 64-bit field on a 32-bit machine) can be read half-written, a torn read of a value never actually stored.

However, races resist testing, as the triggering interleaving depends on interrupt timing and system load beyond the program’s control (i.e. may arise once in millions of runs). Worse, print statements or a debugger perturb the timing enough to hide the bug, known as the Heisenbug (Gray, 1985). Dynamic race detectors (e.g. ThreadSanitizer in Clang/GCC) therefore instrument every memory access and report data races. Still, the guarantee is bounded twice: i) a clean run vouches only for the schedules observed; and ii) a semantic race goes unreported, its accesses individually synchronised and the flaw in the gap between them.

3.2. Memory Reordering

Shared memory fails a second way, beneath the scheduler rather than within it, as the hardware itself reorders reads and writes for performance. Distinct from cache coherence (§601#1.3), which keeps copies of a single location aligned across cores, memory consistency models define ordering guarantees for operations on different locations across threads. Sequential consistency (Lamport, 1979), the ordering programmers implicitly assume, requires a single total order over all reads and writes, consistent with each thread’s program order, where each read returns the latest prior write.

Most hardware instead provides relaxed consistency, where x86-TSO is relatively strong (only store-load reordering) while ARM weak ordering permits load-load, load-store, and store-store reorderings as well. The classic casualty on weakly ordered hardware is publication, where one thread writes data then sets a ready flag, yet a second thread that sees the flag still reads the stale data, since the store buffers and out-of-order execution that keep each core busy (§601#1.2) let stores drain late and loads issue early.

Happens-before (Lamport, 1978) formalises visibility as a strict partial order generated by program order and synchronisation edges, so a data race is precisely a pair of conflicting accesses (i.e. same location, at least one a write) left incomparable by it. Memory barriers (fences) are ISA-level instructions (mfence on x86, dmb on ARM, fence on RISC-V) that force the missing ordering, and compilers insert them behind language-level primitives (e.g. std::atomic in C++, volatile in Java). Language memory models build on the same order, C++11 declaring any racy program undefined while Java 5 bounds the damage with weak but defined semantics, and in both the fences arrive bundled inside the synchronisation primitives that follow, so correctly locked code is correctly ordered for free.

3.3. Synchronisation

Synchronisation primitives answer both problems at once, as they enforce atomicity over critical sections and insert the ordering that relaxed hardware omits. A mutual exclusion lock (mutex) puts a waiting thread to sleep until the lock is released, while a spinlock keeps the thread checking in a tight loop, skipping the context switch and thus faster when locks are held briefly on multicore machines but wasting cycles otherwise. A reentrant lock (recursive mutex) maintains an acquisition count so the same thread can reacquire it without deadlocking against itself, and read-write locks allow concurrent reads but exclusive writes for read-heavy workloads.

Semaphores (Dijkstra, 1965) answer a second need beyond exclusion, namely coordination, by generalising the lock into an integer counter that holds the invariant $v \geq 0$, where wait decrements $v$ or blocks at zero and signal increments it. An initial value $N$ thus admits at most $N$ threads into a critical section simultaneously, and a binary semaphore ($N = 1$) behaves like a mutex. Unlike a mutex, however, a semaphore has no owner, as any thread may signal it, which is what lets one thread wake another rather than merely unlock its own critical section. Condition variables let a thread atomically release a lock and sleep until another thread signals that a predicate has changed, and the waiter must recheck the predicate in a loop because of spurious wakeups .

Atomic operations are the hardware’s own indivisible steps, single instructions the CPU executes without interruption. The earliest, test-and-set (TAS, IBM System/360, 1964), sets a flag and returns its old value in one step, enough to build a spinlock but no more. Compare-and-swap (CAS, System/370, 1970) generalises it, replacing a memory location’s value only if it still holds an expected one (e.g. x86 LOCK CMPXCHG). The locks above are themselves built on these, since acquiring a lock is a check-then-set that two threads could interleave, recreating one level down the very race it guards against.

Lock-free data structures instead use atomics directly, where an update reads the old value, computes the new, and retries the CAS until no other thread has interfered (e.g. C++’s std::atomic, Java’s AtomicInteger). This guarantees that some thread always makes progress even if others stall, whereas a lock holder preempted mid-section blocks every waiter. The subtlety is that a location can change from $A$ to $B$ and back to $A$ between the read and the CAS, which then succeeds though the state moved beneath it, known as the ABA problem.

These primitives are best understood through classical synchronisation problems. The producer-consumer (bounded buffer) problem has producers and consumers sharing a fixed-size buffer, and needs a mutex to protect it plus two semaphores (or condition variables) to block producers when it is full and consumers when it is empty. The readers-writers problem schedules many readers and rare writers over one shared object without starving either side, and maps directly onto the read-write lock. Both illustrate that correct synchronisation fits the primitive to the access pattern rather than wrapping every operation in a lock, while scope matters equally, as one coarse lock serialises the very parallelism threads were meant to buy (the GIL being the extreme case), whereas finer locks, as in free-threaded CPython, recover it only by setting a thread to hold several at once, the setup for a failure of the cure’s own making.

3.4. Deadlock

Locks cure races, yet holding one while acquiring another introduces a failure mode of their own. A deadlock is a set of threads each permanently blocked on a lock another holds. The Coffman conditions (1971), illustrated by the dining philosophers problem (Dijkstra, 1965), are jointly necessary for deadlock: i) mutual exclusion; ii) hold-and-wait; iii) no preemption; and iv) circular wait, a directed cycle in the wait-for graph, which draws an edge $T_i \to T_j$ whenever thread $T_i$ awaits a lock that $T_j$ holds. The cycle alone is also sufficient, as a lock frees only when its sole holder proceeds yet every holder on the cycle is itself blocked, hence no thread on it ever proceeds.

Prevention strategies fall into the following: i) lock ordering: acquisitions only ascend a fixed total order and thus no cycle can close, as when every philosopher picks up the lower-numbered chopstick first; ii) timeouts: an acquisition that waits too long is abandoned and retried; and iii) detection: the wait-for graph is searched for cycles and one member is aborted to break any found. For example, when two transactions update the same two rows in opposite orders, each holds one exclusive row lock and awaits the other’s, closing the cycle $T_1 \xrightarrow{\text{awaits}} T_2 \xrightarrow{\text{awaits}} T_1$. PostgreSQL runs DFS after the timeout (1$\text{s}$), aborts the checker, and thereby releases its locks (§606#2.2).

Even so, deadlock has two milder relatives, both of which also violate the liveness property, i.e. $\forall$ thread $\exists$ a later step where it makes progress. Specifically, livelock violates it in motion, as threads change state indefinitely without progressing (e.g. two threads that time out, back off, and retry in lockstep). Starvation violates it selectively, as one thread waits unboundedly while the rest proceed (e.g. a writer never admitted under a read-heavy read-write lock). Deadlock and its relatives close the account of concurrency where it began, with a scarcity of waiting answered by consolidation, and a scarcity of computing by distribution, which is paid for in synchronisation.



I gathered words solely for my own purposes without any intention to break the rigour of the subjects.
I also prefer eating corn in spiral .

Ready