T TestsWorld
← All topic guides

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

  1. 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.
  2. WT from the Gantt chart directly. For non-preemptive algorithms, WT = start time − arrival time. Only preemptive schedules need the full TAT − burst calculation.
  3. 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

  1. Using start − arrival for preemptive algorithms. A preempted process waits multiple times; use TAT − burst.
  2. Scheduling a process before it arrives. Always check which processes are in the ready queue at each decision point.
  3. Forgetting idle time. If no process has arrived, the CPU idles; the Gantt chart must show the gap.
  4. Choosing a huge quantum. When q exceeds every burst, Round Robin behaves exactly like FCFS; when q is tiny, context-switch overhead dominates.
  5. Calling SJF starvation-free. Long jobs can wait indefinitely if short jobs keep arriving; ageing fixes this.

Practice now: https://www.testsworld.com/mocks

Ready to practise CPU Scheduling?
Take a free mock test

Related guides