Threads & Concurrency

Imagine reading a book. Your eyes move from word to word, line to line — that sequential path through the text is a "thread" of reading. A thread of execution in a program is exactly analogous: it is a sequential path through the program's instructions, maintaining a position (the program counter, PC) and a stack (the local variables and call frames built up so far).

More precisely, a thread is defined by the CPU state that is private to it:

• Program Counter (PC/RIP/PC): which instruction executes next
• Stack pointer (SP/RSP): where the current call stack lives in memory
• Stack: the actual memory for local variables and return addresses
• General-purpose registers: the CPU's scratch space while computing
• Thread-local storage (TLS): a small per-thread data area (like errno in C)

Everything else — the heap, code segment, file descriptors, signal handlers, memory mappings — is shared among all threads in the same process.

This is a crucial insight: threads are a way of time-sharing (or space-sharing) the CPU's sequential execution model across multiple independent sequences of instructions, all operating on the same data. The sharing of data is the source of both their power (easy communication) and their danger (race conditions).

The Linux kernel represents each thread as a task_struct. In Linux, there is no separate "process" structure — a process is simply a group of threads that share the same memory mapping (mm_struct). fork() creates a new task with a copy of the parent's address space; clone() with CLONE_VM creates a new task that shares the address space — that is a thread.

// Inspect your own thread ID and process ID
#include <stdio.h>
#include <unistd.h>      // getpid, gettid
#include <sys/syscall.h> // SYS_gettid

int main(void) {
    pid_t pid = getpid();
    // gettid() is a Linux-specific syscall
    pid_t tid = (pid_t)syscall(SYS_gettid);
    printf("process id: %d\n", pid);
    printf("thread  id: %d\n", tid);
    // In a single-threaded process, they are equal.
    // In a multi-threaded process, pid is the same for all
    // threads; tid is unique per thread.
    return 0;
}

The distinction between a process and a thread is fundamentally about what is shared. This table is worth memorizing because it governs everything else in this module:

Creating a new process (fork()) duplicates the address space. This is expensive (even with copy-on-write, the page tables must be cloned, TLBs flushed, etc.) and communication between processes requires explicit IPC (pipes, sockets, shared memory). Processes are isolated — a crash in one cannot corrupt another's memory.

Creating a new thread (pthread_create() or clone()) is far cheaper: a new stack is allocated (typically 8 MB by default on Linux, but only a few pages are actually touched initially), and the new thread begins executing immediately in the same address space. Communication is trivial — just read/write shared variables — but there is no isolation. One thread's bug can corrupt another thread's data or crash the entire process.

The analogy: threads are like colleagues sharing the same office (same files, same whiteboard, same coffee machine — and they can knock each other's work over). Processes are like separate companies in separate buildings — they can only communicate by sending messages or using shared meeting rooms with explicit booking.

On Linux, the kernel makes no structural distinction between "thread" and "process" — both are task_struct entries. The distinction is whether they share mm_struct (address space). This is why Linux threads are sometimes called lightweight processes (LWP).

// See the difference: fork vs pthread_create
#include <stdio.h>
#include <unistd.h>
#include <pthread.h>

int shared = 0;

void *thread_fn(void *arg) {
    shared = 42;  // visible to main thread immediately
    return NULL;
}

int main(void) {
    // --- Thread: shares memory ---
    pthread_t t;
    pthread_create(&t, NULL, thread_fn, NULL);
    pthread_join(t, NULL);
    printf("After thread: shared = %d\n", shared); // 42

    // --- Fork: copy of memory ---
    shared = 0;
    if (fork() == 0) {
        shared = 99;  // only in child's copy
        _exit(0);
    }
    wait(NULL);
    printf("After fork:   shared = %d\n", shared); // 0, unchanged
    return 0;
}

When a thread is "visible" to the OS kernel, the OS can schedule it independently on a CPU. When it is not visible, the OS sees only the process — a single schedulable entity — and the threads inside are managed entirely by user-space code (a threading library). This gives us two extremes:

Kernel threads (1:1 model): Every user-visible thread maps to exactly one kernel-scheduled entity. The kernel knows about all your threads and can schedule them simultaneously on multiple CPUs. This is what Linux pthreads gives you via clone(CLONE_VM|...). The advantages are real parallelism and the ability to block one thread in a syscall without blocking others. The cost is that thread creation/destruction requires a syscall, and context switching threads requires kernel involvement (trap into kernel, save/restore kernel-side state).

User-space threads (N:1 model / green threads): Many threads inside the process are managed by a threading library, all multiplexed onto a single kernel-scheduled entity (one OS thread). The library has its own scheduler and switch routine. Context switches are fast (no kernel trap), and you can have millions of threads. But: only one thread runs at a time (no parallelism on multiple cores), and if any thread makes a blocking syscall, the entire process blocks — every other thread freezes too. Classic examples: early Java green threads, Python 2's greenlet.

Why the distinction matters for the kernel: When you write a kernel module or study the kernel scheduler, you are only interacting with kernel threads. The scheduler in kernel/sched/ picks from the set of runnable task_struct entries — it has no knowledge of user-space "fibers" or "green threads" inside a process.

The OS provides kernel threads because:

1. Blocking I/O: a thread can sleep in the kernel waiting for a disk read without blocking other threads.
2. True parallelism: on a 16-core machine, 16 kernel threads can genuinely run simultaneously.
3. Fair scheduling: the kernel can pre-empt a compute-hogging thread and give CPU time to others.

// Check how many kernel threads your pthreads program creates
// Compile: gcc -o threads threads.c -lpthread
// Run:     ./threads &; ls /proc/$!/task
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>

void *spin(void *arg) {
    while (1) pause(); // sleep until signal
    return NULL;
}

int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, spin, NULL);
    pthread_create(&t2, NULL, spin, NULL);
    printf("PID=%d. Check: ls /proc/%d/task\n", getpid(), getpid());
    // You will see 3 entries: main + t1 + t2
    // Each is a real kernel task_struct (LWP)
    pause();
    return 0;
}

