Threads, concurrency and parallelism

These words get used interchangeably, and they mean different things. This is a full walk through the subject, from what a process is down to what CPUs do with memory.

Measurements come from one 11-core Mac, using C compiled with clang and Python 3.14 with the GIL enabled. The results show shapes, not universal numbers.

Concurrency and parallelism

Concurrency is about structure: dealing with several things at once. Parallelism is about execution: doing several things at the same instant.

A single chef with four dishes on the go is concurrent: they switch between tasks, and only do one at a time. Four chefs working together are parallel. Concurrency is possible on one core. Parallelism needs several.

Processes and threads

A process is a running program. The operating system gives it its own virtual address space, open files and at least one thread. Processes are isolated, so a crash in one doesn’t harm another.

A thread is one line of execution in a process. Threads share memory, files and code, and each has its own stack and registers.

Process
+---------------------------------------+
|  Heap, globals, code, open files      |  shared
|                                       |
|  Thread 1      Thread 2    Thread 3   |
|  [stack]       [stack]     [stack]    |  private
|  [registers]   [registers] [registers]|
+---------------------------------------+

Sharing memory makes threads fast at exchanging data, and it’s also what makes them dangerous.

On Linux, the kernel treats both as tasks, and the difference is what they share. The fork and exec chapter follows this in the source.

Creating and joining a thread took about 13.2 µs here, so thread pools exist for a reason.

The scheduler

With more threads than cores, the operating system’s scheduler switches between them. A context switch saves one thread’s registers, and loads another’s. The direct cost is small, and the indirect cost is larger, because CPU caches now hold the wrong data.

Preemptive scheduling means the OS can interrupt a thread at any instruction, which is why races happen anywhere. Cooperative scheduling means a task runs until it yields, as in async code. The scheduler chapter covers how Linux chooses.

Which work suits which model

This is the most important practical distinction.

CPU-bound work is limited by the processor: compression, image processing, calculations. I/O-bound work spends its time waiting: networks, disks, databases.

In Python, running CPU work four times:

Threads gave almost no speedup, and processes gave 2.7 times. Now 20 sleeps of 50 ms, standing in for I/O:

Threads cut this eighteen-fold, because waiting doesn’t need a CPU. And 10,000 concurrent sleeps with asyncio took just 0.12 s.

The GIL

CPython’s global interpreter lock lets only one thread run Python bytecode at a time. So threads don’t speed up pure Python CPU work, as the table shows. It’s released during blocking I/O, and C extensions can release it. Hashing large data with hashlib does so:

Python 3.14 officially supports a free-threaded build without the GIL, though it remains optional, and the default build keeps it. The GIL also doesn’t make code thread-safe, because a thread can be switched out between bytecodes.

Amdahl’s law

Parallelism has limits. If a fraction $p$ of a job can be parallelized, the speedup on $N$ cores is:

$S = \frac{1}{(1-p) + p/N}$

At 95% parallel, the limit is 20 times, with infinite cores. Starting and stopping threads, and sharing data, make it worse in practice. The earlier result of 2.7 times on four processes shows these costs.

Race conditions

A race condition is when the result depends on the timing of threads. count++ looks like one operation, but it’s three:

Thread A                Thread B
read count (5)
                        read count (5)
add 1 (6)
                        add 1 (6)
write 6
                        write 6       <- one increment lost

Two C threads each incremented a shared volatile long 20 million times:

volatile ++ : 20122162 of 40000000

About half the updates vanished, and a second run gave a different number. That’s a key feature of races: they’re nondeterministic, so tests can pass and production can fail.

(Without volatile, the compiler optimized the loop into one addition, and hid the race completely. Compilers assume no other thread is touching ordinary variables.)

A data race is a specific case: two threads access the same memory, at least one writes, and nothing orders them. In C and C++, this is undefined behaviour, so the program has no meaning at all. volatile isn’t a fix. It’s used here only to stop the optimizer.

Critical sections and mutexes

A critical section is code that touches shared state. A mutex (mutual exclusion lock) lets only one thread into it:

pthread_mutex_lock(&m);
count++;
pthread_mutex_unlock(&m);

Measured with the same test:

Correctness costs time when threads are fighting over one value. Without contention, costs are tiny here: 4.6 ns for a mutex, and 1.73 ns for an atomic. So the cost of a lock is mostly contention, not the lock itself.

How locks work

Locks use atomic CPU instructions. On Linux, a mutex is built on a futex: it tries an atomic operation in user space, and only makes a system call to sleep if the lock is taken. So an uncontended lock never enters the kernel.

A spinlock loops instead of sleeping. It’s useful for very short waits, and wasteful otherwise. Kernels use them where sleeping isn’t possible.

Lock varieties

Condition variables

A thread waiting for something shouldn’t spin. A condition variable lets it sleep until told. Waits must be in a loop, because of spurious wakeups, and because another thread may have got there first:

with cond:
    while not queue:
        cond.wait()
    item = queue.pop()

This is the base of the producer-consumer pattern.

Deadlock

A deadlock is when threads wait for each other forever. This Python program takes two locks in opposite orders:

import threading,time
a,b=threading.Lock(),threading.Lock()
def w1():
    with a:
        time.sleep(.05)
        with b: pass
def w2():
    with b:
        time.sleep(.05)
        with a: pass
