Module 2 · Unit 5 of 5

CPU Scheduling

When more than one process is ready to run and only one CPU is available, the operating system must choose. This unit establishes the metrics that measure a scheduler and examines the classic algorithms — FCFS, SJF, SRTF, priority, round robin, and multilevel queues — that populate every operating-systems textbook.

Start Lesson 5.1 See all lessons

6 lessons Lab 4 · Scheduling simulation CLO3 ≈ 1 week at recommended pace

01 Unit learning outcomes

Upon completion of this unit you will be able to

U5.1 — Explain scheduling objectives.
U5.2 — Analyse scheduling algorithms.
U5.3 — Calculate scheduling metrics.
U5.4 — Compare scheduler designs.
U5.5 — Evaluate trade-offs.

This unit addresses course learning outcomes CLO3 and CLO8.

02 Lessons in this unit

Lesson 5.1 establishes the goals and metrics. Lessons 5.2 through 5.5 walk through the four most important classical algorithms. Lesson 5.6 shows how real systems combine them.

Lesson 5.1

Scheduling Objectives

Throughput, turnaround, waiting time, response time — and the conflicts between them.

Lesson 5.2

First-Come, First-Served

The simplest scheduler, the convoy effect, and why FIFO is rarely the right choice.

Lesson 5.3

SJF and SRTF

The optimal non-preemptive scheduler, its preemptive variant, and the burst-estimation problem.

Lesson 5.4

Priority Scheduling

Assigning priorities, preemptive versus non-preemptive variants, and the starvation problem.

Lesson 5.5

Round Robin

Time-sliced scheduling, the choice of quantum, and why RR is the workhorse of interactive systems.

Lesson 5.6

Multilevel Queue Scheduling

Combining several schedulers, feedback queues, and how modern general-purpose kernels actually work.

03 What you will learn, lesson by lesson

5.1 Scheduling Objectives

Explain CPU–I/O burst behaviour.
Define scheduling metrics.
Distinguish preemptive and non-preemptive.
Analyse metric conflicts.
Evaluate design goals.

5.2 First-Come, First-Served

Describe FCFS operation.
Calculate FCFS metrics.
Explain the convoy effect.
Analyse FCFS behaviour.
Evaluate FCFS trade-offs.

5.3 SJF and SRTF

Describe SJF operation.
Explain SJF optimality.
Describe SRTF preemption.
Analyse burst estimation.
Evaluate SJF trade-offs.

5.4 Priority Scheduling

Define priority scheduling.
Describe preemptive variants.
Explain starvation.
Analyse aging solutions.
Evaluate priority design.

5.5 Round Robin

Describe round-robin operation.
Explain the time quantum.
Calculate RR metrics.
Analyse quantum trade-offs.
Evaluate RR for interactive systems.

5.6 Multilevel Queue

Describe multilevel queues.
Explain feedback queues.
Analyse queue transitions.
Compare real-world schedulers.
Evaluate hybrid designs.

04 Worked example

The same three processes, scheduled by three different algorithms. The differences in the metrics are instructive.

Workload

Process	Arrival time	Burst time
P1	0	8
P2	0	12
P3	0	6

Comparing metrics

FCFS. Order P1, P2, P3. Wait times: P1 = 0, P2 = 8, P3 = 20. Average wait = 9.33. Turnaround: 8, 20, 26; average = 18.
SJF (non-preemptive). Order P3, P1, P2. Wait times: P3 = 0, P1 = 6, P2 = 14. Average wait = 6.67. Turnaround: 6, 14, 26; average = 15.33. SJF minimises average waiting time among non-preemptive schedulers.
SRTF (preemptive SJF). All three arrive at t = 0, so we always pick the shortest remaining. Order P3 (0–6), P1 (6–14), P2 (14–26). Wait times: P3 = 0, P1 = 6, P2 = 14. Same as SJF here because all arrive simultaneously.
Round Robin with quantum = 4. Order P1(0–4), P2(4–8), P3(8–12), P1(12–16), P2(16–20), P3(20–24), P1(24–26), P2(26–30), P3(30–32) — this depends on arrival times. Wait times: P1 = 14, P2 = 16, P3 = 18. Average wait = 16. But the first response times are P1 = 0, P2 = 4, P3 = 8 — far better than FCFS or SJF.
The point. RR has the worst average waiting time but the best response time. SJF is optimal for average wait but starves long jobs. Different metrics, different winners.

How to approach a scheduling problem

Always draw the Gantt chart first. Compute completion times, then turnaround (completion − arrival), then wait (turnaround − burst). The chart is the fastest way to avoid arithmetic slips.

05 Required reading

OSTEP — Chapter 7, Scheduling: Introduction, and Chapter 8, Scheduling: The Multi-Level Feedback Queue.
Operating System Concepts — Chapter 5, CPU Scheduling.

06 Unit discussion

Discussion prompt

The choice of round-robin time quantum is a well-known tuning problem. A very small quantum improves response time but increases the fraction of CPU time spent on context switches. A very large quantum behaves like FCFS.

Suppose you are designing a scheduler for a system that handles both interactive terminals and CPU-bound batch jobs. How would you set the quantum, and what information would you use to decide when to change it? Argue for a specific policy.

Post your response to the Unit 5 discussion forum and reply to at least two classmates. Supports CLO3.

07 Laboratory connection

Lab 4 — Scheduling Simulation is completed at the end of this unit. You will implement FCFS, SJF, SRTF, and RR in a small simulator, feed them the same workload, and compare the metrics. This lab also supplies the reference code for the CPU Scheduler Simulator option in Assignment 2.

Lab 4 coverage
Lesson	Lab 4 exercise
5.1 Objectives	Implement metric calculations
5.2 FCFS	Implement FCFS, run on benchmark workload
5.3 SJF and SRTF	Implement SJF and SRTF, compare to FCFS
5.4 Priority	Add priorities, demonstrate starvation
5.5 Round Robin	Implement RR, sweep quantum from 1 to 32
5.6 Multilevel	Design a two-level scheduler

08 Knowledge check & quiz

Quick check before you begin

Question 1

Three processes arrive at t = 0 with burst times 3, 6, and 9. What is the average waiting time under FCFS if they run in that order? What about SJF?

Show answer

FCFS: wait times are 0, 3, 9. Average = 4.0. SJF: the order is 3, 6, 9 (same as FCFS here because they are already sorted shortest-first). Average = 4.0. If the arrival order were 9, 6, 3, SJF would reorder them to 3, 6, 9 and the average would still be 4.0, while FCFS would give wait times 0, 9, 15 → average 8.0.

Question 2

Why is shortest-job-first optimal for average waiting time, yet rarely used directly in real systems?

Show answer

SJF is provably optimal for average wait because putting short jobs first reduces the wait of many jobs at the expense of the wait of few. It is rarely used directly because the next burst length is unknown in advance. Real systems approximate it using exponential averaging of past bursts, which works well for some workloads but poorly for others. SJF also starves long jobs: a steady stream of short jobs can keep a long one waiting indefinitely.

Question 3

A system has 10 processes on the ready queue. Round Robin with a quantum of 100 ms will give what worst-case response time for the tenth process?

Show answer

Up to about 900 ms — the first nine processes must each get one quantum before the tenth is scheduled. This is why quanta are typically much smaller (10–50 ms) in interactive systems, and why multilevel feedback queues — which push CPU-bound processes to lower-priority queues — reduce response time for interactive tasks without giving them an unfair share of total CPU.