The 1:1 (pthreads/Linux) and N:1 (green threads) models are the extremes. The M:N model (also called the hybrid model) sits in between: M user-space threads are multiplexed across N kernel threads, where M >> N is possible but N > 1 allows real parallelism.

The idea is to get the best of both worlds:

• Fast context switches for user threads that don't block (no kernel trap needed)
• Real parallelism because there are multiple kernel threads running on multiple CPUs
• When a user thread blocks in a syscall, the kernel thread it was running on can pick up another user thread

Historically, Solaris used M:N (with "scheduler activations" — the kernel notifies the user-space scheduler of events like blocking/unblocking). Early versions of the Go runtime used M:N (Goroutines are M user-space goroutines multiplexed over N OS threads, where N = GOMAXPROCS). Modern Go still uses this model and calls the three levels: G (goroutine), M (machine/OS thread), P (processor/scheduler context).

Why is M:N hard to implement correctly?

1. Scheduler synchronization: the user-space scheduler and kernel scheduler must coordinate. If the kernel pre-empts an OS thread while it holds a user-space mutex, progress can stall.
2. Blocking syscalls: if a user thread calls read() and blocks, the kernel thread is consumed. The library must detect this and spin up a replacement kernel thread — complex and racy.
3. Signal handling: signals arrive at a kernel thread; figuring out which user thread should handle them is non-trivial.

This complexity is why Linux (and Windows, and modern macOS) settled on 1:1: just make kernel threads cheap enough that the extra overhead is acceptable. Linux thread creation (via clone()) is significantly cheaper than fork() and fast enough for most applications. The M:N complexity is reserved for language runtimes (Go, Erlang BEAM) that need to manage millions of lightweight tasks.

# Visualize Go's M:N model conceptually
# (no runnable code, but inspect it at runtime)
# In a Go program:
#   go tool trace -> shows goroutines on OS threads
#   GOMAXPROCS=4  -> 4 kernel threads (M=4)
#   thousands of goroutines (G >> M)

# On Linux, inspect a Go binary's kernel threads:
#   ps -L -p <pid>   # shows all LWPs (= OS/M threads)
#   ls /proc/<pid>/task  # same via procfs

# Each M is a real kernel task_struct.
# Goroutines (G) are purely user-space stacks
# parked/runnable in the runtime scheduler queues.

Now we arrive at the problem that makes concurrent programming notoriously difficult. A race condition occurs when the correctness of a program depends on the relative timing or ordering of operations in multiple threads — and that ordering is not controlled.

Consider two threads both doing counter++. In C, this compiles to roughly:

load  reg, [counter]   ; read current value
add   reg, 1           ; increment
store [counter], reg   ; write back

These three instructions are not atomic. If Thread A reads counter = 5, then Thread B reads counter = 5, then both add 1 and both write 6 — we have lost one increment. The final value is 6, not 7. This is called a lost update.

