What a scheduler actually decides
Whenever there are more runnable threads/processes than CPU cores — which is essentially always, on any real system — something has to decide who runs next, and for how long. That "something" is the OS scheduler, and its decisions are driven by competing goals that are worth naming explicitly, because scheduling algorithms only make sense as trade-offs between them:
- Throughput — total work completed per unit time.
- Turnaround time — how long a given task takes from arrival to completion.
- Response time — how long until a task starts making visible progress (critical for interactive systems, distinct from turnaround time).
- Fairness — whether every runnable task eventually gets CPU time (the opposite failure is starvation, covered in depth later in this roadmap).
No single algorithm maximizes all four simultaneously — optimizing for throughput (run the shortest job to completion, uninterrupted) actively hurts response time (a long job now blocks everything behind it), which is precisely why real schedulers are compromises.
Preemptive vs. cooperative scheduling
This is the single most load-bearing distinction in this subtopic:
| Preemptive | Cooperative |
|---|
| Who decides when to switch | The scheduler, forcibly, via a timer interrupt | The running task itself, voluntarily |
| Can one task monopolize the CPU? | No — a timer interrupt will eventually reclaim it | Yes — if it never yields, nothing else runs |
| Overhead | Regular timer interrupts + more frequent context switches | None until a yield point |
| Examples | Virtually all modern OS thread schedulers (Linux CFS, Windows) | Coroutines/green threads, cooperative user-space schedulers |
Every mainstream OS schedules kernel threads preemptively: a hardware timer fires at a fixed interval (a tick), interrupts whatever is running, and hands control to the scheduler, which decides whether to let the same task continue or switch to another. This is what guarantees that a single runaway thread can't freeze your entire machine. Coroutines, by contrast (see the previous subtopic), are scheduled cooperatively — which is cheaper per-switch but pushes the responsibility for not hogging the thread onto the code itself.
The mechanics of a context switch
A context switch is the act of saving all state needed to resume a paused task later, and loading the equivalent state for the task that's about to run. Concretely, at minimum this means:
- Save the current task's program counter, stack pointer, and general-purpose registers into that task's control block (a Process Control Block/PCB for a process, a Thread Control Block/TCB for a thread).
- Update scheduler bookkeeping (move the old task to the ready/blocked queue; pick the next task to run).
- Load the next task's saved registers, stack pointer, and program counter.
- If switching between processes, additionally swap the page table / memory-management context — the next task's virtual addresses now need to map to its physical memory, not the previous task's.
That last step is the key asymmetry to remember: a thread-to-thread context switch (same process) skips the page-table swap, because both threads share one address space. That's precisely why thread context switches are meaningfully cheaper than process context switches, even though both save/restore a similar amount of register state.
context_switch(from_task, to_task):
save_registers(from_task.control_block)
from_task.state = READY # or BLOCKED, if it's waiting on I/O
to_task.state = RUNNING
if from_task.process != to_task.process:
switch_page_table(to_task.process) # the expensive extra step
restore_registers(to_task.control_block)
jump_to(to_task.program_counter)
What a context switch actually costs
Direct cost — just the register save/restore and scheduler bookkeeping — is small: empirical measurements on modern Linux put a pinned thread-to-thread switch at roughly 1-2 microseconds. That alone sounds negligible. The real cost is indirect: switching tasks invalidates CPU caches (L1/L2) and the TLB (the cache that maps virtual to physical addresses) for the previous task's working set. When you switch back, that data has to be reloaded from slower memory, one cache miss at a time — and this indirect cost scales with how much memory the tasks actually touch, which is why the "true" cost of excessive context switching is highly workload-dependent and can be far larger than the raw microsecond figure suggests.
This is precisely the economic argument behind async I/O and coroutines: if you can avoid needing a context switch at all (by never blocking a kernel thread in the first place), you avoid both the direct and the indirect cost — which is why a single-threaded event loop handling thousands of concurrent connections can outperform a thread-per-connection model at scale, purely on context-switch overhead.
Scheduling policies you should recognize
| Policy | Idea | Weakness |
|---|
| FCFS (First-Come-First-Served) | Run tasks in arrival order, to completion | A long task blocks everything behind it (convoy effect) |
| SJF / STCF (Shortest Job/Time-to-Completion First) | Always run whichever task finishes soonest | Requires knowing run-time in advance; can starve long tasks |
| Round Robin | Fixed time slice per task, then rotate | Great response time; too-small a slice wastes time on switching overhead |
| MLFQ (Multi-Level Feedback Queue) | Multiple queues by priority; demote CPU-hungry tasks, promote I/O-bound ones | Complex; tunable parameters (quantum length, promotion rules) affect fairness |
| CFS (Completely Fair Scheduler, Linux's default) | Approximates "everyone gets an equal share of CPU time" via a virtual-runtime accounting scheme | Optimizes fairness, not necessarily worst-case latency |
You don't need to reimplement these, but you should be able to reason about why a naive FCFS approach fails interactively (one slow task starves everyone else) and why something like Round Robin or MLFQ exists specifically to fix that — this "policy vs. problem it solves" framing is what interviewers are actually listening for, not algorithm trivia.
Why this matters for interviews
Questions like "why is my thread pool of size 1,000 slower than one of size 16 on a 16-core machine?" or "why does async I/O outperform thread-per-request at scale?" are really questions about context-switch cost and scheduling overhead in disguise. Being able to say "beyond a certain point, adding threads adds scheduling and cache-thrashing overhead without adding real parallelism, because we only have N cores" is the concrete, quantitative version of the concurrency-vs-parallelism distinction from the previous subtopic.
Pitfalls and interview gotchas
- Assuming context switches are "free" because the direct cost is microseconds. The indirect cache/TLB cost is workload-dependent and often dominates — don't quote "1-2 microseconds" as the whole story.
- Conflating process and thread context switches. They are not the same cost — the page-table swap is the differentiator, and it's a common trick question to ask which is cheaper and why.
- Assuming preemption prevents starvation. It doesn't automatically — a preemptive priority scheduler can still starve low-priority tasks indefinitely if high-priority work keeps arriving (this is explored fully in the Deadlock, Livelock & Starvation topic later in this roadmap).
- Thinking a smaller time quantum is always better for responsiveness. Too small a quantum means the CPU spends a larger fraction of its time context-switching rather than doing useful work — there's a real trade-off, not a free lunch.
Where this leads
With scheduling and context-switch mechanics established, Topic 2 — Race Conditions & Critical Sections — asks the natural next question: if a preemptive scheduler can interrupt any thread at any instruction boundary, what happens when two threads are in the middle of reading and writing the same shared memory when that interruption occurs? The answer is a race condition, and everything from that topic onward is about controlling it.