Foundations · Lesson 2/8

CPU Scheduling — Who Gets the Processor Next?

40 min 1 quiz Graded labs: 3

What you'll learn

Why the OS needs a scheduler and what it optimises
The metrics: arrival, burst, completion, turnaround, waiting
FCFS, SJF, Round Robin and priority scheduling, and where each one hurts
Starvation and how aging fixes it
How to simulate schedulers and compare them with numbers

You will code three simulators: FCFS vs SJF in Python, Round Robin in Java and priority-with-aging in JavaScript.

One checkout counter, many customers 🛒

Picture a supermarket with one open checkout counter. The cashier is the CPU, the customers waiting in line are the processes in the READY queue, and the store's rule for who goes next is the scheduling policy.

"First come, first served"? Simple and fair, but one customer with a full cart makes everyone behind them wait.
"Quickest basket first"? Short waits for most people, but the person with the huge cart might wait forever.
"Everybody gets two minutes, then back of the line"? Nobody waits too long to start, but the line shuffles a lot.

That is the whole subject. A real CPU core runs one process at a time, so the OS scheduler repeatedly picks the next READY process. It runs when a process blocks or exits, when a timer interrupt ends a time slice, and when a process becomes READY.

Two kinds of processes

CPU-bound: long stretches of computation (video encoding, compiling)
I/O-bound: short bursts of computing between waits for disk, network or the user (an editor, a web server)

A good scheduler keeps interactive, I/O-bound programs snappy while still letting CPU-bound jobs make progress.

Preemptive or not?

A non-preemptive scheduler lets a process keep the CPU until it blocks or exits. A preemptive one can take the CPU away (usually when a timer fires). Every modern general-purpose OS is preemptive, because otherwise one infinite loop would freeze the machine. Each switch costs a context switch, which is pure overhead.

Measuring a schedule

To compare policies we need numbers. For each process:

Arrival time: when it enters the READY queue
Burst time: how much CPU time it needs in total
Completion time: the clock value when it finishes
Turnaround time = completion − arrival (how long it was in the system)
Waiting time = turnaround − burst (how long it sat READY without running)
Response time = first run − arrival (how long until it first got the CPU)

Schedulers are usually compared on average waiting time and average turnaround time, plus fairness and responsiveness.

A worked example

Four processes (arrival, burst): P1 (0, 7), P2 (2, 4), P3 (4, 1), P4 (5, 4).

FCFS runs them in arrival order: P1 0–7, P2 7–11, P3 11–12, P4 12–16. Waiting times: 0, 5, 7, 7, so the average is 4.75.
SJF (non-preemptive): at time 7 the ready jobs are P2 (4), P3 (1), P4 (4), so it runs the shortest, P3, first: P1 0–7, P3 7–8, P2 8–12, P4 12–16. Waiting times: 0, 6, 3, 7, so the average is 4.00.

Run it yourself:

The only difference between the two schedules is the order. Same work, but SJF lowers the average wait because short jobs stop waiting behind long ones.

# name -> (arrival, burst): the textbook set from the lesson
procs = {"P1": (0, 7), "P2": (2, 4), "P3": (4, 1), "P4": (5, 4)}

def report(title, order):
    clock = 0
    total_wait = total_turn = 0
    print(title)
    for name in order:
        arrival, burst = procs[name]
        clock = max(clock, arrival)       # the CPU may sit idle until a process arrives
        wait = clock - arrival
        clock += burst
        turnaround = clock - arrival
        total_wait += wait
        total_turn += turnaround
        print(f"  {name}: starts {clock - burst:>2}, finishes {clock:>2}, waited {wait}, turnaround {turnaround}")
    n = len(order)
    print(f"  average wait {total_wait / n:.2f}, average turnaround {total_turn / n:.2f}")

report("FCFS (arrival order)", ["P1", "P2", "P3", "P4"])
report("SJF (shortest ready job first)", ["P1", "P3", "P2", "P4"])

Open in Code Lab

The classic policies

FCFS (First Come, First Served). A plain queue. Easy to implement, no starvation. Its weakness is the convoy effect: one long CPU-bound job at the front makes many short jobs wait, so the average wait can be terrible.