The terrifying thing about race conditions is that they are non-deterministic. On a lightly loaded machine with two threads, the race window (the time between Thread A's read and write) may be only a few nanoseconds, so the bug appears almost never. Under load, with more threads, or on a machine with stronger memory reordering, it appears constantly. This makes them extraordinarily hard to reproduce, test for, and debug.

Data race vs. race condition: These terms are often conflated but are distinct:

• A data race is a specific technical condition: two threads access the same memory location concurrently, at least one access is a write, and there is no synchronization between them. The C11 and C++11 standards say a program with a data race has undefined behavior — the compiler and CPU are allowed to do anything.
• A race condition is a higher-level correctness issue: the program's behavior depends on timing. You can have a race condition even with proper synchronization if the locking logic is wrong.

Tooling: ThreadSanitizer (TSan), enabled with gcc -fsanitize=thread, instruments memory accesses at compile time and detects data races at runtime. It is one of the most valuable tools in a systems programmer's arsenal.

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

// Compile with: gcc -o race race.c -lpthread
// Then also:    gcc -fsanitize=thread -o race_tsan race.c -lpthread

long counter = 0;

void *increment(void *arg) {
    for (int i = 0; i < 1000000; i++)
        counter++;  // NOT ATOMIC: load-add-store, data race!
    return NULL;
}

int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, increment, NULL);
    pthread_create(&t2, NULL, increment, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    // Expected: 2000000. Actual: unpredictably less.
    printf("counter = %ld\n", counter);
    return 0;
}

The solution to data races is mutual exclusion: ensure that only one thread at a time executes the critical section — the code that reads and writes shared data. The classical mechanism is the mutex (mutual exclusion lock).

A mutex has two operations: lock() and unlock(). The invariant is: at most one thread holds the lock at any moment. Any thread that tries to lock() while another holds it will block (sleep) until the holder calls unlock().

The metaphor: a mutex is a key to a single-occupancy bathroom. If the key is on the hook, you take it, do your business, and return it. If it's gone, you wait outside until the current occupant returns it.

In POSIX C:

pthread_mutex_t mu = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_lock(&mu);
// --- critical section ---
counter++;
// --- end critical section ---
pthread_mutex_unlock(&mu);

How is a mutex implemented? At the lowest level, you need an atomic read-modify-write instruction — something the hardware guarantees completes without interruption. On x86, this is LOCK XCHG or CMPXCHG. On ARM, it is LDREX/STREX (Load-Exclusive / Store-Exclusive) or LDAXR/STLXR on ARMv8. The kernel's futex (Fast Userspace muTEX) system call sits underneath pthreads mutexes: the fast path is a single atomic CAS in user space (no syscall), and the slow path (when a thread must actually sleep) calls futex(FUTEX_WAIT).

Locking discipline is critical: every access to shared data must be protected by the same lock. If one thread locks and another thread accesses the same data without locking, you still have a data race — the lock only works if everyone uses it.

The cost of a mutex: acquiring an uncontended mutex is very cheap (one atomic CAS, ~10–30 ns on modern hardware). A contended mutex (another thread holds it) requires a syscall and a context switch — orders of magnitude more expensive. This is why minimizing contention is a major theme in high-performance concurrent programming.

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

long counter = 0;
pthread_mutex_t mu = PTHREAD_MUTEX_INITIALIZER;

void *increment(void *arg) {
    for (int i = 0; i < 1000000; i++) {
        pthread_mutex_lock(&mu);
        counter++;   // protected: only one thread here at a time
        pthread_mutex_unlock(&mu);
    }
    return NULL;
}

int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, increment, NULL);
    pthread_create(&t2, NULL, increment, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("counter = %ld\n", counter); // Always 2000000
    return 0;
}

Deadlock is the second major hazard of concurrent programming. It occurs when two (or more) threads each hold a resource and are each waiting for a resource the other holds — creating a cycle of waiting from which no thread can escape.

The classic example: Thread A holds lock L1 and waits for L2. Thread B holds lock L2 and waits for L1. Neither can proceed. The program hangs forever.

Deadlock requires four conditions simultaneously (Coffman conditions):

1. Mutual exclusion: resources cannot be shared (mutex by definition).
2. Hold and wait: a thread holds a resource while waiting for another.
3. No preemption: resources cannot be forcibly taken from a thread.
4. Circular wait: there is a circular chain of threads waiting for each other.

Breaking any one of these conditions prevents deadlock:

• Lock ordering: always acquire locks in a consistent global order. If everyone takes L1 before L2, no circular wait is possible. This is the most common practical defense.
• Try-lock with timeout: use pthread_mutex_trylock() — if you can't get the lock immediately, release what you hold and retry. Avoids hold-and-wait.
• Lock hierarchy: assign a numeric level to each lock; you may only acquire a lock of higher level than any you currently hold.

