2.3 — Threads & Scheduling

2.2 gave us the process — a running program with its own private memory. Processes are wonderfully isolated, but that isolation has a price: they can't easily share data (each has a separate address space), and creating or switching between them is relatively expensive. Yet a huge amount of software wants concurrency within one program: a web server juggling a thousand connections, a game updating physics while rendering, a spreadsheet recalculating while you type. Spawning a whole process per task would be wasteful. The answer is the thread — a lighter-weight strand of execution that lives inside a process and shares its memory. This chapter builds the thread, distinguishes the two words everyone confuses (concurrency vs parallelism), and then tackles the question that a thread raises and a process raised before it: with far more threads than CPU cores, who decides which one runs right now? That is the scheduler, and its choices shape whether your machine feels instant or sluggish.

1. The thread: concurrency that shares memory

Recall a process bundles two different things: a container of resources (its address space, open files, PID) and a strand of execution (the CPU registers and program counter marching through instructions). A thread is that second thing pulled out and multiplied. A process can contain several threads, each an independent strand of execution — its own program counter, its own registers, its own stack — but all sharing the one process's memory: the same code, the same globals, the same heap.

That shared memory is the entire point, and the entire danger. Two threads in the same process can pass data by simply reading and writing the same variable — no copying, no messaging, instant and free. (Two separate processes can't; they'd need explicit inter-process communication.) This makes threads the natural tool when tasks must cooperate closely on shared state. But — and this is the theme of the next chapter — because they share memory, two threads touching the same data at the same time can corrupt it, which is the whole problem of concurrency (Chapter 2.4).

Here's the precise division of what threads share versus own:

Figure 1 — Threads within a process. Every thread has its own execution state (stack, registers, program counter) but shares the process's code, globals, and heap. Sharing memory is what makes threads powerful — and hazardous.

Because a thread carries so much less than a process (no new address space — just a fresh stack and register set), creating one and switching between two threads of the same process is cheaper than the process equivalent (no need to swap the entire memory map). This is why threads are sometimes called "lightweight processes." A thread has the same states as a process — Ready, Running, Blocked — and the same PCB-style bookkeeping, just less of it.

2. Concurrency vs parallelism — the distinction everyone blurs

Two words get used interchangeably and mean genuinely different things; keeping them straight is a mark of a careful engineer.

• Concurrency is dealing with many things at once — a structure where multiple tasks are in progress over the same period, making progress by interleaving. A single-core CPU rapidly switching between ten threads is concurrent: at any given instant only one runs, but over a second all ten advance. Concurrency is about composition and structure — how you organise independent tasks.
• Parallelism is doing many things at once — literally, physically, at the same instant, which requires multiple execution units (multiple CPU cores). Four cores each running a thread is parallelism: four instructions genuinely execute in the same nanosecond.

