Big idea
Scheduling policies decide which process gets the CPU. Mechanisms are the low-level tools; these chapters are about the policies on top.
Working assumptions (chapter starts here)
1. Each job runs for the same amount of time 2. All jobs arrive at the same time 3. Once a job starts, it runs to completion 4. Jobs only use the CPU (no I/O) 5. Run time of each job is known
Relaxing these assumptions is how you move from FIFO → SJF → STCF → Round Robin.
Metrics
- Turnaround time = time completed − time arrived
- Response time = time first run − time arrived
Turnaround favors batch-style policies. Response time matters for interactive use (typing into a terminal should feel immediate).
Policies that help turnaround
- FIFO (First In First Out) — simple; works under the ideal assumptions. Falls apart when job lengths vary: a long job blocks everyone behind it (convoy effect).
- SJF (Shortest Job First) — run the shortest known job next; better turnaround when lengths differ. Still stuck if a shorter job arrives while a longer one is already running (non-preemptive).
- STCF (Shortest Time-to-Completion First) — preempt when a newly arrived job would finish sooner. Relaxes “run to completion.”
Policies that help response time
- Round Robin — each job gets a time slice (quantum). Smaller slices → better response time, but more context-switch cost (and warm caches / TLB / predictors get flushed). Larger slices → less overhead, worse interactivity. RR is fair on response time but usually worse on turnaround.
Dropping the “CPU-only” assumption
Real jobs block on disk and other I/O. While one process waits, another can use the CPU — overlap I/O with useful work instead of idle spinning on a blocked job.