Scheduling: Metrics and Concepts
What a scheduler does
The scheduler (or dispatcher) selects which of the ready processes runs next on the CPU. It is invoked whenever:
- A process transitions from Running → Blocked (non-preemptive yield).
- A process transitions from Running → Ready (timer interrupt — preemption).
- A process transitions from Blocked → Ready (a newly-woken process may have higher priority).
- A process terminates.
Preemptive vs non-preemptive
| Type | Description | Example |
|---|---|---|
| Non-preemptive | Once a process is Running, it keeps the CPU until it blocks (I/O) or terminates. | Early batch systems, cooperative multitasking in classic Mac OS |
| Preemptive | The OS can forcibly remove a Running process from the CPU via a timer interrupt. | Linux, Windows, macOS, all modern general-purpose OSes |
Preemptive scheduling requires a hardware timer that generates periodic interrupts. Without it, a process in an infinite loop would monopolise the CPU forever.
Key scheduling metrics
| Metric | Definition | Goal |
|---|---|---|
| CPU utilisation | Fraction of time the CPU is busy | Maximise (keep the CPU working) |
| Throughput | Number of processes completed per unit time | Maximise |
| Turnaround time | Wall-clock time from submission to completion | Minimise |
| Waiting time | Total time spent in the Ready queue (not Running, not Blocked) | Minimise |
| Response time | Time from submission to first CPU response (first time on CPU) | Minimise (important for interactive systems) |
These goals conflict: minimising turnaround time for long CPU-bound jobs may increase response time for interactive jobs. Real schedulers trade them off with tunable parameters (e.g., Linux’s nice value).
I/O-bound vs CPU-bound
- CPU-bound processes: long bursts of computation, infrequent I/O. The scheduler should not starve them entirely, but they can tolerate longer gaps between CPU allocations.
- I/O-bound processes: short CPU bursts followed by I/O waits. The scheduler should give them the CPU quickly when they become ready, or they will under-utilise the I/O devices.
The classic “convoy effect” (FCFS) illustrates the problem: one CPU-bound job at the head of the queue blocks all the I/O-bound jobs behind it, reducing overall I/O and CPU utilisation.
Time-slice (quantum)
In a time-shared system, the CPU is allocated in time slices (quanta). When the quantum expires, a timer interrupt invokes the scheduler, which may preempt the running process.
Choosing the quantum is a trade-off:
- Too large → degrades to FCFS; interactive response suffers.
- Too small → excessive context switching; throughput drops.
A typical quantum is 10–100 ms. The Linux CFS default target latency is 6 ms (scaled by the number of runnable processes).
Nice value
In UNIX, the nice value lets users express relative priority. Range: −20 (highest priority) to +19 (lowest). Default: 0. Only root can assign negative nice values. The scheduler translates nice to a weight; in CFS, nice 0 corresponds to weight 1024, and each nice step changes the weight by roughly 10%.
Summary
- Preemptive scheduling requires a hardware timer.
- Turnaround time, waiting time, and response time measure different things and often conflict.
- I/O-bound processes need quick CPU access to keep devices busy.
- The quantum determines granularity: too large hurts interactivity; too small hurts throughput.