CPU Scheduling: formulas, shortcuts & solved examples
What it is
CPU scheduling decides which ready process gets the CPU next. Since only one process runs per core at a time, the choice of algorithm changes waiting time, response time and throughput. Numerical scheduling problems with Gantt charts are a fixture of GATE-style and campus OS questions.
Key formulas
For each process:
- Turnaround time (TAT) = Completion time − Arrival time
- Waiting time (WT) = TAT − Burst time
- Response time = Time of first run − Arrival time
- Average WT = (sum of WT) / number of processes
- Throughput = processes completed / total time
Algorithms at a glance
| Algorithm | Preemptive? | Notes |
|---|---|---|
| FCFS | No | Simple; suffers the convoy effect |
| SJF | No | Optimal average WT among non-preemptive algorithms when bursts are known |
| SRTF | Yes | Preemptive SJF; optimal average WT overall |
| Priority | Either | Risk of starvation; fixed by ageing |
| Round Robin | Yes | Time quantum q; good response time |
In Round Robin with n processes and quantum q, a process waits at most (n − 1) × q before its next turn (ignoring context-switch cost).
Shortcuts
- Shortest first minimises the sum. For processes all arriving at 0, sorting bursts in ascending order gives the minimum total waiting time. WT of the k-th job is the sum of the bursts before it.
- WT from the Gantt chart directly. For non-preemptive algorithms, WT = start time − arrival time. Only preemptive schedules need the full TAT − burst calculation.
- Tie-breaking. When bursts or remaining times tie, the usual convention is FCFS (earlier arrival first). State it if the question does not.
Solved examples
Example 1: FCFS and the convoy effect
P1, P2, P3 all arrive at time 0 with bursts 24, 3, 3 ms.
Solution. Order P1, P2, P3: start times 0, 24, 27, so WT = 0, 24, 27 and average WT = 51 / 3 = 17 ms.
If the order were P2, P3, P1: WT = 0, 3, 6, average = 3 ms. One long job in front makes everyone wait; this is the convoy effect.
Example 2: Non-preemptive SJF with arrivals
| Process | Arrival | Burst |
|---|---|---|
| P1 | 0 | 7 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 5 | 4 |
Solution. At t = 0 only P1 is ready, so it runs to t = 7. Ready now: P2 (4), P3 (1), P4 (4). P3 is shortest: runs 7–8. P2 and P4 tie at 4; P2 arrived first: 8–12. Then P4: 12–16.
WT = start − arrival: P1 = 0, P2 = 8 − 2 = 6, P3 = 7 − 4 = 3, P4 = 12 − 5 = 7. Average = 16 / 4 = 4 ms.
Example 3: SRTF on the same data
Solution. Gantt chart:
| P1 | P2 | P3 | P2 | P4 | P1 |
0 2 4 5 7 11 16
At t = 2, P2 (4) is shorter than P1's remaining 5, so P1 is preempted. At t = 4, P3 (1) beats P2's remaining 2. At t = 5, P2 (remaining 2) beats P4 (4) and P1 (5), finishing at 7. P4 runs 7–11, P1 finishes 11–16.
Completion: P1 16, P2 7, P3 5, P4 11. WT = completion − arrival − burst: P1 = 16 − 0 − 7 = 9, P2 = 7 − 2 − 4 = 1, P3 = 5 − 4 − 1 = 0, P4 = 11 − 5 − 4 = 2. Average = 12 / 4 = 3 ms, better than the non-preemptive 4 ms.
Example 4: Round Robin, q = 2
P1 = 5, P2 = 3, P3 = 1 ms, all arriving at 0.
Solution.
| P1 | P2 | P3 | P1 | P2 | P1 |
0 2 4 5 7 8 9
Completion: P1 9, P2 8, P3 5. Since arrival is 0, TAT equals completion. WT = TAT − burst: P1 = 4, P2 = 5, P3 = 4. Average WT = 13 / 3 ≈ 4.33 ms.
Common mistakes
- Using start − arrival for preemptive algorithms. A preempted process waits multiple times; use TAT − burst.
- Scheduling a process before it arrives. Always check which processes are in the ready queue at each decision point.
- Forgetting idle time. If no process has arrived, the CPU idles; the Gantt chart must show the gap.
- Choosing a huge quantum. When q exceeds every burst, Round Robin behaves exactly like FCFS; when q is tiny, context-switch overhead dominates.
- Calling SJF starvation-free. Long jobs can wait indefinitely if short jobs keep arriving; ageing fixes this.
Practice now: https://www.testsworld.com/mocks