The classic framing (Rob Pike's): concurrency is about dealing with lots of things at once; parallelism is about doing lots of things at once. You can have concurrency without parallelism (one core, many interleaved threads — the whole pre-multicore era, and still how a Node event loop works). You can have parallelism only if the hardware has multiple cores. And concurrency is what enables parallelism: you first structure work into independent concurrent tasks, and then a multicore machine can run them in parallel. The reason this matters practically: some problems are limited by waiting (network, disk — helped by concurrency, keeping the CPU busy with other tasks while one waits), and others by computation (number-crunching — helped only by parallelism, actual extra cores). Diagnosing which kind you have tells you whether more threads will even help.

Figure 2 — Concurrency vs parallelism. Concurrency interleaves tasks over time (progress without simultaneity); parallelism runs them literally at once on separate cores. Concurrency is structure; parallelism is execution.

3. The scheduler: deciding who runs next

Whether you have ten processes or a hundred threads, they vastly outnumber your cores, so most are Ready and waiting. Something must repeatedly answer: of everything that could run, which one gets a core next, and for how long? That something is the scheduler, a core piece of the kernel, and it runs constantly — thousands of times a second.

First, a fundamental choice about when the scheduler is allowed to take the CPU away from a running task:

• Cooperative scheduling: a task runs until it voluntarily yields (or blocks on I/O). Simple, but one selfish or buggy task that never yields freezes the entire system. (Early Windows and classic Mac OS worked this way — one hung app could lock the whole machine.)
• Preemptive scheduling: the kernel forcibly interrupts a running task after its time is up, using a hardware timer interrupt — a clock chip that fires periodically, yanking control into the kernel no matter what the task is doing, so the scheduler can pick someone else. This guarantees no task can monopolise the CPU, which is why every modern general-purpose OS is preemptive. The slice of time a task gets before it can be preempted is its time quantum (or time slice), typically a few to tens of milliseconds.

The mechanism connects straight back to 2.2: the timer interrupt fires → the kernel runs the scheduler → the scheduler picks a new task → a context switch saves the old task's state and loads the new one's. The scheduler is the decision; the context switch is the execution of that decision.

What the scheduler is trying to optimise

There's no single "best" schedule, because the goals conflict:

• Throughput — total work completed per unit time (favours long uninterrupted runs, fewer context switches).
• Latency / responsiveness — how quickly a task that becomes ready gets to run (favours short slices and quick preemption, so your keystroke registers instantly).
• Fairness — every task gets a reasonable share; none starves.

These pull against each other: maximising throughput means switching less (long slices), but responsiveness means switching more (short slices). A good scheduler balances them, and different systems weight them differently — a desktop prizes responsiveness (you must feel the UI react), a batch server prizes throughput, a real-time system prizes guaranteed latency bounds above all.

A ladder of scheduling algorithms

The ideas built on each other historically:

• First-Come, First-Served (FCFS): run tasks in arrival order, to completion. Simple but terrible for responsiveness — one long task blocks everyone behind it (the "convoy effect," like one loaded shopper holding up a single checkout line).
• Round-Robin: give each ready task one time quantum in turn, cycling endlessly. Fair and responsive; the quantum size is the tuning knob (too long → poor responsiveness; too short → context-switch overhead dominates).
• Priority scheduling: each task has a priority; the scheduler always runs the highest-priority ready task. Essential (a video call should beat a background backup) but risks starvation — a low-priority task might never run if higher ones keep arriving. The fix is aging: gradually raise a waiting task's priority so it eventually runs.
• Multi-Level Feedback Queue (MLFQ): several priority queues; tasks that use their whole quantum (CPU-bound) drift to lower-priority queues, while tasks that yield early (I/O-bound, interactive) stay high. This automatically favours interactive, responsive tasks without being told which is which — a beautiful self-tuning idea that shaped decades of schedulers.

Linux's CFS — fairness as the organising principle

For years, Linux used the Completely Fair Scheduler (CFS), and its core idea is elegant enough to carry as a mental model. Instead of fixed time slices, CFS tracks each task's virtual runtime (vruntime) — essentially, how much CPU time it has already received. The rule: always run the task with the lowest vruntime — the one most "starved" of CPU so far. As a task runs, its vruntime climbs; once it exceeds another ready task's, the scheduler switches. Over time everyone converges to an equal share — "completely fair." To pick the lowest-vruntime task instantly among thousands, CFS keeps them in a red-black tree, ordered by vruntime. (A tree here is a data structure that keeps items sorted by branching: each item has a smaller-value branch and a larger-value branch, so finding or inserting means following a path down rather than scanning everything. "Self-balancing" means it automatically keeps itself short and even, so those paths never grow long. The practical consequence: with thousands of tasks, the smallest vruntime is always the leftmost item — found immediately — and inserting a task costs only a handful of steps rather than a full scan. Chapter 4.13 builds these trees properly.) That's why the scheduler can re-pick a winner thousands of times a second without the cost growing as tasks pile up. (Recent kernels have moved to a successor called EEVDF, refining the same fairness-with-latency-bounds goal — but "run whoever's had the least CPU" remains the intuition worth keeping.)

Priorities still exist, via the Unix nice value (−20 = highest priority, +19 = lowest, "nice" because a high nice value means you're being nice to others by taking less CPU). Under CFS, niceness weights how fast a task's vruntime accrues: a high-priority task's vruntime rises slower, so it's chosen more often — priority expressed as a fairness weight rather than absolute precedence. Separately, true real-time scheduling classes exist for tasks needing guaranteed timing (audio, industrial control), which preempt all normal tasks — because for them, a missed deadline is a failure, not a slowdown.

4. The expert lens

More threads is not more speed — and often the opposite. The naïve intuition "add threads to go faster" fails on two rocks. First, if your work is CPU-bound, you can only truly run as many threads in parallel as you have cores; beyond that, extra threads just concurrently time-slice the same cores, adding context-switch overhead and cache pollution (1.6) for zero extra throughput — performance can drop. Second, threads sharing data must coordinate (locks — Chapter 2.4), and that coordination serialises them; past a point, adding threads adds contention, not progress. The right thread count depends on the nature of the work: roughly "number of cores" for CPU-bound tasks, but potentially far more for I/O-bound tasks (where threads spend most time Blocked, not competing for CPU). Measuring which regime you're in beats guessing.

This is exactly why async I/O exists. For a server handling 10,000 mostly-idle connections (waiting on network — I/O-bound), the thread-per-connection model means 10,000 threads, mostly Blocked, but still costing memory (each needs a stack) and context-switch churn whenever they wake. The alternative — Node.js's model (Part 3) — is a single thread with an event loop that multiplexes all 10,000 connections, doing a tiny bit of work for whichever is ready and never blocking. It trades away multi-core parallelism (for that one loop) to eliminate the per-connection thread cost, which is the right trade when the bottleneck is waiting, not computing. Understanding the scheduler is what lets you see why that trade wins for I/O-bound workloads and loses for CPU-bound ones.

Priority inversion — when priorities backfire. A subtle, famous failure: a high-priority task waits for a lock held by a low-priority task, but the low-priority task never gets scheduled to release it (a medium-priority task keeps preempting it) — so the high-priority task is effectively blocked by a medium one, its priority "inverted." This nearly killed NASA's 1997 Mars Pathfinder mission (its computer kept resetting) until engineers remotely enabled priority inheritance (temporarily boosting the lock-holder's priority so it can finish and release). It's a permanent lesson that priorities interact with locking in non-obvious ways — a recurring hazard whenever scheduling meets shared resources.

The scheduler is why your OS feels the way it does. Every judgment about responsiveness — whether your typing lags when a build runs, whether music stutters under load — is the scheduler balancing throughput against latency. It's also why "set this process to high priority" is a blunt tool that can hurt (starving the very services your task depends on), and why real-time audio/video needs special scheduling classes rather than just "more priority." The scheduler is invisible when it works and maddening when it doesn't.

Next chapter: threads share memory — which we called both their power and their peril. When two threads read and write the same data at the same time, the results can be silently, catastrophically wrong. Chapter 2.4 confronts the race condition and builds the tools — mutexes, semaphores, condition variables — that make shared-memory concurrency correct, along with the deadlocks those tools can cause.

Recall

• A thread is a strand of execution inside a process: its own stack, registers, and program counter, but sharing the process's code, globals, and heap. Sharing memory makes threads fast to coordinate — and dangerous (next chapter). Threads are cheaper to create/switch than processes.
• Concurrency = structuring work as interleaved tasks making progress over a period (possible on one core); parallelism = literally executing tasks at the same instant (needs multiple cores). Concurrency is structure and enables parallelism.
• The scheduler decides which ready task runs next and for how long. Modern OSes are preemptive (a timer interrupt lets the kernel forcibly switch after a time quantum), balancing conflicting goals: throughput, latency, fairness.
• Algorithm ladder: FCFS → Round-Robin → Priority (risks starvation, fixed by aging) → MLFQ (auto-favours interactive tasks). Linux's CFS runs the lowest-vruntime task (least CPU so far) via a red-black tree; nice values weight the fairness.
• More threads ≠ more speed: CPU-bound work scales only to core count (extra threads add context-switch overhead + contention); I/O-bound work tolerates many threads (mostly Blocked) — which is exactly why single-threaded async I/O wins for high-connection servers.

Self-test: What do threads of one process share, and what does each own? State the difference between concurrency and parallelism in one sentence each. What makes a scheduler preemptive, and what hardware enables it? What does Linux's CFS optimise, and how does it pick the next task? Why can adding threads to a CPU-bound program make it slower?

Quiz Bank

FoundationalWhat is a thread, and how does it differ from a process?

A thread is an independent strand of execution within a process — it has its own stack, registers, and program counter, but shares the process's memory (code, globals, heap) with the other threads in that process. A process has its own isolated address space; threads inside it do not. Consequences: threads can share data directly (fast, but requires synchronization to be safe), and are cheaper to create and context-switch than processes (no address-space swap). Threads are sometimes called "lightweight processes."

FoundationalWhat exactly do threads of the same process share, and what does each thread have of its own?

Shared across all threads of a process: the text/code segment, global/static data, and the heap (so an object one thread allocates, another can access via a shared pointer), plus open file descriptors. Private to each thread: its own stack (local variables, call frames), its CPU registers, and its program counter. This split is why passing data between threads is trivial (write a shared variable) but hazardous (two threads writing it concurrently corrupt it — Chapter 2.4).

AppliedExplain concurrency vs parallelism with an example of each.

Concurrency is structuring a program so multiple tasks are in progress over the same period, interleaving — e.g. a single-core CPU rapidly switching between handling ten network requests: only one runs at any instant, but all ten advance over a second. Parallelism is physically executing multiple tasks at the same instant, requiring multiple cores — e.g. a 4-core CPU running four threads simultaneously to crunch a large matrix. Concurrency is about dealing with many things (structure); parallelism is about doing many at once (execution). Concurrency can exist without parallelism (one core), and it's what enables parallelism when cores are available.

AppliedWhat is the difference between preemptive and cooperative scheduling, and what makes preemption possible?

Under cooperative scheduling, a running task keeps the CPU until it voluntarily yields or blocks — so one task that never yields can freeze the whole system. Under preemptive scheduling, the kernel can forcibly take the CPU from a running task after its time quantum expires, guaranteeing no task monopolises the CPU. Preemption is made possible by a hardware timer interrupt: a clock periodically forces control into the kernel regardless of what the task is doing, letting the scheduler run and switch tasks. All modern general-purpose OSes are preemptive.

InterviewWhat does Linux's CFS scheduler do, and how does it choose the next task?

The Completely Fair Scheduler aims to give every task an equal share of CPU over time. It tracks each task's virtual runtime (vruntime) — roughly how much CPU it has already consumed — and always runs the task with the lowest vruntime (the most "starved"). As a task runs, its vruntime rises until another ready task's is lower, triggering a switch; over time shares equalise. It stores runnable tasks in a red-black tree keyed by vruntime, so the next task (leftmost node) is found in O(\log n). nice values weight how fast vruntime accrues, expressing priority as a fairness weight. (Newer kernels use EEVDF, refining the same idea with explicit latency targets.)

InterviewWhy doesn't adding more threads always make a program faster?

Two reasons. (1) CPU-bound work can only truly run in parallel up to the number of cores; beyond that, extra threads merely time-slice the same cores, adding context-switch overhead and cache pollution for no extra throughput — it can get slower. (2) Contention: threads sharing data must synchronize (locks), which serialises them; past a point, more threads mean more lock contention, not more progress. The ideal count depends on workload: ~core-count for CPU-bound tasks, but potentially many more for I/O-bound tasks (which spend most time Blocked, not competing for CPU). Measure to find the regime rather than assuming more threads help.

StaffDescribe priority inversion, why it's dangerous, and how it's mitigated.

Priority inversion occurs when a high-priority task blocks waiting for a resource (lock) held by a low-priority task, but the low-priority task can't run to release it because medium-priority tasks keep preempting it — so effectively a medium-priority task is blocking a high-priority one, inverting the intended order. It's dangerous in real-time/safety systems because a critical task can miss its deadline indefinitely (it famously caused NASA's Mars Pathfinder to keep resetting in 1997). Mitigations: priority inheritance (temporarily raise the lock-holder's priority to that of the highest waiter so it can finish and release quickly) or priority-ceiling protocols (a lock confers a preset high priority to whoever holds it). The general lesson: scheduling priorities and shared-resource locking interact in non-obvious, sometimes catastrophic ways.

Flashcards

FlashThread vs process (memory)

Threads share the process's code/globals/heap but each has its own stack + registers; processes have fully isolated address spaces.

FlashConcurrency vs parallelism

Concurrency = dealing with many tasks by interleaving (possible on 1 core). Parallelism = doing many at the same instant (needs multiple cores).

FlashPreemptive scheduling enabler

A hardware timer interrupt periodically forces control to the kernel so the scheduler can take the CPU from a running task after its time quantum.

FlashThree conflicting scheduler goals

Throughput (work/time), latency/responsiveness (time-to-run), fairness (no starvation).

FlashCFS core rule

Always run the task with the lowest virtual runtime (least CPU received so far); nice values weight how fast vruntime accrues.

FlashStarvation and its fix

A task never getting to run under priority scheduling; fixed by aging (gradually raising a waiting task's priority).

FlashIdeal thread count rule of thumb

~number of cores for CPU-bound work; can be many more for I/O-bound work (threads mostly Blocked).

Scenario Drill

DrillYour image-processing service resizes photos (pure CPU work). It runs on an 8-core machine. A colleague sets it to use a pool of 200 threads 'to go faster,' but throughput drops versus 16 threads. Explain what's happening and how to choose the pool size.

The work is CPU-bound, so real speedup comes only from parallelism, which is capped at the 8 cores. With 200 threads, at most 8 run at any instant; the other ~192 are Ready, and the scheduler constantly context-switches among them, each switch costing pure overhead plus cache pollution (1.6) — the incoming thread's pixel data isn't in cache, so it stalls refilling. There's also memory pressure (200 stacks) and, if the threads share any structures, lock contention. Net: more threads add coordination cost without adding parallelism, so throughput falls — the classic "too many threads" anti-pattern. How to size it: for CPU-bound work, a pool of about N or N+1 threads for N cores (here ~8–9) maximises parallelism while minimising switching — the small extra covers occasional blocking.

If the task has some I/O (reading/writing image files), a modest bump above core count can help hide that I/O latency, but 200 is far past the useful point. The method: benchmark throughput across pool sizes (8, 12, 16, 24…) and pick the plateau; don't guess. Contrast with an I/O-bound server, where hundreds of mostly-Blocked threads can make sense — the right number is dictated by whether the bottleneck is the CPU or the wait.