CPU Scheduling Solved: FCFS vs SJF vs SRTF vs Round Robin on One Table
Operating Systems exams love one question: "Given these processes, draw the Gantt chart and find the average waiting time." The trick is not the formula. It is doing the same bookkeeping calmly for every algorithm. So here is one process table, run through four algorithms.
The processes
| Process | Arrival time | Burst time |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |
Two formulas are all you need:
- Turnaround time = completion time − arrival time
- Waiting time = turnaround time − burst time
1. FCFS (First Come First Served)
Whoever arrives first runs first, to completion. No preemption.
| P1 | P2 | P3 | P4 |
0 8 12 21 26
| Process | Completion | Waiting |
|---|---|---|
| P1 | 8 | 0 |
| P2 | 12 | 12 − 1 − 4 = 7 |
| P3 | 21 | 21 − 2 − 9 = 10 |
| P4 | 26 | 26 − 3 − 5 = 18 |
Average waiting time = (0 + 7 + 10 + 18) / 4 = 8.75
The weakness is visible: P2 and P4 are short, but they wait behind the long P1 and P3. This is the convoy effect.
2. SJF (non-preemptive Shortest Job First)
When the CPU becomes free, pick the shortest burst among the processes that have already arrived.
At time 0 only P1 exists, so it runs 0–8. At time 8 the ready processes are P2 (4), P3 (9), P4 (5). Shortest is P2, then P4, then P3.
| P1 | P2 | P4 | P3 |
0 8 12 17 26
Waiting times: P1 = 0, P2 = 8 − 1 = 7, P4 = 12 − 3 = 9, P3 = 17 − 2 = 15.
Average waiting time = (0 + 7 + 9 + 15) / 4 = 7.75
3. SRTF (preemptive SJF, Shortest Remaining Time First)
Now the scheduler re-checks every time a process arrives. If the newcomer has a shorter remaining time than the running process, it takes over.
- t = 0: P1 starts (8 left).
- t = 1: P2 arrives with 4. P1 has 7 left, so P2 preempts it.
- t = 2 and t = 3: P3 (9) and P4 (5) arrive, but P2 has less remaining, so P2 continues until t = 5.
- t = 5: ready are P1 (7), P3 (9), P4 (5). P4 runs 5–10.
- t = 10: P1 (7) runs 10–17, then P3 runs 17–26.
| P1 | P2 | P4 | P1 | P3 |
0 1 5 10 17 26
Waiting time = completion − arrival − burst:
- P1: 17 − 0 − 8 = 9
- P2: 5 − 1 − 4 = 0
- P3: 26 − 2 − 9 = 15
- P4: 10 − 3 − 5 = 2
Average waiting time = (9 + 0 + 15 + 2) / 4 = 6.5
SRTF gives the smallest average waiting time of the three. The price: long processes can wait a very long time (starvation), and it needs the burst time in advance, which a real OS can only estimate.
4. Round Robin (time quantum = 4)
Each process gets at most 4 time units, then goes to the back of the queue. New arrivals join the queue behind whoever is already waiting.
| P1 | P2 | P3 | P4 | P1 | P3 | P4 | P3 |
0 4 8 12 16 20 24 25 26
Completion times: P2 = 8, P1 = 20, P4 = 25, P3 = 26.
- P1: 20 − 0 − 8 = 12
- P2: 8 − 1 − 4 = 3
- P3: 26 − 2 − 9 = 15
- P4: 25 − 3 − 5 = 17
Average waiting time = (12 + 3 + 15 + 17) / 4 = 11.75
Round Robin has the worst average waiting time here, and that is fine, because it is not trying to win that contest. It guarantees that nobody waits more than one quantum cycle before getting the CPU, which is why it suits interactive, time-sharing systems.
Summary table
| Algorithm | Avg waiting time | Preemptive? | Main weakness |
|---|---|---|---|
| FCFS | 8.75 | No | Convoy effect |
| SJF | 7.75 | No | Needs burst time, can starve long jobs |
| SRTF | 6.5 | Yes | Starvation, more context switches |
| Round Robin (q = 4) | 11.75 | Yes | Higher average wait, quantum choice matters |
What examiners check
- Did you account for arrival times? Forgetting them is the most common mistake.
- Is the Gantt chart gap-free and does it end at the sum of bursts (26 here)?
- Did you subtract the arrival time as well as the burst time when computing waiting time?
Sumantrak™ is an AI mentor built for Indian engineering, diploma, BCA and BSc CS/IT students — Operating Systems, Networks, and the rest of your syllabus, explained like this. Free to start →