Deadlocks are insidious because they don't always manifest immediately. A program might run correctly for weeks before a timing coincidence produces the cycle. Tools like valgrind --tool=helgrind and thread sanitizers can detect potential deadlocks by tracking lock acquisition order.

// Classic deadlock — DO NOT LEAVE IN PRODUCTION
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>

pthread_mutex_t L1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t L2 = PTHREAD_MUTEX_INITIALIZER;

void *thread_a(void *arg) {
    pthread_mutex_lock(&L1);   // grabs L1
    usleep(1000);               // yields, giving B time to grab L2
    pthread_mutex_lock(&L2);   // BLOCKS: B holds L2
    printf("A done\n");
    pthread_mutex_unlock(&L2);
    pthread_mutex_unlock(&L1);
    return NULL;
}

void *thread_b(void *arg) {
    pthread_mutex_lock(&L2);   // grabs L2
    usleep(1000);
    pthread_mutex_lock(&L1);   // BLOCKS: A holds L1
    printf("B done\n");
    pthread_mutex_unlock(&L1);
    pthread_mutex_unlock(&L2);
    return NULL;
}

// FIX: both threads acquire in same order (L1, then L2).

Here is something that shocks most programmers when they first encounter it: even without data races, threads on different CPU cores may not see each other's writes immediately. This is not a bug — it is a fundamental property of modern hardware.

Modern CPUs do not write directly to main memory for every store. They use store buffers, write-combining buffers, and multi-level caches (L1/L2/L3). When Core 0 writes to variable x, the write may sit in Core 0's store buffer or L1 cache for many nanoseconds before becoming visible to Core 1. Similarly, compilers reorder instructions for optimization, and CPUs execute instructions out of order.

The memory model defines the rules for when and how writes by one thread become visible to others. The x86 memory model is relatively strong (called Total Store Order, TSO): stores are seen by all cores in the order they were issued by each core, though stores may be delayed relative to loads. The ARM and RISC-V memory models are much weaker — loads and stores can be reordered arbitrarily unless you explicitly insert memory barriers (also called memory fences).

Memory barriers are hardware instructions that force ordering:

• mfence (x86): full barrier — no load or store may move across it
• dmb sy (ARM): data memory barrier
• fence rw,rw (RISC-V): full fence

In C11/C++11, this is abstracted as atomic operations and memory orderings (memory_order_acquire, memory_order_release, memory_order_seq_cst). You should use these rather than raw fence instructions in user space. In the kernel, you use smp_mb(), smp_rmb(), smp_wmb(), and READ_ONCE()/WRITE_ONCE() macros.

The practical takeaway: if you share data between threads, use either mutexes (which include barriers) or C11 atomics. Never assume that a plain global variable written by one thread is immediately visible to another without synchronization.

// Safe atomic counter using C11 <stdatomic.h>
#include <stdatomic.h>
#include <pthread.h>
#include <stdio.h>

atomic_long counter = 0;

void *increment(void *arg) {
    for (int i = 0; i < 1000000; i++)
        atomic_fetch_add_explicit(&counter, 1, memory_order_relaxed);
        // relaxed: no ordering guarantee, but the add itself is atomic
        // For a shared flag between threads, use acquire/release.
    return NULL;
}

int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, increment, NULL);
    pthread_create(&t2, NULL, increment, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    // memory_order_seq_cst (default) gives full sequentially consistent view
    printf("counter = %ld\n", atomic_load(&counter)); // Always 2000000
    return 0;
}

Let's step back and understand at a deeper level why concurrent programs are so much harder to reason about than sequential ones.

A sequential program with N steps has a single execution trace: step 1, step 2, ..., step N. You can reason about it by reading from top to bottom. A concurrent program with two threads of N steps each has up to C(2N, N) possible interleavings — the number of ways to interleave two sequences of N steps. For N=10, that's 184,756 possible orderings. For N=100, it's approximately 10^58. You cannot test all orderings.

This means:

1. Testing is insufficient. A test that runs 10,000 times without failure does not mean the program is correct — the buggy interleaving may simply be rare. The race window might be 1 nanosecond; you might need to run 10^9 times to hit it.
2. Bugs are non-reproducible. Once you attach a debugger, the timing changes, and the bug disappears — the infamous Heisenbug.
3. Optimization can introduce bugs. A compiler may reorder your code in a way that is valid sequentially but incorrect when another thread is observing the memory.

The field's response to this complexity:

