Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Notes › Operating Systems

CPU Scheduling Algorithms

When several processes are ready, the CPU scheduler decides which one runs next. Good scheduling keeps the CPU busy and users happy.

Terms and formulas

Term Meaning
Arrival time (AT) when the process enters the ready queue
Burst time (BT) CPU time it needs
Completion time (CT) when it finishes
Turnaround time (TAT) CT − AT (total time in the system)
Waiting time (WT) TAT − BT (time spent waiting in the ready queue)
Response time (RT) first time it gets the CPU − AT
Throughput processes finished per unit time

Goals: maximise CPU utilisation and throughput; minimise waiting, turnaround and response time.

Preemptive = the OS can take the CPU away from a running process. Non-preemptive = it runs until it finishes or blocks.

The example (used for every algorithm)

Process AT BT
P1 0 8
P2 1 4
P3 2 9
P4 3 5

1. FCFS — First Come, First Served (non-preemptive)

Run in order of arrival.

| P1 | P2 | P3 | P4 |
0    8    12   21   26
P1 P2 P3 P4 Average
CT 8 12 21 26
TAT 8 11 19 23 15.25
WT 0 7 10 18 8.75

Simple and fair, but suffers from the convoy effect: short jobs wait behind one long job.

2. SJF — Shortest Job First (non-preemptive)

When the CPU is free, pick the ready process with the smallest burst. At t = 0 only P1 is here → it runs to 8. Then P2 (4), P4 (5), P3 (9).

| P1 | P2 | P4 | P3 |
0    8    12   17   26
P1 P2 P3 P4 Average
TAT 8 11 24 14 14.25
WT 0 7 15 9 7.75

SJF gives the minimum average waiting time among non-preemptive algorithms — but burst times must be known (estimated in practice) and long jobs can starve.

3. SRTF — Shortest Remaining Time First (preemptive SJF)

Whenever a process arrives, run the one with the least remaining time.

| P1 | P2 | P4 | P1 | P3 |
0    1    5    10   17   26
P1 P2 P3 P4 Average
TAT 17 4 24 7 13.00
WT 9 0 15 2 6.50

Optimal average waiting time overall, at the cost of more context switches and possible starvation.

4. Round Robin (quantum = 3)

Each process runs for at most one time quantum, then goes to the back of the queue. (A process arriving at the same moment another is preempted joins the queue first.)

| P1 | P2 | P3 | P4 | P1 | P2 | P3 | P4 | P1 | P3 |
0    3    6    9    12   15   16   19   21   23   26
P1 P2 P3 P4 Average
CT 23 16 26 21
TAT 23 15 24 18 20.00
WT 15 11 15 13 13.50

Higher average waiting time here, but great response time — every process gets the CPU quickly, which is why time-sharing systems use it.

5. Priority scheduling

Each process has a priority (often a smaller number = higher priority); the highest runs first. Can be preemptive or not.

Comparison

Algorithm Preemptive Avg WT (example) Starvation Notes
FCFS no 8.75 no convoy effect
SJF no 7.75 yes needs burst estimates
SRTF yes 6.50 yes best average WT
Round Robin (q=3) yes 13.50 no best response time
Priority either — yes (fix: aging)

Multilevel queue & multilevel feedback queue

Context switch

Saving the current process's state (registers, program counter) in its PCB and loading another's. It's pure overhead — no useful work happens.

Exam tips

Interview one-liners

More Operating Systems notes