Scheduling Algorithms

This lesson covers the CPU scheduling algorithms on the OCR H446 specification — round robin, first come first served, shortest job first, shortest remaining time and multilevel feedback queues — together with the pre-emptive/non-pre-emptive distinction and fully worked timing examples.

Spec Mapping

This lesson develops OCR H446 section 1.2.1 (Operating Systems), specifically processor scheduling. It requires you to describe each named scheduling algorithm, distinguish pre-emptive from non-pre-emptive scheduling, and work out waiting time and turnaround time from a set of processes. It builds on the process-state and context-switching material from the Operating System Functions lesson: scheduling is what drives the Ready → Running → Ready transitions, and every pre-emption is a context switch triggered (in real hardware) by a timer interrupt.

Why Scheduling Is Needed

In a multi-tasking system, multiple processes sit in the ready queue competing for CPU time. The scheduler decides the order in which they run; the dispatcher then performs the context switch to hand the CPU over. Good scheduling aims to balance several goals, some of which pull against each other:

Goal	Explanation
Maximise CPU utilisation	Keep the CPU busy as much as possible
Maximise throughput	Complete as many processes as possible per unit of time
Minimise waiting time	Reduce the time processes spend in the ready queue
Minimise response time	Reduce the delay between a user action and the system's first response
Fairness	Ensure every process gets a reasonable share of CPU time

No single algorithm wins on every goal at once — minimising average waiting time (SJF) can starve long jobs, while guaranteeing fairness (round robin) raises average waiting time. Choosing a scheduler is choosing which goals matter most for the workload.

Two Key Definitions

Almost every scheduling question reduces to two measurements, so learn them precisely:

$\text{Turnaround time} = \text{completion time} - \text{arrival time}$

$\text{Waiting time} = \text{turnaround time} - \text{burst time}$

In words: turnaround is the total wall-clock time from a process arriving to it finishing; waiting is the part of that turnaround the process spent in the ready queue not running. Equivalently, waiting time is the time from arrival to completion minus the CPU time the process actually used.

Preemptive vs Non-Preemptive Scheduling

Type	Description
Non-preemptive	Once a process starts executing, it runs until it finishes or voluntarily gives up the CPU (e.g. for I/O). The scheduler cannot interrupt it
Preemptive	The scheduler can interrupt a running process and move it back to the ready queue to give the CPU to another process. This allows fairer sharing of CPU time

The pre-emptive/non-pre-emptive split is the single most useful classifier for these algorithms: FCFS and SJF are non-pre-emptive; SRT, round robin and MLFQ are pre-emptive. Pre-emption improves responsiveness and fairness but adds context-switch overhead.

First Come First Served (FCFS)

Aspect	Detail
Type	Non-preemptive
Rule	Processes are executed in the order they arrive in the ready queue
Data structure	Simple FIFO queue

Worked Example

Process	Arrival Time	Burst Time
P1	0	6
P2	1	3
P3	2	8
P4	3	4

Timeline (Gantt chart):

Time	0 → 6	6 → 9	9 → 17	17 → 21
Running	P1	P2	P3	P4

Processes run strictly in arrival order, so completion times are 6, 9, 17, 21. Applying the two formulae:

Process	Arrival	Burst	Completion	Turnaround (= comp − arr)	Waiting (= turn − burst)
P1	0	6	6	6	0
P2	1	3	9	8	5
P3	2	8	17	15	7
P4	3	4	21	18	14

$\text{Average waiting} = \frac{0+5+7+14}{4} = 6.5 \qquad \text{Average turnaround} = \frac{6+8+15+18}{4} = 11.75$

Notice P4 waits 14 even though its own burst is only 4 — it is stuck behind the long P3. That is the convoy effect made concrete.

Advantages and Disadvantages

Advantages	Disadvantages
Very simple to implement	Convoy effect — short processes wait behind long ones
No starvation — every process eventually runs	Poor average waiting time
No overhead from context switching	Not suitable for interactive or time-sharing systems

Shortest Job First (SJF)

Aspect	Detail
Type	Non-preemptive
Rule	The process with the shortest burst time in the ready queue is executed next

Worked Example (same processes)

