Before the questions, make sure you can: explain the CPU–I/O burst cycle; distinguish the long-, medium- and short-term schedulers and preemptive from non-preemptive scheduling; define and compute CPU utilization, throughput, turnaround, waiting and response time; draw Gantt charts and compute these metrics for FCFS, SJF, SRTF, priority (preemptive and not), Round Robin and HRRN, handling arrival times and idle periods; explain the convoy effect, starvation and aging; predict the next CPU burst with exponential averaging; describe multilevel and multilevel feedback queues and trace an MLFQ; explain lottery and fair-share scheduling; and choose an algorithm for a workload by the metric that matters.
When several processes are ready and there is one CPU, someone must decide who goes next. That decision — scheduling — changes everything users feel: a good choice finishes jobs sooner and keeps the system responsive; a bad one leaves a student waiting 20 seconds for a keystroke to appear. There is no single best algorithm: each one optimizes a different metric. This chapter teaches the classic algorithms with numbers, because in scheduling, intuition is often wrong until you draw the Gantt chart.
Bursts, levels and decision points
Programs alternate between CPU bursts (computing) and I/O bursts (waiting). CPU-bound programs have long CPU bursts (video encoding); I/O-bound programs have many short ones (an editor, a web server).
Three schedulers act at different time scales:
| Scheduler | Frequency | Decides |
|---|---|---|
| Long-term (admission) | Seconds–minutes | Which jobs enter the system (controls the degree of multiprogramming) |
| Medium-term (swapper) | Seconds | Which processes to suspend/resume when memory is short |
| Short-term (CPU scheduler, dispatcher) | Milliseconds | Which ready process runs next |
Scheduling decisions happen when a process (1) switches from running to waiting, (2) from running to ready (interrupt/timer), (3) from waiting to ready, or (4) terminates. If decisions happen only in cases 1 and 4, scheduling is non-preemptive (a process keeps the CPU until it blocks or ends); otherwise it is preemptive.
Scheduling criteria
For each process with arrival time A, total CPU time (burst) B, first time on the CPU S and finish (completion) time C:
- Turnaround time = C − A (total time in the system)
- Waiting time = turnaround − B (time spent in the ready queue)
- Response time = S − A (time until the first response)
- Throughput = number of processes finished ÷ elapsed time
- CPU utilization = busy time ÷ elapsed time
Batch systems care about throughput and turnaround; interactive systems about response time; everybody about fairness (no starvation).
FCFS — first come, first served
Run processes in arrival order, non-preemptively. Simple and fair in order — but a long job at the front makes everyone wait: the convoy effect (like a slow truck on a one-lane road).
Throughout this chapter we use this workload (times in ms; smaller priority number = higher priority):
| Process | Arrival | Burst | Priority |
|---|---|---|---|
| A | 0 | 3 | 2 |
| B | 2 | 6 | 1 |
| C | 4 | 4 | 3 |
| D | 6 | 5 | 2 |
| E | 8 | 2 | 1 |
FCFS: | A 0-3 | B 3-9 | C 9-13 | D 13-18 | E 18-20 |
| A | B | C | D | E | Average | |
|---|---|---|---|---|---|---|
| Finish | 3 | 9 | 13 | 18 | 20 | |
| Turnaround | 3 | 7 | 9 | 12 | 12 | 8.60 |
| Waiting | 0 | 1 | 5 | 7 | 10 | 4.60 |
Throughput = 5 / 20 = 0.25 processes per ms.
SJF and SRTF — shortest job first
SJF (non-preemptive): when the CPU becomes free, pick the ready process with the shortest burst. SRTF (shortest remaining time first) is the preemptive version: a new arrival with a shorter remaining time preempts the running process.
SJF: | A 0-3 | B 3-9 | E 9-11 | C 11-15 | D 15-20 | → average turnaround 7.60, waiting 3.60.
At t = 9, C (4), D (5) and E (2) are ready: E is shortest.
SRTF: | A 0-3 | B 3-4 | C 4-8 | E 8-10 | B 10-15 | D 15-20 | → average turnaround 7.20, waiting 3.20, response 2.00.
At t = 4, C arrives with 4 < B's remaining 5, so C preempts B; at t = 8, E (2) is shorter than B's remaining 5.
SJF is provably optimal for average waiting time when all jobs are available together — but it needs to know burst lengths in advance, and long jobs may starve if short ones keep arriving.
Predicting the next burst — exponential averaging. The OS cannot know the next CPU burst, but it can predict it from history:
τₙ₊₁ = α · tₙ + (1 − α) · τₙ
where tₙ is the actual length of the last burst, τₙ the previous prediction, and 0 ≤ α ≤ 1 (α = 0.5 weights recent and past history equally). Example with τ₀ = 10 and α = 0.5, actual bursts 6, 4, 6, 4, 13, 13, 13:
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| Prediction τ | 10 | 8 | 6 | 6 | 5 | 9 | 11 | 12 |
| Actual t | 6 | 4 | 6 | 4 | 13 | 13 | 13 |
The prediction follows the behaviour change (bursts become longer) with some delay.
Priority scheduling, starvation and aging
Each process has a priority; the highest-priority ready process runs (here, a smaller number means higher priority). It can be preemptive or not. SJF is a special case (priority = burst length).
Classic example, all arriving at 0 — P1 (10, priority 3), P2 (1, 1), P3 (2, 4), P4 (1, 5), P5 (5, 2): non-preemptive priority gives | P2 0-1 | P5 1-6 | P1 6-16 | P3 16-18 | P4 18-19 |, average waiting 8.20.
On our workload, preemptive priority: | A 0-2 | B 2-8 | E 8-10 | A 10-11 | D 11-16 | C 16-20 | → average waiting 5.00 (C, the lowest priority, waits 12).
Starvation: a low-priority process may wait forever if higher-priority work keeps arriving. Aging fixes it: gradually raise the priority of processes that wait a long time.
Round Robin (RR)
Each process gets a time quantum q; if it has not finished, it goes to the back of the ready queue. Convention used in this course: when a new arrival and a preempted process enter the queue at the same moment, the new arrival is queued first.
RR, q = 2:
| A 0-2 | B 2-4 | A 4-5 | C 5-7 | B 7-9 | D 9-11 | C 11-13 | E 13-15 | B 15-17 | D 17-20 |
→ average turnaround 10.00, waiting 6.00, but response only 1.80, with 9 context switches.
RR gives the best response time and no starvation — at the price of worse turnaround and more switches. The quantum matters:
- q very large → RR becomes FCFS;
- q very small → excellent response, but context-switch overhead dominates (Chapter 3: efficiency = q/(q + s)). A common rule of thumb: about 80% of CPU bursts should be shorter than q.
HRRN — highest response ratio next
Non-preemptive: when the CPU is free, pick the process with the highest response ratio
R = (W + S) / S
where W is the time already waited and S the service (burst) time. Short jobs start with a high ratio, and waiting raises every job's ratio, so long jobs cannot starve.
On our workload: at t = 9 the ratios are C = (5 + 4)/4 = 2.25, D = (3 + 5)/5 = 1.60, E = (1 + 2)/2 = 1.50 → C runs; at t = 13, D = 2.40 and E = 3.50 → E. Result: | A 0-3 | B 3-9 | C 9-13 | E 13-15 | D 15-20 |, average waiting 4.00.
Multilevel queues and multilevel feedback queues (MLFQ)
A multilevel queue puts processes into fixed classes (e.g., system, interactive, batch), each with its own algorithm, and schedules between queues by priority.
An MLFQ lets processes move between queues based on behaviour, so the OS learns which ones are interactive:
- New processes enter the top queue (short quantum).
- A process that uses its whole quantum is demoted (it looks CPU-bound).
- The CPU always serves the highest non-empty queue.
Example — three queues: Q0 (q = 2), Q1 (q = 4), Q2 (FCFS). Jobs: batch (arrives 0, needs 12), edit1 (1, 1), sim (3, 7), edit2 (5, 2):
| batch(Q0) 0-2 | edit1(Q0) 2-3 | sim(Q0) 3-5 | edit2(Q0) 5-7 | batch(Q1) 7-11 | sim(Q1) 11-15 | batch(Q2) 15-21 | sim(Q2) 21-22 |
The two short interactive jobs finish with turnaround 2 each, while the long jobs sink to the bottom queue. Real MLFQs also boost all processes back to the top periodically, to prevent starvation and to re-detect interactive behaviour.
Proportional share: lottery and fair-share
- Lottery scheduling: each process holds tickets; the scheduler draws a random ticket. A process with 25% of the tickets gets about 25% of the CPU on average.
- Fair-share scheduling: CPU is divided among users or groups first, then among their processes — a student with 50 processes does not get 50 times more CPU than a student with one. Linux cgroups and cloud schedulers apply the same idea (Chapter 12).
Summary on our workload
| Algorithm | Avg turnaround | Avg waiting | Avg response | Switches |
|---|---|---|---|---|
| FCFS | 8.60 | 4.60 | 4.60 | 4 |
| SJF | 7.60 | 3.60 | 3.60 | 4 |
| SRTF | 7.20 | 3.20 | 2.00 | 5 |
| Priority (preemptive) | 9.00 | 5.00 | 3.40 | 5 |
| RR (q = 2) | 10.00 | 6.00 | 1.80 | 9 |
| HRRN | 8.00 | 4.00 | 4.00 | 4 |
For every scheduling problem: (1) write the ready queue at each decision point, (2) draw the Gantt chart including idle gaps, (3) compute finish times, then turnaround = finish − arrival and waiting = turnaround − burst. Most mistakes come from forgetting arrival times or idle periods.
These single-CPU algorithms are the ancestors of research schedulers for clusters and clouds: shortest-job-first ideas appear in cluster job schedulers, priority queues in list scheduling for task graphs (Chapter 6), and exponential averaging in predictors that estimate task runtimes — today often with machine learning.
Key takeaways
- Metrics: turnaround = C − A, waiting = turnaround − B, response = first run − A, throughput = jobs ÷ time.
- FCFS: simple, convoy effect. SJF/SRTF: best average waiting, needs burst estimates, can starve long jobs.
- Exponential averaging: τₙ₊₁ = α·tₙ + (1 − α)·τₙ.
- Priority: flexible, starvation → aging. RR: best response, overhead grows as q shrinks.
- HRRN (R = (W + S)/S) favours short jobs without starving long ones.
- MLFQ learns behaviour: demote CPU-bound processes, keep interactive ones on top, boost periodically.
- Lottery/fair-share give proportional shares to processes or users.
Ready? Close the notes and practise.
30 questions. Predict the output before you check — that is the skill the exam measures.