• Formal reasoning: prove your locks protect all shared state, prove no deadlock cycle exists in your lock graph.
• Design patterns: use well-understood patterns (producer-consumer, readers-writer locks, single-writer ownership) that have known correct implementations.
• Minimize shared state: the less shared state you have, the fewer concurrent accesses you need to protect. Immutable data doesn't need protection. Message-passing (like Erlang/Go channels) trades shared memory for explicit communication.
• Tools: ThreadSanitizer, Helgrind, model checkers (TLA+, Spin) can find bugs a human reviewer would miss.

The lesson is not "avoid concurrency" but rather "treat concurrent code with the same rigor you would a mathematical proof." Every shared variable must have a documented owner/protector. Every lock must have a documented invariant.

In the Linux kernel, there is a single abstraction for both processes and threads: task_struct (defined in include/linux/sched.h). This is one of the largest structures in the kernel — over 700 lines of fields — because it stores everything the kernel needs to manage a schedulable entity.

Key fields relevant to threading:

• mm: pointer to mm_struct (the address space). Two tasks with the same mm pointer are threads of the same process.
• stack: the kernel stack for this task (used during syscalls and interrupts)
• pid: the thread ID (what gettid() returns)
• tgid: the thread group ID (what getpid() returns — same for all threads of a process)
• thread_group: a linked list connecting all threads of the same process
• files: pointer to open file descriptors (shared among threads)

clone() is the fundamental primitive. Both fork() and pthread_create() are implemented on top of it:

• fork() calls clone() with flags that cause most resources to be copied (new mm_struct, new files table, etc.)
• pthread_create() (via the NPTL library) calls clone() with CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND | CLONE_THREAD, which causes all these resources to be shared.

You can see this yourself: strace -e clone ./your_threaded_program will show the exact clone call with its flags.

The scheduler in kernel/sched/core.c picks the next task_struct to run on each CPU. It does not know or care whether that task is the "main thread" or a worker thread — they are all equal-status schedulable entities. This uniformity is one of Linux's design strengths.

// Observe clone() flags used by pthreads:
// strace -e trace=clone ./your_program
//
// Typical output for pthread_create:
// clone(child_stack=0x7f..., flags=CLONE_VM|CLONE_FS|
//       CLONE_FILES|CLONE_SIGHAND|CLONE_THREAD|
//       CLONE_SYSVSEM|CLONE_SETTLS|
//       CLONE_PARENT_SETTID|CLONE_CHILD_CLEARTID,
//       ...) = 12345
//
// Typical output for fork():
// clone(child_stack=NULL, flags=SIGCHLD) = 12346
//
// The contrast is stark: fork shares NOTHING (just SIGCHLD
// for parent notification); pthread shares EVERYTHING.
//
// Kernel source: kernel/fork.c, copy_process()

On a single CPU core, true parallelism is impossible — there is only one stream of executed instructions. Yet your system runs dozens or hundreds of threads "simultaneously." This is the magic of context switching: the CPU rapidly switches between threads, giving each a slice of time, fast enough that humans perceive it as simultaneous.

A context switch involves:

1. Saving the running thread's context: PC, stack pointer, all general-purpose registers, floating-point state, and (on modern hardware) vector registers (SSE/AVX) — stored in the thread's task_struct in a thread_struct sub-field.
2. Selecting the next thread: the scheduler runs its algorithm (CFS on Linux — Completely Fair Scheduler) to pick the next task_struct.
3. Restoring the new thread's context: load its saved registers, update the stack pointer, update the page table root (CR3 on x86) if switching to a different process, flush the TLB if needed.
4. Jumping: the CPU begins executing the new thread at its saved PC.

Cost of a context switch:

• Pure register save/restore: ~200-300 ns on modern x86
• With TLB flush (process switch): ~1-5 µs
• With cache warming costs (cache working sets differ): can be much higher

This is why too many threads can hurt performance: if you create 10,000 threads on a 4-core machine, the OS spends enormous time context-switching rather than doing real work. Thread pools (a fixed number of worker threads pulling tasks from a queue) are the standard response.

In the kernel, context switches happen in context_switch() in kernel/sched/core.c, which calls switch_mm() (to update the address space) and switch_to() (the architecture-specific register save/restore, in arch/x86/include/asm/switch_to.h for x86).

// Measure context switch cost experimentally:
// Use two threads and a ping-pong pattern via pipes.
// Each pipe write forces a context switch.

// For a quick estimate on Linux:
//   sudo perf stat -e context-switches ./your_program
// or:
//   /proc/<pid>/status  (voluntary_ctxt_switches, nonvoluntary_ctxt_switches)

// Rough rule of thumb from benchmarks:
//   Thread context switch (same process): ~1-3 µs
//   Process context switch (different mm): ~3-10 µs
//   Goroutine switch (user-space, Go):     ~100 ns