Critical Sections

A critical section is a sequence of operations on shared state that must appear atomic to every other thread — no other thread may observe or modify that state between the first operation and the last. The counter++ of Race Conditions is a three-instruction critical section. "Check the balance, then debit it" is one. "Remove the node from the list and update its neighbours’ pointers" is one; a reader that sees the list halfway through walks into freed memory.

The classic requirements, from Dijkstra’s 1965 formulation, are three. Mutual exclusion: at most one thread inside at a time. Progress: if no thread is inside and some want in, one of them gets in — the mechanism cannot deadlock by itself. Bounded waiting: a thread that wants in eventually gets in — the mechanism cannot starve a thread forever. Peterson’s algorithm and Dekker’s algorithm show that two threads can achieve all three with plain loads and stores *given a sequentially consistent memory* — which real hardware does not provide, which is why real implementations use atomic instructions (Atomic Operations) and are packaged as a Mutexes.

The boundaries are the design decision. Too narrow and the invariant is not protected: locking each of two updates separately leaves a window between them where another thread sees the first without the second. Too wide and you serialise work that did not need serialising. The right boundary is the smallest region across which the shared state’s invariant is temporarily false.

One lock for everything is coarse-grained: simple to reason about, impossible to deadlock against itself, and a serialisation point for the whole program. The Linux kernel’s Big Kernel Lock was exactly this — one lock around most kernel code — and its removal, completed in 2011, took over a decade of splitting it into per-subsystem and per-object locks. CPython’s GIL is a coarse-grained lock around the interpreter: it makes the runtime’s own data structures safe cheaply and caps Python-level parallelism at one core, which is why CPU-bound Python scales with processes, not threads (How C++, JavaScript and Python Map onto the OS).

Fine-grained locking gives each object, bucket or row its own lock so unrelated operations proceed in parallel. Java’s ConcurrentHashMap locks per bucket (per bin); a database locks per row (Locks and Deadlocks); a kernel locks per inode, per socket, per page. The cost is complexity: more locks means more possible orderings and more ways to deadlock (Deadlocks), more memory for lock words, and more cache-line traffic when locks are acquired and released. Lock *striping* — N locks, choose by hash — is the usual middle ground.

Reader-writer locks split by intent instead of by object: many readers or one writer. They pay off when reads dominate and the section is long enough that the extra bookkeeping (a reader count, two wait queues) is amortised; for short sections a plain mutex is often faster. RCU (read-copy-update, pervasive in the Linux kernel) goes further: readers take no lock at all, writers publish a new version and free the old one after every reader that could have seen it has finished. It is the mechanism behind lock-free routing-table and dentry lookups.

Contention is the product of how often a lock is taken and how long it is held. Halving the hold time halves the contention at the same request rate, so the second design lever after granularity is what you do while holding the lock. The rule is: only the operations on the shared state. Everything else — computing the new value, formatting a log line, allocating the node you are about to insert — happens before or after.

Three things must never be inside a critical section. I/O: a write to a log or socket can block for milliseconds, and every other thread wanting the lock blocks with it; a network call under a lock turns a 100 ns section into a 100 ms one. Memory allocation: malloc and new take their own internal locks and can page-fault; holding a lock while allocating both lengthens the section and creates a lock-order dependency you did not choose. Callbacks into unknown code: a user callback may try to take the same lock (deadlock with a non-recursive mutex) or a different one in the wrong order. Copy what you need out, release, then call.

The measurable symptom of a fat section is convoying: threads arrive faster than the section drains, queue up on the lock, and each one’s wait includes every predecessor’s hold time — including the time predecessors spent descheduled while holding the lock. Latency then depends on the scheduler rather than the work. perf lock on Linux, -XX:+PrintConcurrentLocks on the JVM and a py-spy dump showing many threads in acquire are the tools.

Every critical section is a serial segment in an otherwise parallel program, and Amdahl’s law says the maximum speedup on N cores is 1 / (s + (1 − s) / N), where s is the serial fraction. If 10% of the work happens under one lock, infinite cores give at most 10×; on 32 cores you get about 7.8×; on 64 about 8.8×. If 1% is serial the ceiling is 100×. The lock does not need to be slow to cap you; it needs only to be *there*.

This is why the granularity and hold-time work above matters beyond fixing races: it is the difference between a service that scales to a machine’s cores and one that flattens at four. It is also why measurement precedes lock-splitting — a lock that is held 0.1% of the time is not your problem even if it looks ugly, and a lock held 15% of the time is your problem even if each hold is 200 ns. The serial fraction is what you measure; the number of locks is an implementation detail.