Threads and concurrency models

A process gives a program its own address space and resources, but sometimes one program wants to do several things at once: a web server handling many clients, a spreadsheet recalculating while you type, a game simulating physics while it draws frames. Creating a separate process for each activity works, but the processes cannot easily share data and each one costs a full address space. Threads solve this. A thread is an independent flow of execution, with its own program counter, registers and stack, that shares its process's address space, open files and other resources with the other threads in the same process.

CMPUT-274 introduced threads, processes and asynchronous code from Python, including the global interpreter lock and race conditions. This lesson looks underneath: how operating systems implement threads, how kernel threads differ from user-level threads, how POSIX threads (pthreads) work in C, and why more cores do not always mean more speed. Synchronizing threads safely is the subject of Lessons 5 and 6.

What threads share and what they keep

Because threads share memory, communication between them is just reading and writing the same variables, which is fast and convenient. It is also dangerous: two threads updating the same variable without coordination can corrupt it, and a bug in one thread, such as a wild pointer, can crash the whole process. Each thread needs its own stack because each is in the middle of its own chain of function calls. On Linux the default stack size for a new pthread is 8 MiB of virtual address space, of which only the pages actually touched are backed by physical memory.

Why use threads?

Threads serve two different goals. The first is responsiveness and overlap: while one thread waits for a disk read or a network reply, another can run, so the program keeps making progress. This helps even on a single core. The second is parallelism: on a multicore processor, threads of the same process can run at the same time on different cores and finish a computation faster. Threads are also cheaper than processes. Creating a thread does not copy an address space, and switching between threads of the same process does not change page tables, so the TLB keeps its entries.

#include <pthread.h>
#include <stdio.h>

#define N 1000000
#define T 4
static double data[N];

struct job { int id; long lo, hi; double sum; };     /* each thread gets its own slot */

static void *partial(void *arg) {
    struct job *j = arg;
    double s = 0;
    for (long i = j->lo; i < j->hi; i++) s += data[i];
    j->sum = s;                                       /* no sharing: no lock needed */
    return NULL;
}

int main(void) {
    for (long i = 0; i < N; i++) data[i] = 1.0 / (i + 1);
    pthread_t tid[T]; struct job jobs[T];
    for (int t = 0; t < T; t++) {
        jobs[t] = (struct job){t, t * (long)N / T, (t + 1) * (long)N / T, 0};
        pthread_create(&tid[t], NULL, partial, &jobs[t]);
    }
    double total = 0;
    for (int t = 0; t < T; t++) {
        pthread_join(tid[t], NULL);                   /* wait, then combine in a fixed order */
        printf("thread %d summed [%7ld, %7ld) = %.6f\n", t, jobs[t].lo, jobs[t].hi, jobs[t].sum);
        total += jobs[t].sum;
    }
    printf("harmonic number H(%d) = %.6f\n", N, total);
    return 0;
}

$ gcc -O2 -Wall -g -pthread -fsanitize=address,undefined toy.c -o toy
$ ./toy
thread 0 summed [      0,  250000) = 13.006434
thread 1 summed [ 250000,  500000) = 0.693146
thread 2 summed [ 500000,  750000) = 0.405465
thread 3 summed [ 750000, 1000000) = 0.287682
harmonic number H(1000000) = 14.392727

This program is a model of safe parallel work. Each thread writes only to its own struct, so no two threads touch the same memory, and the main thread combines results only after pthread_join confirms each thread has finished. Combining in a fixed order also makes the floating-point result identical on every run, because floating-point addition is not associative and a different order could change the last digits. The pthread functions follow a simple pattern: pthread_create starts a thread running a function with one pointer argument, and pthread_join waits for it and collects its return value.

Kernel threads, user threads and the mapping between them

Threads can be implemented by the kernel, by a user-level library or by both. With kernel threads, the kernel knows about every thread, schedules each one independently on the available cores and blocks only the thread that makes a blocking system call. Linux implements threads this way: a thread is a task created with the clone system call and flags saying which resources to share, and the scheduler treats it much like a process. This is the one-to-one model, used today by Linux, Windows and macOS.

With user-level threads, a library inside the process creates and switches threads without the kernel's knowledge. Switching is very fast, a function call rather than a system call, but the kernel sees only one schedulable entity, so the threads cannot run in parallel on several cores, and if one thread blocks in the kernel, all of them stop. The many-to-many model multiplexes many user threads onto a smaller pool of kernel threads, combining cheap switching with parallelism. Go's goroutines, Java's virtual threads (since Java 21) and Erlang processes use this idea: a runtime schedules millions of lightweight tasks onto a handful of kernel threads, parking a task when it would block.

# The kernel sees each thread as a schedulable task inside one process
import threading, os, time
def threads_line():
    for line in open(f"/proc/{os.getpid()}/status"):
        if line.startswith("Threads:"):
            return line.split()[1]
