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.
- t=0: P1 starts. t=1: P2 arrives (4 < P1's remaining 7) → P2 preempts.
- P2 runs 1–5. Then P4 (5) beats P1 (7) → P4 runs 5–10. Then P1 10–17, P3 17–26.
| 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.
- Quantum too big → behaves like FCFS. Too small → too many context switches (overhead).
- Rule of thumb: about 80% of bursts should finish within one quantum.
5. Priority scheduling
Each process has a priority (often a smaller number = higher priority); the highest runs first. Can be preemptive or not.
- Problem: starvation — low-priority processes may never run.
- Fix: aging — slowly raise the priority of processes that wait a long time.
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
- Multilevel queue: separate queues (system, interactive, batch), each with its own algorithm; a process stays in its queue.
- Multilevel feedback queue (MLFQ): processes move between queues — a CPU-heavy process sinks to lower-priority queues with bigger quanta, an interactive one stays high. Real OSes use variants of this; Linux uses the Completely Fair Scheduler (CFS).
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
- Always draw the Gantt chart first; mark arrival times.
- When there's a tie, use arrival order (FCFS) unless told otherwise.
- Remember idle time: if no process has arrived, the CPU is idle.
Interview one-liners
- TAT = CT − AT; WT = TAT − BT.
- SJF minimises average waiting time (non-preemptive); SRTF does it overall.
- FCFS → convoy effect; Priority → starvation, fixed by aging.
- Round Robin trades waiting time for fast response; quantum size matters.
- Related: Process vs Thread, Deadlocks.