The trick with SJF is to re-evaluate the ready queue only at the moments the CPU becomes free. At $t=0$ only P1 has arrived, so it must run (0→6). At $t=6$ the ready queue holds P2 (3), P3 (8) and P4 (4); the shortest is P2, so it runs (6→9). Next shortest of the remaining is P4 (4), so P4 runs (9→13), and finally P3 (13→21).

Timeline (Gantt chart):

Time	0 → 6	6 → 9	9 → 13	13 → 21
Running	P1	P2	P4	P3

Process	Arrival	Burst	Completion	Turnaround	Waiting
P1	0	6	6	6	0
P2	1	3	9	8	5
P4	3	4	13	10	6
P3	2	8	21	19	11

$\text{Average waiting} = \frac{0+5+6+11}{4} = 5.5 \qquad \text{Average turnaround} = \frac{6+8+10+19}{4} = 10.75$

Compare with FCFS on the same processes (average waiting 6.5): re-ordering P3 and P4 so the shorter P4 goes first has lowered the average waiting time. For a fixed set of jobs that are all available, SJF gives the lowest possible average waiting time of any non-pre-emptive schedule.

Advantages and Disadvantages

Advantages	Disadvantages
Optimal average waiting time for non-preemptive scheduling	Requires knowledge of burst times in advance (often estimated)
Reduces the convoy effect	Starvation — long processes may never run if shorter ones keep arriving
Good for batch systems	Not practical for interactive systems

Shortest Remaining Time (SRT)

Aspect	Detail
Type	Preemptive (preemptive version of SJF)
Rule	When a new process arrives, if its burst time is shorter than the remaining time of the currently running process, the current process is preempted

Worked Example

Process	Arrival Time	Burst Time
P1	0	6
P2	1	3
P3	2	8
P4	3	4

Timeline (Gantt chart):

Time	0 → 1	1 → 4	4 → 8	8 → 13	13 → 21
Running	P1	P2	P4	P1	P3

At time 1: P2 arrives (remaining 3) < P1 remaining (5). P1 preempted. At time 2: P3 arrives (remaining 8) > P2 remaining (2). P2 continues. At time 3: P4 arrives (remaining 4) > P2 remaining (1). P2 continues. At time 4: P2 finishes. P4 (4) < P1 (5) < P3 (8). P4 runs. At time 8: P4 finishes. P1 (5) < P3 (8). P1 runs. At time 13: P1 finishes. P3 runs.

Now compute the timings. Each process completes when its segment ends in the Gantt chart — P2 at 4, P4 at 8, P1 at 13, P3 at 21:

Process	Arrival	Burst	Completion	Turnaround	Waiting
P1	0	6	13	13	7
P2	1	3	4	3	0
P3	2	8	21	19	11
P4	3	4	8	5	1

$\text{Average waiting} = \frac{7+0+11+1}{4} = 4.75 \qquad \text{Average turnaround} = \frac{13+3+19+5}{4} = 10$

This is the lowest average waiting time of all the algorithms on this same workload — better than non-pre-emptive SJF (5.5) — because pre-emption lets a newly-arrived short job (P2, then P4) jump ahead immediately rather than waiting for the running job to finish. The cost is the extra context switch when P1 is pre-empted at $t=1$ .

Advantages and Disadvantages

Advantages	Disadvantages
Optimal average waiting time overall	High overhead from frequent context switching
Better response time than SJF	Starvation of long processes
Good for time-sharing systems	Must estimate remaining burst times

Round Robin (RR)

Aspect	Detail
Type	Preemptive
Rule	Each process is given a fixed time quantum (time slice). If the process does not finish within its quantum, it is preempted and placed at the back of the ready queue

Worked Example (time quantum = 4)

Process	Arrival Time	Burst Time
P1	0	6
P2	0	3
P3	0	8

Timeline (Gantt chart):

Time	0 → 4	4 → 7	7 → 11	11 → 13	13 → 17
Running	P1	P2	P3	P1	P3

P1 runs for 4 (2 remaining, goes to back of queue). P2 runs for 3 (finishes — used less than a full quantum). P3 runs for 4 (4 remaining, to back). P1 runs for its last 2 (finishes). P3 runs for its last 4 (finishes). All three arrived at time 0, so turnaround equals completion time:

Process	Burst	Completion	Turnaround	Waiting
P1	6	13	13	7
P2	3	7	7	4
P3	8	17	17	9

