My Computer cs600 699. videos untitled

My Computer

All cs300cs600maths200maths400
NameSizeTypeDate
23 object(s)
 

604. concurrency

🔍
Aa

Concurrency

The post sits on the application’s side of the kernel, composing what the OS provides, the C APIs (e.g. pthreads) and their higher wrappings (e.g. Python’s threading, asyncio), rather than how it provides them (§603). The theory lands in the working stack, FastAPI’s workers on the event loop and free-threaded CPython on the cores, with synchronisation as the toll between them.

I

1.1. Thread-per-Connection

Concurrency is the logical simultaneity of tasks progressing through interleaved executions. Parallelism is their physical simultaneity on different processing units. The former matured first, through batch processing, time-sharing, and GUIs. In fact, it remained the concern of the OS scheduler and the toolkit’s message loop, until two major developments left the application programmer to work directly with the kernel’s processes and threads, i) waiting: networked services drove connections into the tens of thousands and exposed thread-per-connection limits; and ii) computing: stalled clock speeds and the multi-core turn forced programs to be restructured explicitly.

The waiting problem arrived with the web (§605#3.2), whose tasks are often I/O-bound, spending most time on the network, disk, or DB, not on computation. The initial try was the thread-per-connection model (e.g. a multithreaded server), in which every accept() is followed by a pthread_create(), and the new thread blocks in read() while holding a 1-8 MB user-space stack (§603#3.1) throughout the wait. Notably, clients set the thread count by connecting, so nothing caps it as they surge into the thousands, whereupon these stacks exhaust memory and the OS scheduler mostly context-switches. The C10K problem (Dan Kegel, 1999) names this wall at $10,000$ concurrent connections.

The natural fix is a fixed-size thread pool of $N$ worker threads fed from the accept queue. However, it bounds resource consumption, not concurrent capacity, because a worker blocked in read() consumes no CPU yet still occupies one of the $N$ slots. This pool serves at most $N$ connections and further arrivals queue until a slot frees, thus it has traded a memory blow-up for clients left waiting. That is, what it runs out of is threads, not CPU, as a waiting connection still holds one. While the concurrency bound $N \gtrsim 10^4$ and the system-resource bound $N \ll 10^4$ leave no viable thread count $N$, the fault lies not in the most appropriate $N$ but in the I/O model illustrated below.

An I/O call could make two binary choices from the $2 \times 2$ matrix $R$, i) {synchronous, asynchronous}: whether the call returns only once the I/O is complete or lets completion be signalled later; ii) {blocking, non-blocking}: whether the call suspends the thread until then or returns at once. Apparently, the thread-per-connection model sits at $R_{00}$, whereas the event loop that displaced it sits at $R_{10}$ and lets one thread multiplex many connections by parking on a single wait. The non-blocking column saw less use, as $R_{01}$ wastes CPU by polling for readiness repeatedly with each attempt returning $\text{EAGAIN}$, and $R_{11}$ lacked a general completion interface on Linux until io_uring.

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 fans one thread out across many connections. Mechanically, it blocks on the kernel’s multiplexing interface via a syscall (e.g. epoll_wait()) until watched descriptors become ready, then dispatches each to its registered handler (i.e. callback). The same call also returns when the timeout set to the nearest timer elapses, so the loop runs due time-based callbacks even when no descriptor fires, a deadline asyncio finds in $O(1)$ by keeping its timers in a min-heap (the heapq module).

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, its cost scaling with ready events rather than watched descriptors) 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 but not for regular files, deemed always ready even when fetching stalls on disk. Hence a file read reports ready yet blocks, and Nginx offloads such disk I/O (e.g. large video files) to a thread pool to keep the loop responsive. Only io_uring (Linux 5.1, 2019) closes the gap, its completion-based interface reporting the finished read rather than a readiness files cannot express. The kernel’s side is 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. The async / await syntax is language-general, arriving in C# (5.0, 2012) before Python and the rest (JavaScript, Kotlin, Rust), 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. Web Servers

