Operating Systems · Lesson 3 of 9 · Updated ·
CPU Scheduling — FCFS, SJF, SRTF, Round Robin and Priority with Gantt Charts
When several processes are ready, the CPU scheduler decides who runs next. Exams and interviews give you a table of processes and ask for average waiting time — here's how to solve every version.
1. The terms
| Term | Formula |
|---|---|
| Arrival time (AT) | when the process becomes ready |
| 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) |
| Response time | first time on CPU − AT |
Preemptive schedulers can take the CPU away from a running process; non-preemptive ones let it finish.
We'll use the same four processes for every algorithm:
| Process | Arrival | Burst |
|---|---|---|
| P1 | 0 | 5 |
| P2 | 1 | 3 |
| P3 | 2 | 8 |
| P4 | 3 | 6 |
2. FCFS (First Come, First Served) — non-preemptive
Run in order of arrival.
| Process | CT | TAT = CT − AT | WT = TAT − BT |
|---|---|---|---|
| P1 | 5 | 5 | 0 |
| P2 | 8 | 7 | 4 |
| P3 | 16 | 14 | 6 |
| P4 | 22 | 19 | 13 |
Average WT = (0 + 4 + 6 + 13) / 4 = 5.75, average TAT = 11.25.
Simple, but a long job at the front makes everyone wait — the convoy effect.
3. SJF (Shortest Job First) — non-preemptive
When the CPU is free, pick the shortest burst among the arrived processes.
At t = 0 only P1 has arrived, so it runs to 5. Then the shortest of P2 (3), P3 (8), P4 (6) is P2, then P4, then P3.
WT: P1 0, P2 4, P4 5, P3 12 → average 5.25, average TAT 10.75.
SJF gives the minimum average waiting time of all non-preemptive algorithms — but it needs burst times in advance (usually estimated), and long jobs can starve.
4. SRTF (Shortest Remaining Time First) — preemptive SJF
At every arrival, run the process with the least remaining time.
- t = 0: P1 starts (remaining 5).
- t = 1: P2 arrives with 3 < P1's remaining 4 → P2 preempts P1. P2 runs 1–4.
- t = 4: P1 (4 left), P3 (8), P4 (6) → P1 runs 4–8.
- Then P4 8–14, P3 14–22.
Gantt: P1 0–1 · P2 1–4 · P1 4–8 · P4 8–14 · P3 14–22
WT: P1 3, P2 0, P3 12, P4 5 → average 5.0 (the best of all here), average TAT 10.5.
5. Round Robin (RR) — preemptive, quantum = 2
Each process gets at most 2 units, then goes to the back of the queue. New arrivals join the queue before the process that was just preempted.
WT: P1 9, P2 7, P3 12, P4 11 → average 9.75, average TAT 15.25.
Waiting time is higher, but response time is excellent — everyone gets the CPU quickly. That's why time-sharing systems use RR.
Quantum size: too large → becomes FCFS; too small → too many context switches.
6. Priority scheduling
Each process has a priority; the highest runs first (preemptive or not). Problem: starvation of low-priority processes. Fix: aging — slowly increase the priority of processes that wait long.
7. Comparison
| Algorithm | Preemptive? | Avg WT here | Strength | Weakness |
|---|---|---|---|---|
| FCFS | no | 5.75 | simple | convoy effect |
| SJF | no | 5.25 | low waiting | starvation; needs burst time |
| SRTF | yes | 5.0 | lowest waiting | starvation; many switches |
| Round Robin (q=2) | yes | 9.75 | fair, responsive | more waiting & switches |
| Priority | either | — | important jobs first | starvation (use aging) |
Real systems use multilevel feedback queues: interactive jobs get high priority and short quanta; CPU-heavy jobs drift to lower queues.
Common mistakes
- Using CT − BT for waiting time (it's TAT − BT, i.e. CT − AT − BT).
- In RR, putting the preempted process ahead of new arrivals.
- Forgetting that SJF can only choose among processes that have arrived.
Quick recap
- TAT = CT − AT; WT = TAT − BT.
- FCFS simple; SJF/SRTF minimise waiting but can starve; RR fair and responsive.
- Draw the Gantt chart first, then fill the table.