$\text{Average waiting} = \frac{7+4+9}{3} \approx 6.67 \qquad \text{Average turnaround} = \frac{13+7+17}{3} \approx 12.33$

Round robin's averages here are higher than SJF's would be on the same jobs — that is the price of fairness. What round robin buys instead is response time: every process gets a turn within the first few quanta, so an interactive process never waits long for its first slice of CPU even if its total turnaround is larger.

Round Robin with Staggered Arrivals

The example above had every process arrive at time 0. Staggered arrivals are trickier because a process only joins the ready queue when it arrives, and the queue order matters. Consider quantum = 2 with:

Process	Arrival	Burst
P1	0	4
P2	1	3
P3	2	2

The subtlety is ordering at each quantum boundary: when a running process is pre-empted, any process that arrived during that quantum is placed in the ready queue before the pre-empted process is added back.

Time	Running	Queue after this slice	Note
0 → 2	P1	P2, P3, P1	P2 (t=1) and P3 (t=2) arrived; then P1 re-joins behind them
2 → 4	P2	P3, P1, P2	P2 used a full quantum (1 left), re-joins
4 → 6	P3	P1, P2	P3 finishes (burst 2 = quantum)
6 → 8	P1	P2	P1 finishes its last 2
8 → 9	P2	—	P2 finishes its last 1

Completion: P3 = 6, P1 = 8, P2 = 9. Turnaround = completion − arrival → P1 = 8, P2 = 8, P3 = 4; waiting = turnaround − burst → P1 = 4, P2 = 5, P3 = 2.

$\text{Average waiting} = \frac{4+5+2}{3} \approx 3.67$

The lesson here is procedural: with round robin, always track the exact ready-queue order at each boundary, and remember the convention that a newly-arrived process is enqueued ahead of a just-pre-empted one. Getting that ordering wrong is the single most common mistake in staggered round-robin questions.

Choosing the Time Quantum

Quantum Size	Effect
Too small	Excessive context switching — too much overhead, less useful CPU work
Too large	Behaves like FCFS — long processes block shorter ones
Optimal	A balance — typically 10-100 milliseconds

A useful rule of thumb examiners like to see: the quantum should be a little larger than a typical CPU burst, so that most interactive jobs finish their burst within one quantum (giving them snappy response) while genuinely CPU-bound jobs are still pre-empted often enough to keep the system fair.

Advantages and Disadvantages

Advantages	Disadvantages
Fair — every process gets equal CPU time	Higher average waiting time than SJF
No starvation — every process runs regularly	Context switching overhead
Good response time for interactive systems	Performance depends heavily on quantum size

Multi-Level Feedback Queues (MLFQ)

Aspect	Detail
Type	Preemptive
Rule	Multiple ready queues with different priority levels and different time quanta. Processes can move between queues based on their behaviour

How MLFQ Works

flowchart TB
    Q0["Queue 0 — highest priority, shortest quantum<br/>[P1] [P5]"]
    Q1["Queue 1 — medium priority, medium quantum<br/>[P3] [P7]"]
    Q2["Queue 2 — lowest priority, longest quantum<br/>[P2] [P4]"]
    Q0 -- "demoted on quantum expiry" --> Q1
    Q1 -- "demoted on quantum expiry" --> Q2

New processes start in the highest-priority queue with a short time quantum.
If a process uses its entire quantum without finishing, it is demoted to a lower-priority queue with a longer quantum.
If a process gives up the CPU before its quantum expires (e.g. for I/O), it stays in the same queue or may be promoted.
The scheduler always runs the highest-priority non-empty queue first.

Scheduling Algorithms

Scheduling Algorithms

Spec Mapping

Why Scheduling Is Needed

Two Key Definitions

Preemptive vs Non-Preemptive Scheduling

First Come First Served (FCFS)

Worked Example

Advantages and Disadvantages

Shortest Job First (SJF)

Worked Example (same processes)

Advantages and Disadvantages

Shortest Remaining Time (SRT)

Worked Example

Advantages and Disadvantages

Round Robin (RR)

Worked Example (time quantum = 4)

Round Robin with Staggered Arrivals

Choosing the Time Quantum

Advantages and Disadvantages

Multi-Level Feedback Queues (MLFQ)

How MLFQ Works

Why This Works Well

More in Computer Science