3. Threads and Concurrency

A process bundles two things that need not travel together: a protected resource container and a stream of execution. This chapter separates them, introducing the thread as an independently schedulable execution stream inside a shared address space, examining where threads are implemented and what that costs, and surveying the programming models — pools, implicit threading, fork-join — that make concurrency tractable in practice. Threads are how a single program exploits multiple cores and stays responsive during blocking work, which makes this material the bridge between the process model of Chapter 2 and the scheduling and synchronisation problems of Chapters 4 and 5.

<a id="31-thread-fundamentals"></a>

3.1 Thread Fundamentals

This section establishes why threads exist at all, what precisely distinguishes them from processes, what the kernel must remember about each one, and the distinction between running concurrently and running in parallel.

Motivation for Threads

Theory

Chapter 2 presented the process as a single unit. Look closely and it is two independent things fused together:

1. A resource container: an address space, open file descriptors, a working directory, an identity.
2. An execution stream: a program counter, a register set, a stack, a scheduling state.

Nothing requires these to be one-to-one. A thread is what you get by keeping one resource container and putting several execution streams inside it. All threads of a process share its memory, its file descriptors, and its identity; each has its own program counter, registers, and stack.

Four concrete pressures made this worth doing:

• Responsiveness. A word processor that spell-checks on the same execution stream as the UI freezes while it works. Move the spell-check to another thread and the interface keeps responding. Any long or blocking operation in a single-threaded interactive program stalls everything.
• Parallelism. A single execution stream uses exactly one core. On a 16-core machine, a single-threaded program leaves 94% of the hardware idle. Only multiple execution streams can occupy multiple cores.
• Economy. Creating a thread is roughly 10-100 times cheaper than creating a process, because there is no address space to build, no page tables to construct, and no file descriptor table to copy. Switching between threads of one process is cheaper too, since the address space does not change.
• Sharing without ceremony. Threads share memory by default. Two processes wanting shared data must set up shared memory or copy through the kernel; two threads simply use the same variable.

The cost, paid throughout Chapter 5, is that sharing by default means racing by default. Anything one thread can see, another can modify at an arbitrary moment. Threads trade the process's automatic isolation for speed and sharing, and the programmer must supply the discipline that isolation used to provide for free.

Analogy: a process is an office with one worker; threading it is hiring several workers into the same office. They share the filing cabinets and the whiteboard, which makes collaboration instant — and means two of them writing on the whiteboard at once produces nonsense unless they agree on rules.