t=[threading.Thread(target=f,daemon=True) for f in (w1,w2)]
[x.start() for x in t]; [x.join(1) for x in t]
print("still blocked after 1s:", [x.is_alive() for x in t])

Output:

still blocked after 1s: [True, True]

Both threads will wait forever. Deadlock needs four conditions, known as the Coffman conditions:

1. Mutual exclusion: resources can’t be shared.
2. Hold and wait: a thread keeps one lock while waiting for another.
3. No preemption: locks can’t be taken away.
4. Circular wait: a cycle of threads waiting.

Breaking any one prevents deadlock. The usual fix is lock ordering: always take locks in the same global order. Other approaches are timeouts, and avoiding holding a lock during a call to unknown code or the network.

Related problems:

• Livelock: threads stay active, reacting to each other, and make no progress.
• Starvation: a thread never gets a turn.
• Priority inversion: a low-priority thread holds a lock that a high-priority one needs, while medium-priority threads run.

Atomics

An atomic operation completes as one indivisible step. CPUs provide atomic add, swap and compare-and-swap (CAS). CAS means “if this value is still X, set it to Y”, and it reports success. It’s the basic building block of lock-free code:

long old, new;
do {
    old = atomic_load(&value);
    new = old * 2;
} while (!atomic_compare_exchange_weak(&value, &old, new));

Lock-free algorithms guarantee that some thread always makes progress, and a paused thread can’t block the rest. They’re hard to get right. The ABA problem is a classic trap: a value changes from A to B and back to A, and CAS can’t see the change.

Memory models

This is the deepest layer. CPUs and compilers reorder instructions for speed, and each core has its own caches and store buffers. So one thread can see another’s writes in a different order from how they were made.

// Thread 1          // Thread 2
data = 42;           while (!ready) {}
ready = 1;           print(data);

Without synchronization, thread 2 may see ready set and still read old data.

A memory model defines what’s allowed. Atomic operations carry an ordering:

A release store paired with an acquire load makes a happens-before relationship: everything before the release is visible after the acquire. Fixing the example above takes just that. Locks do this for you, which is one reason to prefer them.

x86 has a strong hardware model, while ARM is weaker, so buggy code that works on an Intel server can fail on ARM.

Cache coherence and false sharing

Each core has its own cache, which holds memory in cache lines, 128 bytes on this machine. A coherence protocol keeps them consistent: for a core to write a line, it needs exclusive ownership, so other copies are invalidated.

That creates a surprising effect. If two threads write different variables on the same line, the line bounces between cores. This is false sharing:

struct same  { long a; long b; };              // same cache line
struct apart { long a; char pad[120]; long b; };  // separate lines

Two threads, each incrementing its own variable 400 million times:

It ran almost four times slower, with no shared data and no locks. Padding fixes it, and high-performance code aligns busy fields to cache lines for this reason.

Async and event loops

Threads are costly at huge scale, because each has a stack and scheduling overhead. Asynchronous programming handles many tasks on few threads. A task runs until it would block, then gives control back to an event loop, which uses OS mechanisms such as epoll or kqueue to find out what’s ready.

async def fetch(url):
    response = await client.get(url)   # yields here
    return response

await marks every point where other tasks can run. This has two effects. Data races are much rarer on one thread, since tasks switch only at known points. But one blocking call or long computation stalls every task on the loop.

Function colouring is the common complaint: async functions can only be awaited from async functions, so the choice spreads through a codebase.

Green threads

Some runtimes offer lightweight threads, which give the simple blocking style at async scale. Goroutines in Go and virtual threads in Java are scheduled by the runtime onto a few OS threads, called M:N scheduling. They start with small stacks, so a program can run very many of them.

Avoiding shared state

The best way to avoid race conditions is not to share mutable data.

Immutability. Data that never changes can be read by any thread.

Thread confinement. Keep data in one thread, as in thread-local storage.

Message passing. Threads own their data, and send messages, as in Go’s channels. The Go proverb is: don’t communicate by sharing memory, share memory by communicating.

The actor model. Each actor has private state and a mailbox, and handles one message at a time, as in Erlang and Akka.

Rust’s ownership goes further: the compiler rejects data races at compile time (Rust vs Go vs C++).

Common patterns

Thread pool size is a common question. For CPU work, it’s about the number of cores. For I/O work, a known formula is:

$\text{threads} = \text{cores} \times (1 + \frac{\text{wait time}}{\text{compute time}})$

A bounded queue in front gives backpressure.

Structured concurrency treats a group of tasks as one unit, so they can’t outlive their parent, and errors and cancellation propagate cleanly.

Debugging

Concurrency bugs are hard to reproduce, so tools help.

• ThreadSanitizer finds data races at runtime: clang -fsanitize=thread.
• Go’s race detector does the same, with go test -race.
• Thread dumps show what each thread is waiting on, which makes deadlocks easy to see.
• perf c2c finds false sharing on Linux.

How to choose

A good order of preference: avoid sharing, then use immutable data, then message passing, and then locks. Lock-free code comes last, and only when measurement demands it.

The takeaway

Concurrency is about structure, and parallelism is about speed. Choose threads, processes or async by whether work waits or computes. Shared mutable state causes races, so protect it or, better, remove it. Below that, memory ordering and cache lines decide what really happens on the hardware.