Source: Operating Systems: Three Easy Pieces (OSTEP) — Chapter 7, Arpaci-Dusseau & Arpaci-Dusseau

Scheduling: Introduction

By now the low-level mechanisms — context switching, traps, timers — should be clear. If not, revisit Limited Direct Execution.

This chapter is about high-level policies: scheduling disciplines that decide which ready process runs next.

Scheduling predates computers — assembly lines and operations research faced the same efficiency questions. Our version:

Crux: how do we develop a basic framework for scheduling policy? What assumptions matter? Which metrics? Which classic approaches?

Workload assumptions (simplified)

Before comparing policies, OSTEP starts with unrealistic but useful assumptions. We relax them as we go toward a “fully operational” discipline.

#	Assumption
1	Each job runs the same amount of time
2	All jobs arrive together
3	Once started, each job runs to completion (non-preemptive)
4	Jobs use CPU only (no I/O)
5	The run time of each job is known

Some assumptions are more unrealistic than others — especially #5 (an omniscient scheduler). We will drop assumptions one by one.

Metrics

We need something to compare policies.

Turnaround time (this chapter’s main metric)

T_turnaround = T_completion − T_arrival

With all jobs arriving at t = 0, turnaround equals completion time.

Performance is our focus here. Fairness (e.g. Jain’s fairness index) matters too — but performance and fairness often conflict.

Response time (added later)

T_response = T_{first run} − T_arrival

Critical for interactive time-shared systems: how long until the job gets its first slice on the CPU?

First In, First Out (FIFO / FCFS)

Simplest policy: run jobs in arrival order.

Equal-length jobs (Fig 7.1): A, B, C each 10 s → finish at 10, 20, 30 → average turnaround = 20. Works fine under our early assumptions.

Different lengths (Fig 7.2): A = 100 s, B = C = 10 s → finish at 100, 110, 120 → average = 110.

This is the convoy effect [B+79]: short jobs queue behind a heavyweight consumer — like the grocery line with three carts and a checkbook.

Shortest Job First principle

SJF is not just for OS schedulers. Any queue that cares about per-customer wait uses the idea — e.g. “ten items or less” lanes.

Shortest Job First (SJF)

Run the shortest job first, then the next shortest (operations research → computer scheduling).

Same example: run B, C, A → turnaround 10, 20, 120 → average = 50 — more than 2× better than FIFO.

With all jobs arriving together, SJF is optimal for average turnaround (we skip the proof — this is a systems class).

Problem: late arrivals

Relax assumption 2: A arrives at 0 (100 s); B and C at t = 10 (10 s each).

Non-preemptive SJF already committed to A → B and C still wait → average ≈ 103.3 s (Fig 7.4). Convoy returns.

Shortest Time-to-Completion First (STCF / PSJF)

Preemptive SJF: whenever a new job arrives, run whoever has the least time remaining.

Requires the mechanisms from LDE: timer interrupts and context switches.

When B and C arrive at t = 10, STCF preempts A, runs B and C, then resumes A → average turnaround = 50 s again (Fig 7.5).

Preemptive schedulers

Batch systems often ran jobs to completion. Modern OS schedulers are preemptive — willing to stop one process to run another.

STCF is great for turnaround when job lengths are known — but time-sharing brought a new goal.

Response time vs turnaround

STCF can be bad for response time. If three jobs arrive together, the third may wait for the first two to finish entirely before its first run.

Example (A@0, B&C@10): response times 0, 0, 10 → average 3.33 — acceptable for batch, painful at a terminal.

Round Robin (RR)

Instead of running to completion, RR gives each job a time slice (quantum), then cycles the run queue.

Three jobs, each 5 s, quantum = 1 s:

Policy	Avg response	Avg turnaround
SJF (run to completion)	5 s	5 s (finishes 5, 10, 15)
RR	1 s	14 s (finishes 13, 14, 15)

RR excels at response; RR hurts turnaround — it stretches every job across many slices.

Quantum length trade-off

Shorter quantum → better response, more context switches (amortization matters)
Longer quantum → fewer switches, worse interactivity

Context-switch cost is not just register save/restore — cache, TLB, branch predictor state is flushed [MB91].

Amortization

Fixed costs (context switches) hurt less if you incur them less often. Longer quanta amortize switching — at the cost of responsiveness.

Inherent trade-off: policies fair on a small time scale (RR) tend to lose on turnaround; policies that favor short jobs (SJF/STCF) win turnaround but lose response.

Incorporating I/O

Relax assumption 4: real programs block on I/O.

When a job issues I/O, the CPU is idle unless the scheduler picks someone else. When I/O completes, the job moves Blocked → Ready (maybe run immediately).

Example: A needs 50 ms CPU in five 10-ms bursts (+ 10 ms I/O each); B needs 50 ms CPU straight.

Naive: run all of A, then B — CPU idle during A’s I/O (Fig 7.8)
STCF on bursts: treat each 10-ms CPU burst as a “job” — interleave with B while A waits on disk (Fig 7.9)

Overlap improves utilization — a recurring systems theme.

No more oracle

Final assumption to drop: known job lengths. General-purpose OSes rarely know them in advance.

How to behave like SJF/STCF without an oracle? How to keep RR-like response?

Next chapter: Multi-Level Feedback Queue — learn from the recent past to predict the future.

Interactive: compare policies

Try: FIFO equal · FIFO convoy · SJF · late arrivals · STCF · Round Robin · I/O overlap.

Check your understanding

Quiz