Example

   SINGLE-THREADED PROCESS            MULTITHREADED PROCESS

   +----------------------+           +--------------------------------+
   | code | data | files  |           | code | data | files            |  shared
   +----------------------+           +--------------------------------+
   | registers | stack    |           | regs  | regs  | regs  |         |
   +----------------------+           | stack | stack | stack |         |  private
   |     one thread       |           | T1    | T2    | T3    |         |
   +----------------------+           +--------------------------------+

   Effect on a 4-core machine, one CPU-bound job:

   single-threaded:  core0 [########]  core1 ....  core2 ....  core3 ....
                     25% of the machine, elapsed time T

   four threads:     core0 [##]  core1 [##]  core2 [##]  core3 [##]
                     100% of the machine, elapsed time ~T/4

   Effect on responsiveness (one blocking operation):

   single-threaded:  [UI][=== 3s file load, UI frozen ===][UI]
   two threads:      UI  [UI][UI][UI][UI][UI][UI][UI][UI]
                     wkr      [=== 3s file load ===]

import threading, time, urllib.request

URLS = ["https://example.com"] * 8

def fetch(url):
    with urllib.request.urlopen(url, timeout=5) as r:
        return len(r.read())

# Sequential: total time is the SUM of the waits. The CPU is idle throughout.
start = time.perf_counter()
for u in URLS:
    fetch(u)
print(f"sequential: {time.perf_counter() - start:.2f}s")

# Threaded: the waits OVERLAP, so total time approaches the slowest single wait.
start = time.perf_counter()
threads = [threading.Thread(target=fetch, args=(u,)) for u in URLS]
for t in threads: t.start()      # each thread blocks in the kernel independently
for t in threads: t.join()       # wait for all of them to finish
print(f"threaded:   {time.perf_counter() - start:.2f}s")

Key takeaways

• A process fuses a resource container with an execution stream; a thread separates them, allowing many streams per container.
• Threads share code, data, and open files; each keeps its own program counter, registers, and stack.
• They exist for responsiveness, parallelism across cores, cheap creation and switching, and effortless sharing.
• Sharing by default means racing by default — the isolation processes gave for free must now be programmed explicitly.

🧪 Practice

1. Run the example above and explain why the threaded version is faster even in Python, whose GIL prevents parallel bytecode execution.
2. Identify three operations in a text editor that belong on a background thread, and say what would freeze without them.
3. Interview-style: "Would threading speed up a program that computes primes for ten minutes with no I/O, in a language with a global interpreter lock?" Hint: separate waiting-bound work from CPU-bound work, and ask what the lock actually protects.

Thread vs Process

Theory

The differences follow mechanically from one fact: threads of a process share an address space; processes do not. Everything else is a consequence.

Property	Process	Thread
Address space	Private	Shared with sibling threads
Open file descriptors	Private copy	Shared
Global variables	Private	Shared
Stack	One per process	One per thread
Registers, program counter	One set	One set per thread
Creation cost	High (page tables, descriptor table)	Low (a stack and a control block)
Context switch cost	High (address space change, TLB flush)	Low (no address space change)
Communication	Kernel-mediated IPC	Direct memory access
Fault isolation	Strong — a crash kills one process	None — a crash kills every thread
Security boundary	Yes	No

Three consequences are worth stating explicitly, because they drive real design decisions:

• A segmentation fault in any thread terminates the whole process. There is no partial failure. This is why browsers put tabs in separate processes rather than threads: one page's crash must not take down the browser. The same reasoning applies to plugin hosts and to any component you do not fully trust.
• Threads are not a security boundary. A thread can read every byte the process can, including keys held by another thread. Privilege separation requires processes.
• Cheapness is not free. Each thread needs a stack — typically 8 MB of reserved virtual address space on Linux, committed lazily. Ten thousand threads is 80 GB of virtual space and a great deal of kernel bookkeeping, which is why high-concurrency servers use event loops or pools rather than a thread per connection.

The choice between them is therefore mostly a question of trust and coupling: use threads for cooperating parts of one program that must share data quickly; use processes when components must be isolated, may crash independently, or run at different privilege levels.

Example

   THREE PROCESSES                        ONE PROCESS, THREE THREADS

   +--------+ +--------+ +--------+       +---------------------------+
   | space1 | | space2 | | space3 |       |     one address space     |
   | stack  | | stack  | | stack  |       | stack1 | stack2 | stack3  |
   | heap   | | heap   | | heap   |       |       shared heap         |
   | fds    | | fds    | | fds    |       |       shared fds          |
   +--------+ +--------+ +--------+       +---------------------------+
     P1 crash does not affect P2/P3         any crash kills all three

   Sharing a counter:

   processes: shm_open + mmap + semaphore ... then counter++
   threads:   counter++                     (it is simply in scope)

   Switching:

   process -> process : save regs, LOAD NEW PAGE TABLE, flush TLB, refill caches
   thread  -> thread  : save regs                              (same page table)
                        ~5-10x cheaper

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <sys/wait.h>

int shared = 0;               /* one variable; the two models see it differently */

void *thread_fn(void *arg) {
    shared = 100;             /* writes the SAME variable the main thread reads */
    return NULL;
}

int main(void) {
    /* --- threads: shared memory by default --- */
    pthread_t t;
    pthread_create(&t, NULL, thread_fn, NULL);
    pthread_join(t, NULL);
    printf("after thread: shared = %d\n", shared);      /* prints 100 */

    shared = 0;

    /* --- processes: copy-on-write, so the write is private --- */
    if (fork() == 0) {
        shared = 200;         /* writes this process's OWN copy of the page */
        _exit(0);
    }
    wait(NULL);
    printf("after fork:   shared = %d\n", shared);      /* prints 0, not 200 */
    return 0;
}

Key takeaways

• The single defining difference is the shared address space; every other difference follows from it.
• Threads are cheaper to create, switch, and communicate between; processes provide fault and security isolation.
• A fatal fault in one thread destroys the entire process — there is no partial failure among threads.
• Choose processes when components must be isolated or mutually distrusted; choose threads for tightly cooperating work.

🧪 Practice

1. Run the example and explain the two different results in terms of copy-on-write and shared address space.
2. Write a program where one thread dereferences a null pointer, and confirm that all threads die. Repeat with processes and contrast.
3. Interview-style: "Chrome uses a process per tab despite the memory cost. Justify the trade-off." Hint: weigh memory overhead against fault isolation and the security boundary for untrusted code.

Thread Control Block

Theory

Just as a process needs a PCB, each thread needs a record of everything required to suspend and resume it: the Thread Control Block (TCB). The interesting part is not what it contains but what it does not — because the difference from the PCB is exactly the measure of what threads share.

A TCB holds the per-thread state:

Field	Purpose
Thread ID	Identity within the process (and, in Linux, a kernel-wide TID)
Saved registers, PC, stack pointer	Restored on a context switch
Stack base and size	Each thread has its own call stack
Scheduling state and priority	The thread, not the process, is the schedulable unit
Signal mask	Signals can be blocked per thread
Thread-local storage pointer	Per-thread variables (see 3.3)
errno	Per-thread, or concurrent calls would corrupt each other's error codes
Pointer to the owning PCB	Where the shared state lives

Everything else — page tables, open file table, working directory, user ID, signal handlers, heap — lives once in the PCB and is shared by all threads.

Two implications follow:

• The thread is the unit of scheduling; the process is the unit of resource ownership. Modern schedulers (Chapter 4) queue threads, not processes. Linux blurs this deliberately: it schedules task_struct entities, and a thread is simply a task that shares memory and file tables with others via clone() flags.
• errno must be per-thread, or two threads making concurrent system calls would overwrite each other's error status. This is why errno is a macro expanding to a thread-local lookup rather than a global variable, and it is the historical reason many old library functions (strtok, gmtime) have _r reentrant variants.

Analogy: the PCB is the office lease, the filing cabinets, and the company name; the TCB is each worker's own desk, notepad, and current task. Hiring another worker means one more desk, not another office.

Example

   One PCB, three TCBs

   +-------------------------------------------------------+
   |  PCB (process 4412)                                   |
   |    page table base | open files | cwd | uid           |  SHARED
   |    signal handlers | heap | code | globals            |
   +---------+----------------+----------------+-----------+
             |                |                |
      +------+-----+   +------+-----+   +------+-----+
      | TCB tid=1  |   | TCB tid=2  |   | TCB tid=3  |     PRIVATE
      | regs, PC   |   | regs, PC   |   | regs, PC   |
      | stack ptr  |   | stack ptr  |   | stack ptr  |
      | state      |   | state      |   | state      |
      | errno      |   | errno      |   | errno      |
      | sig mask   |   | sig mask   |   | sig mask   |
      | TLS ptr    |   | TLS ptr    |   | TLS ptr    |
      +------------+   +------------+   +------------+

   Address space with three stacks:

   high | stack T1 (8 MB reserved) |
        | guard page               |
        | stack T2                 |
        | guard page               |
        | stack T3                 |
        | ...                      |
        | shared heap              |   <- all threads allocate from here
   low  | shared code and globals  |

/* A teaching-sized TCB: note how short it is compared with a PCB. */
struct tcb {
    tid_t  tid;
    struct context { uint64_t rip, rsp, rbp, rax, rflags; } ctx;  /* private */

    void  *stack_base;
    size_t stack_size;                    /* its own stack, always */

    enum { READY, RUNNING, BLOCKED, TERMINATED } state;
    int    priority;

    sigset_t signal_mask;                 /* per-thread blocking mask ...      */
    int      thread_errno;                /* ... and per-thread error status   */
    void    *tls;                         /* thread-local storage block        */

    struct pcb *process;                  /* EVERYTHING shared lives here:
                                             page tables, fds, cwd, handlers  */
    struct tcb *next_in_queue;
};

ps -eLf | head              # -L shows threads: note LWP column vs PID
cat /proc/self/status | grep Threads
ls /proc/self/task/         # one directory per thread, each with its own stat

Key takeaways

• The TCB stores only per-thread state: registers, stack, scheduling data, signal mask, TLS, and errno.
• All shared state — page tables, file descriptors, working directory, signal handlers, heap — stays in the PCB.
• The thread is the unit of scheduling; the process remains the unit of resource ownership and protection.
• errno and functions like strtok need per-thread storage or reentrant variants precisely because of this split.

🧪 Practice

1. Inspect /proc/self/task/ in a multithreaded program. Which per-thread files exist, and which fields differ between threads?
2. Explain why signal handlers are per-process while signal masks are per-thread. What would break if handlers were per-thread?
3. Interview-style: "Why does strtok have a strtok_r variant?" Hint: ask where strtok keeps its position between calls, and what happens when two threads call it.

Concurrency vs Parallelism

Theory

These words are used interchangeably in casual speech and mean genuinely different things, and the distinction determines whether adding threads will help.

Concurrency is a property of program structure: the program is composed of multiple independently progressing tasks whose execution may interleave. Concurrency exists on a single core — the tasks take turns — and is about dealing with many things at once.

Parallelism is a property of execution: multiple tasks literally execute at the same instant on different hardware. Parallelism requires multiple cores and is about doing many things at once.

Concurrency without parallelism is a single-core time-sharing system, or an event loop. Parallelism without concurrency is a vectorised numeric kernel, where one instruction stream operates on many data elements. Most real systems use both.

The practical consequence is that the two solve different problems:

	Concurrency	Parallelism
Solves	Latency hiding, responsiveness, structuring I/O-bound work	Throughput on CPU-bound work
Needs	One core is enough	Multiple cores
Helps when	Tasks spend time waiting	Tasks spend time computing
Typical tool	Event loop, async/await, blocking threads	Thread pool sized to cores, SIMD, GPU

Adding threads to a CPU-bound problem on one core gains nothing and costs switching overhead. Adding threads to an I/O-bound problem helps enormously even on one core, because the waits overlap.

Amdahl's law bounds what parallelism can achieve: if a fraction S of a program is inherently serial, the maximum speed-up with N processors is 1 / (S + (1 - S) / N). With 5% serial work, the ceiling is 20x no matter how many cores you add. This is why reducing the serial fraction — often lock contention — matters more than adding hardware.

Analogy: a single barista serving a queue while drinks brew is concurrent — one worker, several drinks progressing. Two baristas working simultaneously is parallel. If the shop has one espresso machine, adding baristas stops helping: that machine is the serial fraction.

Example

   CONCURRENT, NOT PARALLEL (one core)

   core0: [A][B][C][A][B][C][A]      tasks interleave; only one runs at a time
   wall clock ------------------->

   PARALLEL (three cores)

   core0: [AAAAAAAA]
   core1: [BBBBBBBB]                 genuinely simultaneous
   core2: [CCCCCCCC]

   CONCURRENT AND PARALLEL (typical: 8 tasks, 3 cores)

   core0: [A][D][G]
   core1: [B][E][H]
   core2: [C][F]

   Amdahl's law: maximum speed-up with a serial fraction S

     S = 0.50 -> ceiling  2x     (even with infinite cores)
     S = 0.10 -> ceiling 10x
     S = 0.05 -> ceiling 20x
     S = 0.01 -> ceiling 100x

   cores:      1     2     4     8    16    64   inf
   S=0.05:   1.0x  1.9x  3.5x  5.9x  9.1x 15.4x  20x   <- flattens hard

import time
from concurrent.futures import ThreadPoolExecutor, ProcessPoolExecutor

def cpu_bound(n):                 # pure computation: needs PARALLELISM
    return sum(i * i for i in range(n))

def io_bound(seconds):            # pure waiting: needs CONCURRENCY only
    time.sleep(seconds)

# I/O-bound work: threads win, even with a GIL, because the waits overlap.
start = time.perf_counter()
with ThreadPoolExecutor(max_workers=8) as ex:
    list(ex.map(io_bound, [1] * 8))
print(f"8 x 1s sleep with threads: {time.perf_counter() - start:.2f}s")  # ~1s

# CPU-bound work: threads do NOT help under a GIL; processes give real parallelism.
N = 3_000_000
start = time.perf_counter()
with ThreadPoolExecutor(max_workers=4) as ex:
    list(ex.map(cpu_bound, [N] * 4))
print(f"cpu-bound, threads:   {time.perf_counter() - start:.2f}s")   # no speed-up

start = time.perf_counter()
with ProcessPoolExecutor(max_workers=4) as ex:
    list(ex.map(cpu_bound, [N] * 4))
print(f"cpu-bound, processes: {time.perf_counter() - start:.2f}s")   # ~4x faster

Key takeaways

• Concurrency is a structural property (tasks interleave); parallelism is an execution property (tasks run simultaneously).
• Concurrency needs only one core and addresses waiting; parallelism needs many cores and addresses computation.
• Adding threads to CPU-bound work on one core costs overhead and gains nothing.
• Amdahl's law caps speed-up by the serial fraction, so reducing contention beats adding cores.

🧪 Practice

1. Run the example on a multi-core machine and explain each of the three timings.
2. A program is 90% parallelisable. Compute the speed-up at 4, 16, and 1024 cores, and state the practical lesson.
3. Interview-style: "Is an event loop like Node.js concurrent, parallel, or both?" Hint: count the execution streams running JavaScript, then ask where the I/O actually happens.

<a id="32-threading-models"></a>

3.2 Threading Models

Threads can be implemented in a user-space library, in the kernel, or both — and the choice determines scheduling, blocking behaviour, and whether threads can use multiple cores.

User-Level Threads

Theory

A thread needs a stack, a saved register set, and something to decide which thread runs next. None of that strictly requires the kernel. User-level threads are implemented entirely inside a library linked into the process: the library allocates stacks from the heap, saves and restores registers itself, and runs its own scheduler. The kernel knows nothing about them — it sees one ordinary single-threaded process.

The advantages come from staying out of the kernel:

• Switching is extremely fast. A switch is a function that saves a few registers and swaps stack pointers: tens of nanoseconds, with no mode transition, no TLB effect, no scheduler involvement. Kernel thread switches cost roughly a hundred times more.
• Creation is cheap — allocate a stack and a small control block. Millions of threads are feasible; kernel threads at that scale are not.
• The scheduling policy is the application's. A library can schedule cooperatively, by priority, or by work-stealing, tuned to the workload rather than to a general-purpose kernel policy.
• It is portable, requiring no kernel support at all.

The two defects are fundamental and both stem from the kernel's ignorance:

• A blocking system call blocks every thread. The kernel sees one process; when that process blocks on read(), all user-level threads stop, even runnable ones. The classic workaround is to make all I/O non-blocking underneath and have the library switch threads on would-block, which is exactly what modern runtimes do.
• No parallelism. One process with one kernel-schedulable entity gets one core, regardless of how many user threads exist.

Historically this made pure user-level threading a dead end. Modern runtimes revived it by pairing it with the kernel: Go's goroutines, Java's virtual threads (Project Loom), Erlang processes, and Rust's async tasks are all user-level threads multiplexed onto a pool of kernel threads, with the runtime intercepting blocking operations. The result keeps the cheapness and adds the parallelism.

Analogy: a manager who subdivides their own work into tasks and switches between them freely. Very efficient, invisible to the company — but the company only ever allocated one desk, so no matter how many tasks exist, one at a time proceeds, and if the manager is stuck waiting on a phone call, everything stops.

Example

   USER-LEVEL THREADS

   user space  | process                                  |
               |  +----+ +----+ +----+ +----+             |
               |  | T1 | | T2 | | T3 | | T4 |  library-   |
               |  +----+ +----+ +----+ +----+  managed    |
               |        thread library + scheduler        |
   ------------+------------------------------------------+
   kernel      |  ONE kernel thread / one schedulable     |
               |  entity -- the kernel sees a plain       |
               |  single-threaded process                 |
   ------------+------------------------------------------+
                          ONE core, always

   The blocking problem:

   T2 calls read() ---> kernel blocks THE PROCESS
   T1, T3, T4 are runnable but cannot run: the library never regains control

/* A minimal cooperative user-level thread library. No kernel involvement. */
#include <ucontext.h>
#define MAX 8

static ucontext_t ctx[MAX];       /* saved register+stack context per thread */
static char stacks[MAX][64 * 1024];
static int  current = 0, count = 0;

void spawn(void (*fn)(void)) {
    getcontext(&ctx[count]);
    ctx[count].uc_stack.ss_sp   = stacks[count];    /* its own stack, from the
                                                       process heap -- no kernel
                                                       allocation involved     */
    ctx[count].uc_stack.ss_size = sizeof stacks[count];
    ctx[count].uc_link          = &ctx[0];
    makecontext(&ctx[count], fn, 0);
    count++;
}

void yield_to_next(void) {
    int prev = current;
    current = (current + 1) % count;   /* the library's own scheduler --
                                          cooperative: threads must call this */
    swapcontext(&ctx[prev], &ctx[current]);   /* ~20 ns, no mode switch */
}

// The modern revival: goroutines are user-level threads that the runtime
// multiplexes onto kernel threads, so blocking and parallelism both work.
func main() {
    for i := 0; i < 100000; i++ {   // 100k goroutines: a few KB each.
        go worker(i)                // 100k OS threads would exhaust the machine.
    }
    // When a goroutine makes a blocking syscall, the Go runtime detaches its
    // kernel thread and schedules other goroutines on another one --
    // exactly the fix pure user-level threading lacked.
}

Key takeaways

• User-level threads live entirely in a library; the kernel sees a single-threaded process.
• Switching and creation are extremely cheap, and the scheduling policy is application-controlled.
• One blocking system call stops every thread, and the process can never use more than one core.
• Modern runtimes (goroutines, virtual threads, async tasks) keep the cheapness by mapping user threads onto kernel threads.

🧪 Practice

1. Extend the ucontext example to three threads that yield in a loop, and measure the switch cost. Compare with pthread switch cost.
2. Explain precisely why a read() from one user-level thread stalls the others, and describe two ways a runtime avoids it.
3. Interview-style: "Why can Go run a million goroutines when a million OS threads would fail?" Hint: compare stack allocation strategy and who does the scheduling.

Kernel-Level Threads

Theory

Kernel-level threads are threads the kernel knows about individually: each has its own kernel-visible entity (in Linux, a task_struct with a TID), sits in the scheduler's run queue on its own, and can be dispatched to any core.

This inverts every property of user-level threads:

• True parallelism. Threads are independently schedulable, so a process with eight threads can occupy eight cores.
• Blocking is contained. When one thread blocks on I/O, the kernel marks that thread blocked and schedules a sibling. The process continues.
• Scheduling is fair across the system, and the kernel can apply priorities, affinity, and real-time policies to individual threads.
• But every operation costs a system call. Creation, destruction, and synchronisation that requires blocking all cross into the kernel.
• And each thread consumes kernel memory — a kernel stack plus a task structure, on the order of 8-16 KB — bounding how many can exist.
• Switching is more expensive than user-level switching, though still cheaper than a process switch since the address space does not change.

Linux implements this with unusual clarity: there is no separate "thread" object. clone() creates a task, and flags decide what it shares with its creator — CLONE_VM shares the address space, CLONE_FILES the descriptor table, CLONE_SIGHAND the signal handlers. fork() is clone() with nothing shared; pthread_create() is clone() with nearly everything shared. Processes and threads are two points on a continuum of sharing.

The practical limit matters: at roughly 8 KB of kernel stack per thread plus scheduler bookkeeping, ten thousand threads is feasible but wasteful, and the scheduler's run queue and cache behaviour degrade. This is why "thread per connection" servers stopped scaling and were replaced by pools and event loops.

Example

   KERNEL-LEVEL THREADS (one-to-one)

   user space  | process                                  |
               |  +----+ +----+ +----+ +----+             |
               |  | T1 | | T2 | | T3 | | T4 |             |
   ------------+----|------|------|------|----------------+
   kernel      |  +-v--+ +-v--+ +-v--+ +-v--+             |
               |  |KT1 | |KT2 | |KT3 | |KT4 |  each in    |
               |  +----+ +----+ +----+ +----+  the run    |
               |     scheduler run queue        queue     |
   ------------+------------------------------------------+
                  core0  core1  core2  core3
                  genuinely parallel; a blocked thread does not stop the others

   Linux: one mechanism, different sharing

   clone(flags):
     fork()            -> no CLONE_VM, no CLONE_FILES     ... a process
     pthread_create()  -> CLONE_VM | CLONE_FILES |
                          CLONE_SIGHAND | CLONE_THREAD    ... a thread
     vfork()           -> CLONE_VM | CLONE_VFORK          ... something between

#define _GNU_SOURCE
#include <stdio.h>
#include <sched.h>
#include <unistd.h>
#include <sys/syscall.h>

int shared_value = 0;
static char child_stack[64 * 1024];

int child_fn(void *arg) {
    /* CLONE_VM was set, so this writes the SAME memory the parent sees. */
    shared_value = 42;
    printf("child  tid=%ld sees shared_value=%d\n",
           syscall(SYS_gettid), shared_value);
    return 0;
}

int main(void) {
    /* Build a thread by choosing what to share -- there is no separate API. */
    clone(child_fn,
          child_stack + sizeof child_stack,   /* stacks grow down: pass the top */
          CLONE_VM |        /* share the address space  -> thread-like */
          CLONE_FILES |     /* share open file descriptors             */
          CLONE_SIGHAND |   /* share signal handlers                   */
          SIGCHLD,
          NULL);
    sleep(1);
    printf("parent tid=%ld sees shared_value=%d\n",
           syscall(SYS_gettid), shared_value);   /* prints 42 */
    return 0;
}

cat /proc/sys/kernel/threads-max     # system-wide ceiling
ulimit -u                            # per-user process/thread limit
ps -eLf | wc -l                      # threads currently alive

Key takeaways

• Kernel-level threads are individually schedulable entities, giving true multi-core parallelism.
• A blocking call suspends only the calling thread; siblings continue running.
• Every thread costs a system call to create and several kilobytes of kernel memory to exist.
• Linux unifies processes and threads under clone(), where flags select what is shared.

🧪 Practice

1. Modify the clone example to omit CLONE_VM and explain the change in observed behaviour.
2. Write a program that creates threads in a loop until failure. How many succeed, and which limit stopped you?
3. Interview-style: "Why did thread-per-connection servers stop scaling around 10,000 connections?" Hint: multiply per-thread kernel memory and stack reservation, then think about scheduler run-queue behaviour.

Many-to-One Model

Theory

The many-to-one model maps many user-level threads onto a single kernel thread. It is pure user-level threading as described above, stated as a mapping.

Thread management happens entirely in user space, so it is fast and portable, and it works on systems with no kernel thread support at all — which is why early Java (the "green threads" of JDK 1.1) and Solaris's original library used it.

Its two flaws are decisive and both follow from the single kernel thread:

• One blocking system call blocks the whole process, because the kernel has exactly one schedulable entity to block.
• No parallelism ever, since one kernel thread occupies one core.

The model therefore only makes sense when either the workload does no blocking I/O, or the runtime converts every blocking operation into a non-blocking one internally. That second option is what modern async runtimes do, which is why the model is worth understanding despite being obsolete in its naive form: a single-threaded event loop (Node.js, Python asyncio on one thread) is many-to-one with the blocking problem engineered away.

Example

   MANY-TO-ONE

        T1   T2   T3   T4        user threads
          \   |   |   /
           \  |   |  /
            +-------+
            |  K1   |            ONE kernel thread
            +-------+
                |
             core0                ONE core, always

   Failure mode:

   T1 blocks on read()  ->  K1 blocks  ->  T2, T3, T4 stall
                                            even though they are runnable

# asyncio: many-to-one done correctly. One kernel thread, many tasks,
# and every blocking operation replaced by an awaitable non-blocking one.
import asyncio

async def worker(n):
    await asyncio.sleep(1)      # yields to the event loop; does NOT block
                                # the kernel thread -- this is the fix that
                                # makes many-to-one viable
    return n * 2

async def main():
    results = await asyncio.gather(*(worker(i) for i in range(1000)))
    print(len(results), "tasks completed in about one second")

asyncio.run(main())

# The trap: one genuinely blocking call ruins it.
async def broken():
    import time
    time.sleep(1)               # BLOCKS the single kernel thread; every other
                                # task stalls -- the many-to-one flaw, live.

Key takeaways

• Many-to-one maps all user threads onto one kernel thread; management is entirely in user space.
• It is fast, portable, and requires no kernel support.
• Any blocking system call stalls every thread, and the process can never exceed one core.
• Modern async runtimes are many-to-one with all blocking operations replaced by non-blocking equivalents.

🧪 Practice

1. Replace asyncio.sleep(1) with time.sleep(1) in the example and measure the total time. Explain the difference.
2. Give two workloads well suited to many-to-one and two that are badly suited, with reasons.
3. Interview-style: "Why is calling a slow synchronous database driver inside an async handler a bug?" Hint: count the kernel threads available to serve the other pending requests.

One-to-One Model

Theory

The one-to-one model maps each user thread to its own kernel thread. It is the model used by Linux (NPTL), Windows, and macOS, and is what pthread_create, std::thread, and java.lang.Thread give you.

Its virtues are the mirror image of many-to-one's flaws: real parallelism across cores, and independent blocking, so a thread waiting on I/O does not impede its siblings. The kernel scheduler handles everything, applying system-wide fairness, priorities, and affinity.

The cost is that threads are now kernel objects:

• Creation requires a system call and kernel memory (a kernel stack plus task structure, ~8-16 KB), plus a user stack whose reserved virtual size defaults to 8 MB on Linux.
• Context switches are kernel operations, roughly 1-5 microseconds plus cache effects.
• The number of threads is bounded by memory and by scheduler efficiency, historically leading systems to cap thread counts.

This makes the model excellent up to hundreds or a few thousand threads and unsuitable for hundreds of thousands. The standard responses are covered in 3.3: use a thread pool sized to the core count for CPU-bound work, and an event loop or a runtime with user-level tasks for very high I/O concurrency.

The tuning knob worth knowing is stack size. Ten thousand threads at the default 8 MB reservation is 80 GB of virtual address space — usually survivable because it is reserved rather than committed, but it can hit limits. Setting a smaller stack via pthread_attr_setstacksize is the standard fix for thread-heavy programs.

Example

   ONE-TO-ONE

        T1   T2   T3   T4        user threads
         |    |    |    |
        K1   K2   K3   K4        one kernel thread each
         |    |    |    |
       core0 core1 core2 core3   true parallelism

   T2 blocks on read():
        T1, T3, T4 keep running -- only K2 is marked BLOCKED

   Cost of one thread:

     kernel stack + task_struct   ~8-16 KB   (committed kernel memory)
     user stack reservation       8 MB       (virtual; committed on use)
     creation                     ~10-30 us  (a system call)
     switch                       ~1-5 us    (plus cache/TLB effects)

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

void *worker(void *arg) {
    long id = (long)arg;
    /* This blocks only THIS thread; the others continue on other cores. */
    sleep(1);
    printf("thread %ld done\n", id);
    return NULL;
}

int main(void) {
    pthread_attr_t attr;
    pthread_attr_init(&attr);
    pthread_attr_setstacksize(&attr, 256 * 1024);   /* 256 KB instead of the
                                                       8 MB default: the fix
                                                       for thread-heavy code  */
    pthread_t t[4];
    for (long i = 0; i < 4; i++)
        pthread_create(&t[i], &attr, worker, (void *)i);   /* a syscall each */

    for (int i = 0; i < 4; i++)
        pthread_join(t[i], NULL);       /* wait; without this, main may exit
                                           and terminate the whole process   */
    pthread_attr_destroy(&attr);
    return 0;
}

ulimit -s                       # default stack size (KB) for the main thread
ps -eLf | grep myprogram        # one row per kernel thread -- the mapping, visible

Key takeaways

• One-to-one gives each user thread its own kernel thread and is the model on Linux, Windows, and macOS.
• It delivers real parallelism and independent blocking, at the cost of a system call and kernel memory per thread.
• Practical limits are hundreds to a few thousand threads, driven by memory and scheduler efficiency.
• Reducing the per-thread stack reservation is the standard remedy for programs that need many threads.

🧪 Practice

1. Create 1,000 threads with the default stack size and again with 64 KB. Compare virtual memory usage via /proc/self/status.
2. Demonstrate independent blocking: one thread sleeps 5 seconds while three others print continuously.
3. Interview-style: "How many threads should a CPU-bound thread pool have on a 16-core machine, and why not more?" Hint: think about what an extra runnable thread adds beyond the core count.

Many-to-Many Model

Theory

The many-to-many model multiplexes M user threads onto N kernel threads, where N is typically close to the core count and M can be far larger. It is an attempt to take the cheapness of user threads and the parallelism of kernel threads simultaneously.

The properties it aims for:

• Cheap, plentiful user threads — create as many as the problem naturally has, not as many as the kernel can afford.
• Real parallelism, since there are several kernel threads to occupy several cores.
• Blocking is survivable: when a user thread blocks, the runtime can move the remaining user threads to another kernel thread, or create one.
• Two-level scheduling: the kernel schedules kernel threads; the runtime schedules user threads onto them.

The two-level model is a common variant that additionally allows a specific user thread to be bound permanently to its own kernel thread, for latency-critical work that must not wait behind the runtime's scheduler.

The difficulty is that two schedulers that cannot see each other make bad decisions together: the runtime may put two runnable user threads on one kernel thread while another sits idle, or the kernel may preempt precisely the kernel thread holding a user-level lock. Solaris and IRIX implemented true many-to-many and later abandoned it — Solaris moved to one-to-one in version 9 — because the complexity was not repaid. Scheduler activations were the research answer: the kernel upcalls the runtime whenever a thread blocks or a core becomes available, so the user scheduler is informed rather than guessing.

The model is now dominant again, in language runtimes rather than operating systems. Go's scheduler (the G-M-P model), Java's virtual threads, Erlang's BEAM, and Rust's Tokio all multiplex enormous numbers of lightweight tasks onto a small pool of kernel threads, with the runtime handling blocking by detaching and replacing kernel threads. The lesson is that many-to-many works well when a single runtime controls both the tasks and the I/O, and poorly when it must guess what the kernel is doing.

Example

   MANY-TO-MANY (M user threads on N kernel threads, M >> N)

     T1  T2  T3  T4  T5  T6  T7  T8      many cheap user threads
       \  |  /      \  |  /   |
        \ | /        \ | /    |
        +----+      +----+  +----+
        | K1 |      | K2 |  | K3 |       N kernel threads, N ~ cores
        +----+      +----+  +----+
          |            |       |
        core0        core1   core2

   When T3 blocks on a syscall:
     K1 is blocked, but the runtime moves T1, T2 to K2/K3
     (or spins up a replacement kernel thread) -- work continues.

   Go's G-M-P scheduler, the same idea named differently:

     G = goroutine (user thread)   M = OS thread   P = logical processor
     each P holds a run queue of Gs and must be attached to an M to run them
     GOMAXPROCS sets the number of Ps -- i.e. the parallelism ceiling
     blocked syscall: M detaches from P; another M picks P up and keeps going

package main

import (
    "fmt"
    "runtime"
    "sync"
)

func main() {
    runtime.GOMAXPROCS(4)     // N: kernel-level parallelism ceiling

    var wg sync.WaitGroup
    for i := 0; i < 100000; i++ {   // M: 100,000 user-level goroutines,
        wg.Add(1)                   // ~2 KB of growable stack each
        go func(n int) {
            defer wg.Done()
            _ = n * n
        }(i)
    }
    wg.Wait()
    // 100k goroutines multiplexed onto ~4 OS threads: neither pure model
    // could do this. One-to-one would need 100k kernel threads;
    // many-to-one would use one core.
    fmt.Println("OS threads in use:", runtime.GOMAXPROCS(0))
}

Key takeaways

• Many-to-many multiplexes M user threads over N kernel threads, aiming for cheap threads plus real parallelism.
• It needs two cooperating schedulers, and their mutual blindness is the source of its difficulty.
• Operating systems largely abandoned it (Solaris moved to one-to-one); scheduler activations were the research fix.
• Language runtimes revived it successfully — goroutines, virtual threads, BEAM, Tokio — because one runtime controls both scheduling and I/O.

🧪 Practice

1. Run the Go example with GOMAXPROCS set to 1 and to your core count, timing both. Explain the difference.
2. Describe a scenario where the kernel preempts a kernel thread holding a user-level lock, and the consequence for the other user threads.
3. Interview-style: "Compare the three models on parallelism, blocking behaviour, and cost, and say when each is appropriate." Hint: build the table yourself; the deciding axis is who knows about the thread.

<a id="33-thread-programming"></a>

3.3 Thread Programming

Knowing what a thread is does not make concurrent programs correct; this section covers the concrete APIs and the patterns that keep thread use manageable at scale.

POSIX Threads

Theory

Pthreads is the POSIX specification for thread creation and synchronisation — an API standard, not an implementation. Linux implements it as NPTL over clone(); other UNIX systems implement it differently. Learning it is worthwhile because nearly every higher-level threading API in C-family languages is a thin layer over it, and its vocabulary is universal.

The core lifecycle has four operations:

• pthread_create(&tid, attr, fn, arg) starts a new thread running fn(arg). It returns immediately; the new thread runs concurrently. The attr parameter sets stack size, detach state, and scheduling policy.
• pthread_join(tid, &ret) blocks until the named thread finishes and collects its return value. This is the thread analogue of waitpid, and it serves the same purpose: without it, the thread's resources are not reclaimed.
• pthread_detach(tid) declares that nobody will join this thread, so its resources are released automatically on exit. A thread that is neither joined nor detached leaks — the thread equivalent of a zombie.
• pthread_exit(ret) terminates the calling thread with a return value; returning from the thread function does the same.

Three rules cause most beginner bugs:

1. The argument is a void *, passed by pointer. Passing the address of a loop variable gives every thread a pointer to the same changing variable — the single most common pthreads mistake.
2. If main returns, the process exits and all threads die, however much work remains. main must join its threads or call pthread_exit itself.
3. Return values must outlive the thread. Returning a pointer to a local variable returns a pointer into a destroyed stack.

Errors do not use errno: pthreads functions return the error number directly, so checking the return value is mandatory.

Example

   Thread lifecycle

   main thread                       worker thread
   -----------                       -------------
   pthread_create() -------------->  starts running fn(arg)
   ... runs concurrently ...         ... runs concurrently ...
   pthread_join()   <== blocks ===   pthread_exit(result) / return result
   receives result, resources freed

   Joinable vs detached

   joinable (default): resources kept until someone joins  -> must join
   detached:           resources freed on exit             -> must not join

   Neither joined nor detached = a leak (the "zombie thread")

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

struct task { int id; long result; };     /* one struct PER THREAD: see below */

void *worker(void *arg) {
    struct task *t = arg;                 /* the void* is cast back here */
    t->result = 0;
    for (int i = 1; i <= 1000; i++)
        t->result += (long)i * t->id;
    return t;                             /* must outlive this thread:
                                             heap or caller-owned, never a local */
}

int main(void) {
    enum { N = 4 };
    pthread_t   tid[N];
    struct task tasks[N];                 /* lives in main's frame, which
                                             outlives the workers because we join */

    for (int i = 0; i < N; i++) {
        tasks[i].id = i + 1;
        /* Pass a pointer to a DISTINCT object per thread.
           Passing &i here would be the classic bug: every thread would see
           the same variable, changing under them. */
        int rc = pthread_create(&tid[i], NULL, worker, &tasks[i]);
        if (rc != 0) {                    /* pthreads returns the error, and
                                             does NOT set errno */
            fprintf(stderr, "pthread_create: %d\n", rc);
            exit(1);
        }
    }

    for (int i = 0; i < N; i++) {
        void *ret;
        pthread_join(tid[i], &ret);       /* blocks; also reclaims resources */
        printf("thread %d returned %ld\n",
               ((struct task *)ret)->id, ((struct task *)ret)->result);
    }
    return 0;                             /* safe: all threads already joined */
}

gcc -pthread prog.c -o prog     # -pthread, not just -lpthread: it sets defines too

Key takeaways

• Pthreads is a specification; create, join, detach, and exit form the lifecycle.
• Every thread must be joined or detached, or its resources leak.
• Pass a distinct object to each thread; sharing a pointer to a loop variable is the classic bug.
• Returning from main terminates the whole process, killing threads that are still running.

🧪 Practice

1. Deliberately pass &i (the loop counter) to each thread and observe the IDs printed. Explain the result precisely.
2. Write a program whose main returns without joining. Show that worker output is truncated, then fix it two different ways.
3. Interview-style: "What is the thread equivalent of a zombie process, and how do you prevent it?" Hint: consider what happens to a joinable thread that nobody ever joins.

Thread Pools

Theory

Creating a thread per unit of work is the obvious design and the wrong one at scale. Each creation costs a system call and kernel memory, the count is unbounded (a traffic spike creates a thread spike), and beyond the core count more threads only add switching overhead and memory pressure without adding throughput.

A thread pool fixes all three by inverting the relationship: create a fixed set of worker threads once at startup, and feed them work through a shared queue. Workers loop forever — take a task, run it, take the next.

The benefits are direct consequences:

• Creation cost is amortised to zero: threads are made once and reused for the program's lifetime.
• Concurrency is bounded, which bounds memory and switching overhead. Under overload the queue grows rather than the thread count — degradation instead of collapse.
• The queue provides natural backpressure if it is bounded, letting the system push back on producers rather than accepting unbounded work.
• Tuning is centralised: one number controls how much of the machine the workload can use.

Sizing follows from the workload type, and getting this wrong is the usual performance bug:

Workload	Recommended size	Reasoning
CPU-bound	Number of cores (or cores + 1)	Extra threads only add switching; no core is idle
I/O-bound	Much larger; approximately cores x (1 + wait/compute)	Threads spend most time blocked, so many are needed to keep cores busy
Mixed	Separate pools per class	One pool sized for both is wrong for each

Two failure modes are worth knowing. Pool starvation/deadlock occurs when a pooled task blocks waiting for another task submitted to the same pool: with all workers blocked, nothing can run the task they wait for. The remedy is to never block on same-pool work, or to use separate pools. And an unbounded queue converts an overload into memory exhaustion — a bounded queue with an explicit rejection policy fails faster and more honestly.

Analogy: a restaurant with four cooks and an order queue, rather than hiring a new cook for every order. On a busy night the queue lengthens; the kitchen does not fill with cooks who cannot reach the stove.

Example

   THREAD POOL

   producers            bounded task queue           fixed workers
   ---------            ------------------           -------------
   submit() --> [T][T][T][T][T][T] --> take() --> [W1] busy
                        ^                          [W2] busy
                        |                          [W3] idle, blocked on take()
                 full -> reject / block            [W4] busy

   Threads are created ONCE. Load shows up as queue depth, not thread count.

   Sizing

   CPU-bound, 8 cores : 8 threads    (more only adds context switches)
   I/O-bound, 8 cores,
     10 ms wait per 1 ms compute     : 8 x (1 + 10/1) = ~88 threads

from concurrent.futures import ThreadPoolExecutor, ProcessPoolExecutor, as_completed
import os

def io_task(n):
    import time; time.sleep(0.1); return n

def cpu_task(n):
    return sum(i * i for i in range(n))

cores = os.cpu_count()

# I/O-bound: many more threads than cores, because they are mostly blocked.
with ThreadPoolExecutor(max_workers=cores * 8) as pool:
    futures = [pool.submit(io_task, i) for i in range(200)]
    for f in as_completed(futures):       # results arrive as they complete,
        _ = f.result()                    # not in submission order

# CPU-bound: processes, sized to cores. More workers than cores gains nothing.
with ProcessPoolExecutor(max_workers=cores) as pool:
    results = list(pool.map(cpu_task, [500_000] * cores))

import java.util.concurrent.*;

// Bounded queue + explicit rejection policy: fail fast instead of running
// out of memory when producers outpace consumers.
ThreadPoolExecutor pool = new ThreadPoolExecutor(
    8, 8,                                    // fixed core and max pool size
    60L, TimeUnit.SECONDS,
    new ArrayBlockingQueue<>(1000),          // BOUNDED: backpressure, not OOM
    new ThreadPoolExecutor.CallerRunsPolicy()// on overflow the submitter runs
);                                           // the task, throttling producers

Key takeaways

• A pool creates a fixed set of reusable workers fed by a shared queue, amortising creation cost.
• Bounded concurrency turns overload into queue growth rather than thread explosion.
• Size CPU-bound pools to the core count and I/O-bound pools much larger, based on the wait-to-compute ratio.
• Use bounded queues with a rejection policy, and never block a pooled task on work submitted to the same pool.

🧪 Practice

1. Benchmark 10,000 short tasks with a thread per task versus a pool of 8. Explain the difference in time and peak memory.
2. Construct a pool deadlock: submit a task that waits on the result of another task in the same single-threaded pool. Then fix it.
3. Interview-style: "Your service has an 8-core box and a 200-thread pool at 100% CPU with poor latency. What do you change?" Hint: ask whether the work is CPU- or I/O-bound, then reason about switching overhead.

Implicit Threading

Theory

Explicit thread management is error-prone: programmers must decide how many threads to create, partition the work, coordinate completion, and get the synchronisation right. Implicit threading moves those decisions from the application to a compiler, runtime, or library. The programmer expresses what may run concurrently; the system decides how many threads to use and when.

The main approaches:

Approach	Programmer writes	System decides
Thread pools	Tasks to submit	Thread count, assignment, reuse
OpenMP	Compiler directives on loops and regions	Team size, loop partitioning, joining
Grand Central Dispatch	Blocks submitted to queues	Threads, cores, priorities
Fork-join frameworks	Recursive task decomposition	Work-stealing across a pool
Parallel collections/streams	A declarative pipeline (.parallelStream())	Splitting, scheduling, merging
async/await	Suspension points in ordinary-looking code	Event loop, continuations, thread mapping

The gain is not only convenience but correctness: the runtime's implementation of task distribution and joining is written once, tested heavily, and reused, rather than reimplemented per project. It also adapts at run time — the same binary uses 4 threads on a laptop and 64 on a server.

The costs are real. Performance becomes less predictable and harder to reason about, since the mapping to threads is hidden. Debugging is harder — a stack trace may show runtime internals rather than your call path. And the abstraction assumes tasks are independent; hidden shared state still races, and implicit threading does nothing to prevent it. The rule of thumb: implicit threading manages parallelism, not synchronisation. You still own every shared variable.

Analogy: hiring a contractor rather than directing each worker. You specify the outcome and constraints; they allocate labour. It goes well when the work is genuinely separable and badly when hidden dependencies exist that only you knew about.

Example

   EXPLICIT                          IMPLICIT

   decide thread count               annotate what is parallelisable
   split the data manually           runtime splits it
   create threads                    runtime manages the pool
   join threads                      runtime joins
   handle partial failures           runtime propagates errors

   for (t = 0; t < 8; t++)           #pragma omp parallel for
     pthread_create(...chunk t...)     for (i = 0; i < n; i++)
   for (t = 0; t < 8; t++)               work(i);
     pthread_join(...)

#include <omp.h>
#include <stdio.h>

int main(void) {
    double data[1000000], total = 0.0;
    for (int i = 0; i < 1000000; i++) data[i] = i * 0.5;

    /* One directive replaces thread creation, partitioning, and joining.
       `reduction(+:total)` gives each thread a private accumulator and
       combines them safely at the end -- the runtime handles the race. */
    #pragma omp parallel for reduction(+:total)
    for (int i = 0; i < 1000000; i++)
        total += data[i] * data[i];

    printf("total=%f using up to %d threads\n", total, omp_get_max_threads());
    return 0;
}
/* compile: gcc -fopenmp prog.c   -- thread count from OMP_NUM_THREADS or cores */

// Parallel streams: declarative, with the same caveat about shared state.
long count = orders.parallelStream()          // runtime splits and schedules
                   .filter(o -> o.total() > 100)
                   .map(Order::customerId)
                   .distinct()
                   .count();

// The trap implicit threading does NOT solve:
List<String> unsafe = new ArrayList<>();
orders.parallelStream()
      .forEach(o -> unsafe.add(o.id()));      // DATA RACE: ArrayList is not
                                              // thread-safe. Parallelism was
                                              // handled; synchronisation was not.

Key takeaways

• Implicit threading lets the programmer express parallelisable work and leaves thread management to the runtime.
• OpenMP, GCD, fork-join frameworks, parallel streams, and async/await are the common realisations.
• It adapts to the machine at run time and removes a large class of thread-management bugs.
• It manages parallelism but not synchronisation: shared mutable state still races and remains the programmer's responsibility.

🧪 Practice

1. Write a serial loop summing a large array, then parallelise it with OpenMP. Measure speed-up against core count.
2. Remove reduction(+:total) from the example and explain the wrong results you get.
3. Interview-style: "When is parallelStream() slower than stream()?" Hint: consider small collections, splitting cost, and whether the operation is genuinely independent.

Fork-Join Parallelism

Theory

Fork-join is a structured pattern for parallelising problems that decompose recursively. A task examines its input: if it is small enough, it computes the answer directly; otherwise it splits the input, forks subtasks to handle the pieces, and joins them to combine the results. Divide and conquer, with the divisions running in parallel.

The structure has a valuable property: parallelism follows the natural recursion of the algorithm, so merge sort, quicksort, tree traversal, matrix multiplication, and prefix sums parallelise almost mechanically. Forks and joins nest properly, so the parallel structure mirrors the call structure and is easy to reason about.

The implementation technique that makes it efficient is work stealing. Each worker keeps a double-ended queue of tasks. It pushes and pops its own tasks from one end (giving good locality — the most recently created task is likely cache-hot), and when it runs out, it steals from the opposite end of a random victim's queue (taking the oldest, largest task, which minimises stealing frequency). The result is automatic load balancing with very little contention, which is why Java's ForkJoinPool, .NET's TPL, Cilk, and Intel TBB all use it.

The one parameter that decides performance is the sequential threshold: the size below which a task computes directly instead of splitting. Too high and there are too few tasks to balance across cores; too low and task-management overhead swamps the actual work. A rule of thumb is to aim for tasks in the range of 10,000 instructions and to produce perhaps 10-100 tasks per core.

Two idioms matter for correctness and speed: fork one side and compute the other in the current thread (avoids creating a task just to wait on it), and join in reverse order of forking (the most recently forked task is likely still on the local queue and cheapest to complete).

Example

   Fork-join on sum(array[0..8])

                        sum[0..8]
                       /         \
              fork    /           \    fork
                sum[0..4]      sum[4..8]
                 /     \         /     \
           sum[0..2] sum[2..4] sum[4..6] sum[6..8]
              |         |         |         |
           (below threshold: compute directly, sequentially)
              \         /         \         /
               join    /           join    /
                sum[0..4]      sum[4..8]
                       \         /
                        join
                        sum[0..8]

   Work stealing

   worker A deque: [t1][t2][t3][t4]      A pops from the BOTTOM (cache-hot)
                    ^                    thieves steal from the TOP (oldest,
                    |                    biggest task -> fewer steals needed)
   worker B (idle) --+ steal

import java.util.concurrent.RecursiveTask;
import java.util.concurrent.ForkJoinPool;

class SumTask extends RecursiveTask<Long> {
    private static final int THRESHOLD = 10_000;   // the tuning knob
    private final long[] data;
    private final int lo, hi;

    SumTask(long[] data, int lo, int hi) { this.data = data; this.lo = lo; this.hi = hi; }

    @Override protected Long compute() {
        if (hi - lo <= THRESHOLD) {                // small enough: do it here
            long sum = 0;
            for (int i = lo; i < hi; i++) sum += data[i];
            return sum;
        }
        int mid = lo + (hi - lo) / 2;
        SumTask left = new SumTask(data, lo, mid);
        left.fork();                               // hand the LEFT half to the pool
        long right = new SumTask(data, mid, hi).compute();  // do the RIGHT half here
                                                   // (never fork both and wait --
                                                   // this thread would idle)
        return right + left.join();                // join the forked one last
    }
}

long[] data = new long[100_000_000];
ForkJoinPool pool = ForkJoinPool.commonPool();     // sized to cores by default
long total = pool.invoke(new SumTask(data, 0, data.length));

Key takeaways

• Fork-join splits a problem recursively, runs the pieces in parallel, and combines the results.
• It suits any divide-and-conquer algorithm, and its parallel structure mirrors the recursion.
• Work-stealing deques give automatic load balancing with low contention and good locality.
• The sequential threshold governs performance: too small drowns in overhead, too large starves cores.

🧪 Practice

1. Implement parallel merge sort with fork-join and compare it with the sequential version on 10 million elements.
2. Vary THRESHOLD across 100, 10,000, and 1,000,000 and plot the runtime. Explain both ends of the curve.
3. Interview-style: "Why compute one half in the current thread instead of forking both?" Hint: count the threads doing useful work in each version while the subtasks run.

Thread Cancellation

Theory

Sometimes a running thread's work becomes unnecessary — a user cancels a search, one of several parallel queries returns first, or the process is shutting down. Thread cancellation is terminating a thread before it finishes on its own, and it is one of the hardest things to do correctly in concurrent programming.

The difficulty is that a thread stopped at an arbitrary point may hold a lock, own a half-updated data structure, or be responsible for freeing a buffer. Killing it there leaves the process permanently broken. Two approaches exist:

• Asynchronous cancellation terminates the target immediately. It is fast and almost always wrong: locks stay held, memory leaks, invariants break. Java deprecated Thread.stop() for precisely this reason.
• Deferred cancellation marks the thread as cancellation-requested; the thread checks periodically at cancellation points and exits cleanly at a safe place, releasing what it holds. This is the default in pthreads and the only responsible option.

In pthreads, cancellation points are functions where the thread may be cancelled — most blocking calls (read, write, sleep, pthread_cond_wait), plus an explicit pthread_testcancel() for compute loops with no blocking calls. Cleanup handlers pushed with pthread_cleanup_push run on cancellation, giving a chance to unlock mutexes and free resources.

Most higher-level environments avoid the mechanism entirely and use cooperative cancellation: a shared flag or token that the worker checks. Java uses interruption (Thread.interrupt() sets a flag and wakes blocking calls with InterruptedException); Go uses context.Context cancellation checked via a channel; .NET uses CancellationToken. All are the same idea: request, do not command.

The universal rules are worth stating plainly: never kill a thread that holds a lock; always give the thread a chance to clean up; and check for cancellation often enough to be responsive but not so often that it costs measurable time.

Analogy: cancellation is asking a surgeon to stop, not switching off the lights in the operating theatre. They must close what they have opened before leaving.

Example

   ASYNCHRONOUS                      DEFERRED / COOPERATIVE

   kill the thread now               set "please stop"
        |                                 |
   thread dies mid-operation          thread notices at a safe point
        |                                 |
   mutex still LOCKED                 releases the mutex
   buffer leaked                      frees the buffer
   invariant broken                   leaves data consistent
   -> process is now broken           -> clean exit

   Where a cooperative check belongs:

   while (!cancelled) {          <- check between units of work,
       process_one_item();          not in the middle of one
   }

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

void cleanup(void *arg) {
    printf("cleanup: releasing resources held by this thread\n");
    pthread_mutex_unlock((pthread_mutex_t *)arg);   /* the lock MUST be released */
}

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

void *worker(void *arg) {
    pthread_setcanceltype(PTHREAD_CANCEL_DEFERRED, NULL);  /* the safe default */

    pthread_mutex_lock(&lock);
    pthread_cleanup_push(cleanup, &lock);   /* runs if cancelled below */

    for (int i = 0; i < 1000000; i++) {
        do_one_unit_of_work(i);
        pthread_testcancel();               /* an explicit cancellation point:
                                               a pure compute loop has none  */
    }

    pthread_cleanup_pop(1);                 /* 1 = also run it on normal exit */
    return NULL;
}

// The modern idiom: cancellation as a value the callee checks.
func worker(ctx context.Context, items []Item) error {
    for _, item := range items {
        select {
        case <-ctx.Done():          // cancellation requested
            return ctx.Err()        // return cleanly; defers still run
        default:
        }
        if err := process(item); err != nil {   // one whole unit of work,
            return err                          // never interrupted midway
        }
    }
    return nil
}

ctx, cancel := context.WithTimeout(context.Background(), 5*time.Second)
defer cancel()                      // always release the context

Key takeaways

• Asynchronous cancellation stops a thread immediately and typically leaves locks held and invariants broken.
• Deferred cancellation sets a request that the thread honours at safe cancellation points.
• Cleanup handlers (or defer/finally) must release locks and resources on the cancellation path.
• Modern APIs use cooperative tokens — interruption, context.Context, CancellationToken — which are requests, not commands.

🧪 Practice

1. Write a thread that acquires a mutex and is cancelled asynchronously without a cleanup handler. Show that another thread then deadlocks.
2. Convert a long compute loop to support cooperative cancellation, and measure the cost of checking every iteration versus every 1,000.
3. Interview-style: "Why was Thread.stop() deprecated in Java?" Hint: think about a monitor held during an update to a shared collection.

Thread-Local Storage

Theory

Threads share everything by default, which is usually what you want and occasionally exactly what you do not. Some state is conceptually per-thread: a request ID for logging, a database connection, a random number generator's seed, a scratch buffer, a transaction context. Passing it explicitly through every function signature pollutes the code; making it global creates a race.

Thread-local storage (TLS) solves this: one declared variable, but each thread gets its own independent instance. Syntactically it looks like a global; semantically it behaves like a per-thread variable that persists across function calls within a thread.

The mechanism is straightforward — the TCB holds a pointer to a per-thread block, and accessing a TLS variable indexes off that pointer — which is why access is nearly as fast as a normal global (typically one extra register-relative indirection).

The canonical uses:

• Context propagation without plumbing: a request or trace ID available to every logging call in the call stack.
• Per-thread caches and buffers: a scratch buffer reused across calls, avoiding both allocation and contention.
• Making non-reentrant APIs safe: errno is thread-local for exactly this reason; so is strtok_r's explicit state, and the reason strtok itself is not thread-safe.
• Per-thread connections: one database connection per worker thread, avoiding a shared pool lock.

The hazards are real and worth respecting. TLS is hidden state: functions depend on values not visible in their signatures, which makes reasoning and testing harder. It interacts badly with thread pools, because a pooled thread outlives the task that set the value — failing to clear TLS at task boundaries leaks one request's context into the next, a genuine correctness and security bug. And it is incompatible with task-based runtimes where a task may migrate between threads mid-execution: a coroutine that suspends and resumes on a different thread sees different TLS. This is why Java added ScopedValue and why Go deliberately has no goroutine-local storage, recommending explicit context.Context instead.

Example

   ONE DECLARATION, N INSTANCES

   __thread int counter;          declared once

   thread 1 TLS block: counter = 5
   thread 2 TLS block: counter = 99      independent storage
   thread 3 TLS block: counter = 0

   Access path:

   TCB -> tls_pointer -> [ counter | request_id | buffer ... ]
                            ^
                            one indirection: nearly as fast as a global

   The thread-pool hazard:

   task A runs on worker 3, sets request_id = "abc"
   task A finishes; worker 3 is REUSED
   task B runs on worker 3, logs before setting anything
        -> logs "abc"    <- another request's identity. Clear TLS at boundaries.

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

/* C11 / GCC thread-local: one declaration, one instance per thread. */
static __thread int  call_count = 0;
static __thread char scratch[256];      /* a per-thread buffer: no contention,
                                           no allocation per call */

void do_work(void) {
    call_count++;                       /* no lock needed: nobody else can see it */
    snprintf(scratch, sizeof scratch, "thread work #%d", call_count);
}

void *worker(void *arg) {
    for (int i = 0; i < 3; i++) do_work();
    printf("thread %ld: call_count=%d (%s)\n", (long)arg, call_count, scratch);
    return NULL;                        /* each thread prints 3, never 6 or 9 */
}

int main(void) {
    pthread_t t[3];
    for (long i = 0; i < 3; i++) pthread_create(&t[i], NULL, worker, (void *)i);
    for (int i = 0; i < 3; i++) pthread_join(t[i], NULL);
    return 0;
}

// The pooled-thread trap, and the fix.
public class RequestContext {
    private static final ThreadLocal<String> REQUEST_ID = new ThreadLocal<>();

    public static void handle(Request req) {
        REQUEST_ID.set(req.id());
        try {
            process(req);          // every logging call downstream can read it
                                   // without it appearing in any signature
        } finally {
            REQUEST_ID.remove();   // MANDATORY in a pool: the thread is reused,
                                   // and a stale value leaks into the next task
        }
    }
}

Key takeaways

• Thread-local storage gives each thread its own instance of a variable that is declared once.
• It is used for context propagation, per-thread caches and connections, and making non-reentrant APIs safe.
• Access costs roughly one extra indirection through the thread's TLS block.
• In thread pools, always clear thread-locals at task boundaries; in task-based runtimes that migrate work between threads, prefer explicit context objects.

🧪 Practice

1. Run the C example and explain why each thread prints 3. Remove __thread and explain the new output.
2. Demonstrate the pool leak: set a ThreadLocal in one pooled task, omit remove(), and read it from a later task on the same worker.
3. Interview-style: "Why does Go provide no goroutine-local storage?" Hint: consider how many goroutines exist, and what happens when work migrates between OS threads.

---

<a id="4-cpu-scheduling"></a>