print("threads before:", threads_line())
stop = threading.Event()
workers = [threading.Thread(target=stop.wait) for _ in range(5)]
for w in workers: w.start()
print("threads with 5 workers:", threads_line())
tids = sorted(os.listdir(f"/proc/{os.getpid()}/task"))
print("entries in /proc/<pid>/task:", len(tids))
stop.set()
for w in workers: w.join()
print("threads after join:", threads_line())

threads before: 1
threads with 5 workers: 6
entries in /proc/<pid>/task: 6
threads after join: 1

How much faster can threads make a program?

Parallelism is limited by the parts of a program that cannot run in parallel. Amdahl's law states that if a fraction p of a program's work can be spread over n cores and the rest must run serially, the best possible speedup is 1 divided by ((1 - p) + p/n). Even with unlimited cores, the speedup can never exceed 1/(1 - p). CMPUT-229 introduced the law for hardware improvements; here it explains why a program that is 90 per cent parallel cannot run more than ten times faster however many threads it uses.

# Amdahl's law: speedup = 1 / ((1 - p) + p / n) for parallel fraction p on n cores
def amdahl(p, n):
    return 1 / ((1 - p) + p / n)
print(f"{'cores':>5} | {'p=0.50':>7} {'p=0.90':>7} {'p=0.95':>7} {'p=0.99':>7}")
for n in (1, 2, 4, 8, 16, 64, 1024):
    print(f"{n:>5} | " + " ".join(f"{amdahl(p, n):7.2f}" for p in (0.5, 0.9, 0.95, 0.99)))
print("limit as n grows: 1/(1-p) =", ", ".join(f"{1/(1-p):.0f}" for p in (0.5, 0.9, 0.95, 0.99)))

cores |  p=0.50  p=0.90  p=0.95  p=0.99
    1 |    1.00    1.00    1.00    1.00
    2 |    1.33    1.82    1.90    1.98
    4 |    1.60    3.08    3.48    3.88
    8 |    1.78    4.71    5.93    7.48
   16 |    1.88    6.40    9.14   13.91
   64 |    1.97    8.77   15.42   39.26
 1024 |    2.00    9.91   19.64   91.18
limit as n grows: 1/(1-p) = 2, 10, 20, 100

Real programs fall short even of Amdahl's limit. Threads must coordinate, and locks, cache-line transfers between cores and memory bandwidth all add overhead. Adding threads beyond the number of cores usually makes a processor-bound program slower, because the extra threads only add context switches. Gustafson's law gives a more hopeful view for large problems: if the problem grows with the number of cores, as when a weather model uses a finer grid on a bigger machine, the parallel part grows and good speedups are achievable. The practical rule: for processor-bound work, use about as many threads as cores; for work that mostly waits on input and output, more threads (or asynchronous code) help.

Thread pools and other concurrency models

Creating a thread for every task is wasteful when tasks are short and numerous. A thread pool creates a fixed number of worker threads up front and feeds them tasks from a queue. This bounds resource use (a server under attack cannot be made to create a million threads) and avoids repeated creation costs. Java's ExecutorService, Python's concurrent.futures and most web servers use pools.

# A fixed-size thread pool processes I/O-like tasks; results come back in submission order
from concurrent.futures import ThreadPoolExecutor
import time
def fetch(n):
    time.sleep(0.05)                 # stands in for waiting on a disk or network reply
    return n * n
t0 = time.perf_counter()
with ThreadPoolExecutor(max_workers=8) as pool:
    results = list(pool.map(fetch, range(16)))
elapsed = time.perf_counter() - t0
print("results:", results)
print("16 tasks of 0.05 s on 8 threads took about",
      "0.1 s" if elapsed < 0.4 else "longer than expected", "(two rounds), not 0.8 s")

results: [0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225]
16 tasks of 0.05 s on 8 threads took about 0.1 s (two rounds), not 0.8 s

Threads are not the only way to handle many activities at once. An event-driven program uses a single thread and an event loop that waits for many file descriptors at once with select, poll, epoll (Linux) or kqueue (BSD and macOS), handling whichever is ready. Node.js, nginx and Python's asyncio work this way, and CMPUT-313 used selectors and asyncio for network servers. Event-driven code avoids most locking but must never block, since one slow handler stalls everything. Many systems combine the approaches: a few threads, each running an event loop, one per core.

Threads and the rest of the operating system

Threads complicate several operating system features. If one thread calls fork, POSIX copies only that thread into the child, so locks held by other threads may stay locked forever in the child; this is why a multithreaded program should call exec soon after fork. Signals sent to a process are delivered to one thread that has not blocked them, so programs often block signals in all threads but one, which waits for them with sigwait. Thread-local storage, declared with the _Thread_local keyword in C or threading.local in Python, gives each thread its own copy of a variable; the C library uses it so that each thread has its own errno.

Worked examples