Why this subject matters now
Single-thread performance stopped improving on schedule around 2005, when Dennard scaling ended and the industry converted transistor budget into cores instead of clock. Herb Sutter's "The Free Lunch Is Over" named the consequence at the time. Software that wants the machine's throughput must be concurrent, and concurrency is not a library detail but a change in the semantics of the language. Twenty years later the machine in question is a 52-way server part or a 10-core phone, and the expectation on a working engineer has hardened accordingly. It is no longer enough to know one language's idioms. Services are polyglot, with a Python control plane spawning processes, a Rust or C++ data plane holding locks for nanoseconds, and an async runtime multiplexing a hundred thousand connections onto a dozen threads. The engineer who understands why these designs differ, rather than only how to imitate them, is the one who can debug the 2 a.m. incident where the answer crosses a language boundary.
The deeper reason to study concurrency comparatively is that the
four languages here occupy four distinct points in a single
design space, and seeing all four at once makes the space
visible. C exposes the operating system's primitives raw,
fork, exec, wait, pipes, pthreads, futexes. C++ keeps C's cost
model but adds a precisely specified memory model (Boehm and
Adve, 2008) so that compilers and programmers finally agree on
what a racy program means, namely nothing at all. Rust keeps
C++'s memory model and moves the race check to compile time.
The type system, through the Send and
Sync traits and the ownership rules, rejects
programs that would race, a guarantee given formal footing by
the RustBelt project (Jung, Jourdan, Krebbers, and Dreyer).
Python historically declined the whole problem by serializing
bytecode execution behind the global interpreter lock, and the
free-threaded build specified by PEP 703, shipping as a
supported option since CPython 3.13, is the most consequential
change to the runtime in decades. Each design is a coherent
answer to the same question, and the differences are the
curriculum.
Everything below is measured where a measurement is possible.
The numbers quoted come from benchmark runs on this repository's
build machine, an Intel Xeon Platinum 8480+ (Sapphire Rapids, 52
logical CPUs visible, Ubuntu 22.04, gcc 11.4 at -O2, rustc
1.97 at -O, CPython 3.10), recorded in
classes/data/concurrency.json. The host is shared
and virtualized, so the numbers are honest order-of-magnitude
engineering data, not microarchitectural truth. Medians of
repeated runs are quoted throughout.
Concurrency versus parallelism
The two words name different things and the confusion between
them is the source of most bad design decisions in this area.
Concurrency is a property of the program's structure.
The program is composed of tasks whose executions may overlap in
time, so their steps interleave in an order the program does not
fix. Parallelism is a property of the execution. Two
operations physically occur at the same instant, which requires
at least two processing elements. A single-core machine running
an event loop over ten thousand sockets is maximally concurrent
and not parallel at all. A vectorized dgemm on one
thread is parallel at the ALU level and not concurrent in any
sense the programmer must reason about. Rob Pike's formulation,
that concurrency is about dealing with many things at once and
parallelism is about doing many things at once, is exactly
right and is worth holding onto because the failure modes
differ. Concurrency bugs are ordering bugs, and parallelism
problems are throughput problems.
concurrency (structure) parallelism (execution)
───────────────────────── ─────────────────────────
task A ▓▓░░░░▓▓░░▓▓░░ core 0 ▓▓▓▓▓▓▓▓▓▓▓▓▓▓
task B ░░▓▓░░░░▓▓░░▓▓ core 1 ▓▓▓▓▓▓▓▓▓▓▓▓▓▓
task C ░░░░▓▓▓▓░░▓▓░░ core 2 ▓▓▓▓▓▓▓▓▓▓▓▓▓▓
one core, interleaved three cores, simultaneous
▓ = running ░ = blocked/descheduled
Three reasons to introduce concurrency, none of which is speed. The first is latency hiding. A task that blocks on a disk read, a network round trip, or a lock is not using the CPU, and structuring the program so another task can run during that window converts dead time into work. The measured pipe round trip on this machine, 3.7 µs, is roughly ten thousand instruction issues wasted per blocking handoff, and a network round trip is a thousand times worse. The second is responsiveness. A user interface, a control loop, or a health-check endpoint must make progress on a deadline regardless of what long computation is in flight, and the only structural way to guarantee that is to make the long computation a separate task that the scheduler can preempt. The third is modelling. Some problems are concurrent in their statement, one task per connection, per sensor, per simulated agent, and forcing them into a sequential program means hand-writing a scheduler that the runtime already provides.
Three reasons to introduce parallelism, all of which are speed, but of different kinds. Throughput is independent work units per second, the metric for a web server or a data loader, improved by adding workers until some shared resource saturates. Latency of a single computation means splitting one job across cores so it finishes sooner, the metric for a matrix multiply or a parallel sort, and the one governed by Amdahl's law, since the serial fraction \(s\) caps speedup at \(1/s\) no matter how many cores are available. Capacity is the case where some working sets simply do not fit in one machine's cache, memory, or memory bandwidth, and spreading across sockets buys aggregate bandwidth rather than aggregate FLOPs. The distinction matters because the three call for different designs. Throughput wants many independent workers and no shared state, single-job latency wants fine-grained decomposition and cheap synchronization, and capacity wants data placement and NUMA awareness.
A useful discipline follows. Decide first whether the problem is concurrent, parallel, or both, then choose the mechanism. Concurrency without parallelism is best served by an event loop or coroutines, which cost nothing per task beyond a stack frame or a state machine. Parallelism without meaningful concurrency, data-parallel loops over disjoint array slices, is best served by a work-stealing pool with no locks in the inner loop. Programs needing both, which is most servers, layer the two: parallel workers, each internally concurrent. Every mechanism described on this page fits somewhere in that grid, and the grid is what the later section on choosing between processes, threads, and async formalizes.
Processes, isolation first
fork, exec, wait
The oldest concurrency primitive on Unix is also the strongest.
A process owns a private virtual address space, so two processes
share nothing unless they arrange to. fork()
duplicates the calling process. The child receives a
copy-on-write image of the parent's memory, open file
descriptors that refer to the same underlying descriptions, and
a return value of 0 where the parent receives the child's pid.
exec*() replaces the current image with a new
program, preserving descriptors, which is the entire mechanism
by which shells wire up redirection. The shell adjusts
descriptors between fork and exec, then execs the target.
wait() and
waitpid() collect the child's exit status and
release the kernel's bookkeeping for it. A dead child that no
one has waited for is a zombie, kept around solely so its status
can still be delivered.
parent child
────── ─────
fork() ──────────────────────────────► (copy-on-write clone begins here)
│ │ dup2(pipe_wr, STDOUT_FILENO)
│ │ close unused ends
│ │ execvp("sort", ...) image replaced
│ read(pipe_rd, ...) ◄── pipe ────── │ writes flow into the pipe
│ waitpid(child, &status, 0) ◄─────── │ _exit(0) status delivered to parent
The cost of this isolation is measurable but smaller than its
reputation. On this machine, a fork immediately followed by
child exit and parent wait costs a median of 118.9 µs;
adding an exec of /bin/true raises it to
499.7 µs, and posix_spawn of the same binary
costs 432.6 µs. For comparison, creating and joining a
pthread costs 33.9 µs. A process is roughly 3.5 times the
price of a thread here, not the orders of magnitude folklore
suggests, because copy-on-write means fork copies page tables
and metadata, not memory. What stays expensive is what happens
after. Every write to a shared-with-parent page takes a fault
and a page copy, and communication requires a kernel-mediated
channel.
Pipes and the cost of a context switch
A pipe is a bounded in-kernel byte queue with a read end and a
write end. Writes of up to PIPE_BUF bytes (4096 on
Linux) are atomic with respect to other writers. A read on an
empty pipe blocks, a write on a full pipe blocks, and a read on
a pipe whose write ends are all closed returns 0, which is how
end-of-file propagates down a shell pipeline. Because blocking
reads and writes deschedule the caller, a pipe doubles as a
crude scheduling instrument. Bouncing one byte between two
processes pinned to the same core forces two context switches
per round trip, and timing it bounds the switch cost. Measured
here, it comes to 3,730 ns per round trip, or roughly 1.9 µs per
context switch including the pipe read/write system calls
themselves. That number is the floor under every design that
blocks per message, and it is about 350 times the 5.5 ns cost
of an uncontended mutex acquire measured below. The ratio is
the quantitative content of the advice "do not take a kernel
round trip when a user-space handoff will do".
The same pattern, three ways. The C version is the canonical
one. The Rust version shows the higher-level
std::process API over the same syscalls, and Python's
subprocess is a direct wrapper over
fork/exec/wait (via posix_spawn or
vfork where it can).
/* run "sort" as a child, feed it words through a pipe, read nothing back:
* the child inherits stdout. gcc -O2 pipeline.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/wait.h>
#include <unistd.h>
int main(void) {
int fds[2]; /* fds[0] = read end, fds[1] = write end */
if (pipe(fds) != 0) { perror("pipe"); exit(1); }
pid_t pid = fork();
if (pid == 0) { /* child */
dup2(fds[0], STDIN_FILENO); /* stdin now reads from the pipe */
close(fds[0]); /* close originals; dup2 kept a copy */
close(fds[1]); /* CRUCIAL: or sort never sees EOF */
execlp("sort", "sort", (char *)NULL);
perror("execlp"); /* only reached if exec failed */
_exit(127);
}
/* parent */
close(fds[0]);
const char *words = "pear\napple\nquince\n";
write(fds[1], words, strlen(words));
close(fds[1]); /* child's read() now returns 0: EOF */
int status;
waitpid(pid, &status, 0);
printf("sort exited with %d\n", WEXITSTATUS(status));
return 0;
}
// std::process wraps the same fork/exec/wait; Stdio::piped() makes the pipe.
use std::io::Write;
use std::process::{Command, Stdio};
fn main() -> std::io::Result<()> {
let mut child = Command::new("sort")
.stdin(Stdio::piped())
.stdout(Stdio::inherit())
.spawn()?; // fork + exec happen here
// Scope the handle so the write end drops (closes) before we wait:
// without the close, sort waits forever for EOF, we wait for sort.
{
let stdin = child.stdin.as_mut().expect("piped stdin");
stdin.write_all(b"pear\napple\nquince\n")?;
}
drop(child.stdin.take()); // explicit close of the pipe
let status = child.wait()?; // waitpid
println!("sort exited with {:?}", status.code());
Ok(())
}
# subprocess wraps fork/exec/wait (using posix_spawn when it can).
import subprocess
# communicate() writes, closes the pipe so the child sees EOF, and waits:
# the same three steps the C version performs by hand.
result = subprocess.run(
["sort"],
input="pear\napple\nquince\n",
capture_output=True,
text=True,
)
print(result.stdout, end="")
print("sort exited with", result.returncode)
# The raw primitives still exist when needed:
# os.fork(), os.execvp(), os.waitpid(), os.pipe()
The single most common bug in hand-rolled pipelines appears in
the comments above, an unclosed write end. The kernel delivers
end-of-file on a pipe only when every descriptor referring to
the write end is closed, and fork duplicates descriptors, so
the child holds a copy of the write end it never uses. If the
child does not close it, the child's own read never returns 0
and the pipeline deadlocks with both processes blocked. The
Rust version makes the same mistake harder by tying the close
to a drop. The Python version buries it inside
communicate().
Processes remain the right tool more often than a
threads-first curriculum suggests. Isolation means a crash,
a leak, or a corrupted heap in the child cannot take down the
parent. Address-space separation is the only memory-safety
boundary C offers at all. Chrome runs a process per site,
not a thread per site, for exactly this reason, and Python's
multiprocessing module (measured below) turns
the same isolation into its escape hatch from the GIL.
Zombies, orphans, and the duty to reap
Process termination on Unix is a two-party protocol, and both
failure modes have names. When a child exits, the kernel keeps
a minimal record, exit status, resource usage, and the pid
itself, until the parent collects it with
wait. Until then the child is a
zombie, with no address space, no threads, and nothing
left to schedule, but still occupying a process-table slot and
a pid. The demonstration is short enough to run. Fork a child
that exits immediately, sleep, and ask ps about it.
On this machine that prints
4142637 Z zombie <defunct>. After the
parent calls waitpid, the same query prints
nothing, because the entry is gone. A long-lived server that
forks and never waits leaks one pid per child until it hits
/proc/sys/kernel/pid_max and
fork starts failing with EAGAIN,
a failure that presents as "cannot start any new process
anywhere on the box" and confuses everyone in the room.
The mirror-image case is the orphan, where the parent
exits first, leaving a running child with no one to report to. The
kernel reparents orphans to pid 1, or to the nearest ancestor
that called prctl(PR_SET_CHILD_SUBREAPER), and
that reaper waits on them, which is why an orphan is a
bookkeeping event rather than a leak. Orphaning is also how
daemonization traditionally works. The program forks, the
parent exits, and the child continues under init with no
controlling terminal. The pattern to internalize is that a zombie is a
parent's bug and an orphan is usually a deliberate design.
Reaping correctly has one subtlety worth stating because it is
missed constantly. SIGCHLD is a standard signal,
not a queued one, so several children exiting close together
may deliver one signal. A handler that calls
waitpid once therefore leaves zombies behind
under load. The handler must loop with
WNOHANG until it returns 0 or -1. On Linux,
setting SIGCHLD to SIG_IGN asks the
kernel to auto-reap, trading away the ability to read exit
statuses. With that set, the measured program above forks
three children and a subsequent waitpid(-1, WNOHANG)
returns -1, meaning there is nothing left to wait for.
/* The only correct SIGCHLD handler shape: loop, WNOHANG, save errno. */
#include <errno.h>
#include <signal.h>
#include <sys/wait.h>
#include <unistd.h>
static volatile sig_atomic_t reaped = 0;
static void on_sigchld(int sig) {
(void)sig;
int saved = errno; /* handlers must not clobber errno */
pid_t p;
/* WNOHANG + loop: signals coalesce, so one delivery may mean many
exits. Calling waitpid once here is the classic zombie leak. */
while ((p = waitpid(-1, NULL, WNOHANG)) > 0)
reaped++;
errno = saved;
}
void install(void) {
struct sigaction sa;
sa.sa_handler = on_sigchld;
sigemptyset(&sa.sa_mask);
sa.sa_flags = SA_RESTART | SA_NOCLDSTOP; /* restart interrupted syscalls */
sigaction(SIGCHLD, &sa, NULL);
/* Alternative on Linux: signal(SIGCHLD, SIG_IGN) auto-reaps, but then
exit statuses are unrecoverable. Measured: waitpid then returns -1. */
}
use std::process::{Command, Stdio};
// Rust's Child does NOT wait on drop: dropping the handle without wait()
// leaves a zombie exactly as in C. The type system does not save you here
// because a leaked kernel resource is not a memory-safety violation.
fn main() -> std::io::Result<()> {
let mut child = Command::new("true").stdout(Stdio::null()).spawn()?;
// try_wait() is waitpid(WNOHANG): poll without blocking.
loop {
match child.try_wait()? {
Some(status) => {
println!("reaped: {status}");
break;
}
None => std::thread::sleep(std::time::Duration::from_millis(1)),
}
}
// Or simply child.wait()?; which blocks until the child is collected.
Ok(())
}
import os, signal, subprocess
# subprocess.Popen objects are reaped by wait()/poll(); the module also
# reaps stragglers opportunistically when new Popens are created, which
# hides the bug in short scripts and exposes it in long-lived servers.
p = subprocess.Popen(["true"])
p.wait() # collects the status; no zombie
# Raw fork/wait is available and behaves exactly like C:
pid = os.fork()
if pid == 0:
os._exit(0)
os.waitpid(pid, 0)
# Auto-reap, giving up exit statuses (POSIX: SA_NOCLDWAIT):
signal.signal(signal.SIGCHLD, signal.SIG_IGN)
IPC beyond the pipe
Once processes are the unit of concurrency, every byte they share has to be arranged explicitly, and the mechanism chosen determines both the cost per message and what synchronization still has to be built by hand. Four mechanisms cover nearly all real use.
| Mechanism | Copies per message | Framing | Synchronization | Best for |
|---|---|---|---|---|
| Pipe / FIFO | 2 (user→kernel→user) | byte stream, writes ≤ PIPE_BUF atomic | free, blocking read/write, EOF on last close | pipelines, small control messages |
| Unix domain socket | 2 | stream or datagram, datagrams preserve boundaries | free, also passes descriptors via SCM_RIGHTS | request/response, descriptor handoff, local RPC |
| POSIX message queue | 2 | discrete messages with priorities | free, blocking send/receive, bounded depth | priority work queues between processes |
| Shared memory (shm_open + mmap) | 0 | none, it is memory | none, the programmer supplies it | bulk data, zero-copy frames and tensors |
The table's last row is the interesting one and its last two
columns explain each other. Shared memory is the only
zero-copy option, and it is the only one that gives back the
entire shared-mutable-state problem. Two processes mapping the
same pages need a mutex, and a pthread mutex works across
processes only if it lives inside the shared region and is
initialized with PTHREAD_PROCESS_SHARED. The
common production compromise is the one measured earlier in
Python. Put the bulk payload in shared memory and send only a
small descriptor, an offset and a length, over a socket or
pipe, so the kernel provides ordering and wakeups while the
data never gets copied. Moving a 64 MiB array to a worker cost
205 ms pickled through a pipe versus 11 ms when only the
shared-memory name crossed the pipe, 18.7 times faster,
and the difference is exactly the two copies the table
promises.
The C version below is the shape of that compromise, a shared
region created with shm_open and
mmap, plus a socketpair used purely
as a doorbell. It runs as written and prints
child processed generation 1 of a 8200-byte shared
region.
/* gcc -O2 ipc.c -lrt : zero-copy payload, socket used only as a doorbell */
#define _GNU_SOURCE
#include <fcntl.h>
#include <stdio.h>
#include <sys/mman.h>
#include <sys/socket.h>
#include <sys/wait.h>
#include <unistd.h>
struct Region { unsigned long seq; double payload[1024]; };
int main(void) {
const char *name = "/conc_demo";
shm_unlink(name); /* start clean */
int fd = shm_open(name, O_CREAT | O_EXCL | O_RDWR, 0600);
ftruncate(fd, sizeof(struct Region)); /* size the object */
struct Region *r = mmap(NULL, sizeof *r, PROT_READ | PROT_WRITE,
MAP_SHARED, fd, 0); /* MAP_SHARED: both see writes */
int sv[2];
socketpair(AF_UNIX, SOCK_STREAM, 0, sv); /* the doorbell */
if (fork() == 0) { /* child */
close(sv[0]);
char c;
while (read(sv[1], &c, 1) == 1) { /* wait for "data ready" */
double sum = 0;
for (int i = 0; i < 1024; i++) sum += r->payload[i];
r->seq++; /* no copy of the payload */
write(sv[1], &c, 1); /* "done" */
}
_exit(0);
}
close(sv[1]);
for (int i = 0; i < 1024; i++) r->payload[i] = i;
char c = 'x';
write(sv[0], &c, 1); /* ring */
read(sv[0], &c, 1); /* wait for completion */
printf("child processed generation %lu of a %zu-byte shared region\n",
r->seq, sizeof *r);
close(sv[0]);
wait(NULL);
munmap(r, sizeof *r);
shm_unlink(name); /* names persist otherwise */
return 0;
}
// C++ uses the same syscalls; the value it adds is putting a real
// process-shared mutex INSIDE the shared region, which is what any
// design with multiple writers needs.
#include <pthread.h>
#include <sys/mman.h>
#include <fcntl.h>
#include <unistd.h>
#include <cstdio>
#include <cerrno>
struct Shared {
pthread_mutex_t m; // must live in the shared pages, not in either heap
unsigned long seq;
double payload[1024];
};
Shared *attach(const char *name, bool create) {
int fd = shm_open(name, create ? (O_CREAT | O_RDWR) : O_RDWR, 0600);
if (create) ftruncate(fd, sizeof(Shared));
auto *s = static_cast<Shared *>(mmap(nullptr, sizeof(Shared),
PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0));
if (create) {
pthread_mutexattr_t a;
pthread_mutexattr_init(&a);
// Without PROCESS_SHARED the mutex is undefined across processes.
pthread_mutexattr_setpshared(&a, PTHREAD_PROCESS_SHARED);
// ROBUST: if the holder dies, the next locker gets EOWNERDEAD
// instead of hanging forever. Crashes are normal across processes.
pthread_mutexattr_setrobust(&a, PTHREAD_MUTEX_ROBUST);
pthread_mutex_init(&s->m, &a);
}
close(fd);
return s;
}
void bump(Shared *s) {
int rc = pthread_mutex_lock(&s->m);
if (rc == EOWNERDEAD) pthread_mutex_consistent(&s->m); // repair invariants
s->seq++;
pthread_mutex_unlock(&s->m);
}
// std gives unix sockets directly; shared memory needs a crate (memmap2)
// or raw libc, because mapping the same bytes into two processes is
// exactly the aliasing the type system cannot check.
use std::io::{Read, Write};
use std::os::unix::net::UnixStream;
use std::thread;
fn main() -> std::io::Result<()> {
// socketpair(2), typed: two connected endpoints, no filesystem name
let (mut a, mut b) = UnixStream::pair()?;
let t = thread::spawn(move || -> std::io::Result<()> {
let mut buf = [0u8; 5];
b.read_exact(&mut buf)?; // datagram-like framing must be
b.write_all(b"pong!")?; // built by hand on SOCK_STREAM
Ok(())
});
a.write_all(b"ping!")?;
let mut reply = [0u8; 5];
a.read_exact(&mut reply)?;
println!("{}", std::str::from_utf8(&reply).unwrap());
t.join().unwrap()?;
Ok(())
}
// For zero-copy across processes: memmap2::MmapMut over a shm_open fd,
// then an explicit protocol. The unsafe is unavoidable and honest: no
// compiler can know what the other process is doing to those pages.
from multiprocessing import Process, shared_memory
import numpy as np
def worker(name: str, n: int, out):
shm = shared_memory.SharedMemory(name=name) # maps the SAME pages
a = np.ndarray((n,), dtype=np.float32, buffer=shm.buf)
out.send(float(a.sum())) # only the result is pickled
shm.close()
if __name__ == "__main__":
from multiprocessing import Pipe
n = 16 * 1024 * 1024 # 64 MiB
shm = shared_memory.SharedMemory(create=True, size=n * 4)
a = np.ndarray((n,), dtype=np.float32, buffer=shm.buf)
a[:] = 1.0
parent, child = Pipe()
p = Process(target=worker, args=(shm.name, n, child))
p.start()
print(parent.recv())
p.join()
shm.close()
shm.unlink() # unlink exactly once, or the segment leaks in /dev/shm
# Measured on this machine: 11 ms this way versus 205 ms passing the same
# array by value through a Pool (pickle over a pipe): 18.7x.
Threads and locks, the shared-memory contract
What a thread is, and what it costs
A thread is an execution context, program counter, registers,
and stack, scheduled by the kernel but sharing its process's
address space, descriptors, and heap with every sibling. On
Linux both threads and processes are created by
clone(). The difference is which resources the
flags say to share. Sharing is the point and the poison. Any
thread can read what any other thread wrote, at the price that
any thread can read what another thread is halfway through
writing. The measured creation costs on this machine, medians
over thousands of create-join pairs, are 33.9 µs for a
pthread, 45.4 µs for a Rust std::thread
(the same pthread plus ownership bookkeeping), 74.5 µs
for a Python threading.Thread (a pthread plus
interpreter-state setup), against 118.9 µs for a fork.
Each thread also reserves stack address space, 8 MB of virtual
memory by default on Linux, committed lazily a page at a time.
Ten thousand threads is feasible in address-space terms and
fatal in scheduler terms, which is the observation that
motivates the thread pools and event loops later on this page.
Mutual exclusion
The mutex is the oldest correctness tool, going back to
Dijkstra's 1965 formulation of the mutual-exclusion problem. At
most one thread executes the critical section at a time, so any
invariant that holds when the lock is released holds when it is
next acquired. A modern Linux mutex costs almost nothing when
uncontended, a single atomic compare-and-swap in user space,
5.53 ns per lock-increment-unlock measured here, and enters the
kernel through a futex (Franke, Russell, and Kirkwood, 2002)
only when a thread must sleep. The four implementations below
are semantically identical. The differences worth noticing are
who unlocks (in C the programmer, everywhere else a destructor
or context manager) and where the lock lives relative to the
data it guards (only Rust ties them together in the type, since
Mutex<i64> owns its data, and the compiler
refuses access without the lock).
/* pthreads: the lock and the data are associated only by convention. */
#include <pthread.h>
#include <stdio.h>
long counter = 0;
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
void *worker(void *arg) {
for (long i = 0; i < 1000000; i++) {
pthread_mutex_lock(&lock);
counter++; /* critical section */
pthread_mutex_unlock(&lock); /* forget this and deadlock later */
}
return NULL;
}
int main(void) {
pthread_t t[4];
for (int i = 0; i < 4; i++) pthread_create(&t[i], NULL, worker, NULL);
for (int i = 0; i < 4; i++) pthread_join(t[i], NULL);
printf("%ld\n", counter); /* always 4000000 */
return 0;
}
// C++: RAII. The guard's destructor unlocks on every exit path,
// including exceptions. g++ -O2 -std=c++20 counter.cpp -lpthread
#include <iostream>
#include <mutex>
#include <thread>
#include <vector>
int main() {
long counter = 0;
std::mutex m;
std::vector<std::thread> threads;
for (int i = 0; i < 4; i++)
threads.emplace_back([&] {
for (long j = 0; j < 1'000'000; j++) {
std::lock_guard<std::mutex> guard(m);
counter++;
} // guard unlocks here
});
for (auto &t : threads) t.join();
std::cout << counter << "\n"; // always 4000000
}
// Rust: Mutex<i64> owns the data. There is no way to reach the i64
// without lock(), so "forgot to take the lock" is a compile error.
use std::sync::{Arc, Mutex};
use std::thread;
fn main() {
let counter = Arc::new(Mutex::new(0i64));
let handles: Vec<_> = (0..4)
.map(|_| {
let c = Arc::clone(&counter);
thread::spawn(move || {
for _ in 0..1_000_000 {
*c.lock().unwrap() += 1; // guard drops (unlocks) here
}
})
})
.collect();
for h in handles {
h.join().unwrap();
}
println!("{}", *counter.lock().unwrap()); // always 4000000
}
import threading
counter = 0
lock = threading.Lock()
def worker():
global counter
for _ in range(1_000_000):
with lock: # context manager releases on any exit
counter += 1
threads = [threading.Thread(target=worker) for _ in range(4)]
for t in threads: t.start()
for t in threads: t.join()
print(counter) # always 4000000
# The lock is NOT redundant under the GIL: counter += 1 compiles to
# LOAD / ADD / STORE bytecodes, and the interpreter may switch threads
# between them. Without the lock this prints less than 4000000.
Condition variables and the bounded buffer
A mutex answers "not at the same time", and a condition
variable answers "not until". The pattern comes from Hoare's
1974 monitors. A thread that finds the state unsuitable
atomically releases the mutex and sleeps. A thread that makes
the state suitable signals, and the sleeper wakes holding the
mutex again and rechecks. The recheck is mandatory, always
while, never if, for two reasons that
hold in all four languages. First, spurious wakeups are
permitted by every one of these APIs (POSIX permits them so
implementations need not suppress them at cost). Second, and
more fundamentally, between the signal and the wakeup another
thread may acquire the mutex and consume the state. The
condition variable promises that the predicate was true at
signal time, not that it is true at wake time. The canonical
exercise is the bounded buffer. Producers wait while full,
consumers wait while empty, with two conditions so that
producers wake consumers and vice versa.
#include <pthread.h>
#define CAP 8
long buf[CAP];
int head = 0, tail = 0, count = 0; /* count disambiguates full/empty */
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t not_full = PTHREAD_COND_INITIALIZER;
pthread_cond_t not_empty = PTHREAD_COND_INITIALIZER;
void put(long v) {
pthread_mutex_lock(&m);
while (count == CAP) /* while, never if */
pthread_cond_wait(¬_full, &m); /* unlocks m, sleeps, relocks */
buf[tail] = v;
tail = (tail + 1) % CAP;
count++;
pthread_cond_signal(¬_empty);
pthread_mutex_unlock(&m);
}
long get(void) {
pthread_mutex_lock(&m);
while (count == 0)
pthread_cond_wait(¬_empty, &m);
long v = buf[head];
head = (head + 1) % CAP;
count--;
pthread_cond_signal(¬_full);
pthread_mutex_unlock(&m);
return v;
}
#include <condition_variable>
#include <deque>
#include <mutex>
class BoundedBuffer {
std::deque<long> q;
const size_t cap = 8;
std::mutex m;
std::condition_variable not_full, not_empty;
public:
void put(long v) {
std::unique_lock<std::mutex> lk(m);
not_full.wait(lk, [&] { return q.size() < cap; });
// wait(lk, pred) is exactly: while (!pred()) wait(lk);
q.push_back(v);
not_empty.notify_one();
}
long get() {
std::unique_lock<std::mutex> lk(m);
not_empty.wait(lk, [&] { return !q.empty(); });
long v = q.front();
q.pop_front();
not_full.notify_one();
return v;
}
};
use std::collections::VecDeque;
use std::sync::{Condvar, Mutex};
pub struct BoundedBuffer {
q: Mutex<VecDeque<i64>>,
cap: usize,
not_full: Condvar,
not_empty: Condvar,
}
impl BoundedBuffer {
pub fn put(&self, v: i64) {
let mut q = self.q.lock().unwrap();
while q.len() == self.cap {
q = self.not_full.wait(q).unwrap(); // gives back the guard
}
q.push_back(v);
self.not_empty.notify_one();
}
pub fn get(&self) -> i64 {
let mut q = self.q.lock().unwrap();
while q.is_empty() {
q = self.not_empty.wait(q).unwrap();
}
let v = q.pop_front().unwrap();
self.not_full.notify_one();
v
}
}
// In production Rust this whole type is a channel:
// std::sync::mpsc::sync_channel(8) or crossbeam_channel::bounded(8).
import threading
from collections import deque
class BoundedBuffer:
def __init__(self, cap=8):
self.q = deque()
self.cap = cap
self.m = threading.Lock()
self.not_full = threading.Condition(self.m)
self.not_empty = threading.Condition(self.m)
def put(self, v):
with self.not_full:
while len(self.q) == self.cap:
self.not_full.wait()
self.q.append(v)
self.not_empty.notify()
def get(self):
with self.not_empty:
while not self.q:
self.not_empty.wait()
v = self.q.popleft()
self.not_full.notify()
return v
# queue.Queue(maxsize=8) is the stdlib's hardened version of the above.
Measured on this machine, the mutex-and-two-condvars queue moves a median of 5.1 million items per second between one producer and one consumer. The lock-free ring buffer derived later on this page moves 19.4 million under the same protocol, and the gap is the cost of the futex sleep/wake cycles and of bouncing the lock's cache line. Both numbers matter. Five million handoffs per second is far more than most applications need, which is why the advice to start with locks is not condescension but arithmetic.
Reader-writer locks, semaphores, and barriers
The mutex and the condition variable are complete in the sense that everything else can be built from them, and three derived primitives are standard enough to be in every library. A reader-writer lock splits acquisition into shared and exclusive modes, any number of readers or one writer, never both. It is the right tool exactly when reads vastly outnumber writes and each critical section is long enough to amortize the lock's own bookkeeping, which is a narrower window than it sounds, because a rwlock's shared acquire still writes a reader count, so it still bounces a cache line between cores. For a critical section of a few nanoseconds, the measured 87 ns of coherence traffic dominates and a plain mutex, or better, per-thread state or RCU, wins. The other trap is writer starvation. An implementation that always admits an arriving reader will never let a writer in under sustained read load, so real implementations choose a policy, and the choice belongs in the design notes rather than in a surprise.
A semaphore is a counter with atomic wait and post, Dijkstra's P and V. Its two uses are worth separating. A binary semaphore used for mutual exclusion is a worse mutex, since it has no notion of an owner and therefore cannot support priority inheritance or error checking, but a counting semaphore expresses resource pools, at most \(k\) concurrent uploads, \(k\) database handles, \(k\) GPU streams, which a mutex cannot express at all. A barrier holds \(n\) participants until all \(n\) arrive, the natural fit for bulk-synchronous iteration. Every worker updates its shard, everyone waits, and everyone reads the merged result. Barriers make the phase boundary a happens-before edge, which is why data written before a barrier is safe to read after it without further synchronization.
/* gcc -O2 syncprims.c -lpthread ; prints config=8 total_ops=8000 */
#define _GNU_SOURCE
#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
static pthread_rwlock_t rw = PTHREAD_RWLOCK_INITIALIZER;
static long shared_config = 7;
static sem_t slots; /* counting semaphore: 3 permits */
static pthread_barrier_t barrier;
static __thread long tls_ops = 0; /* one instance per thread */
static long total_ops = 0;
static pthread_mutex_t total_m = PTHREAD_MUTEX_INITIALIZER;
static void *worker(void *arg) {
long id = (long)arg;
for (int i = 0; i < 1000; i++) {
pthread_rwlock_rdlock(&rw); /* many readers concurrently */
volatile long v = shared_config; (void)v;
pthread_rwlock_unlock(&rw);
tls_ops++; /* private: no synchronization */
}
if (id == 0) {
pthread_rwlock_wrlock(&rw); /* exclusive against all readers */
shared_config = 8;
pthread_rwlock_unlock(&rw);
}
sem_wait(&slots); /* at most 3 threads inside */
sem_post(&slots);
pthread_barrier_wait(&barrier); /* all 8 arrive before any leaves */
pthread_mutex_lock(&total_m);
total_ops += tls_ops; /* fold private counters once */
pthread_mutex_unlock(&total_m);
return NULL;
}
int main(void) {
sem_init(&slots, 0, 3);
pthread_barrier_init(&barrier, NULL, 8);
pthread_t t[8];
for (long i = 0; i < 8; i++) pthread_create(&t[i], NULL, worker, (void *)i);
for (int i = 0; i < 8; i++) pthread_join(t[i], NULL);
printf("config=%ld total_ops=%ld (main's tls_ops=%ld)\n",
shared_config, total_ops, tls_ops); /* main's own copy is 0 */
return 0;
}
// C++17 gave shared_mutex; C++20 gave semaphore, barrier, latch, jthread.
// g++ -O2 -std=c++20 cppprims.cpp -lpthread
#include <barrier>
#include <cstdio>
#include <mutex>
#include <semaphore>
#include <shared_mutex>
#include <thread>
#include <vector>
std::shared_mutex rw;
long config = 7;
std::counting_semaphore<3> slots{3};
std::barrier sync_point{8};
thread_local long tls_ops = 0; // language-level TLS since C++11
std::mutex total_m;
long total_ops = 0;
int main() {
std::vector<std::jthread> ts; // jthread joins in its destructor
for (int i = 0; i < 8; i++)
ts.emplace_back([i] {
for (int j = 0; j < 1000; j++) {
std::shared_lock rl(rw); // reader
volatile long v = config; (void)v;
rl.unlock();
tls_ops++;
}
if (i == 0) { std::unique_lock wl(rw); config = 8; } // writer
slots.acquire();
slots.release();
sync_point.arrive_and_wait();
std::lock_guard g(total_m);
total_ops += tls_ops;
});
ts.clear(); // joins all eight
printf("config=%ld total_ops=%ld main_tls=%ld\n",
config, total_ops, tls_ops); // prints 8, 8000, 0
}
// std has RwLock and Barrier; a counting semaphore lives in tokio::sync
// or is three lines of Mutex + Condvar. thread_local! is the TLS macro.
use std::cell::Cell;
use std::sync::{Barrier, Mutex, RwLock};
use std::thread;
thread_local! {
static TLS_OPS: Cell<u64> = const { Cell::new(0) };
}
fn main() {
let config = RwLock::new(7i64);
let barrier = Barrier::new(8);
let total = Mutex::new(0u64);
thread::scope(|s| {
let (config, barrier, total) = (&config, &barrier, &total);
for i in 0..8 {
s.spawn(move || {
for _ in 0..1000 {
let v = *config.read().unwrap(); // shared mode
std::hint::black_box(v);
TLS_OPS.with(|c| c.set(c.get() + 1));
}
if i == 0 {
*config.write().unwrap() = 8; // exclusive mode
}
barrier.wait();
*total.lock().unwrap() += TLS_OPS.with(|c| c.get());
});
}
});
println!("config={} total={} main_tls={}", // 8, 8000, 0
config.read().unwrap(), total.lock().unwrap(),
TLS_OPS.with(|c| c.get()));
}
import threading
# threading has Semaphore, Barrier, RLock, and local(), but NO rwlock:
# the writer-preferring minimum is a Condition plus three counters.
class RWLock:
def __init__(self):
self._c = threading.Condition()
self._readers = 0
self._writer = False
self._waiting_writers = 0 # prevents writer starvation
def acquire_read(self):
with self._c:
while self._writer or self._waiting_writers:
self._c.wait() # while, never if
self._readers += 1
def release_read(self):
with self._c:
self._readers -= 1
if self._readers == 0:
self._c.notify_all()
def acquire_write(self):
with self._c:
self._waiting_writers += 1
while self._writer or self._readers:
self._c.wait()
self._waiting_writers -= 1
self._writer = True
def release_write(self):
with self._c:
self._writer = False
self._c.notify_all()
slots = threading.Semaphore(3) # counting: 3 permits
barrier = threading.Barrier(8)
tls = threading.local() # attributes are per-thread
# Measured: 8 workers x 1000 ops fold to total_ops = 8000, and the main
# thread's tls has no 'ops' attribute at all: separate storage, not a copy.
Recursive locks are a design smell
A recursive (reentrant) mutex lets the thread that already
holds it acquire it again, counting the acquisitions and
releasing only when the count returns to zero. It exists
because a natural refactor breaks without it. A public method
takes the lock and calls another public method that also takes
the lock, and with a plain mutex the second acquisition
self-deadlocks. Reaching for the recursive variant fixes the
symptom and hides the real problem, which is that the class
has no stated invariant boundary. The reason to care is
precise rather than aesthetic. A mutex's contract is that
invariants hold whenever the lock is not held. Recursive
acquisition means the inner critical section runs while the
outer one has the object half-updated, so the inner
code sees a state the class documentation says is impossible.
Worse, a condition variable cannot be used correctly with a
recursive lock, since wait releases the mutex once, not
\(n\) times, so a nested waiter sleeps while still holding the
lock, and nothing can wake it.
The standard fix is the two-layer split. Public methods take
the lock and immediately delegate to private
_locked methods that assume it is held and never
take it themselves. Every language on this page offers the
recursive variant (PTHREAD_MUTEX_RECURSIVE,
std::recursive_mutex,
threading.RLock) and every style guide worth
following treats its appearance as a question to answer, not
a tool to reach for. Python is the exception that proves the
rule. RLock is the default recommendation there
because module-level code and __del__ can
re-enter almost anything, and the interpreter's own
import lock is reentrant for exactly that reason.
Thread-local storage
Thread-local storage is the primitive that makes the other
primitives unnecessary, and it is underused for exactly that
reason. It solves the problem by deleting it. A thread-local
variable has one instance per thread, so accesses need no
synchronization at all, no atomics, no locks, no coherence
traffic. The measured payoff was already quoted in the
sharded-counter row. Per-thread padded counters ran at 21,780
Mops against 11.5 Mops for the same work behind one mutex,
a factor of about 1,900, because the shared version pays a
cache-line migration per operation and the thread-local
version pays nothing. The implementation is cheap. On x86-64
Linux, a thread-local access with the initial-exec model is a
single mov off the %fs segment base,
which is why __thread and
thread_local cost roughly what a global costs.
Dynamically loaded modules pay more, since the general-dynamic
model calls __tls_get_addr.
The idiom is the same in all four languages and appears in the
code above. Accumulate privately, fold once. Per-thread
allocator arenas (tcmalloc, jemalloc, mimalloc), per-thread
random number generators, per-CPU statistics in the kernel,
and Python's threading.local() request contexts
are all one pattern. The costs to remember are lifetime and
leakage. Thread-local objects are destroyed when the thread
exits, so a pool that recycles threads carries state from one
task to the next, which is the source of the classic bug
where a request's authentication context leaks into an
unrelated later request served by the same pool worker.
Deadlock, livelock, and priority inversion
The four Coffman conditions
Deadlock is a set of threads each waiting for a resource another member of the set holds, so none ever proceeds. Coffman, Elphick, and Shoshani (1971) showed that four conditions must hold simultaneously, which is useful because it converts prevention into a menu. Break any one and deadlock becomes impossible.
| Condition | Statement | How real systems break it |
|---|---|---|
| Mutual exclusion | a resource is held exclusively | use immutable data, copies, or lock-free structures, with RCU for read paths |
| Hold and wait | a holder requests more while holding | acquire all locks at once (std::scoped_lock) or none. Take, then release, then retake. |
| No preemption | a lock cannot be taken away | try-lock with timeout and rollback. Database transactions abort a victim. |
| Circular wait | a cycle exists in the wait-for graph | impose a total order on locks and always acquire in it. This is the practical answer. |
Circular wait is the condition to attack, because it is the only one that can be enforced statically by convention and checked mechanically. Assign every lock a level and require that a thread holding a lock at level \(k\) may acquire only locks at levels \(> k\). Then the wait-for graph is a DAG by construction, since an edge always increases level and a cycle would need one to decrease. Linux's lockdep validator does precisely this at runtime, learning the observed order between lock classes on the first acquisition and reporting a splat the first time any execution violates it, which finds potential deadlocks even in runs that did not deadlock. That last property is the important one. Deadlocks are timing dependent, so testing for them directly is nearly worthless, and order checking is the only scalable defense.
A worked deadlock and three fixes
The canonical example is transferring between two accounts,
each guarded by its own mutex, where a thread locks the source
and then the destination. Two threads transferring in opposite
directions, A to B and B to A, produce the cycle. This is not
hypothetical. The version below, compiled with g++ -O2 and run
on this machine with a 50 µs sleep between the two
acquisitions to widen the window, hangs on every run and had
to be killed by a 5-second timeout (exit status 124). The same
program with std::scoped_lock completes 400
transfers and conserves the balances (a=1000, b=1000,
sum=2000).
thread 1: transfer(a → b) thread 2: transfer(b → a)
────────────────────────── ──────────────────────────
lock(a.m) ✓ lock(b.m) ✓
... 50 µs window ...
lock(b.m) ✗ blocked lock(a.m) ✗ blocked
│ │
└──── waits for thread 2 ──────────┘
waits for thread 1
wait-for graph: a cycle of length 2 → deadlock
Three repairs, in the order a reviewer should prefer them.
Order the locks. Sort the two mutexes by address (or
by account id, or by any total order agreed program-wide) and
always take the smaller first, which removes the cycle and
costs one comparison. Take them together.
std::scoped_lock, std::lock, and
Rust's equivalents use a try-and-back-off algorithm that never
holds one while blocking on another, breaking hold-and-wait.
Try-lock with backoff. Attempt the second lock with
try_lock, and on failure release the first, wait
a randomized interval, and retry. The third is the general
technique when no total order exists, for instance when locks
are discovered dynamically, and its hazard is the subject of
the next subsection. Without randomization, two threads can
retry in lockstep forever.
#include <mutex>
#include <thread>
struct Account { long id; long balance; std::mutex m; };
// BROKEN: locks in the order the arguments arrive. Measured: hangs,
// killed by a 5 s timeout on every run.
void transfer_broken(Account &from, Account &to, long amount) {
std::lock_guard<std::mutex> g1(from.m);
std::this_thread::sleep_for(std::chrono::microseconds(50));
std::lock_guard<std::mutex> g2(to.m); // ← the cycle closes here
from.balance -= amount;
to.balance += amount;
}
// FIX 1: a total order on addresses. Every thread agrees, so no cycle.
void transfer_ordered(Account &from, Account &to, long amount) {
Account *a = &from, *b = &to;
if (a > b) std::swap(a, b);
std::lock_guard<std::mutex> g1(a->m);
std::lock_guard<std::mutex> g2(b->m);
from.balance -= amount;
to.balance += amount;
}
// FIX 2: acquire both atomically. scoped_lock never blocks holding one.
void transfer_scoped(Account &from, Account &to, long amount) {
std::scoped_lock lk(from.m, to.m); // measured: 400 transfers,
from.balance -= amount; // balances conserved
to.balance += amount;
}
// FIX 3: try-lock with randomized backoff, for dynamically found locks.
void transfer_trylock(Account &from, Account &to, long amount) {
for (int spin = 0;; spin++) {
std::unique_lock<std::mutex> l1(from.m);
std::unique_lock<std::mutex> l2(to.m, std::try_to_lock);
if (l2.owns_lock()) {
from.balance -= amount;
to.balance += amount;
return;
}
l1.unlock(); // release before retrying:
// randomized so two threads do not retry in lockstep (livelock)
std::this_thread::sleep_for(
std::chrono::microseconds(1 + (rand() % (1 << std::min(spin, 10)))));
}
}
/* C has no scoped_lock, so the total order is the whole technique.
The convention must be written down; nothing checks it for you. */
#include <pthread.h>
struct account { long id; long balance; pthread_mutex_t m; };
void transfer(struct account *from, struct account *to, long amount) {
struct account *first = from, *second = to;
if (first->id > second->id) { /* order by a stable key, not by
address, if ids are stable */
first = to; second = from;
}
pthread_mutex_lock(&first->m);
pthread_mutex_lock(&second->m);
from->balance -= amount;
to->balance += amount;
pthread_mutex_unlock(&second->m); /* unlock order is irrelevant */
pthread_mutex_unlock(&first->m); /* to correctness, only to
convoy behaviour */
}
/* try-lock variant: pthread_mutex_trylock returns EBUSY instead of blocking */
int transfer_try(struct account *a, struct account *b, long amt) {
pthread_mutex_lock(&a->m);
if (pthread_mutex_trylock(&b->m) != 0) {
pthread_mutex_unlock(&a->m); /* never hold while waiting */
return -1; /* caller backs off and retries */
}
a->balance -= amt; b->balance += amt;
pthread_mutex_unlock(&b->m);
pthread_mutex_unlock(&a->m);
return 0;
}
// Rust prevents data races, NOT deadlocks: this compiles and hangs
// exactly like the C++ version. The fix is the same discipline.
use std::sync::Mutex;
pub struct Account {
pub id: u64,
pub balance: Mutex<i64>,
}
pub fn transfer(from: &Account, to: &Account, amount: i64) {
// Total order on a stable key. Sorting by id, not by pointer, keeps
// the order stable across runs and across processes.
let (first, second) = if from.id < to.id { (from, to) } else { (to, from) };
let mut a = first.balance.lock().unwrap();
let mut b = second.balance.lock().unwrap();
if std::ptr::eq(first, from) {
*a -= amount;
*b += amount;
} else {
*b -= amount;
*a += amount;
}
} // both guards drop here, in reverse order
pub fn transfer_try(from: &Account, to: &Account, amount: i64) -> bool {
let Ok(mut a) = from.balance.try_lock() else { return false };
let Ok(mut b) = to.balance.try_lock() else { return false }; // a drops
*a -= amount; // on return
*b += amount;
true
}
import random, threading, time
class Account:
def __init__(self, ident, balance):
self.id = ident
self.balance = balance
self.lock = threading.Lock()
def transfer(a: Account, b: Account, amount: int) -> None:
# id() is not stable across processes; use a domain key when one exists
first, second = (a, b) if a.id < b.id else (b, a)
with first.lock:
with second.lock:
a.balance -= amount
b.balance += amount
def transfer_try(a: Account, b: Account, amount: int) -> None:
backoff = 0.0001
while True:
with a.lock:
if b.lock.acquire(blocking=False): # try-lock
try:
a.balance -= amount
b.balance += amount
return
finally:
b.lock.release()
# released a.lock by leaving the with-block before sleeping
time.sleep(random.uniform(0, backoff)) # randomize or livelock
backoff = min(backoff * 2, 0.05)
Livelock and starvation
A livelock is the failure the try-lock fix invites. Threads are running, changing state, and making no progress. Two threads each acquire their first lock, fail the second, back off by the same fixed interval, and retry in perfect lockstep forever. The system is busy, the CPUs are hot, no transfer completes, and no deadlock detector fires because nothing is blocked. The cure is the one used by Ethernet's binary exponential backoff and by every retry loop that works. Randomize, and grow the interval, so the symmetry that causes the collision is broken probabilistically. The code above does both, doubling to a cap with a uniform random multiplier.
Starvation is weaker and more common. A thread makes no progress while others do. Sources are a barging mutex where an arriving thread can steal the lock from a queued waiter (which is what makes most fast mutexes fast, and unfair), a reader-preferring rwlock under constant read load, and any priority scheme without aging. The remedies cost throughput, which is why they are opt-in. Ticket locks and MCS locks (Mellor-Crummey and Scott, 1991) grant in FIFO order and, as a side benefit, have each waiter spin on its own cache line rather than on one shared word, which is why they scale to high core counts where a naive test-and-set lock collapses.
Priority inversion
Priority inversion is the pathology where a high-priority thread waits on a lock held by a low-priority thread, which is itself preempted by an unrelated medium-priority thread. The high-priority thread is effectively running at the low thread's priority, and the medium thread, which needs no locks at all, holds up the whole system. The famous instance is the Mars Pathfinder lander in 1997. A high-priority bus management task blocked on a mutex held by a low-priority meteorological task, a medium-priority communications task kept preempting the latter, and the watchdog rebooted the spacecraft repeatedly until engineers enabled priority inheritance remotely by flipping a VxWorks flag.
Two standard countermeasures exist, both supported by POSIX
through pthread_mutexattr_setprotocol.
Priority inheritance (PTHREAD_PRIO_INHERIT)
temporarily raises the lock holder to the highest priority
among its waiters, so the low-priority holder cannot be
preempted by the medium-priority thread and exits the
critical section promptly. Priority ceiling
(PTHREAD_PRIO_PROTECT) raises any holder to a
statically assigned ceiling, the maximum priority of any
thread that can ever take the lock, which additionally
prevents deadlock among ceiling-ordered locks at the cost of
requiring the analysis up front. Neither is free, and neither
is on by default. Inversion is a real-time problem, and code
with no priority differences cannot suffer it, which is one
more argument for keeping thread priorities uniform unless
there is a specific reason not to.
Data races, what actually goes wrong
A definition worth being precise about
A data race is two accesses to the same memory
location from different threads, at least one a write, neither
an atomic operation, and neither ordered before the other by
synchronization. The C++11 standard, following Boehm and Adve,
declares the behavior of any program containing a data race
undefined. C11 adopted the same model, and Rust adopts it for
unsafe code while making safe code race-free by
construction. A data race is not the same thing as a
race condition, which is any timing-dependent
correctness bug. Withdraw-then-withdraw on a bank balance can
be a race condition built entirely out of perfectly
synchronized operations. Data races are the narrower, sharper
notion. They are the thing the memory model needs to outlaw so
that compilers can optimize single-threaded code as if it were
single-threaded.
The textbook demonstration is four threads incrementing a
shared counter five million times each with no lock. The
increment is a load, an add, and a store. Two threads that
load the same value store the same value, and one increment is
lost. Measured on this machine, gcc -O2, the counter declared
volatile so the compiler actually performs each
memory round trip, the expected total is 20,000,000 and the
five observed runs were
5,135,947, 5,125,041, 5,034,240, 5,045,762, 5,116,295. The
median run lost 74.4 percent of all updates. It is worth
pausing on how bad that is. Not a few percent lost at unlucky
interleavings, but three quarters of all work discarded,
because under contention the load-add-store windows of four
cores overlap almost constantly. And this is the
friendly failure mode, visible because the counter is
a single word. Without volatile, gcc hoists the
counter into a register and stores once per thread at the end,
which is a perfectly legal compilation of the racy program and
loses updates in a completely different pattern. That
sensitivity to optimization level is what undefined behavior
means in practice.
thread A thread B counter
──────── ──────── ───────
load counter → 41 41
load counter → 41 41
add 1 → 42 41
add 1 → 42 41
store 42 42
store 42 42 ← one increment lost
Why volatile is not a fix
volatile in C and C++ orders and preserves
accesses with respect to the compiler for a single
thread. It says nothing about atomicity or about what other
cores observe, and it does not prevent the interleaving above.
It exists for memory-mapped I/O. The measured 74 percent loss
happened with volatile. The correct tools are the
mutex (semantic simplicity, 11.5 M contended ops/s measured
below) or the atomic (44.6 M ops/s), and which to choose is a
later section's subject. Java's volatile is a
different and stronger construct (it gives ordering and
visibility, though still not read-modify-write atomicity),
a terminological collision that has caused real bugs in
programmers moving between the languages.
Rust, data races as type errors
Ownership, then Send and Sync
Rust's claim, "fearless concurrency" in Klabnik and Nichols's
phrase, is precise. Safe Rust programs contain no data races,
checked at compile time, with no runtime cost. The mechanism
is not a race detector. It is the composition of three rules
that exist independently of concurrency. First, every value
has one owner, and aliasing is governed by borrowing. At any
point there may be either many shared references
&T or exactly one mutable reference
&mut T, never both. Second, the
Send marker trait declares that ownership of a
type may move to another thread, and Sync
declares that a shared reference to it may be used from
another thread (formally, T: Sync iff
&T: Send). Third, APIs that cross thread
boundaries demand these traits in their signatures.
thread::spawn requires its closure to be
Send + 'static. Both traits are auto-derived
structurally, so a type is Send unless it contains something
that is not, and the "not" list is exactly the types whose
invariants a second thread could break,
Rc<T> (non-atomic reference counts),
Cell/RefCell shared across threads
(unsynchronized interior mutability, so they are Send but not
Sync), raw pointers (no invariants at all).
The consequence is that the racy counter from the previous section is not a bug you find in Rust; it is a program you cannot write. Here it is, attempted honestly, with the actual compiler output from rustc 1.97 on this machine.
// This is the C data-race program, transliterated. It does not compile.
use std::thread;
fn main() {
let mut counter = 0i64;
let mut handles = Vec::new();
for _ in 0..4 {
handles.push(thread::spawn(|| {
for _ in 0..5_000_000 {
counter += 1; // 4 threads, one &mut: rejected
}
}));
}
for h in handles {
h.join().unwrap();
}
println!("{counter}");
}
error[E0373]: closure may outlive the current function, but it borrows
`counter`, which is owned by the current function
--> compile_fail.rs:7:36
|
7 | handles.push(thread::spawn(|| {
| ^^ may outlive borrowed value `counter`
9 | counter += 1;
| ------- `counter` is borrowed here
|
note: function requires argument type to outlive `'static`
error[E0499]: cannot borrow `counter` as mutable more than once at a time
--> compile_fail.rs:7:36
|
7 | handles.push(thread::spawn(|| {
| - ^^ `counter` was mutably borrowed here
| in the previous iteration of the loop
Two independent rules each reject the program. E0373 is a
lifetime error. The spawned thread may outlive
main's stack frame, so borrowing a stack variable
into it is unsound (the same dangling-pointer bug C permits
silently). E0499 is the aliasing error, and it is the one that
encodes race freedom. Four closures each need
&mut counter, and the borrow checker permits
only one mutable borrow at a time. Note what the error is not.
It is not a special concurrency diagnostic. It is the ordinary
aliasing rule, applied across a spawn boundary.
The second rejection is the one that names the traits. Wrap
the counter in Rc<RefCell<i64>>, the
single-threaded shared-mutability idiom, and move a clone into
the thread.
use std::cell::RefCell;
use std::rc::Rc;
use std::thread;
fn main() {
let counter = Rc::new(RefCell::new(0i64));
let c2 = Rc::clone(&counter);
let h = thread::spawn(move || {
*c2.borrow_mut() += 1; // Rc's refcount is a plain integer:
}); // two threads cloning/dropping would race it
h.join().unwrap();
println!("{}", counter.borrow());
}
error[E0277]: `Rc<RefCell<i64>>` cannot be sent between threads safely
--> compile_fail2.rs:8:27
|
8 | let h = thread::spawn(move || {
| ------------- ^------ within this closure
| required by a bound introduced by this call
|
= help: the trait `Send` is not implemented for `Rc<RefCell<i64>>`
note: required by a bound in `spawn`
Rc bumps its reference count with ordinary
arithmetic, exactly the load-add-store that lost 74 percent of
updates above, so Rc opts out of
Send and the bound on spawn refuses
the closure. The fix is to buy back each capability with a
type that pays for it. Arc replaces the plain
refcount with an atomic one (restoring Send/Sync), and
Mutex replaces RefCell's
single-threaded borrow flag with real mutual exclusion. That
is why the working Rust counter earlier reads
Arc<Mutex<i64>>. Each wrapper is the
minimal payment for one trait bound, and the compiler will
name the missing trait if either is omitted. The RustBelt
project (Jung, Jourdan, Krebbers, Dreyer, POPL 2018) proved in
Coq that this discipline is sound. The ownership rules,
including the unsafe implementations inside
Arc, Mutex, and friends, compose
into a machine-checked absence-of-races theorem for the safe
fragment. The guarantee has limits worth stating exactly. Safe
Rust rules out data races, not race conditions, not
deadlocks (two Mutexes acquired in opposite
orders deadlock in Rust as anywhere), and not races through
unsafe code that violates its obligations.
Interior mutability, and the ladder of shared-mutability types
The borrow rule, many &T or one
&mut T, is too strict for real programs, so
Rust provides interior mutability, types that permit
mutation through a shared reference by enforcing the exclusion
some other way. They form a ladder, and knowing which rung a
type sits on is most of what Send/Sync reasoning amounts to in
practice. Cell<T> allows get and set with no
checking at all, which is sound only because it never hands
out an interior reference. It is Send but not Sync.
RefCell<T> tracks borrows with a counter and
panics on violation, moving the borrow check to runtime. It is
also Send, not Sync. Mutex<T> and
RwLock<T> enforce exclusion with real locks
and are therefore Sync when T: Send. The atomics
enforce it in hardware and are Sync unconditionally. Each rung
costs more and grants more, and the compiler requires climbing
exactly as far as the sharing pattern demands, no further.
The diagnostic is worth seeing because it is the clearest
statement of what Sync means. Attempting to share a
&Cell<i64> across scoped threads on this
machine, rustc 1.97.1 says
error[E0277]: `Cell<i64>` cannot be shared between
threads safely, with the notes
the trait `Sync` is not implemented for
`Cell<i64>` and
required for `&Cell<i64>` to implement
`Send`, plus a suggestion to use RwLock or
AtomicI64 instead. That last line is the
\(T: \text{Sync} \iff \&T: \text{Send}\) equivalence
printed by the compiler. Sharing a reference is
sending the reference, and Cell's whole design assumes only
one thread ever holds one.
Channels, sharing by communicating
The other half of Rust's story is that much concurrent code
needs no shared state at all. Ownership transfer through a
channel moves a value from one thread to another, and because
the sender's copy is statically dead afterwards, there is
nothing left to race over. The requirement is only
T: Send. std::sync::mpsc provides
multi-producer single-consumer channels in both unbounded
(channel) and bounded
(sync_channel(k)) forms, where the bounded
version supplies backpressure, the property that makes a
pipeline stable rather than a memory leak with extra steps.
crossbeam_channel adds multi-consumer support and
a select! over several channels.
One detail traps everyone once. A receiver's iteration ends
when all senders have been dropped, and the original
tx held by the spawning function is a sender, so
a loop that clones tx into each worker and then
iterates the receiver hangs forever unless the original is
explicitly dropped. This is the same closed-write-end
discipline as the pipe from the processes chapter, enforced by
Drop instead of by close. The
program below was compiled with rustc 1.97.1 and prints
7998000, the sum of the four workers' output.
use std::sync::mpsc;
use std::thread;
fn channel_pipeline() -> i64 {
let (tx, rx) = mpsc::channel::<i64>(); // unbounded; sync_channel(k)
for w in 0..4i64 { // for backpressure
let tx = tx.clone(); // one sender per worker
thread::spawn(move || {
for i in 0..1000 {
tx.send(w * 1000 + i).unwrap();
}
}); // this clone drops here
}
drop(tx); // the ORIGINAL sender: without this, rx never ends
rx.iter().sum() // ends when every sender has been dropped
}
fn main() {
println!("{}", channel_pipeline()); // measured: 7998000
}
// C++ has no standard channel. The idiom is a bounded queue plus an
// explicit "no more producers" signal, which is exactly the bookkeeping
// Rust's Drop does automatically.
#include <condition_variable>
#include <mutex>
#include <optional>
#include <queue>
template <class T>
class Channel {
std::queue<T> q;
std::mutex m;
std::condition_variable cv;
size_t senders; // the manual refcount Rust infers
size_t cap;
public:
Channel(size_t n_senders, size_t capacity)
: senders(n_senders), cap(capacity) {}
void send(T v) {
std::unique_lock lk(m);
cv.wait(lk, [&] { return q.size() < cap; }); // backpressure
q.push(std::move(v));
cv.notify_all();
}
void close_sender() { // every producer MUST call this
std::lock_guard g(m);
if (--senders == 0) cv.notify_all();
}
std::optional<T> recv() {
std::unique_lock lk(m);
cv.wait(lk, [&] { return !q.empty() || senders == 0; });
if (q.empty()) return std::nullopt; // closed and drained
T v = std::move(q.front());
q.pop();
cv.notify_all();
return v;
}
};
import queue, threading
# queue.Queue is the channel; the sentinel is the manual "all senders
# dropped" signal, and forgetting one sentinel per consumer hangs the
# program in exactly the way forgetting drop(tx) does in Rust.
q = queue.Queue(maxsize=64) # maxsize gives backpressure
SENTINEL = object()
N_WORKERS = 4
def producer(w: int):
for i in range(1000):
q.put(w * 1000 + i)
total = 0
def consumer():
global total
while True:
item = q.get()
if item is SENTINEL:
q.task_done()
return
total += item # safe: one consumer thread
q.task_done()
ws = [threading.Thread(target=producer, args=(w,)) for w in range(N_WORKERS)]
c = threading.Thread(target=consumer)
for t in ws: t.start()
c.start()
for t in ws: t.join()
q.put(SENTINEL) # one per consumer
c.join()
print(total) # 7998000
Memory models, what one thread sees of another
Happens-before
Everything in this section rests on one relation. Lamport's 1978 paper defined happens-before for distributed systems as the smallest transitive relation containing program order within each process and send-before-receive across messages. The shared-memory memory models of C++11, C11, and Rust are the same construction with synchronization operations playing the role of messages. Write \( a \xrightarrow{sb} b \) when \(a\) precedes \(b\) in one thread's program order (sequenced-before), and \( a \xrightarrow{sw} b \) when \(a\) is a release operation that \(b\), an acquire operation, synchronizes with, for instance a mutex unlock and the next acquisition of that mutex, or an atomic store with release ordering and an atomic load with acquire ordering that reads the stored value. Then happens-before is the transitive closure.
$$ \xrightarrow{hb} = \big( \xrightarrow{sb} \cup \xrightarrow{sw} \big)^{+} $$The model's two load-bearing guarantees follow. If a write \(w\) happens-before a read \(r\) of the same location and no other write intervenes in happens-before order, \(r\) observes \(w\). If two conflicting accesses are unordered by happens-before and not both atomic, the program has a data race and, in C and C++, undefined behavior. The entire discipline of lock-based programming compresses to one sentence. Every unlock synchronizes-with the next lock of the same mutex, so everything done inside one critical section happens-before everything done in the next, and threads that only touch shared data inside critical sections can pretend the interleaving is sequential.
Sequential consistency, and why hardware refuses it
Lamport's 1979 note defined the gold-standard model. An execution is sequentially consistent (SC) if its result equals that of some single interleaving of all threads' operations in which each thread's operations appear in program order. SC is what every programmer assumes until corrected. Hardware does not provide it by default because the store is the slow operation. A core that had to make every store globally visible before its next load would stall constantly. Instead, each x86 core retires stores into a private store buffer and lets younger loads proceed, reading its own buffered stores early (store forwarding) while other cores cannot see them yet. The resulting model, formalized as x86-TSO by Sewell, Owens, and colleagues (CACM 2010), preserves all orderings except one. A store followed by a load of a different location may be observed in the reverse order. ARM and POWER relax much further, reordering nearly everything absent explicit barriers, which is why code that "worked on x86 for years" dies on a phone.
core A core B
────── ──────
X = 1 ─► [store buffer A] Y = 1 ─► [store buffer B]
r1 = Y (reads memory: 0) r2 = X (reads memory: 0)
│ │
▼ (later) ▼ (later)
X=1 drains to L1/memory Y=1 drains to L1/memory
both loads ran before either store became visible: r1 = r2 = 0
The store-buffering litmus test, worked and then measured
The canonical two-line demonstration, called SB in the litmus
literature. Shared variables X and Y start at 0. Thread A runs
X = 1; r1 = Y. Thread B runs
Y = 1; r2 = X. Under SC the outcome
\( r_1 = r_2 = 0 \) is impossible, and the proof is worth
doing precisely because it is short (Problem 3 below does it
in full). Some operation goes first in the interleaving, that
operation is one of the stores, and whichever store goes first
is seen by the other thread's later load, forcing at least one
of \(r_1, r_2\) to be 1. On real x86 both stores can sit in
store buffers while both loads read memory, so both-zero
appears. The measurement here used two threads pinned to
distinct cores, released per trial by a coordinator, one
million trials per run. With relaxed atomics, which compile to
plain mov store and mov load, the
forbidden-under-SC outcome appeared 56 times per million in
one run and 104 in another. With
memory_order_seq_cst, for which gcc 11.4 compiles
the store to xchg, an implicitly locked
instruction that drains the store buffer, the count was 0 in
2,000,000 trials. The anomaly is rare, roughly one trial in
ten thousand here, which is exactly what makes this bug class
vicious. A test suite can pass ten thousand times.
// Core of the measured harness (per-trial reset and pinning omitted).
#include <atomic>
std::atomic<long> X{0}, Y{0};
long r1, r2;
void thread_a() { // relaxed: mov store, mov load
X.store(1, std::memory_order_relaxed);
r1 = Y.load(std::memory_order_relaxed);
}
void thread_b() {
Y.store(1, std::memory_order_relaxed);
r2 = X.load(std::memory_order_relaxed);
}
// measured: r1==0 && r2==0 in 56-104 of 1,000,000 trials on this Xeon.
// with memory_order_seq_cst (store compiles to xchg): 0 in 2,000,000.
/* C11 stdatomic: same model, same spelling modulo syntax. */
#include <stdatomic.h>
atomic_long X = 0, Y = 0;
long r1, r2;
void thread_a(void) {
atomic_store_explicit(&X, 1, memory_order_relaxed);
r1 = atomic_load_explicit(&Y, memory_order_relaxed);
}
void thread_b(void) {
atomic_store_explicit(&Y, 1, memory_order_relaxed);
r2 = atomic_load_explicit(&X, memory_order_relaxed);
}
/* plain long without _Atomic would be a data race: undefined behavior,
and the compiler may cache, reorder, or invent accesses. */
// Rust adopted the C++ orderings wholesale (minus consume).
use std::sync::atomic::{AtomicI64, Ordering};
static X: AtomicI64 = AtomicI64::new(0);
static Y: AtomicI64 = AtomicI64::new(0);
fn thread_a() -> i64 {
X.store(1, Ordering::Relaxed);
Y.load(Ordering::Relaxed) // r1
}
fn thread_b() -> i64 {
Y.store(1, Ordering::Relaxed);
X.load(Ordering::Relaxed) // r2
}
// Note: no data race here even with Relaxed. Atomics are never *racy*
// in the UB sense; Relaxed only abandons ordering, not atomicity.
The ordering menu
C++11 (Boehm and Adve, PLDI 2008; formalized further by Batty,
Owens, Sarkar, Sewell, and Weber, POPL 2011) exposes the
hardware's spectrum as per-operation orderings, and Rust uses
the identical set minus consume. Each row buys
strictly more ordering and costs strictly more on weakly
ordered hardware; on x86 the first four rows compile to plain
loads and stores, and only seq_cst stores pay for a drain.
| Ordering | Guarantee | Typical use | x86 cost |
|---|---|---|---|
| relaxed | atomicity only, no ordering, no synchronizes-with | counters, statistics, flags checked elsewhere | plain mov (lock-prefixed if RMW) |
| acquire (loads) | no later access moves before the load, and it sees everything before the matching release | lock acquire, consumer side of publication | plain mov |
| release (stores) | no earlier access moves after the store | lock release, producer side of publication | plain mov |
| acq_rel | both, for read-modify-write operations | reference counts' final decrement, queue CAS loops | lock-prefixed RMW |
| seq_cst | acquire/release plus one global total order over all seq_cst ops | anything resembling SB, default when unsure | store drains store buffer (xchg/mfence) |
The pairing that carries almost all real code is
release/acquire publication. A producer writes data
with plain stores, then stores a flag or pointer with release.
A consumer loads the flag with acquire and, if it sees the
published value, is guaranteed by
\( \text{writes} \xrightarrow{sb} \text{release}
\xrightarrow{sw} \text{acquire} \xrightarrow{sb}
\text{reads} \) to see the data. That chain is the entire
correctness argument for the lock-free queue in the next
section, for every mutex implementation, and for
Arc::drop's refcount protocol. What
release/acquire deliberately does not give is a single global
order. In SB, each thread's store-then-load is a
release-then-acquire pair on different variables,
no synchronizes-with edge forms, and both-zero remains
allowed. Only seq_cst forbids it, which is precisely why
seq_cst exists as a distinct, more expensive level. Adve and
Gharachorloo's 1996 tutorial remains the best single survey of
why every one of these levels exists in hardware terms.
Fences, and when an ordering on an operation is not enough
The orderings above attach to a specific atomic operation.
A fence is the standalone form.
std::atomic_thread_fence(memory_order_release)
in C and C++, std::sync::atomic::fence in Rust,
orders all prior accesses against all later ones
rather than just the one operation it decorates. The rule
connecting the two is worth memorizing. A release fence
followed later in program order by any relaxed store to a
location \(m\) has the effect of a release store to \(m\),
and an acquire fence preceded by a relaxed load of \(m\) has
the effect of an acquire load. So the SPSC publication can be
written either way, and the two versions generate identical
code on x86.
Three situations genuinely call for the standalone fence.
First, publishing several locations at once, where one release
fence before a batch of relaxed stores costs one barrier
instead of one per store, which matters on ARM where each
release store emits a stlr. Second, the
reference-count destructor idiom. Arc::drop
decrements with Release so prior uses of the
object cannot move after the decrement, and the thread that
observes the count hit zero then executes an
Acquire fence before running the destructor, so
that every other thread's uses happen-before the
deallocation. Writing that with an AcqRel
decrement would force an acquire barrier on every drop
instead of only the final one. Third, interoperating with
code that must use plain loads and stores for other reasons,
such as a signal handler or a hand-written assembly sequence.
The one thing a fence is not is a fix for a data race. Fences
order atomic and non-atomic accesses relative to each other,
but two conflicting non-atomic accesses with no
synchronizes-with edge between them remain undefined
behavior no matter how many fences surround them.
#include <atomic>
struct Frame { double a[64]; };
Frame g_frame;
std::atomic<unsigned> g_seq{0};
void publish(const Frame &f) { // producer
g_frame = f; // many plain stores
std::atomic_thread_fence(std::memory_order_release);
g_seq.store(g_seq.load(std::memory_order_relaxed) + 1,
std::memory_order_relaxed); // relaxed: the fence ordered it
}
bool consume(Frame &out, unsigned &last) { // consumer
unsigned s = g_seq.load(std::memory_order_relaxed);
if (s == last) return false;
std::atomic_thread_fence(std::memory_order_acquire);
out = g_frame; // safe: fence paired with fence
last = s;
return true;
}
// The refcount idiom, the other classic use:
// if (count.fetch_sub(1, std::memory_order_release) == 1) {
// std::atomic_thread_fence(std::memory_order_acquire);
// delete ptr; // acquire only on the final decrement
// }
use std::sync::atomic::{fence, AtomicUsize, Ordering};
// This is, essentially verbatim, what Arc::drop does in std::sync.
pub struct RefCount {
count: AtomicUsize,
}
impl RefCount {
/// Returns true if the caller is the last owner and must destroy.
pub fn release(&self) -> bool {
// Release: our uses of the object cannot be reordered after this.
if self.count.fetch_sub(1, Ordering::Release) != 1 {
return false;
}
// Only the final decrement pays for an acquire barrier, making
// every other thread's uses happen-before the destructor below.
fence(Ordering::Acquire);
true
}
}
Atomics under contention, the counter measured four ways
The shared counter is worth measuring carefully because it is the worst case for every mechanism. The entire computation is the contended operation. Eight threads, ten million increments each, on the 52-CPU Xeon, with aggregate throughput in millions of increments per second, medians of repeated runs.
| Strategy | C++ (Mops/s) | Rust (Mops/s) | vs one lock-free thread |
|---|---|---|---|
| 1 thread, no sharing (volatile increment) | 2,933.6 | — | 1× |
| 1 thread, uncontended mutex per increment | 180.8 | — | 16× slower |
| 8 threads, one mutex | 11.5 | 6.2 | 255× slower |
| 8 threads, one relaxed atomic fetch_add | 44.6 | 45.4 | 66× slower |
| 8 threads, per-thread padded counters, summed at end | 21,780 | — | 7.4× faster |
Three lessons, in increasing order of importance. First, the
atomic beats the mutex under contention by about 4×
(44.6 vs 11.5), because a lock-prefixed add is
one cache-line acquisition while a mutex round trip is at
least two (the lock word and the data) plus futex sleeps when
the spin fails. Second, both are catastrophically slower than
not sharing. Eight threads with a mutex deliver 11.5 Mops
where one thread with no lock delivers 2,934 Mops.
Adding seven threads made the program 255 times slower than
leaving it alone. The hardware explanation is MESI coherence.
Every increment must gain exclusive ownership of the counter's
cache line, so the line ping-pongs between cores at dozens of
nanoseconds per hop (86 ns per critical section at the
measured rate), and no amount of cleverness in the lock makes
the ping-pong cheaper. Third, the sharded row shows the only
real cure is to stop sharing. Per-thread counters padded to
separate cache lines and summed at the end run at 21,780 Mops
aggregate, faster than one thread by 7.4×, i.e. actual
parallel speedup, because there is no communication until the
end. This is the design inside Linux per-CPU counters, Java's
LongAdder, and every serious metrics library.
False sharing
The sharded design has one trap. Coherence operates on 64-byte
cache lines, not variables. Eight per-thread counters packed 8
bytes apart occupy one line, and the hardware ping-pongs that
line exactly as if the threads shared one variable, despite
every thread touching only its own count. Measured here, with
each thread incrementing its own relaxed atomic 50 million
times, packing into one line gave 61.5 Mops aggregate, and
padding with alignas(64) so each counter owns a
line gave 1,309 Mops. A 21.3× speedup from adding padding bytes. Per
operation that is 130 ns packed versus 6.1 ns padded, and the
130 ns is pure coherence traffic. False sharing is invisible
in source code, survives code review, and appears only in
perf counters (perf c2c exists specifically to
find it), which is why the padded-counter idiom is worth
memorizing rather than rediscovering.
Contention does not amortize
A separate sweep in the same benchmark data varies the thread count and makes the shape of the problem explicit. For the single shared mutex, aggregate throughput falls as threads are added and then stays flat, 55.8 Mops at one thread, 16.9 at two, 12.1 at eight, 11.9 at thirty-two. The shared relaxed atomic behaves identically in shape, 164 Mops alone, 37.4 at two threads, and roughly 29 from four threads onward regardless of count. Once the cache line is saturated, additional threads change nothing except queueing. The sharded per-thread counters, by contrast, scale almost linearly, 164, 328, 654, 1,295, 2,536 Mops from one to sixteen threads, flattening only past sixteen as the shared host's scheduling and power limits intrude. One table of numbers, one conclusion. Contended throughput is a property of the cache line, not of the thread count, and only designs that eliminate sharing scale.
How contention scales with thread count
The eight-thread row above is one point on a curve, and the shape of the curve is the part worth internalizing. The same benchmark run at 1, 2, 4, 8, 16, and 32 threads, two million increments per thread, best of three runs, aggregate millions of increments per second.
| Threads | One mutex | One relaxed atomic | Per-thread padded counters |
|---|---|---|---|
| 1 | 55.8 | 164.0 | 163.9 |
| 2 | 16.9 | 37.4 | 328.1 |
| 4 | 16.8 | 32.3 | 654.0 |
| 8 | 12.1 | 29.0 | 1,294.6 |
| 16 | 12.7 | 28.6 | 2,536.2 |
| 32 | 11.9 | 29.4 | 2,317.3 |
Three shapes, three lessons. The shared columns are flat after two threads and below their one-thread value. The mutex loses 70 percent of its throughput going from one thread to two and then changes almost nothing out to 32, because a serialized resource's ceiling is set by the handoff cost, not by the number of threads waiting. That is the arithmetic behind the observation that adding cores to a contended lock does nothing. The curve is not sublinear, it is horizontal. The atomic column behaves the same way at a ceiling roughly 2.4× higher, confirming that atomics buy a constant factor and not scalability. The sharded column is the only one that grows, and it grows almost linearly to 16 threads (163.9 to 2,536.2, a 15.5× gain on 16× the threads) before turning over at 32, where the machine's 26 physical cores are oversubscribed by hyperthreads sharing execution ports. Scalability is a property of the data layout, not of the synchronization primitive.
NUMA and where memory physically lives
On multi-socket machines a further asymmetry appears. Memory
is attached to sockets, and a core reading memory attached to
another socket pays an interconnect crossing, typically 1.5
to 2.2 times the local latency and with markedly lower
bandwidth. Linux therefore allocates on a first-touch policy.
A page is placed on the NUMA node of the thread that first
writes it, not the thread that called
malloc. The consequence is a standard bug. A
single-threaded initialization loop that touches an entire
array places all of it on one node, and a subsequent parallel
loop then has every remote thread reaching across the
interconnect for its own slice. The fix is to parallelize the
initialization with the same decomposition as the
computation, so each thread first-touches the pages it will
later use, plus pinning
(numactl --cpunodebind --membind,
sched_setaffinity,
hwloc) to keep threads from migrating away from
their memory. Drepper's memory paper is the standard
treatment and remains accurate about the mechanisms.
This particular machine reports a single NUMA node across all 52 logical CPUs, so no cross-node measurement is available here and none is invented. The effect is real on two-socket servers and on the multi-die packages common in current server parts, where even a single "node" hides core-to-core latency differences of several nanoseconds between dies. The design conclusion is the same one the sharded counter already taught, applied one level up. Put the data next to the thread that uses it, and if that is impossible, replicate it.
Lock-free queues
An SPSC ring buffer, derived
With one producer and one consumer, a correct queue needs no
locks and no read-modify-write operations at all. It needs
exactly two release/acquire edges, and deriving where they go
is the cleanest possible exercise in the memory model. The
structure is a power-of-two array plus two monotonically
increasing indices, tail, written only by the
producer, and head, written only by the consumer.
Since each index has a single writer, no atomic RMW is ever
needed. The indices are atomic only so the other
thread can read them without a data race. Occupancy is
\( \text{tail} - \text{head} \), which is why the indices are
never wrapped. Unsigned subtraction gives the count correctly
even across overflow, and slots are addressed modulo capacity.
The ordering argument, stated as the two happens-before chains
that must exist. (1) The consumer must see the element, not
just the index. The producer writes buf[t] and
then stores tail = t+1 with release, and
the consumer loads tail with acquire and
only then reads buf[t]. The chain
\( \text{write elem} \xrightarrow{sb} \text{store tail}
\xrightarrow{sw} \text{load tail} \xrightarrow{sb}
\text{read elem} \) makes the element visible. (2) The
producer must not overwrite a slot the consumer has not
finished reading. The consumer reads the element and then
stores head with release, and the
producer loads head with acquire before
reusing the slot. Remove either release/acquire pair and the queue
fails on ARM within seconds while passing on x86 for months,
because x86-TSO happens to provide both orderings for free.
#include <atomic>
#include <cstddef>
template <typename T, size_t CAP> // CAP must be a power of two
class SpscRing {
alignas(64) std::atomic<size_t> head_{0}; // consumer writes
alignas(64) std::atomic<size_t> tail_{0}; // producer writes
alignas(64) T buf_[CAP]; // padding: keep indices off each
// other's cache lines (false sharing)
public:
bool push(const T& v) { // producer only
size_t t = tail_.load(std::memory_order_relaxed); // own index
if (t - head_.load(std::memory_order_acquire) == CAP)
return false; // full
buf_[t % CAP] = v; // write element FIRST
tail_.store(t + 1, std::memory_order_release); // THEN publish
return true;
}
bool pop(T& out) { // consumer only
size_t h = head_.load(std::memory_order_relaxed); // own index
if (tail_.load(std::memory_order_acquire) == h)
return false; // empty
out = buf_[h % CAP]; // read element FIRST
head_.store(h + 1, std::memory_order_release); // THEN free slot
return true;
}
};
// Measured on this machine: 19.4M items/s (median) between two threads,
// vs 5.1M for std::queue + mutex + two condition_variables.
use std::cell::UnsafeCell;
use std::mem::MaybeUninit;
use std::sync::atomic::{AtomicUsize, Ordering};
pub struct SpscRing<T, const CAP: usize> {
head: AtomicUsize, // consumer writes
tail: AtomicUsize, // producer writes
buf: [UnsafeCell<MaybeUninit<T>>; CAP],
}
// The unsafe impls are the honest part: we assert single-producer/
// single-consumer, which the compiler cannot check. crossbeam and rtrb
// wrap this in split Producer/Consumer handles so misuse cannot compile.
unsafe impl<T: Send, const CAP: usize> Sync for SpscRing<T, CAP> {}
impl<T, const CAP: usize> SpscRing<T, CAP> {
pub fn push(&self, v: T) -> Result<(), T> {
let t = self.tail.load(Ordering::Relaxed);
if t.wrapping_sub(self.head.load(Ordering::Acquire)) == CAP {
return Err(v); // full
}
unsafe { (*self.buf[t % CAP].get()).write(v) } // element first
self.tail.store(t.wrapping_add(1), Ordering::Release);
Ok(())
}
pub fn pop(&self) -> Option<T> {
let h = self.head.load(Ordering::Relaxed);
if self.tail.load(Ordering::Acquire) == h {
return None; // empty
}
let v = unsafe { (*self.buf[h % CAP].get()).assume_init_read() };
self.head.store(h.wrapping_add(1), Ordering::Release);
Some(v)
}
}
Compare-and-swap, and the loop that everything is built from
Every lock-free structure past the single-writer case is built
from one instruction. Compare-and-swap takes an address, an
expected value, and a new value. It atomically writes the new
value if and only if the current value equals the expected
one, and reports which happened. On x86 it is
lock cmpxchg, and on ARM and RISC-V it is a
load-linked/store-conditional pair that the compiler wraps in
a retry loop. Its power is exactly characterized. In Herlihy's
1991 hierarchy, CAS has consensus number \( \infty \), meaning
it can implement a wait-free consensus object for any number
of threads, while atomic read and write alone have consensus
number 1 and cannot solve consensus for even two threads. That
is not a performance statement but an impossibility result. No
amount of clever code using only loads and stores can build a
lock-free stack, so hardware must provide a read-modify-write
primitive, and it does.
The universal shape is the CAS loop. Read the current value,
compute the desired new value from it, attempt the swap, and
retry from the fresh value if someone else changed it in
between. Two details separate correct loops from broken ones.
First, on failure the expected variable must be
reloaded, which C++ and Rust do automatically by writing
the observed value back into the expected argument. Recomputing
from a stale local is the most common lock-free bug. Second,
compare_exchange_weak may fail spuriously on
load-linked/store-conditional machines and is therefore
correct only inside a loop, where it compiles to tighter code
than _strong. Use _strong when there
is no loop to absorb the failure.
#include <atomic>
// Atomically apply an arbitrary function to a shared value. This is what
// fetch_add would be if the hardware had no fetch_add.
template <class F>
long atomic_update(std::atomic<long> &v, F f) {
long expected = v.load(std::memory_order_relaxed);
long desired;
do {
desired = f(expected); // recompute from the FRESH value
} while (!v.compare_exchange_weak( // on failure, expected is updated
expected, desired,
std::memory_order_acq_rel, // success: publish + observe
std::memory_order_relaxed)); // failure: just a reload
return expected; // the value we replaced
}
// A maximum that never decreases: impossible with fetch_add, trivial here.
void record_max(std::atomic<long> &hi, long sample) {
long cur = hi.load(std::memory_order_relaxed);
while (sample > cur &&
!hi.compare_exchange_weak(cur, sample,
std::memory_order_release,
std::memory_order_relaxed)) {
} // cur was refreshed by the failure
}
#include <stdatomic.h>
/* C11 spells the same operation with an explicit pointer to expected. */
long atomic_update_max(_Atomic long *hi, long sample) {
long cur = atomic_load_explicit(hi, memory_order_relaxed);
while (sample > cur) {
if (atomic_compare_exchange_weak_explicit(
hi, &cur, sample, /* &cur is updated on fail */
memory_order_release, memory_order_relaxed))
return sample;
}
return cur;
}
/* GCC/Clang also expose the older builtins, still common in C codebases:
__atomic_compare_exchange_n(ptr, &expected, desired, weak,
success_order, failure_order)
and the legacy full-barrier __sync_bool_compare_and_swap(ptr, old, new). */
use std::sync::atomic::{AtomicI64, Ordering};
// Rust returns Result instead of mutating an out-parameter: Ok(previous)
// on success, Err(actual) on failure. The Err value IS the refreshed read.
pub fn record_max(hi: &AtomicI64, sample: i64) {
let mut cur = hi.load(Ordering::Relaxed);
while sample > cur {
match hi.compare_exchange_weak(cur, sample,
Ordering::Release, // on success
Ordering::Relaxed) { // on failure
Ok(_) => return,
Err(actual) => cur = actual, // retry from what is really there
}
}
}
// fetch_update packages the whole loop, which is the form to prefer:
pub fn record_max_short(hi: &AtomicI64, sample: i64) {
let _ = hi.fetch_update(Ordering::Release, Ordering::Relaxed, |cur| {
if sample > cur { Some(sample) } else { None } // None = give up
});
}
# CPython exposes no CAS on Python objects; the GIL is the CAS. The
# faithful translation of a CAS loop is a lock plus a compare, and it is
# correct, just not lock-free:
import threading
class AtomicMax:
def __init__(self, value=0):
self._v = value
self._lock = threading.Lock()
def record(self, sample: int) -> int:
with self._lock: # the "atomically" of the CAS loop
if sample > self._v:
self._v = sample
return self._v
# Where real CAS appears in Python is at the C level: CPython's own
# free-threaded build (PEP 703) uses _Py_atomic_compare_exchange_* on
# reference counts, and multiprocessing.Value can be updated under its
# own lock. Numeric kernels that need real atomics live in extensions.
The ABA problem, traced
CAS compares values, not histories, and the gap between those two is the ABA problem. If a thread reads a value \(A\), stalls, and other threads change the location to \(B\) and back to \(A\), the stalled thread's CAS succeeds even though the world it reasoned about is gone. With integers this is usually harmless. With pointers it is catastrophic, because the same address can be recycled by the allocator for a different node. The concrete trace runs on a Treiber stack holding nodes \(A \to B \to C\).
time thread 1 (pop) thread 2 stack
──── ────────────────────────────── ───────────────────── ─────────────
t0 head = A ; next = A->next = B A → B → C
t1 (descheduled between the read
and the CAS)
t2 pop() → returns A B → C
t3 pop() → returns B C
t4 free(B) C
t5 push(A) (reuses the A → C
SAME address A)
t6 CAS(head, A, next=B) SUCCEEDS B → ???
because head really is A again
t7 the stack's head is now B, which was freed at t4:
the next pop dereferences freed memory, and C has vanished
from the stack entirely. Two bugs from one successful CAS.
Three countermeasures are standard. Tagged pointers,
Michael and Scott's original answer, pack a monotonically
increasing counter next to the pointer and CAS both together
with a double-width instruction
(lock cmpxchg16b on x86-64), so the reused
address carries a different tag and the stale CAS fails. The
counter can wrap, which makes this a probabilistic fix, but
with 48 bits of tag the wrap time is measured in years.
Hazard pointers (Michael, 2004) invert the problem.
Before dereferencing a node, a thread publishes that pointer
in a per-thread single-writer slot, and a thread that wants to
free a node first scans all hazard slots and defers the free
if any thread has announced it. Reclamation becomes bounded
(at most \(N \cdot K\) retired nodes for \(N\) threads and
\(K\) hazard slots each) and the read path costs one store
plus a fence. Epoch-based reclamation, the scheme in
crossbeam and in the kernel's RCU, has each thread announce a
global epoch counter on entering a critical region. Memory
retired in epoch \(e\) is freed once every thread has been
observed in epoch \(e+2\). EBR's read path is cheaper than
hazard pointers, often a single relaxed store, but a thread
that stalls inside a critical region blocks reclamation
globally, so memory usage is unbounded in the worst case. The
trade is exactly bounded memory versus cheaper reads, and it
is the reason both schemes still exist.
A Treiber stack, and an honest measurement
Treiber's 1986 stack is the smallest interesting lock-free
structure. Push CASes a new node's next to the
current head and then CASes the head to the new node, and pop
CASes the head forward. Its correctness argument is one
sentence per operation. For push, the node is fully initialized
before the CAS, and the CAS is a release, so any thread that
later reads the head with acquire sees the initialized node.
For pop, the CAS succeeds only if the head is still what was read,
so at most one thread can claim a given node, which gives
linearizability with the linearization point at the successful
CAS. What the argument does not cover is memory reclamation,
which is why the version below leaks deliberately and why the
ABA trace above applies to it directly.
The measurement is the part usually omitted. On this machine,
with pop-then-push pairs on a shared stack and one thread, the
Treiber stack sustains 40.5 M ops/s against 27.9 M for a
std::stack behind a std::mutex,
a 1.5× win from avoiding the lock's extra cache line.
With eight threads the two collapse together, 5.9 M versus
4.2 M, and the multi-threaded numbers vary by a factor of two
between runs on this shared host. The reason is the one the
counter table already established. Both designs funnel every
operation through a single cache line, so both are bounded by
coherence, and lock-freedom changes the progress guarantee
rather than the bandwidth. Lock-free is the right choice when
a thread may be preempted or killed while holding state (a
signal handler, a real-time deadline, a process that can
crash while holding a shared-memory lock), not when the goal
is simply to go faster.
// Treiber (1986). Nodes are never freed here: reclamation is a separate
// problem, solved by hazard pointers or epochs, not by this code.
#include <atomic>
struct Node { long v; Node *next; };
class TreiberStack {
std::atomic<Node *> head{nullptr};
public:
void push(Node *n) {
Node *old = head.load(std::memory_order_relaxed);
do {
n->next = old; // fully initialize BEFORE publishing
} while (!head.compare_exchange_weak(
old, n,
std::memory_order_release, // publishes n's fields
std::memory_order_relaxed));
}
Node *pop() {
Node *old = head.load(std::memory_order_acquire);
while (old && !head.compare_exchange_weak(
old, old->next, // ← ABA lives here:
std::memory_order_acquire,
std::memory_order_acquire)) {
}
return old; // caller must NOT free() this yet
}
};
// Measured on this machine, pop+push pairs: 40.5 M/s single-threaded vs
// 27.9 M/s for std::stack + std::mutex; 5.9 M/s vs 4.2 M/s at 8 threads.
// The same structure in Rust needs either raw pointers and unsafe, or a
// reclamation scheme. crossbeam-epoch supplies the latter, and the
// resulting code has no unsafe in it at all: Guard proves the node
// cannot be freed while borrowed.
use crossbeam_epoch::{self as epoch, Atomic, Owned};
use std::sync::atomic::Ordering::{Acquire, Relaxed, Release};
pub struct TreiberStack<T> {
head: Atomic<Node<T>>,
}
struct Node<T> {
value: T,
next: Atomic<Node<T>>,
}
impl<T> TreiberStack<T> {
pub fn push(&self, value: T) {
let mut n = Owned::new(Node { value, next: Atomic::null() });
let guard = &epoch::pin(); // enter the epoch
loop {
let head = self.head.load(Relaxed, guard);
n.next.store(head, Relaxed);
match self.head.compare_exchange(head, n, Release, Relaxed, guard) {
Ok(_) => break,
Err(e) => n = e.new, // reuse the allocation
}
}
}
pub fn pop(&self) -> Option<T> {
let guard = &epoch::pin();
loop {
let head = self.head.load(Acquire, guard);
match unsafe { head.as_ref() } {
None => return None,
Some(h) => {
let next = h.next.load(Relaxed, guard);
if self.head
.compare_exchange(head, next, Acquire, Relaxed, guard)
.is_ok()
{
// defer_destroy: freed only once every pinned thread
// has moved on, which is what makes ABA impossible.
unsafe { guard.defer_destroy(head) };
return Some(unsafe { std::ptr::read(&h.value) });
}
}
}
}
}
}
Michael-Scott and the multi-producer world
With multiple producers, single-writer reasoning dies and
compare-and-swap arrives. The Michael and Scott queue (PODC
1996) is the canonical MPMC design and the ancestor of
java.util.concurrent.ConcurrentLinkedQueue, a
linked list with a permanent dummy node, where enqueue CASes
the last node's next pointer from null to the new
node and then swings tail, and dequeue CASes
head forward past the dummy. Two of its ideas
generalize. First, helping. Because enqueue takes two
steps, another thread can observe the intermediate state
(tail's next non-null) and complete the swing itself, so no
thread's stall can block the structure. This is what makes the
queue lock-free in Herlihy's sense, some thread always makes
progress in a bounded number of steps. Second, its exposure to
the ABA problem traced above, which the original paper
answered with tagged pointers and which crossbeam answers with
epochs. That second point is also the honest argument for
reaching for a library, moodycamel's ConcurrentQueue, folly's
MPMCQueue, crossbeam's channels, instead of writing one. The
queue is 40 lines, and the reclamation is the other
2,000. Herlihy's 1991 wait-free hierarchy supplies the
theoretical floor under all of it. Consensus number
\( \infty \) for CAS means CAS can build any wait-free object,
while atomic registers alone (consensus number 1) cannot solve
even two-thread consensus, so some RMW primitive is not a
convenience but a necessity.
The code is worth reading in full because every line is
forced by an argument. The sentinel node exists so that
head and tail never alias even when
the queue is empty, which is what lets enqueue and dequeue
proceed without interfering. The enqueue reads
tail, rereads it to confirm it did not move, and
branches on whether tail->next is null. Null
means tail is current and the CAS on next is the
linearization point, and non-null means another enqueuer got as
far as linking but not as far as swinging tail, so this
thread helps by swinging it and retries. The dequeue reads
the value before the CAS that unlinks the node,
because after the CAS another thread may already have freed
it. The version below was run on this machine with four
producers enqueueing 200,000 items each and four consumers
draining. The result was 800,000 items dequeued, checksum 80,000,400,000,
exactly the expected \( 4 \sum_{j=1}^{200000} j \), with no
item lost or duplicated.
// Michael & Scott (PODC 1996), lock-free MPMC queue.
// Nodes are leaked on purpose: pair this with hazard pointers or epochs.
#include <atomic>
struct Node {
long value;
std::atomic<Node *> next{nullptr};
explicit Node(long v = 0) : value(v) {}
};
class MSQueue {
std::atomic<Node *> head, tail;
public:
MSQueue() {
Node *dummy = new Node(0); // permanent sentinel: head != tail
head.store(dummy); // logic never sees an empty list
tail.store(dummy);
}
void enqueue(long v) {
Node *n = new Node(v); // fully built before it is linked
while (true) {
Node *t = tail.load(std::memory_order_acquire);
Node *next = t->next.load(std::memory_order_acquire);
if (t != tail.load(std::memory_order_acquire)) continue; // moved
if (next != nullptr) { // another enqueuer linked but did
tail.compare_exchange_strong(t, next, // not yet swing tail:
std::memory_order_release, std::memory_order_relaxed);
continue; // HELP it, then retry
}
Node *expected = nullptr;
if (t->next.compare_exchange_strong(expected, n,
std::memory_order_release, // ← linearization point
std::memory_order_relaxed)) {
tail.compare_exchange_strong(t, n, // may fail: someone
std::memory_order_release, // else already helped
std::memory_order_relaxed);
return;
}
}
}
bool dequeue(long &out) {
while (true) {
Node *h = head.load(std::memory_order_acquire);
Node *t = tail.load(std::memory_order_acquire);
Node *next = h->next.load(std::memory_order_acquire);
if (h != head.load(std::memory_order_acquire)) continue;
if (next == nullptr) return false; // genuinely empty
if (h == t) { // tail is lagging
tail.compare_exchange_strong(t, next, // help, then retry
std::memory_order_release, std::memory_order_relaxed);
continue;
}
out = next->value; // READ BEFORE the CAS: after it,
// another thread may free the node
if (head.compare_exchange_strong(h, next, // ← linearization
std::memory_order_release, std::memory_order_relaxed))
return true; // h is garbage now (leaked here)
}
}
};
// Measured: 4 producers x 200,000 + 4 consumers = 800,000 items dequeued,
// checksum 80,000,400,000, matching the expected value exactly.
Python, the GIL measured, and its removal
What the GIL is
CPython's global interpreter lock is a single mutex that a
thread must hold to execute Python bytecode. It exists because
CPython's core data structures, above all the reference count
in every object header, are mutated with plain non-atomic
operations. The GIL makes the whole interpreter one critical
section so those mutations never race. A running thread
releases the GIL voluntarily around blocking system calls
(file and socket I/O, time.sleep), and
involuntarily every 5 ms (sys.getswitchinterval())
when the eval loop checks a drop request, the mechanism
visible in Python/ceval_gil.c. The consequence is
a precise asymmetry. Threads provide real concurrency for
I/O-bound work, because waiting threads do not hold the GIL,
and none at all for CPU-bound pure-Python work, because
exactly one thread interprets bytecode at any instant.
The asymmetry, measured
The CPU-bound case is eight tasks, each summing \( i^2 \) for
\(i\) up to two million in pure Python, on CPython 3.10 on the
52-CPU Xeon. Sequential execution takes 0.767 s. Eight threads
take 0.963 s, which is
25 percent slower than doing nothing concurrent, the
extra being GIL handoff overhead and cache disturbance while
eight threads take turns on one interpreter. Eight processes
via multiprocessing.Pool take 0.115 s, a 6.7×
speedup. The I/O-bound case is 32 sleeps of 100 ms. Sequential
execution takes 3.204 s, 32 threads take 0.106 s, and asyncio
with gather takes 0.101 s, both within noise of
the ideal 0.1 s. The rule the numbers teach is to use
processes or a compiled extension for CPU-bound Python, while
for I/O-bound work threads and
asyncio are equivalent in throughput and differ in ergonomics
and memory (a coroutine costs on the order of a kilobyte, a
thread costs a stack).
import time, threading, multiprocessing as mp
N, TASKS = 2_000_000, 8
def cpu(n=N):
s = 0
for i in range(n):
s += i * i
return s
def timed(f):
t0 = time.perf_counter(); f(); return time.perf_counter() - t0
def seq():
for _ in range(TASKS): cpu()
def threads(): # GIL: one bytecode stream at a time
ts = [threading.Thread(target=cpu) for _ in range(TASKS)]
for t in ts: t.start()
for t in ts: t.join()
def procs(): # sidesteps the GIL: 8 interpreters
with mp.Pool(TASKS) as p:
p.map(cpu, [N] * TASKS)
if __name__ == "__main__":
print(f"sequential {timed(seq):.3f}s") # measured: 0.767 s
print(f"8 threads {timed(threads):.3f}s") # measured: 0.963 s (slower!)
print(f"8 procs {timed(procs):.3f}s") # measured: 0.115 s (6.7x)
multiprocessing buys its speedup with real
processes, so its costs are process costs, and each was
measured here separately. Worker startup depends on the
start method. With the fork method a single
no-op Process starts and joins in 2.2 ms, with
forkserver 98 ms, and with spawn
(the only option on Windows and the macOS default) 128 ms,
because spawn boots a fresh interpreter and re-imports the
module. Arguments and results cross the boundary by pickling
through pipes. Shipping a 64 MiB float32 array to a pool
worker took 205 ms pickled, versus 11 ms, 18.7×
faster, when the array lived in
multiprocessing.shared_memory and only its name
crossed the pipe. Shared mutable state likewise requires
explicit machinery (Value, Array,
managers) rather than an assignment. The 6.7× observed
against an ideal 8× reflects exactly these overheads
plus pool startup, an Amdahl calculation done precisely in
Problem 1 below.
PEP 703, free-threaded CPython
PEP 703 (Sam Gross, accepted 2023) removes the GIL rather than
working around it, and the engineering is a tour of this
page's earlier sections. Reference counting becomes
biased. Each object's count is split into an owner
thread's field, updated with plain arithmetic because only the
owner touches it, and a shared field updated with atomics by
everyone else, the sharded-counter trick from the measurements
above applied inside every object header. Objects that live
forever (interned strings, None,
True) are immortalized so their counts
are never written at all, eliminating the worst false-sharing
and contention sources. Container internals (list,
dict) gain per-object locks with an optimistic
retry fast path, and the allocator becomes mimalloc so
per-thread heaps avoid a global allocator lock. CPython 3.13
shipped this as an experimental separate build
(--disable-gil, the python3.13t
binaries), and 3.14 promoted free-threading to a supported
option with single-thread overhead reduced to the several-
percent range. This machine has only 3.10, so no free-threaded
measurement appears here. The honest current summary is that
CPU-bound thread scaling now works, extension compatibility
is the migration bottleneck, and the ecosystem is in the
multi-year transition PEP 703 predicted.
Subinterpreters, the other answer
CPython pursued a second, independent escape from the GIL, and
the two are worth keeping distinct because they make opposite
trades. A subinterpreter is a separate interpreter
state inside one process, with its own modules, its own
built-ins, and, since PEP 684 landed in 3.12, its own GIL.
\(n\) subinterpreters therefore run \(n\) bytecode streams in
parallel in one address space, which is the multiprocessing
model without the fork, with no separate process, no page
tables to duplicate, and startup cost far below the measured
128 ms of a
spawn. PEP 554, and its successor PEP 734 which
supplies the interpreters module in 3.14, defines
the Python-level API and, crucially, the communication
channel, since objects cannot simply be shared. Each
interpreter has its own object allocations and refcounts, so
values cross by copy or through a small set of shareable
types, memoryview-backed buffers among them.
The comparison is clean. Free threading gives one interpreter with true shared objects and therefore requires every invariant in every extension to be re-examined. Subinterpreters give isolation by construction, so existing single-threaded assumptions hold inside each one, at the cost of an explicit serialization boundary between them and of per-interpreter memory for modules and caches. The honest engineering read is that they serve different shapes. Subinterpreters suit worker pools running independent tasks, and free threading suits code that genuinely wants to share one large object graph. Neither is measurable on this machine, which has CPython 3.10 only, and no numbers for either are quoted here.
Async/await, concurrency without threads
The event loop idea
Threads spend most of a server's life blocked, and each
blocked thread costs a stack, a scheduler entry, and two
context switches (1.9 µs each, measured above) per
wakeup. The event-loop alternative inverts control. One
thread asks the kernel which of many file descriptors are
ready (epoll_wait on Linux,
kqueue on BSD, IOCP on Windows), runs the
handler for each ready event to its next blocking point, and
repeats. The debate over which model is better is old and
symmetrical, Ousterhout's "Why Threads Are a Bad Idea" (1996)
versus von Behren, Condit, and Brewer's "Why Events Are a Bad
Idea" (2003), and async/await is the synthesis both sides
wanted, code written in thread-like sequential style,
compiled into the state machines an event loop needs. An
async fn is a function that returns immediately
with a suspended computation, and await marks the
points where it can yield the thread. The scheduling is
cooperative, which is the model's sharp edge. A
handler that computes for 100 ms without awaiting stalls
every other task on that loop, a failure mode with no
analogue under preemptive threads.
┌──────────────────────────────────────────────┐
│ event loop │
│ epoll_wait(...) ──► ready: [fd 7, fd 12] │
│ │ │
│ ▼ │
│ resume task waiting on fd 7 ──► runs to │
│ resume task waiting on fd 12 next await│
│ │ │
│ ▼ │
│ timers due? run them; then epoll_wait again│
└──────────────────────────────────────────────┘
one thread, thousands of tasks; a task that never awaits starves all
asyncio and tokio, side by side
The same program in both runtimes fetches three "resources"
concurrently (simulated by sleeps, so the example runs
without a network), with a timeout on the slowest. The
structural differences are the instructive part. Python's
coroutines run on a single-threaded loop by default, so tasks
share state freely without locks. Tokio's default runtime is
multi-threaded and work-stealing, so a task must be
Send to cross tokio::spawn, and the
compiler enforces it, the Send/Sync machinery from the Rust
section applied to futures. Rust futures are also
lazy. They do nothing until polled, whereas
asyncio.create_task schedules eagerly, and
because a Rust future is an inert state machine, dropping it
is cancellation, where Python cancellation is a
CancelledError injected at the next await.
import asyncio
async def fetch(name: str, delay: float) -> str:
await asyncio.sleep(delay) # yields the loop; stands in for I/O
return f"{name}: done after {delay}s"
async def main():
# create_task schedules eagerly; gather awaits all of them
tasks = [
asyncio.create_task(fetch("a", 0.10)),
asyncio.create_task(fetch("b", 0.20)),
asyncio.create_task(fetch("c", 0.15)),
]
try:
results = await asyncio.wait_for(asyncio.gather(*tasks), timeout=1.0)
for r in results:
print(r)
except TimeoutError:
print("timed out; unfinished tasks were cancelled")
asyncio.run(main())
# measured earlier: 32 concurrent 100ms sleeps complete in 0.101 s
# on one thread; the same throughput as 32 OS threads, at ~1KB/task.
use std::time::Duration;
use tokio::time::{sleep, timeout};
async fn fetch(name: &str, ms: u64) -> String {
sleep(Duration::from_millis(ms)).await; // yields the executor
format!("{name}: done after {ms}ms")
}
#[tokio::main] // multi-threaded, work-stealing runtime
async fn main() {
// join! polls all three concurrently on this task; no spawn needed
let all = async {
tokio::join!(fetch("a", 100), fetch("b", 200), fetch("c", 150))
};
match timeout(Duration::from_secs(1), all).await {
Ok((a, b, c)) => println!("{a}\n{b}\n{c}"),
Err(_) => println!("timed out; dropping the future IS cancellation"),
}
// To run on another worker thread, spawn: the future must be
// Send + 'static, checked at compile time. Hold an Rc across an
// .await inside this block and the spawn stops compiling, the
// same Send machinery as thread::spawn earlier.
let handle = tokio::spawn(async { fetch("d", 50).await });
println!("{}", handle.await.unwrap());
}
Under both runtimes sits the same kernel interface, and it is
worth knowing the layering. Asyncio's default loop wraps
epoll via the selectors module (libuv plays this
role for Node.js), and tokio wraps epoll through mio. The
readiness model itself is being displaced at the frontier by
io_uring, a completion-based interface where the
application submits operations to a shared ring and the
kernel reports completions, cutting per-operation syscalls.
More on that appears in the frontier section.
Thread pools and work stealing
Sizing a pool is arithmetic, not folklore
A thread pool exists to amortize the 34-75 µs creation cost measured earlier and to cap concurrency at what the machine can schedule. The right size follows from Little's law, \( L = \lambda W \). The number of in-flight requests equals arrival rate times time in system. For CPU-bound work the answer is the core count, and the counter measurements explain why more is worse. Extra threads add context switches and cache pressure while the cores are already saturated. For mixed work, if each request holds a worker for \(W\) seconds of which \(C\) is CPU, a target of \( \lambda \) requests/s needs \( \lambda W \) workers but only \( \lambda C \) cores. Problem 5 runs the numbers. The classic sizing failure is the convoy. A pool of \(n\) workers that all block on one downstream lock or slow service serializes into a queue, and throughput collapses to the downstream's, with \(n-1\) workers merely holding memory.
Work stealing
For fork-join parallelism (divide an array, recurse on both halves, join), a global task queue becomes the contended counter all over again. Every spawn and completion fights for one lock. The work-stealing scheduler, analyzed by Blumofe and Leiserson (JACM 1999) and implemented in Cilk, Java's ForkJoinPool, TBB, tokio, and rayon, gives each worker its own deque. A worker pushes and pops its own tasks at the bottom, LIFO, so the task it runs next is the one whose data is hottest in its cache, and an idle worker steals from the top of a random victim's deque, FIFO, taking the oldest and typically largest task, which amortizes the steal over the most work. The two ends only collide when the deque has one element, which is the only case needing a CAS. The Chase-Lev deque (SPAA 2005) is the standard lock-free realization, and its correctness on ARM was subtle enough that proving and fixing the memory orderings produced its own line of research. Blumofe and Leiserson's bound is worth knowing. With \(P\) workers, a computation with total work \(T_1\) and critical path \(T_\infty\) completes in expected time
$$ T_P \le \frac{T_1}{P} + O(T_\infty) $$linear speedup up to \( P \approx T_1 / T_\infty \), the computation's inherent parallelism, and no benefit beyond. The steal-from-the-top heuristic is why the bound's constant is small in practice. Steals are rare when the tree is deep, so workers run almost entirely out of their own cache-warm deques.
// rayon: work stealing behind an iterator. The closure runs on a pool
// of num_cpus workers with Chase-Lev deques; par_iter splits the range
// recursively so idle workers steal the big untouched halves.
use rayon::prelude::*;
fn main() {
let total: u64 = (0..2_000_000u64 * 8)
.into_par_iter()
.map(|i| i * i % 1_000_003)
.sum();
println!("{total}");
// The same machinery, explicitly: divide and conquer with join.
fn sum_sq(xs: &[u64]) -> u64 {
if xs.len() < 4096 {
return xs.iter().map(|x| x * x % 1_000_003).sum();
}
let (lo, hi) = xs.split_at(xs.len() / 2);
let (a, b) = rayon::join(|| sum_sq(lo), || sum_sq(hi));
a + b
}
let v: Vec<u64> = (0..1_000_000).collect();
println!("{}", sum_sq(&v));
}
// C++: the standard library's pool is implicit in std::async, but a
// fixed pool with a shared queue is short enough to show whole.
#include <condition_variable>
#include <functional>
#include <mutex>
#include <queue>
#include <thread>
#include <vector>
class ThreadPool {
std::vector<std::thread> workers;
std::queue<std::function<void()>> tasks; // ONE queue: contended.
std::mutex m; // work stealing exists to
std::condition_variable cv; // eliminate this hot spot
bool stop = false;
public:
explicit ThreadPool(size_t n) {
for (size_t i = 0; i < n; i++)
workers.emplace_back([this] {
for (;;) {
std::function<void()> task;
{
std::unique_lock<std::mutex> lk(m);
cv.wait(lk, [&] { return stop || !tasks.empty(); });
if (stop && tasks.empty()) return;
task = std::move(tasks.front());
tasks.pop();
}
task(); // run OUTSIDE the lock
}
});
}
void submit(std::function<void()> f) {
{ std::lock_guard<std::mutex> g(m); tasks.push(std::move(f)); }
cv.notify_one();
}
~ThreadPool() {
{ std::lock_guard<std::mutex> g(m); stop = true; }
cv.notify_all();
for (auto &w : workers) w.join();
}
};
# Python: the stdlib pools. Thread pool for I/O, process pool for CPU;
# the GIL measurements earlier are the entire reason two pools exist.
from concurrent.futures import ProcessPoolExecutor, ThreadPoolExecutor
def cpu_task(n: int) -> int:
return sum(i * i % 1_000_003 for i in range(n))
def io_task(url: str) -> int:
import urllib.request
with urllib.request.urlopen(url, timeout=10) as r:
return len(r.read())
if __name__ == "__main__":
# CPU-bound: processes. 8 workers gave 6.7x on this machine.
with ProcessPoolExecutor(max_workers=8) as pool:
print(sum(pool.map(cpu_task, [2_000_000] * 8)))
# I/O-bound: threads are fine; the GIL is released while blocked.
urls = ["https://example.com"] * 16
with ThreadPoolExecutor(max_workers=16) as pool:
sizes = list(pool.map(io_task, urls))
Futures, coroutines, and structured concurrency
Rust's poll model with Future, Waker, and executor
Rust's async is worth dissecting because it makes visible the
machinery every other language hides. A
Future is a trait with one method,
poll, which returns
Poll::Ready(v) or Poll::Pending.
An async fn compiles to a state machine
implementing that trait. Each await becomes a
state, and the compiler lays out exactly the locals that must
survive the suspension, which is why a Rust future's size is
known at compile time and requires no heap allocation of its
own. Nothing runs until something polls it, the property
called laziness, and it is why creating a future has no
observable effect and why dropping one is cancellation. There
is no scheduled work to cancel, only a state machine to
discard.
The missing piece is how a pending future ever gets polled
again, and the answer is the Waker passed in the
Context. A leaf future that cannot complete
stores a clone of the waker somewhere an external event can
reach it, a timer thread, an epoll registration, a channel's
queue, and returns Pending. When the event
occurs, whoever holds the waker calls
wake(), which the executor implements by pushing
the owning task back onto its run queue. That contract, poll
until Pending, then wait to be woken, is the entire interface
between futures and runtimes, and it is why tokio, smol, and
embassy can all run the same futures. A complete executor is
short enough to show whole. The version below was compiled
with rustc 1.97.1 and prints done after 50 ms,
having polled the task exactly twice.
executor task (state machine) external event
──────── ──────────────────── ──────────────
pop task from run queue
poll(task, cx{waker}) ───────► state 0: start timer
store waker.clone()
◄──────── return Pending
(nothing to do; block) timer fires
waker.wake()
push task to run queue ◄─────────────────────────────────────┘
poll(task, cx{waker}) ───────► state 1: timer elapsed
◄──────── return Ready(v)
task complete; drop the state machine
// A complete executor. rustc -O --edition 2021 exec.rs
use std::future::Future;
use std::pin::Pin;
use std::sync::mpsc::{sync_channel, Receiver, SyncSender};
use std::sync::{Arc, Mutex};
use std::task::{Context, Poll, Wake, Waker};
use std::thread;
use std::time::{Duration, Instant};
// A leaf future: the only kind that ever really returns Pending.
struct Delay { until: Instant, spawned: bool }
impl Future for Delay {
type Output = &'static str;
fn poll(mut self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output> {
if Instant::now() >= self.until {
return Poll::Ready("done");
}
if !self.spawned {
self.spawned = true;
let waker = cx.waker().clone(); // hand the waker to the event
let until = self.until;
thread::spawn(move || {
thread::sleep(until.saturating_duration_since(Instant::now()));
waker.wake(); // this is what reschedules us
});
}
Poll::Pending
}
}
struct Task {
future: Mutex<Option<Pin<Box<dyn Future<Output = ()> + Send>>>>,
sender: SyncSender<Arc<Task>>,
}
impl Wake for Task { // wake() = re-enqueue self
fn wake(self: Arc<Self>) {
let s = self.sender.clone();
let _ = s.send(self);
}
}
fn main() {
let (tx, rx): (SyncSender<Arc<Task>>, Receiver<Arc<Task>>) = sync_channel(64);
let fut = async {
let t0 = Instant::now();
let d = Delay { until: Instant::now() + Duration::from_millis(50),
spawned: false }.await;
println!("{d} after {} ms", t0.elapsed().as_millis());
};
let task = Arc::new(Task { future: Mutex::new(Some(Box::pin(fut))),
sender: tx.clone() });
tx.send(task).unwrap();
drop(tx);
while let Ok(task) = rx.recv() { // the entire scheduler
let mut slot = task.future.lock().unwrap();
if let Some(mut f) = slot.take() {
let waker: Waker = Waker::from(task.clone());
let mut cx = Context::from_waker(&waker);
if f.as_mut().poll(&mut cx).is_pending() {
*slot = Some(f); // keep it for the next wake
}
}
}
}
// Measured: prints "done after 50 ms"; the task is polled exactly twice.
// C++20 coroutines are lower level than Rust's: the language provides
// suspension and a customization protocol, and the program supplies
// the type that says what suspension means. g++ -std=c++20 -fcoroutines
#include <coroutine>
#include <cstdio>
#include <exception>
template <class T>
struct Generator {
struct promise_type { // the compiler looks for this name
T current;
Generator get_return_object() {
return Generator{
std::coroutine_handle<promise_type>::from_promise(*this)};
}
std::suspend_always initial_suspend() noexcept { return {}; }
std::suspend_always final_suspend() noexcept { return {}; }
std::suspend_always yield_value(T v) { current = v; return {}; }
void return_void() {}
void unhandled_exception() { std::terminate(); }
};
std::coroutine_handle<promise_type> h; // the heap-allocated frame
~Generator() { if (h) h.destroy(); } // ownership is manual
bool next() { h.resume(); return !h.done(); }
T value() const { return h.promise().current; }
};
Generator<long> fib(int n) {
long a = 0, b = 1;
for (int i = 0; i < n; i++) {
co_yield a; // suspends; locals live in the frame
long t = a + b; a = b; b = t;
}
}
int main() {
auto g = fib(10);
while (g.next()) printf("%ld ", g.value()); // 0 1 1 2 3 5 8 13 21 34
printf("\n");
}
// Note what is absent: a scheduler. C++20 ships the mechanism and leaves
// the runtime to libraries (cppcoro, folly::coro, asio's awaitables), and
// C++23's std::generator is the first standard type built on it.
# Python's coroutines are the same idea with the runtime included, and
# asyncio.TaskGroup (3.11+) is the structured-concurrency form: the block
# cannot exit until every child finishes, and one failure cancels the rest.
import asyncio
async def fetch(name: str, delay: float) -> str:
await asyncio.sleep(delay)
return name
async def main():
async with asyncio.TaskGroup() as tg: # a "nursery"
a = tg.create_task(fetch("a", 0.10))
b = tg.create_task(fetch("b", 0.20))
# Control reaches here only after BOTH complete. If either raised,
# the other is cancelled and an ExceptionGroup propagates here.
print(a.result(), b.result())
asyncio.run(main())
# Without a TaskGroup, create_task returns a handle nobody has to await:
# the task can outlive its logical parent, exceptions vanish into the
# loop's exception handler, and cancellation has no defined scope. That
# unstructured spawn is what structured concurrency exists to remove.
Structured concurrency as a discipline
The argument, made forcefully by Martin Sustrik and by Nathaniel
Smith in the design of Trio and independently adopted by Kotlin,
Swift, and Java's structured task scope, is an analogy to
goto. An unstructured spawn creates a
control-flow edge that leaves the current function and never
comes back to a place the reader can see, exactly as
goto did, and the consequences match. There is no
reliable place to handle errors, no defined lifetime for
borrowed resources, and no cancellation except what is
implemented by hand
for every task. The remedy is to require that task lifetimes
nest. A scope may spawn children, and the scope does not exit
until every child has finished, so concurrency composes like a
function call. Three properties follow automatically. Errors
propagate to the parent, because there is a parent to propagate
to. Cancellation is well defined, because cancelling a scope
means cancelling its subtree. Borrowing works, because a child
cannot outlive the scope whose data it borrowed, which is
exactly why std::thread::scope in Rust can lend
stack references to threads that thread::spawn
cannot.
The costs are real and worth stating. Strict nesting forbids
the legitimate pattern of a long-lived background task that
outlives its creator, which then has to be modelled as a
child of a longer-lived scope, and that restructuring is
sometimes awkward. Rust's async ecosystem has the hardest
version of the problem, because a scoped async API must
contend with the fact that a future can be dropped at any
await point, so a scope cannot force its children to run to
completion the way a blocking join can. That tension is the
reason std::thread::scope shipped in 1.63 while
an async equivalent has not. The practical rule that survives
all of this is modest and still valuable. Prefer a scope,
prefer join over detach, and if a task must be detached, give
it an explicit owner and an explicit shutdown signal rather
than letting it float.
Worked problems
On this machine, eight CPU-bound Python tasks took 0.767 s sequentially and 0.115 s on an 8-worker process pool. (a) Compute the speedup. (b) Using Amdahl's law, infer the effective parallelizable fraction \(p\) of the workload. (c) Predict the best possible speedup on this machine's 52 CPUs, and the asymptotic limit.
Solution. (a) Speedup \( S_8 = 0.767 / 0.115 = 6.67 \) against an ideal 8.
(b) Amdahl's law with \(n\) workers gives \( S_n = \dfrac{1}{(1-p) + p/n} \). Inverting with \( S_8 = 6.67 \) and \( n = 8 \) yields \( 1/6.67 = 0.150 = (1-p) + p/8 = 1 - \tfrac{7p}{8} \), so \( \tfrac{7p}{8} = 0.850 \) and \( p = \tfrac{8}{7}(0.850) = 0.971 \). About 2.9 percent of the run behaves as serial overhead, pool startup at fork prices, pickling arguments and results through pipes, and the sequential map scatter/gather.
(c) With \( n = 52 \), \( S_{52} = 1 / (0.0285 + 0.9715/52) = 1 / (0.0285 + 0.01868) = 21.2 \). Asymptotically \( S_\infty = 1/(1-p) = 1/0.0285 = 35.1 \). The lesson is the shape of the curve. A workload that looks 97 percent parallel already loses 59 percent of the machine at 52 cores (21.2 of an ideal 52), because the serial fraction is measured against ever-shrinking parallel time.
The counter benchmark measured an aggregate 11.5 million increments/s for 8 threads sharing one mutex, and 5.53 ns per lock-increment-unlock for one thread with no contention. (a) Compute the effective cost of one contended critical section. (b) Compute the contention multiplier. (c) A service performs 400,000 requests/s, and each request takes one such contended lock twice. What fraction of a single serialized lock's capacity is consumed, and at what request rate does the lock saturate?
Solution. (a) A mutex admits one holder at a time, so aggregate throughput is the reciprocal of the per-section cost regardless of thread count, \( 10^9 / 11.5\times10^6 = 87.0 \) ns per critical section.
(b) \( 87.0 / 5.53 = 15.7\times \). Contention did not change the work inside the section (one increment). The other 81 ns is cache-line migration of the lock word and the data, plus futex wake/sleep traffic.
(c) The lock serializes \( 2 \times 400{,}000 = 800{,}000 \) sections/s, costing \( 8\times10^5 \times 87\,\text{ns} = 0.0696 \) s of lock occupancy per second, 7.0 percent utilization. Saturation is at \( 11.5\times10^6 / 2 = 5.75 \) million requests/s if the cost stayed at 87 ns. In practice it degrades earlier because queueing delay grows sharply with utilization. The useful engineering habit is exactly this calculation. A lock is a server with a service time, and 87 ns of service time is a budget one can spend deliberately.
Prove that under sequential consistency the store-buffering
outcome \( r_1 = r_2 = 0 \) is impossible for
thread A running X=1; r1=Y and
thread B running Y=1; r2=X, with X and Y
initially 0.
Then exhibit the happens-before analysis under
release/acquire semantics showing why the outcome is
permitted there, and reconcile the result with the measured
56-104 occurrences per million trials.
Solution. SC part. An SC execution is a total order \(<\) on the four operations \( \{W_X, R_Y\} \cup \{W_Y, R_X\} \) that respects each thread's program order (\( W_X < R_Y \) and \( W_Y < R_X \)) and in which every read returns the latest earlier write. Suppose for contradiction \( r_1 = r_2 = 0 \). \( r_1 = 0 \) means \( R_Y \) reads the initial value, so \( R_Y < W_Y \) (otherwise the latest write before \(R_Y\) would be \(W_Y\), forcing \(r_1 = 1\)). Chaining with program order gives \( W_X < R_Y < W_Y < R_X \). Then \( R_X \) has \( W_X \) before it in the total order, and no other write to X exists, so \( R_X \) must return 1, contradicting \( r_2 = 0 \). Symmetrically if one starts from \( r_2 = 0 \). Hence at least one register is 1 in every SC execution. \( \blacksquare \)
Release/acquire part. Upgrade the stores to release and the loads to acquire. A synchronizes-with edge requires an acquire load to read the value written by a release store to the same location. Here A's load of Y could only synchronize with B's store of Y, but in the candidate execution it reads 0, not B's value, so no edge forms, and likewise for B's load of X. The happens-before relation is then just the two program orders, two disjoint chains, and nothing orders \(W_X\) against \(R_X\) or \(W_Y\) against \(R_Y\). A read unordered with a write may read either value, so \( r_1 = r_2 = 0 \) is a consistent execution. No data race exists, the accesses are atomic, so the outcome is well-defined, merely surprising. Forbidding it requires the single total order over all seq_cst operations, which is exactly what seq_cst adds.
Reconciliation. The measured rate, 56-104 per million, is the probability that both stores were still in their store buffers when both loads executed, roughly the ratio of the store-buffer drain window (tens of nanoseconds) to the trial's synchronization overhead (microseconds). Rarity is a property of this microarchitecture and this harness, not of the model. The permitted outcome will occur, and any invariant that depends on its absence fails at a rate that scales with deployment size.
Eight threads each increment their own private counter, but the counters are packed 8 bytes apart in one 64-byte cache line. The measurements were 61.5 Mops/s aggregate packed and 1,309 Mops/s with each counter padded to its own line. (a) Compute the per-operation cost in each case. (b) Attribute the difference. (c) How many bytes of padding memory bought the speedup, and what is the speedup per wasted kilobyte?
Solution. (a) Total operations are \( 8 \times 50\times10^6 = 4\times10^8 \). Packed, that is \( 4\times10^8 / 61.5\times10^6 = 6.50 \) s of wall time, and each thread performed its \( 5\times10^7 \) ops in that window, \( 6.50\,\text{s} / 5\times10^7 = 130 \) ns per increment. Padded, it is \( 4\times10^8 / 1309\times10^6 = 0.306 \) s, giving \( 0.306 / 5\times10^7 = 6.1 \) ns per increment.
(b) The 21.3× ratio (1309/61.5) is entirely coherence traffic. A locked increment needs the line in Modified state. With eight writers on one line, nearly every increment must invalidate seven other cores' copies and pull the line across the mesh, so the 130 ns is dominated by cross-core line transfers. Padded, the line never leaves its home core's L1, and 6.1 ns is just the locked-RMW pipeline cost. No instruction differs between the two runs, only addresses do.
(c) Padding grew eight 8-byte counters to eight 64-byte
lines, \( 512 - 64 = 448 \) wasted bytes, under half a
kilobyte, for 21.3×. This is among the highest
returns per byte in systems programming, which is why
alignas(64), crossbeam's
CachePadded, and folly's
hardware_destructive_interference_size
idioms are reflexes in concurrent code.
A service must sustain \( \lambda = 10{,}000 \) requests/s. Each request holds a worker thread for \( W = 5.5 \) ms total, of which \( C = 0.5 \) ms is CPU and 5 ms is waiting on a downstream call. (a) Size the thread pool with Little's law and the CPU requirement. (b) The team instead deploys 16 workers. Compute the maximum throughput and the shortfall. (c) Recompute the pool size if the downstream wait is converted to async/await so workers are not held while waiting.
Solution. (a) By Little's law, in-flight requests are \( L = \lambda W = 10{,}000 \times 0.0055 = 55 \), so 55 workers are simultaneously occupied (round to 64 for headroom). CPU demand is \( \lambda C = 10{,}000 \times 0.0005 = 5 \) cores. The pool is large because workers are parked, not because the machine is busy.
(b) 16 workers each complete \( 1/W = 181.8 \) requests/s when saturated, so the ceiling is \( 16 / 0.0055 = 2{,}909 \) requests/s, 29 percent of target, with the other 71 percent queueing without bound. This failure looks like a downstream outage in dashboards (latency exploding) while every worker thread is merely asleep on I/O.
(c) Async workers are held only for CPU time, giving \( L = \lambda C = 5 \) concurrent workers, so an 8-thread runtime suffices, with the 50,000 concurrent waits (\( \lambda \times 5\,\text{ms} = 50 \) in flight per ms... precisely \( 10{,}000 \times 0.005 = 50 \) in-flight downstream calls at any instant) held as coroutine or future state at kilobytes each instead of thread stacks at megabytes each. This is the entire economic argument for async runtimes, and it evaporates when \(C\) approaches \(W\), since CPU-bound work gains nothing from await.
Using this page's measurements, decide between two designs for handing 64-byte messages from one thread to another, (i) a blocking pipe (one write and one blocked read per message), and (ii) the SPSC ring measured at 19.4 M items/s. The producer emits bursts at 5 million messages/s. (a) Compute each design's ceiling. (b) For the pipe, compute CPU time lost to context switches per second of burst. (c) State when the pipe is nevertheless the right choice.
Solution. (a) The measured pipe round trip was 3,730 ns, and a one-way blocking handoff is half a round trip, about 1,865 ns, giving a ceiling of \( 1/1.865\,\mu\text{s} \approx 536{,}000 \) messages/s, an order of magnitude short of the 5 M/s requirement. The SPSC ring's measured 19.4 M/s carries the burst with 3.9× headroom. (Even the mutex-condvar queue at 5.1 M/s is marginal, since 98 percent utilization leaves no slack for jitter.)
(b) At its 536 K/s ceiling the pipe forces about one million switches/s (two per message at \( \approx 1.9\,\mu\text{s} \) each, i.e. essentially 100 percent of two cores' time spent switching rather than computing). Blocking designs do not degrade gracefully past saturation. They convert throughput demand into scheduler load.
(c) The pipe wins when the producer and consumer are separate processes (isolation, or Python's GIL escape), when rates are low enough that 1.9 µs is irrelevant, and when blocking semantics are the feature. A sleeping consumer costs nothing, while the SPSC ring as written spins when empty, burning a core to poll. Production designs often hybridize. They spin briefly, then fall back to a futex or eventfd sleep, buying lock-free throughput in bursts and pipe-like economy when idle.
One program, four ways
The closing exercise is the same complete program in all four
languages. Partition a range among workers, compute a sum of
squares modulo a prime in parallel, and merge, the minimal
shape of every embarrassingly parallel job. Each version uses
its language's native idiom rather than a transliteration,
and the idioms are the summary of this page. C passes a
struct through a void* and trusts the
programmer about lifetimes. C++ captures by reference into
lambdas, safe here only because join() precedes
the reads. Rust uses thread::scope, which
encodes "join precedes the reads" in lifetimes so the borrow
checker can prove the captures safe, no Arc
needed. Python uses processes, because the threads version
of this exact workload measured 25 percent slower than
sequential.
#include <pthread.h>
#include <stdio.h>
#define NT 8
#define N 16000000UL
#define MOD 1000003UL
struct job { unsigned long lo, hi, out; }; /* out: no false sharing risk
worth worrying about here;
each is written once */
static void *worker(void *arg) {
struct job *j = arg;
unsigned long s = 0; /* accumulate in a register */
for (unsigned long i = j->lo; i < j->hi; i++)
s += (i * i) % MOD;
j->out = s; /* single write at the end */
return NULL;
}
int main(void) {
pthread_t t[NT];
struct job jobs[NT];
unsigned long chunk = N / NT;
for (int k = 0; k < NT; k++) {
jobs[k].lo = k * chunk;
jobs[k].hi = (k == NT - 1) ? N : (k + 1) * chunk;
pthread_create(&t[k], NULL, worker, &jobs[k]);
}
unsigned long total = 0;
for (int k = 0; k < NT; k++) {
pthread_join(t[k], NULL); /* join = synchronizes-with: */
total += jobs[k].out; /* reading out is race-free */
}
printf("%lu\n", total);
return 0;
}
#include <cstdint>
#include <iostream>
#include <thread>
#include <vector>
int main() {
constexpr int NT = 8;
constexpr uint64_t N = 16'000'000, MOD = 1'000'003;
std::vector<uint64_t> partial(NT, 0);
std::vector<std::thread> threads;
uint64_t chunk = N / NT;
for (int k = 0; k < NT; k++)
threads.emplace_back([&partial, k, chunk] {
uint64_t lo = k * chunk;
uint64_t hi = (k == NT - 1) ? N : lo + chunk;
uint64_t s = 0;
for (uint64_t i = lo; i < hi; i++) s += (i * i) % MOD;
partial[k] = s; // distinct elements: no data race,
}); // (though adjacent: see false sharing;
// one write each makes it harmless)
uint64_t total = 0;
for (int k = 0; k < NT; k++) {
threads[k].join(); // join happens-before the read below
total += partial[k];
}
std::cout << total << "\n";
}
fn main() {
const NT: usize = 8;
const N: u64 = 16_000_000;
const MOD: u64 = 1_000_003;
let mut partial = [0u64; NT];
let chunk = N / NT as u64;
// scope guarantees every spawned thread joins before scope returns,
// so borrowing disjoint &mut slices of a stack array is provably
// safe: no Arc, no Mutex, no 'static bound.
std::thread::scope(|s| {
for (k, slot) in partial.iter_mut().enumerate() {
s.spawn(move || {
let lo = k as u64 * chunk;
let hi = if k == NT - 1 { N } else { lo + chunk };
let mut acc = 0u64;
for i in lo..hi {
acc += (i * i) % MOD;
}
*slot = acc; // each thread owns exactly one slot
});
}
}); // all joins happen here
let total: u64 = partial.iter().sum();
println!("{total}");
}
# Processes, not threads: this is CPU-bound pure Python, the case the
# GIL serializes (measured: 8 threads ran 25% SLOWER than sequential;
# 8 processes ran 6.7x faster).
from concurrent.futures import ProcessPoolExecutor
N = 16_000_000
MOD = 1_000_003
NT = 8
def partial_sum(bounds):
lo, hi = bounds
s = 0
for i in range(lo, hi):
s += (i * i) % MOD
return s
if __name__ == "__main__": # required: workers re-import
chunk = N // NT
ranges = [(k * chunk, N if k == NT - 1 else (k + 1) * chunk)
for k in range(NT)]
with ProcessPoolExecutor(max_workers=NT) as pool:
total = sum(pool.map(partial_sum, ranges))
print(total)
How it is done in practice
Production systems rarely use these primitives raw. They compose a small set of proven patterns, and it is worth naming which pattern each famous system chose. Nginx and Redis are event loops, one process per core (nginx) or one main thread (Redis, with I/O threads bolted on since 6.0), with no shared mutable state between event handlers, which is why Redis operations are atomic without locks. PostgreSQL is a process per connection, the 1980s design that survives because address-space isolation contains the blast radius of a crashing backend. Its shared buffer pool lives in explicit shared memory guarded by lightweight locks. Chrome is a process per site with message passing (Mojo IPC), paying the 118-microsecond-scale process costs for security isolation. Go bet the language on channels and goroutines multiplexed over a work-stealing scheduler. Tokio and rayon are the same bet split into two libraries, one for I/O concurrency and one for CPU parallelism. Linux itself is the largest lock-based program in the world, roughly 30,000 lock-related call sites, plus read-copy-update (RCU, McKenney's work) for read-mostly paths, the pattern where readers take no locks at all and writers publish new versions with release stores, an industrial-scale application of the publication idiom from the memory-model section.
The measured numbers on this page also set the practical budgets. An uncontended lock at 5.5 ns means fine-grained locking is affordable almost everywhere. A contended lock at 87 ns per section means a hot lock caps a system near 11 million sections/s no matter how many of the 52 cores exist. A context switch near 1.9 µs means designs that block per message top out near half a million messages/s per channel. And false sharing's 21× penalty means data layout is a concurrency decision, not an afterthought. Teams that internalize these four numbers, or better, re-measure them on their own hardware, stop guessing which refactor will matter.
Tooling deserves the same first-class status as the
primitives, and it is treated separately below, but one
asymmetry belongs here. Python's diagnostic story is cruder
than C's because its failure modes were cruder.
faulthandler dumps stacks,
sys.settrace can be bent into a deadlock
detector, and multiprocessing has logging hooks,
but there is no ThreadSanitizer equivalent, because until
recently the GIL forgave races it never promised to forgive.
The free-threaded build stops forgiving them, and closing that
tooling gap is one of the migration's real costs.
What a data loader, an inference server, and a training loop each do concurrently
Three workloads dominate applied machine-learning systems, and
each is concurrent for a different one of the three reasons
named at the top of this page. A data loader exists
to hide latency. The accelerator must never wait for JPEG
decoding, tokenization, or a network fetch, so the loader runs
\(k\) workers ahead of the consumer and hands finished batches
over a queue. In PyTorch those workers are processes, not
threads, for the reason the GIL measurements establish, decode
and augmentation are CPU-bound Python and native code, and the
transport is precisely the compromise described in the IPC
section. Tensors are allocated in shared memory and only file
descriptors and metadata travel over the workers' sockets, so
a batch is not copied on the way out. The costs to budget are
the ones measured here, worker startup at fork or spawn prices
(2.2 ms versus 128 ms, which is why spawn plus
persistent_workers=False is a pathology on small
epochs), and per-batch handoff, which is why a loader that
pickles arrays instead of sharing them is 18.7 times slower on
a 64 MiB payload.
An inference server exists for responsiveness and throughput at once, and its structure is a layered answer. The front is an event loop holding thousands of connections, each costing a coroutine rather than a thread, because Little's law says a thread-per-request design at 10,000 requests per second and 50 ms of latency needs 500 parked threads. Behind it sits a batching queue. Requests are accumulated until either a batch size or a few-millisecond timeout is reached, which converts many small matrix multiplies into one large one. The model itself is owned by a single worker per accelerator, because the device is a serial resource and two host threads submitting to it would need a lock anyway. The concurrency that matters there is stream-level, host code enqueues work and returns immediately while the device executes. Tokenizing and detokenizing go to a thread pool sized to the cores, not to the request count. The lock discipline is the strict one. The queue lock is held for the duration of a push or a pop and never across a device call, since an 87 ns critical section protecting a 20 ms inference is free while the reverse is a hung server.
A training loop is concurrent mainly to overlap communication with computation. In data-parallel training, gradients for early layers are ready long before the backward pass finishes, so frameworks bucket them and launch asynchronous all-reduces as soon as each bucket fills, hiding most of the collective under the remaining backward compute. Around that core sit several background activities that are pure latency hiding, the loader described above, asynchronous checkpoint writes so a multi-gigabyte save does not stall the step, and metric aggregation. The failure modes are instructive because they are this page's failure modes in costume. A collective is a barrier, so one straggler rank stalls every rank. A deadlock appears when two ranks enqueue collectives in different orders, which is circular wait with the ranks as threads and the collectives as locks. And the standard fix is the standard fix, a total order, where every rank issues collectives in identical sequence.
Choosing processes, threads, or async
The decision is mechanical once the workload is classified, and the answer differs by language because the languages differ in what a thread can do. The table states the default, and deviations should have a reason written down next to them.
| Workload | C / C++ | Rust | Python |
|---|---|---|---|
| CPU-bound, shared read-only data | threads, one per core, per-thread accumulators | threads or rayon, with scope to borrow the data | processes, or move the kernel into NumPy/C/Rust |
| CPU-bound, needs fault isolation | processes + shared memory | processes + shared memory | processes (the default anyway) |
| I/O-bound, hundreds of connections | threads are fine at this scale | threads or async, either works | threads or asyncio, equivalent throughput |
| I/O-bound, tens of thousands | event loop (epoll/io_uring) | async (tokio) | asyncio |
| Mixed, latency-sensitive | event loop + CPU thread pool | tokio + spawn_blocking / rayon | asyncio + run_in_executor |
| Untrusted or crash-prone code | processes, always | processes, always | processes, always |
Four rules cut across the table. Prefer the coarsest unit that meets the requirement, because coarse units share less. Prefer message passing to shared memory when the message is small, and shared memory with an explicit protocol when it is large, which is the 205 ms versus 11 ms result generalized. Never block an event loop. Move anything longer than a fraction of a millisecond to a pool. And size pools from arithmetic, cores for CPU work and Little's law for blocking work, rather than from a constant someone once typed.
Tooling, finding what testing cannot
Concurrency bugs resist ordinary testing for a reason that can be quantified with this page's own measurement. The store-buffering anomaly appeared 56 to 104 times per million trials, call it \( p = 8\times10^{-5} \). A test that exercises the racy path ten thousand times sees the bug with probability \( 1 - (1-p)^{10^4} \approx 1 - e^{-0.8} = 0.55 \), so a thorough-looking suite passes cleanly 45 percent of the time. The same code deployed at \( 10^9 \) operations per day hits the anomaly about 80,000 times a day. Test-and-hope is not a strategy against a bug with that profile. The tools below are, because each one either amplifies the probability or removes the dependence on probability altogether.
ThreadSanitizer is the first thing to reach
for in C, C++, and Rust. It instruments memory accesses and
maintains vector clocks, so it reports a data race whenever
two conflicting accesses are unordered by happens-before,
whether or not the bad interleaving occurred. Run
against this page's unsynchronized counter on this machine, it
names both accesses, both threads, and the variable, while the
program's own output that run was the correct 200,000, a
perfect illustration of catching a bug the test could not see.
The measured cost on a lock-heavy benchmark here was 7.9×
(0.53 s to 4.2 s), which is affordable in continuous
integration. Its limits are worth knowing. It only examines
code that actually runs, it needs every component compiled
with it, and on this kernel it required ASLR to be disabled
(setarch -R) to map its shadow memory.
$ gcc -O1 -g -fsanitize=thread race.c -o race_tsan -lpthread
$ setarch $(uname -m) -R ./race_tsan
==================
WARNING: ThreadSanitizer: data race (pid=4140076)
Read of size 8 at 0x555555558018 by thread T2:
#0 worker race.c:4 (race_tsan+0x1263)
Previous write of size 8 at 0x555555558018 by thread T1:
#0 worker race.c:4 (race_tsan+0x128d)
Location is global 'counter' of size 8 at 0x555555558018
SUMMARY: ThreadSanitizer: data race race.c:4 in worker
==================
ThreadSanitizer: reported 1 warnings
200000 # note: this run's ANSWER was correct anyway
# Other members of the same family:
# valgrind --tool=helgrind ./prog no recompile, 20-100x slower
# cargo +nightly miri test Rust UB and aliasing in unsafe code
# perf c2c record ./prog locates false sharing by address
// loom: exhaustive model checking of a small concurrent test. Instead of
// running one interleaving, it runs ALL of them, plus every ordering the
// C++11 memory model permits for the atomics involved. tokio and
// crossbeam gate their unsafe code on loom tests.
#[cfg(loom)]
mod tests {
use loom::sync::atomic::{AtomicUsize, Ordering};
use loom::sync::Arc;
use loom::thread;
#[test]
fn publication_is_ordered() {
loom::model(|| { // explores every interleaving
let data = Arc::new(AtomicUsize::new(0));
let flag = Arc::new(AtomicUsize::new(0));
let (d2, f2) = (data.clone(), flag.clone());
let t = thread::spawn(move || {
d2.store(42, Ordering::Relaxed);
f2.store(1, Ordering::Release); // publish
});
if flag.load(Ordering::Acquire) == 1 {
// With Release/Acquire this assertion holds in every
// execution loom explores. Weaken either to Relaxed and
// loom finds a counterexample and prints the schedule.
assert_eq!(data.load(Ordering::Relaxed), 42);
}
t.join().unwrap();
});
}
}
// Run with: RUSTFLAGS="--cfg loom" cargo test --release
Above the level of code sits specification. TLA+
(Lamport) describes a protocol as a state machine and a set of
temporal properties, and its model checker explores the state
space exhaustively for small parameters, which finds the
design errors no amount of testing the implementation can
reach because the implementation faithfully implements a wrong
design. Amazon's engineers reported using it on S3 and
DynamoDB and finding subtle bugs in already-reviewed
protocols. It is the right tool for a replication or
consensus protocol and the wrong tool for a mutex. Between the
extremes sit Miri, which interprets Rust
under a formal aliasing model and catches undefined behavior
in unsafe blocks including data races, and
loom, which model-checks small Rust tests
over all permitted interleavings and orderings. Loom is
exactly how the SPSC ring earlier on this page should be
validated before anyone trusts it on ARM, because the bug it
would have is a missing Release that x86 hides.
The practical stack for a serious concurrent codebase is all
of them, TSan on every CI run, loom or Miri on the handful of
unsafe or lock-free modules, a model checker on the protocol,
and stress tests with randomized delays to widen the windows
the other tools cannot reason about.
The current research frontier
Four active fronts, each traceable from a citation on this
page. First, free-threaded Python. PEP 703's design (biased
reference counting following Choi and colleagues' work,
immortalization, per-object locks, mimalloc) shipped as
CPython 3.13's experimental build and became a supported
option in 3.14, and the open questions are ecosystem-scale,
which C extensions are quietly racy now that the GIL no
longer serializes them, how far single-thread overhead can
be pushed down, and whether subinterpreters (per-interpreter
GILs, a parallel line of CPython work) retain a niche once
free threading is default. Second, kernel I/O interfaces.
io_uring (Jens Axboe's work at Meta, liburing on GitHub) is
displacing epoll's readiness model with completion-based
submission rings, and runtimes are being redesigned around
it, including tokio-uring and glommio's thread-per-core
design, which abandons work stealing entirely on the
argument that stealing's cache misses cost more than
imbalance does for sharded workloads. Third, verified and
formalized concurrency. The RustBelt line continues at
MPI-SWS and its successors (Iris-based separation logics,
Tree Borrows and its predecessor Stacked Borrows as candidate
aliasing models for unsafe Rust), while the
hardware-model community that produced x86-TSO at Cambridge
has delivered mechanized ARMv8 and RISC-V models, and the
C++ committee continues to repair the standard's known
soundness gaps (the out-of-thin-air problem for relaxed
atomics remains formally unresolved). Fourth, structured
concurrency. The argument, made independently in Kotlin
coroutines, Swift's task trees, Python's
asyncio.TaskGroup (3.11) and Trio's nurseries,
is that unscoped spawn is the goto of concurrency and that
task lifetimes should nest lexically. Rust's async ecosystem
is mid-debate on the same point because its cancellation story
(drop the future) interacts badly with borrowed data across
await points.
Open source to read
Each of these is a canonical implementation of something derived above. The file suggested is the one where the ideas are visible.
-
rust-lang/rust,
the standard library's own synchronization code, which is
unusually readable and heavily commented on exactly the
questions this page asks. Open
library/std/src/sync/mutex.rsfirst, thenlibrary/std/src/sync/mpmc/for the channel andlibrary/alloc/src/sync.rsforArc's release/acquire refcount protocol. -
crossbeam-rs/crossbeam,
Rust's concurrency toolbox, with channels, the Chase-Lev
deque, and epoch-based reclamation (the ABA countermeasure).
Start with
crossbeam-deque/src/deque.rsand read the ordering comments against the SPSC derivation above. -
tokio-rs/tokio,
the dominant Rust async runtime. The work-stealing
scheduler lives under
tokio/src/runtime/scheduler/multi_thread/, andworker.rsshows the LIFO slot and steal policy. -
rayon-rs/rayon,
fork-join work stealing behind parallel iterators.
rayon-core/src/join/mod.rsis Blumofe-Leiserson in 200 readable lines. -
tokio-rs/loom,
the interleaving model checker used to validate tokio's and
crossbeam's unsafe internals. Read
src/model.rsto see how the execution space is enumerated, then the tests intests/for the shape a checkable concurrency test takes. -
taskflow/taskflow,
header-only C++ task-graph parallelism with conditional and
nested tasks.
taskflow/core/executor.hppis a compact, modern work-stealing executor worth diffing mentally against rayon's. -
oneapi-src/oneTBB,
Intel's Threading Building Blocks, the longest-running
production work-stealing runtime in C++.
src/tbb/arena.cppandsrc/tbb/scheduler_common.hshow how a mature scheduler handles arenas, task affinity, and oversubscription. -
google/sanitizers,
the documentation and issue history for ThreadSanitizer.
Start with the
ThreadSanitizerAlgorithmwiki page, which explains the vector-clock and shadow-cell design that lets TSan report races that did not actually manifest. -
Amanieu/parking_lot,
word-sized locks with adaptive spinning.
src/raw_mutex.rsshows the CAS-then-futex-style fast/slow path split that produces the 5.5 ns uncontended cost class. -
facebook/folly,
Meta's C++ library.
folly/MPMCQueue.his a production ticket-based bounded queue, andfolly/concurrency/CacheLocality.hhandles false sharing systematically. - cameron314/concurrentqueue, moodycamel's MPMC queue, a single header widely embedded in game engines and trading systems. The README's design notes are a course in why real queues deviate from Michael-Scott.
-
libuv/libuv,
the event loop under Node.js.
src/unix/core.candepoll.cshow exactly what an event loop is with no language sugar over it. -
python/cpython.
The GIL itself is
Python/ceval_gil.c(small and readable),Modules/_threadmodule.cwraps pthreads, and the free-threaded build's biased refcounting is inInclude/internal/pycore_object.handObjects/object.con 3.13+. -
axboe/liburing,
the io_uring userspace library.
examples/io_uring-cp.cis the smallest complete completion-model program.
Common misconceptions
"volatile makes shared variables
thread-safe." The lost-update benchmark on this page
ran with volatile and lost 74 percent of its
updates. C/C++ volatile constrains the compiler's treatment
of accesses for a single thread (its purpose is
memory-mapped I/O). It provides neither atomicity nor
inter-thread ordering. The confusion is fed by Java, where
volatile genuinely provides visibility and
ordering. In C, C++, and Rust, the tools are atomics and
locks, never volatile.
"The GIL makes Python operations atomic, so locks
are unnecessary." The GIL serializes bytecodes, and
counter += 1 is several bytecodes. The
interpreter can switch threads between the load and the
store, and unlocked counters lose updates in ordinary
CPython today. The GIL is an implementation detail
protecting the interpreter's internals, not your invariants,
and code written to the contrary is exactly the code the
free-threaded build will break.
"x86 is strongly ordered, so memory-ordering bugs cannot happen there." The store-buffering test produced the SC-forbidden outcome 56-104 times per million trials on this x86 machine. TSO forbids most reorderings but explicitly permits store-load, and the compiler is free to reorder far more than the hardware unless the source uses atomics. "It cannot happen on x86" is true only for the specific reorderings TSO excludes, and only after the compiler is also constrained.
"Lock-free is faster than locking." Under contention on one cache line, the relaxed atomic counter measured 44.6 Mops against the mutex's 11.5, a real but modest 4×, while the sharded design beat both by more than two orders of magnitude. Lock-freedom is a progress guarantee, valuable against preemption and priority inversion. It does not repeal coherence costs, and the fastest design is almost always the one that shares less, not the one with cleverer atomics.
"Adding threads speeds up a parallel program." Eight threads on one mutex delivered 11.5 Mops where one lockless thread delivered 2,934, so parallelizing made the program 255 times slower. Speedup requires that the work dominate the communication. When the shared operation is the whole loop body, threads only buy contention. Amdahl's law (Problem 1) is the polite version of this; the counter table is the blunt one.
"async/await makes code run in parallel." Async is concurrency (interleaving waits), not parallelism (simultaneous execution). Python's asyncio runs one coroutine at a time on one thread; it matched threads on the I/O benchmark (0.101 s vs 0.106 s) and would do nothing for the CPU benchmark. Tokio's runtime is parallel because it is a thread pool underneath, not because of the keyword. The corollary bites in reverse too: one CPU-heavy handler stalls an entire event loop, a bug preemptive threads structurally cannot have.
"Rust prevents race conditions." Safe Rust
prevents data races: unsynchronized conflicting
accesses. It happily compiles deadlocks, livelocks, atomicity
violations across two correctly-locked critical sections
(check-then-act on a Mutex released in
between), and ordering bugs among relaxed atomics. The
guarantee is precise and worth having; overselling it
discredits it.
"Processes are too expensive to use for concurrency." Measured here, fork-plus-wait costs 118.9 µs against 33.9 µs for a thread: 3.5×, not 100×, thanks to copy-on-write. PostgreSQL, Chrome, and nginx are process-structured at scale. Processes cost more per message (kernel IPC vs shared memory) but buy isolation that no thread design can, and in Python they are the only route to CPU parallelism on a GIL build, worth 6.7× on this machine's measurement.
Self-check
References
- Herlihy, M., Shavit, N., Luchangco, V., Spear, M. The Art of Multiprocessor Programming, 2nd edition. Morgan Kaufmann, 2020.
- Butenhof, D. Programming with POSIX Threads. Addison-Wesley, 1997.
- Williams, A. C++ Concurrency in Action, 2nd edition. Manning, 2019.
- Klabnik, S., Nichols, C. The Rust Programming Language, 2nd edition. No Starch Press, 2023. Chapter 16, "Fearless Concurrency". doc.rust-lang.org/book
- Kerrisk, M. The Linux Programming Interface. No Starch Press, 2010.
- Blandy, J., Orendorff, J., Tindall, L. Programming Rust, 2nd edition. O'Reilly, 2021. Chapters 19-20 on concurrency and asynchronous programming.
- Drepper, U. "What Every Programmer Should Know About Memory." Red Hat technical report, 2007. cpumemory.pdf
- McKenney, P. Is Parallel Programming Hard, And, If So, What Can You Do About It? Continuously updated. kernel.org/pub/.../perfbook
- Lamport, L. "Time, Clocks, and the Ordering of Events in a Distributed System." Communications of the ACM 21(7), 1978. doi:10.1145/359545.359563
- Lamport, L. "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs." IEEE Transactions on Computers C-28(9), 1979. doi:10.1109/TC.1979.1675439
- Adve, S., Gharachorloo, K. "Shared Memory Consistency Models: A Tutorial." IEEE Computer 29(12), 1996. doi:10.1109/2.546611
- Boehm, H.-J. "Threads Cannot Be Implemented As a Library." PLDI, 2005. doi:10.1145/1065010.1065042
- Boehm, H.-J., Adve, S. "Foundations of the C++ Concurrency Memory Model." PLDI, 2008. doi:10.1145/1375581.1375591
- Batty, M., Owens, S., Sarkar, S., Sewell, P., Weber, T. "Mathematizing C++ Concurrency." POPL, 2011. doi:10.1145/1926385.1926394
- Sewell, P., Sarkar, S., Owens, S., Zappa Nardelli, F., Myreen, M. "x86-TSO: A Rigorous and Usable Programmer's Model for x86 Multiprocessors." Communications of the ACM 53(7), 2010. doi:10.1145/1785414.1785443
- Michael, M., Scott, M. "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms." PODC, 1996. doi:10.1145/248052.248106
- Treiber, R. K. "Systems Programming: Coping with Parallelism." IBM Almaden Research Center technical report RJ 5118, 1986.
- Michael, M. "Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects." IEEE Transactions on Parallel and Distributed Systems 15(6), 2004. doi:10.1109/TPDS.2004.8
- Coffman, E. G., Elphick, M., Shoshani, A. "System Deadlocks." ACM Computing Surveys 3(2), 1971. doi:10.1145/356586.356588
- Herlihy, M. "Wait-Free Synchronization." ACM TOPLAS 13(1), 1991. doi:10.1145/114005.102808
- Herlihy, M., Wing, J. "Linearizability: A Correctness Condition for Concurrent Objects." ACM TOPLAS 12(3), 1990. doi:10.1145/78969.78972
- Mellor-Crummey, J., Scott, M. "Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors." ACM TOCS 9(1), 1991. doi:10.1145/103727.103729
- Blumofe, R., Leiserson, C. "Scheduling Multithreaded Computations by Work Stealing." Journal of the ACM 46(5), 1999. doi:10.1145/324133.324234
- Chase, D., Lev, Y. "Dynamic Circular Work-Stealing Deque." SPAA, 2005. doi:10.1145/1073970.1073974
- Jung, R., Jourdan, J.-H., Krebbers, R., Dreyer, D. "RustBelt: Securing the Foundations of the Rust Programming Language." POPL, 2018. doi:10.1145/3158154
- Gross, S. "PEP 703: Making the Global Interpreter Lock Optional in CPython." Python Enhancement Proposal, accepted 2023. peps.python.org/pep-0703
- Snow, E., et al. "PEP 554: Multiple Interpreters in the Stdlib" and "PEP 734: Multiple Interpreters in the Stdlib." Python Enhancement Proposals, 2017-2024. peps.python.org/pep-0554
- Newcombe, C., Rath, T., Zhang, F., Munteanu, B., Brooker, M., Deardeuff, M. "How Amazon Web Services Uses Formal Methods." Communications of the ACM 58(4), 2015. doi:10.1145/2699417
- Dijkstra, E. W. "Solution of a Problem in Concurrent Programming Control." Communications of the ACM 8(9), 1965. doi:10.1145/365559.365617
- Hoare, C. A. R. "Monitors: An Operating System Structuring Concept." Communications of the ACM 17(10), 1974. doi:10.1145/355620.361161
- Franke, H., Russell, R., Kirkwood, M. "Fuss, Futexes and Furwocks: Fast Userlevel Locking in Linux." Ottawa Linux Symposium, 2002.
- Ousterhout, J. "Why Threads Are a Bad Idea (For Most Purposes)." Invited talk, USENIX Technical Conference, 1996.
- von Behren, R., Condit, J., Brewer, E. "Why Events Are a Bad Idea (for High-Concurrency Servers)." HotOS, 2003.
Key takeaway
Concurrency has one problem, shared mutable state, and the four languages on this page are four policies toward it. C gives the operating system's primitives and no policy at all; C++ keeps C's costs and adds a formal contract, the happens-before memory model, under which a data race is not a wrong answer but the absence of any answer. Rust makes that contract a type system, so the racy counter is a compile error naming the exact missing trait, and Python historically made the whole interpreter one critical section and is now, via PEP 703, unwinding that choice with the very techniques (sharded counters, per-object locks, padding) this page measures. The measurements are the part to carry: an uncontended lock costs 5.5 ns, a contended one 87 ns, a context switch 1.9 microseconds, false sharing costs 21 times, and eight threads fighting over one cache line run 255 times slower than one thread left alone. Sharing less always beats synchronizing better, and every great concurrent design, from per-CPU counters to work stealing to the event loop, is that one sentence applied with discipline.