The entire arc (i.e. thread-per-connection $\to$ event loops $\to$ coroutines) resurfaces in Python web frameworks. The web server gateway interface (WSGI, 2003) decoupled its application from the server, once bound together via CGI or mod_python, so that any app can run on any conforming server. The asynchronous server gateway interface (ASGI, 2016) generalised the contract to the asynchronous model. That is, the former exposes a single synchronous callable app(environ, start_response) that the server invokes once per request, but the latter exposes an async def app(scope, receive, send) whose receive and send channels stream events across the asyncio loop.

In particular, ASGI is realised as a stack of layers, each wrapping the one beneath. FastAPI (2018) routes and validates the request into its async def handler. Uvicorn (2017), the ASGI server below it, turns each HTTP request into that coroutine call (e.g. httptools is used to parse the raw bytes) and runs the loop. asyncio (2014) is the event-loop library underneath that drives the socket I/O via the OS (§603#2.3). Since ASGI is only a contract between server and app, either side is definitely interchangeable (e.g. Uvicorn $\leftrightarrow$ Hypercorn, FastAPI $\leftrightarrow$ Starlette), and the substitution can be extended to the loop itself, which asyncio can hand to uvloop, built on the same libuv as Node.js.

The concurrency of an ASGI worker rests on a single condition. All requests share the loop’s one thread, so any request that blocks stalls every other, while a slow request only costs a single worker under WSGI. One such offender is a def endpoint, that has no await to yield at and would hold the thread for its whole body, so FastAPI keeps a thread pool to run it off the loop. Likewise, any blocking call inside a coroutine (e.g. time.sleep, a sync DB driver) holds a thread, thus an async server demands async libraries throughout. CPU-bound work, by contrast, stalls the loop equally but merits a process pool instead, since only this can reach the host’s remaining cores under the GIL.

Yet the loop itself runs on one core regardless of how many the host offers, so one runs several loops under Gunicorn (2010), a pre-fork master that calls fork() once per core and supervises the spawned Uvicorn workers. The master never touches a request, as the workers inherit the listening socket, and the kernel hands each connection to one of them to serve end-to-end. In containerised deployments, an orchestrator (e.g. Kubernetes) replaces the master and replicates single-worker containers to the same effect (§607#3.1). By contrast, Nginx (2004) is a reverse proxy in front of either that sits on the data path to terminate TLS and buffer slow clients until the requests complete.

II

2.1. Multiprocessing

CPU-bound workloads (e.g. numerics) saturate a processor and gain only from true parallelism across cores. Two classical results bound the gain by the fraction of a program that runs serially. Namely, Amdahl’s Law (1967) holds the problem size fixed, so the serial part caps the speedup, and a program with serial fraction $f$ attains at most $1/(f + (1-f)/p) \to 1/f$ as the processor count $p \to \infty$ (e.g. $0.05 : 20$). Gustafson’s Law (1988) lets the problem grow with $p$ instead, the parallel part scaling with it while the serial part stays fixed, and yields the scaled speedup $f + (1-f)p$, linear in $p$. The former measures speed on a fixed problem, the latter work in a fixed time.

Two approaches deliver that parallelism, multiprocessing and multithreading, which differs in whether the work stays isolated or shares memory. Multiprocessing runs it in separate processes each with its own address space (§603#3.1). The absence of shared memory rules out data races by construction and confines a crash to one process (e.g. one Chrome tab failing alone). The cost is then paid in memory, each process carrying its own page table, fd table, and kernel bookkeeping, and in explicit IPC to communicate. Fork-based multiprocessing still underlies traditional web servers (Apache prefork), DB engines (PostgreSQL, §606#3.3), and ASGI deployments (Gunicorn’s workers).

The GIL-ed Python achieves parallelism through separate processes. The multiprocessing module (2.6, 2008) and ProcessPoolExecutor (3.2, 2011) supply them, one full interpreter per worker, that buys a core apiece but leaves $N$ workers holding $N$ copies of what threads would share. Two kinds of work decomposition apply to such a pool, i) data parallelism: mapping one operation across partitioned data (e.g. Pool.map), the embarrassingly parallel case in which workers never communicate; and ii) task parallelism: routing distinct pipeline stages (e.g. fetch $\to$ transform $\to$ write) to distinct processes, both of which §608#3.2 scales from cores to machines.

The two costs of a process pool, creating a worker and moving data through it, each hide a trap. A worker starts by fork, duplicating the parent via copy-on-write (§603#3.1), or by spawn, a fresh interpreter that re-imports every module and reloads any model the parent held. Fork is cheaper yet unsafe once the parent has threads, since a lock held by another thread at the fork is copied held and never released, hence spawn by default on macOS (3.8) and forkserver on Linux (3.14). Arguments and results then travel by pickling (§605#4.1), so for large arrays the copy can outweigh the compute, which shared_memory (3.8) avoids by mapping one buffer into every worker.

2.2. Multithreading

Multiprocessing suits work that is partitioned once and rarely talks, whereas workers that share state continuously, a cache, a model, a queue, call for multithreading. It trades isolation for a shared address space, and is lighter and so faster, as communication reduces to ordinary memory access rather than IPC, but pays for it in synchronisation. The sharing also shrinks the memory footprint, as $m$ threads carry one heap, text segment, and page table where $m$ processes each keep their own. Fork’s copy-on-write narrows the gap only until writes diverge the copies. A thread switch also skips the page-table swap and TLB flush a process switch pays (§603#3.1).

Given that a thread reduces to the triple $($register set, stack, scheduler$)$, it must pay for creation, storage, and context switch. How much each costs depends on who supplies it. The user-space runtime supplies $m$ user threads, each created by an allocation and switched by a function call, unseen by the kernel. The kernel supplies $n$ kernel threads, each created by a system call and backed by a kernel stack. A threading model fixes the ratio $m \colon n$, that is, how many of a program’s threads the kernel will know about. While every mainstream OS now buys one per thread, only a kernel thread can be dispatched onto a core, and hence each one bought is a core the program can use.

For instance, Linux adopts the $1 \colon 1$ model by setting $n = m$. A C program in user-space requests a thread by pthread_create(), the API that POSIX Threads (POSIX.1c, 1995) standardise while leaving the mapping to each implementation, and glibc’s native POSIX thread library (NPTL, 2003) answers each call with one clone(), one task_struct per thread. The runtime then writes no scheduler of its own. The kernel parks a thread that blocks, preempts one that computes, and resumes each in turn, so no thread can hold up another. Every one of those acts, however, is a syscall, and every thread a kernel stack. The cost thus scales as $O(m)$ while one caps $m$ at the C10K wall.

The $m \colon 1$ model (green threads, early Java) drops the kernel’s share to zero. The runtime multiplexes every user thread onto one kernel thread, cheap enough to spawn one flow per task, so nothing runs in parallel and one blocking syscall stalls all $m$. The $m \colon n$ model (Go goroutines, Java virtual threads) instead splits the bill so cheapness and parallelism coexist. The runtime keeps the $m$ triples while the kernel carries a small $n$ ($m \gg n$, one per core), and a runtime scheduler migrates user threads across the $n$ on blocking. Coroutines are the $m \colon 1$ model in all but name, one kernel thread carrying every flow, so a blocking call stalls the loop and Gunicorn must supply the $n$.

2.3. Thread Safety

The shared address space that made threads cheap however lets concurrent access corrupt what they share. For the author, thread safety means correctness under concurrent calls, held by avoiding shared mutable state (e.g. immutability, thread-local storage) or by guarding it with synchronisation primitives. The latter ship with pthreads on Unix-like systems and most languages wrap its pthread_mutex_lock and related calls into higher-level APIs {e.g. Python: threading, C++: std::thread}. CPython’s own global interpreter lock (GIL) is such a mutex and admits a single thread to run its bytecode at a time, withholding the parallelism threading’s $1\colon1$ kernel threads would deliver.

For the caller, safety is stated explicitly, whether in the type (e.g. Java’s HashMap against ConcurrentHashMap) or in the reference (e.g. CPython’s queue.Queue). Note that the GIL’s serialising of bytecode also makes a single list.append or dict lookup thread-safe, a benefit CPython delivers but never promises. The same serialisation means threads still help with I/O-bound work, since each releases the GIL before it blocks in a system call, and so many can wait at once while one runs CPython. By contrast, CPU-bound work gains nothing and the threads take turns at the GIL, each holding it until a waiter’s 5 ms switch interval (see sys.getswitchinterval) expires and requests it.

The GIL dates from 1991 when single-core machines dominated and a whole-interpreter lock forfeited no parallelism since none existed beyond one core. Its necessity traces to CPython’s use of reference counting for GC (§602#1.3), which puts a count on every object that even a read updates, and one lock over the interpreter was preferred to one on every object since concurrent reads race. The design became a liability once multicore arrived and Python rose to the language of data science, whose users saw one core in use and began complaining about the GIL. However, Linux faced the same trade with the big kernel lock (BKL, §603#2.1) and removed it by 2.6.39 (2011).

Greg Stein’s 1996 patch against Python 1.4 tried the removal and was rejected for halving single-threaded speed. Once multicore was the norm, the trial was revived in 2023 as the experimental free-threaded build of 3.13 (2024, PEP 703), that trades the single lock for per-object locking and atomic counts at the cost of single-thread overhead and C extensions opting in via Py_mod_gil. Subsequently, 3.14 (2025, PEP 779) promoted the build to supported and re-enabled the specialising interpreter to recover the lost speed, aiming at a free-threaded default. CPU-bound code will thus gain parallelism and with it the synchronisation problems that follow.

III

3.1. Race Conditions

Although shared memory makes communication faster, concurrent executions can corrupt whatever they share, and a race condition is any such outcome whose correctness depends on the timing of concurrent operations. For instance, if two threads read the same file and each writes back its own edit, then whoever finishes last silently erases the other. The root cause is non-atomicity, as x += 1 compiles to a sequence $(\text{load}$, $\text{add}$, $\text{store})$ whose gaps admit another execution, whether by preemption (§603#3.1) on one core or simultaneity across two. An atomic operation, by contrast, is a single hardware instruction that runs to completion while no other core may touch its address.

Programs acquire races in three recurring shapes. The narrowest is the data race, where two threads touch one memory location, at least one of them writing, with nothing ordering them (e.g. two threads incrementing the same counter). A critical section is a region of code that must execute atomically over shared state, which threads must enter one at a time, and enclosing each access in one cures this shape. Unguarded, the counter loses an update, one write overwriting the other, and worse, 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.

Wider gaps produce semantic races, faults in the order of operations that arise between sections each already guarded. In check-then-act, one thread tests a condition and acts on what it found while another invalidates it in between (e.g. both find a file absent and both create it). Security names this 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 any file. In the lost wakeup, one thread announces a change before its waiter listens (e.g. the queue fills just before the waiter sleeps). In both, the interval, not the operation, is what the section must span.

Race condition and data race are hence neither equivalent nor nested terms, the former a fault in order, the latter in the accesses, as two individually locked withdrawals race on arrival order with no data race at all. Yet both resist testing, as the triggering interleaving is outside the program’s control, and even a print statement perturbs the schedule enough to hide the Heisenbug (Gray, 1985). Dynamic race detectors (e.g. ThreadSanitizer) therefore instrument every access and report data races. Still, a clean run vouches only for the schedules observed, and a semantic race goes unreported, its accesses individually synchronised and the flaw in the gap between them.

3.2. Memory Ordering

Shared memory fails a second way, in visibility rather than interleaving, 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, not atomicity, 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, promising only some of sequential consistency’s orderings. x86-TSO is relatively strong (only store-load reordering), while ARM’s 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. Memory barriers (fences) are the ISA instructions that force the missing ordering (mfence on x86, dmb on ARM).

Happens-before (adapted from Lamport, 1978) formalises visibility as a strict partial order generated by program order and synchronisation edges, so a data race is a pair of conflicting unsynchronised accesses (same location, at least one write) left incomparable by it. 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. In both, the fences arrive behind language primitives (std::atomic in C++, volatile in Java) and inside the synchronisation primitives that follow, so correctly locked code is correctly ordered for free.

3.3. Synchronisation

Synchronisation primitives supply critical sections with atomicity and the ordering that relaxed hardware trades for speed. The simplest, the spinlock, burns cycles in a busy wait until the lock frees. A mutual exclusion lock (mutex, e.g. pthread_mutex_lock()) instead sleeps until the release and trades the burn for a context switch that pays once the hold outlasts it. Linux’s fast userspace mutex (futex) enters the kernel only when contended, while the two combine in the adaptive mutex by spinning briefly before parking. Variants adjust not the wait but whom they admit, as a reentrant lock re-admits its holder and read-write locks admit many readers or one writer.

Acquiring a lock is itself a check-then-set, which two threads could interleave to recreate the very race the lock guards against. Every lock is therefore built from a hardware atomic operation, requested of the hardware by an ISA instruction rather than of the OS by a syscall. The earliest such instruction, test-and-set (IBM System/360, 1964), sets a flag and returns the flag’s old value in one step, rich enough to build a spinlock but no more. Compare-and-swap (CAS, System/370, 1970) generalises it by writing a new value only if the address still holds the one the caller expects (e.g. x86 LOCK CMPXCHG). A failure can only mean another thread wrote first. A LOCK-prefixed instruction moreover acts as a full fence, supplying the ordering along with the atomicity.

Lock-free data structures instead use atomics directly, where an update reads the old value, computes the new, and retries the CAS on failure (e.g. C++’s std::atomic, Java’s AtomicInteger). This guarantees some thread always progresses even if others stall, whereas a lock holder preempted mid-section blocks every waiter. The ABA problem is the one caveat, as a location can change from $A$ to $B$ and back between the read and the CAS, which then succeeds though the state moved beneath it. It bites hardest on pointers, where a freed and reallocated node returns at its old address, and is defeated by packing a version counter beside the value so every write changes the pair.

Semaphores (Dijkstra, 1965) extend the lock from exclusion to coordination by generalising its binary state to an integer counter, the counting semaphore, under the invariant $v \geq 0$, where P decrements $v$ or blocks at zero and V increments it, both named in his native Dutch. POSIX.1b (1993) ships the pair as sem_wait() and sem_post() in <semaphore.h>, and underneath sem_wait() parks on the same futex a contended mutex does. A DB connection pool is a notable realisation (§606#3.3), such that an initial value $N$ admits at most $N$ threads at once, a bound that suits a pool of $N$ interchangeable resources, not a critical section.

A mutex is a key its holder must return, a semaphore is a count any thread may raise, and a binary semaphore ($N = 1$) is simply a mutex without an owner. Ownerlessness cuts both ways, letting one thread post what another awaits, a signalling no lock can express, while a wrong-thread release cannot be caught nor priority inheritance defined, hence mutexes for exclusion and semaphores for counting. The initial value declares the intent, $N$ for a pool and zero for a signal yet to come, where the first post mints what the first wait collects. Both thus bound admission to what they guard (e.g. section or pool), yet neither selects the admitted thread, as a release frees an arbitrary waiter.

A thread may own the lock yet be unable to proceed until its predicate holds. For instance, a consumer finds the queue empty which only a producer needing that same lock can fill. The crude fix is to unlock, nap on a timer, and retry, although any interval merely trades lock contention against latency. Condition variables remedy this with notification. Under POSIX, a consumer calls pthread_cond_wait() to atomically release the lock and sleep with no gap for a lost wakeup. The producer, on fill, calls pthread_cond_signal() or _broadcast() to rouse one sleeper or all. The variable itself is only a queue of sleepers, so a signal without a waiter is discarded, unlike a semaphore’s.

The waiter then rechecks the predicate in a loop, for a wake can be spurious, POSIX permitting returns with no signal, or stale, a third thread having taken the item first. Mesa semantics (Xerox PARC, 1980) then promise only that the predicate may have changed. Hoare semantics (1974) instead suspend the signaller and hand the lock straight to the waiter, so the predicate is guaranteed on waking. Yet the weaker guarantee is the one that composes, as pthread_cond_broadcast() cannot hand the lock to every waiter it wakes and a timed wait expires promising nothing, whereas one loop absorbs both. POSIX passes no lock with either call, so a woken thread reacquires it to proceed.

A concurrent program ultimately borrows what it cannot do alone, the indivisible step only hardware can take and the sleep only the kernel can grant, and every primitive above is some ratio of the two. The classical problems rehearse it. The producer-consumer problem needs a mutex and two semaphores (or condition variables) to block producers when the fixed-size buffer is full and consumers when it is empty, whereas the readers-writers problem schedules many readers and rare writers over one shared object without starving either side and maps onto the read-write lock. Correct synchronisation thus fits the primitive to the access pattern rather than wrapping every operation in a lock.

3.4. Liveness

Correctness decomposes into two guarantees, safety that nothing bad ever happens and liveness that something good eventually does. A race and a hang are the failures of under- and over-synchronised sharing, violating the former and the latter respectively. The race does not cause the hang, its cure does, as locks buy safety by forbidding orders of execution, and an over-broad ban leaves none to run. Lock granularity, how much state one lock guards, decides the balance. Specifically, a single coarse-grained lock serialises the very parallelism multithreading was meant to buy (e.g. the GIL), whereas fine-grained locks (e.g. free-threaded CPython) buy it back.

If every object carries its own lock, then an operation touching two objects must hold both locks, and holding one while awaiting another is where the hang begins. Formally, a set of threads each permanently blocked on a lock another holds is called a deadlock, for which the Coffman conditions (1971) are jointly necessary: i) mutual exclusion; ii) hold-and-wait; iii) no preemption; and iv) circular wait. The last appears as a cycle in the wait-for graph, where an edge $T_i \to T_j$ reads as $T_i$ waiting on a lock that $T_j$ holds. A chain of waits closed into a cycle is in fact the deadlock, since each thread proceeds only after the next, and so the loop has no first mover (i.e. cycle $\iff$ deadlock).

Against the cycle stand three defences: i) lock ordering: acquisitions only ascend a fixed total order, so 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 & recovery: the wait-for graph is searched and a member of any cycle found is aborted. Ordering falsifies circular wait in advance, whereas timeouts and recovery break hold-and-wait and no-preemption respectively, after the fact. Ordering is strongest but presupposes that fixed total order, which locks created per row or taken inside libraries deny, and therefore the fallback to the other two.

For example, the cycle closes when PostgreSQL transactions update the same two rows in opposite orders ($T_1\colon A \to B$, $T_2\colon B \to A$). Its detector runs DFS after a 1$\text{s}$ timeout, and the checker, say $T_1$, aborts itself with ERROR: deadlock detected, its rollback releasing A for $T_2$ (§606#2.2). At the other extreme, Linux uses the ostrich algorithm, and ignores deadlock because a rare hang does not justify checking every wait. Neither helps against a lock never released, which hangs its waiters without any cycle, yet higher-level languages cure it with scope-bound acquisition (e.g. with in Python). It releases on every exit path one would accidentally miss (e.g. pthread_mutex_unlock() in C).

Beyond the hang, two subtler relatives also violate liveness. 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), and is cured by fairness, a bound on how long any waiter can be overtaken. 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 .

‹ Previous603. operating system Next ›605. networking
Ready