SJF (Shortest Job First). Always run the ready job with the smallest burst. For a known set of jobs it gives the lowest possible average waiting time. Two problems: the OS cannot know the next burst in advance (real systems estimate it from the process's history), and long jobs can starve if short ones keep arriving. Its preemptive form is SRTF (Shortest Remaining Time First).

Round Robin (RR). FCFS plus a timer. Each process runs for at most one time quantum, then goes to the back of the queue. Good response time and fairness. The quantum is a trade-off: if it is huge, RR degenerates into FCFS; if it is tiny, the CPU wastes its time on context switches.

Priority scheduling. Each process has a priority, and the highest priority READY process runs. Great for urgent work (audio, interrupts), but low-priority processes can starve. The cure is aging: the longer a process waits, the more its priority improves.

MLFQ (Multi-Level Feedback Queue). Several queues with different priorities. New jobs start at the top; a job that uses its whole quantum is demoted, while one that blocks early (I/O-bound) stays high; every so often everything is boosted back up to prevent starvation. It learns what each process is like without being told.

Real kernels combine these ideas. Linux's default scheduler aims for fair sharing of CPU time among normal tasks, and offers separate real-time policies (SCHED_FIFO, SCHED_RR); see man 7 sched.

Your turn: FCFS vs SJF

In the first lab you will simulate both policies, including the awkward case where the CPU sits idle until the next process arrives.

Lab exercise 1

PythonGraded in Code Lab

Simulate FCFS and non-preemptive SJF on the same set of processes and report both averages.

Input: the first number is n, followed by n lines name arrival burst (integers, in any order).

Rules:

The CPU runs one process at a time and never stops a running process.
If no process has arrived yet, the CPU idles until the next arrival.
FCFS picks the ready process that arrived first (ties: earlier in the input).
SJF picks the ready process with the smallest burst (ties: earlier arrival, then earlier in the input).
waiting = start − arrival, turnaround = completion − arrival.

Output: two lines with the averages rounded to 2 decimals (both 0.00 when n is 0):

FCFS avg_wait=<w> avg_turnaround=<t>
SJF avg_wait=<w> avg_turnaround=<t>

Example (the lesson's worked example):

prints

FCFS avg_wait=4.75 avg_turnaround=8.75
SJF avg_wait=4.00 avg_turnaround=8.00

Visible tests (6)

The lesson's worked example
Convoy effect: a long job first
CPU idles between arrivals
Input is not sorted by arrival
Single process
No processes

Example run

Input: 4 P1 0 7 P2 2 4 P3 4 1 P4 5 4
Expected output: FCFS avg_wait=4.75 avg_turnaround=8.75 SJF avg_wait=4.00 avg_turnaround=8.00

Starter code

import sys

def read_processes():
    tokens = sys.stdin.read().split()
    n = int(tokens[0]) if tokens else 0
    return [(tokens[1 + 3 * i], int(tokens[2 + 3 * i]), int(tokens[3 + 3 * i])) for i in range(n)]

def simulate(procs, pick):
    """Run non-preemptively. pick(ready) returns the index of the process to run next.
    Returns (average waiting time, average turnaround time)."""
    # TODO 1: keep a clock and the list of processes that have not run yet
    # TODO 2: collect the ready ones (arrival <= clock); if none, jump the clock to the next arrival

More lines in Code Lab: 11

Try in Code Lab

Hints and instant feedback are in Code Lab. Optional practice: it does not block finishing the lesson.

JavaScript and Python also run in your browser without an account; other languages use the secure server runner and need a free account.

Round Robin in motion

Round Robin is the scheduler behind "everybody gets a turn". The rules:

Processes wait in a FIFO queue.
Take the front process and run it for min(quantum, remaining) time units.
If it still has work left, it goes to the back of the queue; otherwise it is done.

One subtle detail every implementation must decide: if a new process arrives while another is running, it joins the queue before the preempted process is put back. (If both happen at the same instant, the newcomer goes first.) That is the convention you will use in the lab.

Watch it work on A needs 5, B needs 3, C needs 1, quantum 2, all arriving at time 0:

The Gantt chart shows the CPU timeline. Short job C escapes early at time 5, while long job A needs three turns. Change the quantum to 1 or to 10 and see how the timeline changes.

const quantum = 2;
const queue = [{ name: "A", left: 5 }, { name: "B", left: 3 }, { name: "C", left: 1 }];
let clock = 0;
const gantt = [];

while (queue.length > 0) {
  const p = queue.shift();                    // front of the ready queue
  const run = Math.min(quantum, p.left);
  gantt.push(p.name + " " + clock + "-" + (clock + run));
  clock += run;
  p.left -= run;
  if (p.left > 0) queue.push(p);              // unfinished: back of the queue
  else console.log(p.name + " finishes at " + clock);
}

console.log(gantt.join(" | "));

Open in Code Lab

Lab exercise 2

JavaGraded in Code Lab

Implement Round Robin with a given time quantum.

Input: the quantum q, then n, then n lines name arrival burst (integers; any order; names have no spaces).

Rules:

Processes join the ready queue in arrival order (ties: input order).
The front process runs for min(q, remaining) units. Processes that arrive at or before the end of that slice are queued before the preempted process goes back to the end.
If the queue is empty, the clock jumps to the next arrival.
turnaround = finish − arrival, waiting = turnaround − burst.

Output: one line per process, in input order, then the average waiting time:

<name>: finish=<f> turnaround=<t> waiting=<w>
...
avg_wait=<x.xx>

For n = 0 print only avg_wait=0.00.

Example: q = 2, processes A 0 5, B 0 3, C 0 1:

A: finish=9 turnaround=9 waiting=4
B: finish=8 turnaround=8 waiting=5
C: finish=5 turnaround=5 waiting=4
avg_wait=4.33

Visible tests (6)

Example from the prompt (q = 2)
Textbook case (q = 4)
A newcomer is queued before the preempted process
CPU idles before a late arrival
Quantum 1 with five processes
No processes

Example run

Input: 2 3 A 0 5 B 0 3 C 0 1
Expected output: A: finish=9 turnaround=9 waiting=4 B: finish=8 turnaround=8 waiting=5 C: finish=5 turnaround=5 waiting=4 avg_wait=4.33

Starter code

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int quantum = in.nextInt();
        int n = in.nextInt();
        String[] name = new String[n];
        int[] arrival = new int[n];
        int[] burst = new int[n];
        for (int i = 0; i < n; i++) {
            name[i] = in.next();

More lines in Code Lab: 20

Try in Code Lab

Hints and instant feedback are in Code Lab. Optional practice: it does not block finishing the lesson.

JavaScript and Python also run in your browser without an account; other languages use the secure server runner and need a free account.

Priorities, starvation and aging

Suppose each process has a priority number (here, smaller number = more urgent, like Unix nice values where -20 is the most favoured). A strict priority scheduler always runs the most urgent READY process.

The danger is starvation: if urgent work keeps arriving, a low-priority process can wait indefinitely. A famous legend says that when the IBM 7094 at MIT was shut down in 1973 they found a low-priority job submitted in 1967 that had never run. Whether or not the story is exact, the problem is real.

Aging is the fix: raise the priority of a process every time it waits a while. Eventually even the least important process becomes the most urgent one and gets its turn.

In the next lab each process runs one time unit at a time. Its effective priority is

effective = max(0, priority - floor(waited / A))

where waited counts the time units it has spent not running since it last ran and A is the aging interval. A huge A means no aging, and you will see starvation in the output.

Lab exercise 3

JavaScript (Node.js)Graded in Code Lab

Simulate priority scheduling with aging, one time unit per step.

Input: the aging interval A (at least 1), then n, then n lines name priority burst. All processes are ready at time 0. A smaller priority number is more urgent.

Each time unit:

For every unfinished process compute effective = max(0, priority - floor(waited / A)).
Run the process with the smallest effective priority for one unit (ties: the one that appears earlier in the input).
The process that ran gets waited = 0; every other unfinished process gets waited += 1.

Output: the timeline on a single line, consecutive units of the same process merged, as name:units separated by spaces. For n = 0 print an empty line.

Example: A = 1000 (no aging), H 1 6 and L 3 2 would print H:6 L:2: L must wait for H to finish. With A = 1 the same input prints

H:3 L:1 H:3 L:1

because L's priority number drops by one for every unit it waits, until it beats H for a turn.

Visible tests (6)

Aging disabled (huge A): strict priority order
Aging lets the low-priority process take turns
Ties go to the earlier process in the input
Three processes with moderate aging
A single process
No processes: an empty line

Example run

Input: 1000 3 A 1 3 B 2 2 C 3 1
Expected output: A:3 B:2 C:1

Starter code

const lines = require("fs").readFileSync(0, "utf8").split("\n").map((l) => l.trim()).filter((l) => l !== "");
const aging = Number(lines[0]);
const n = Number(lines[1]);
const procs = lines.slice(2, 2 + n).map((line) => {
  const [name, priority, burst] = line.split(/\s+/);
  return { name, priority: Number(priority), left: Number(burst), waited: 0 };
});

const timeline = []; // [{ name, units }]

// TODO 1: loop while some process still has time left (left > 0)
// TODO 2: pick the unfinished process with the smallest effective priority:

More lines in Code Lab: 5

Try in Code Lab

Hints and instant feedback are in Code Lab. Optional practice: it does not block finishing the lesson.

JavaScript and Python also run in your browser without an account; other languages use the secure server runner and need a free account.

Quick quiz

Question 1 of 5

How is a process's turnaround time defined?

Question 2 of 5

What is the convoy effect in FCFS scheduling?

Question 3 of 5

SJF gives the lowest average waiting time for a known set of jobs. Why can't real operating systems use it exactly as is?

Question 4 of 5

What happens to Round Robin as the time quantum becomes very large (larger than every burst)?

Question 5 of 5

What problem does aging solve in priority scheduling?

Summary

The scheduler picks the next READY process; preemptive schedulers can take the CPU back, which all general-purpose systems need
Compare policies with waiting (turnaround − burst) and turnaround (completion − arrival) times
FCFS: simple, but suffers the convoy effect. SJF: optimal average wait, but needs burst predictions and can starve long jobs. Round Robin: fair and responsive; the quantum is the trade-off. Priority: urgent first, fixed with aging against starvation. MLFQ learns process behaviour
You simulated FCFS vs SJF, Round Robin with its tie-breaking rule, and aging

Practice: add response time to the Round Robin lab, or run chrt -p $$ and nice on a Linux machine to see real policies and priorities. Next: memory management, how every process gets the illusion of a private address space.