// the one-minute version
When more processes are ready than there are CPUs, the scheduler decides who runs next. Algorithms optimize different goals — short waiting time, high throughput, fairness — and these conflict, so there's no single best one. The big four: FCFS (simple, convoy effect), SJF (optimal average wait, needs to predict the future), priority (important first, risks starvation), and round robin (fair time slices, the basis of interactive systems). Real systems combine them in a multilevel feedback queue.
Your laptop has maybe 8 cores but hundreds of ready threads. Something decides, thousands of times a second, which gets a core right now. That something is the CPU scheduler — the difference between a snappy machine and a sluggish one.
01 The CPU–I/O burst cycle
Programs alternate between bursts of computation (CPU bursts) and waiting for I/O (I/O bursts). Some programs are CPU-bound (long compute bursts — a video encoder); others are I/O-bound (short bursts, lots of waiting — a text editor). A good scheduler mixes them so the CPU and devices both stay busy: while the CPU-bound job computes, the I/O-bound jobs use the disk and network.
02 When scheduling happens
The scheduler runs when a process changes state — finishes, blocks on I/O, gets preempted by the timer, or a new process arrives. If it can yank a running process off the CPU before it's done, scheduling is preemptive; if a process keeps the CPU until it voluntarily yields, it's non-preemptive. Modern interactive systems are preemptive — that's the timer interrupt's job. The small piece of code that actually hands the CPU to the chosen process is the dispatcher; the time it takes is dispatch latency.
03 What we're optimizing for
| Criterion | Meaning | Want |
|---|---|---|
| CPU utilization | fraction of time the CPU is busy | high |
| Throughput | processes finished per unit time | high |
| Turnaround time | arrival to completion | low |
| Waiting time | time in the ready queue | low |
| Response time | request to first response | low (interactive) |
04 The classic algorithms
FCFS — first come, first served
Run in arrival order. Simple and fair-by-arrival, but one long job makes everyone behind it wait — the convoy effect. Non-preemptive.
SJF / SRTF — shortest job first
Run the smallest next burst (preemptive version: shortest remaining time first). Provably the lowest average waiting time — but you can't truly know burst lengths, so they're estimated. Can starve long jobs.
Priority
Each process has a priority; highest runs first. Flexible, but low-priority jobs may starve forever. Fix: aging — slowly raise a waiting job's priority.
Round robin
Give each ready process a fixed time slice (quantum), then rotate. Fair and responsive — the heart of time-sharing.
05 Estimating the next burst
Since SJF needs the next burst length, schedulers estimate it from history using an exponential average: the predicted next burst is a weighted blend of the last prediction and the last actual burst. Recent behavior dominates, so a process that's been short stays predicted-short. It's imperfect, which is why pure SJF is rare and adaptive schemes win.
06 Multilevel feedback queues
Real systems use several policies at once. A multilevel queue splits processes into classes (interactive, batch, background), each with its own queue and policy. A multilevel feedback queue goes further and moves processes between queues by behavior: a job that uses its whole slice drops to a lower-priority, longer-slice queue; an interactive job that blocks quickly stays high. This favors short, responsive tasks automatically — without knowing burst lengths in advance.
07 Scheduling on multiple cores
With many cores: one shared ready queue, or one per core? Keeping a process on the same core (processor affinity) preserves its warm cache; load balancing moves work off busy cores onto idle ones. The two tug against each other — migrating balances load but throws away cache warmth. Real schedulers (like Linux's CFS, Chapter 20) juggle both, plus NUMA memory locality.
common catches & gotchas
- SJF needs the future — It's optimal only because it assumes known burst lengths. In reality you estimate, and the estimate can be wrong — so pure SJF is theoretical.
- Convoy effect — Under FCFS, one CPU-bound job stalls all the short jobs behind it, wrecking average wait. Like cars stuck behind a slow truck.
- Starvation vs the fix — Priority scheduling can starve low-priority jobs forever; aging (gradually raising priority) is the standard cure. Expect both in exams.
- Quantum too small — Tiny quanta feel responsive but waste huge time context-switching. There's a sweet spot, not "smaller is better."
- Affinity vs balancing — Moving a process to an idle core balances load but cold-starts its cache. Good multicore scheduling is a trade-off, not pure load balancing.
08 Questions students actually ask
Why isn't shortest-job-first always used, since it's optimal?
It needs each job's next burst length in advance, which is impossible in general. Systems estimate it from history, and even then it can starve long jobs — so it's rarely used raw.
What is the convoy effect?
Under FCFS, one long CPU-bound job at the front makes all the short jobs behind it wait a long time, tanking average waiting time.
How does round robin stay fair?
It gives every ready process an equal fixed time slice in rotation, so no single process can hog the CPU. That equal slicing makes interactive systems responsive.
What is starvation and how is it fixed?
Starvation is when a process never runs because higher-priority work keeps arriving. The fix is aging: gradually raise a waiting process's priority so it eventually runs.
Why do real systems use multilevel feedback queues?
They favor short, interactive tasks automatically by watching behavior — demoting CPU hogs and keeping responsive jobs high — without needing to know burst lengths ahead of time.
09 Key takeaways
- The scheduler picks which ready process runs when CPUs are scarce.
- Programs alternate CPU and I/O bursts; mixing CPU- and I/O-bound jobs keeps everything busy.
- Preemptive scheduling can interrupt a running process; non-preemptive can't.
- Criteria (throughput, waiting, response) conflict — every scheduler is a compromise.
- FCFS → convoy effect; SJF → optimal-but-unknowable; priority → starvation (fix: aging); round robin → fair.
- Multilevel feedback queues sort jobs by behavior; multicore adds affinity vs load-balancing.
10 Wrapping up
Scheduling is the resource-manager role at its most visible — constant arbitration of a scarce resource. With many threads sharing the CPU and memory, the next problem is keeping their shared data correct. Next up: Synchronization Tools.