CPU Scheduling Algorithms with Solved Examples: FCFS, SJF, SRTF, Priority and Round Robin

CPU scheduling numericals are among the most predictable questions in Operating Systems. Learn the method once and you can solve any of them in under three minutes.

Key terms and formulas#

We use the same processes for every algorithm:

FCFS (First Come First Served)#

Non-preemptive; processes run in arrival order.

| P1 | P2 | P3 | P4 |
0    5    8    9    11

Average WT = 16/4 = 4. Problem: the convoy effect, where short jobs wait behind a long one.

SJF (Shortest Job First, non-preemptive)#

When the CPU is free, pick the arrived process with the smallest burst.

At 0 only P1 has arrived, so it runs to 5. At 5, P2 (3), P3 (1) and P4 (2) are waiting: pick P3, then P4, then P2.

| P1 | P3 | P4 | P2 |
0    5    6    8    11

WT: P1 = 0, P3 = 5−2 = 3, P4 = 6−3 = 3, P2 = 8−1 = 7. Average WT = 13/4 = 3.25.

SJF gives the minimum average waiting time among non-preemptive algorithms, but long jobs can starve.

SRTF (Shortest Remaining Time First, preemptive SJF)#

Whenever a process arrives, compare its burst with the remaining time of the running process.

• 0: P1 starts (remaining 5).
• 1: P2 arrives (3) < P1's remaining 4 → switch to P2.
• 2: P3 arrives (1) < P2's remaining 2 → switch to P3, which finishes at 3.
• 3: P2 (2), P4 (2), P1 (4) → tie; choose by arrival → P2 finishes at 5.
• 5: P4 runs to 7, then P1 runs to 11.

| P1 | P2 | P3 | P2 | P4 | P1 |
0    1    2    3    5    7    11

WT: P1 = 11−0−5 = 6, P2 = 5−1−3 = 1, P3 = 3−2−1 = 0, P4 = 7−3−2 = 2. Average WT = 9/4 = 2.25, the best so far.

Priority scheduling (non-preemptive)#

Pick the waiting process with the highest priority (lowest number here). P1 runs first (alone at 0). At 5: P2 (1), P4 (2), P3 (4).

| P1 | P2 | P4 | P3 |
0    5    8    10   11

WT: P1 = 0, P2 = 4, P4 = 5, P3 = 8. Average = 17/4 = 4.25.

Starvation is fixed by ageing: slowly raising the priority of waiting processes.

Round Robin (time quantum = 2)#

Each process runs for at most 2 units, then goes to the back of the queue. New arrivals join the queue before the process that was just pre-empted.

| P1 | P2 | P3 | P1 | P4 | P2 | P1 |
0    2    4    5    7    9    10   11

WT: P1 = 11−0−5 = 6, P2 = 10−1−3 = 6, P3 = 5−2−1 = 2, P4 = 9−3−2 = 4. Average = 18/4 = 4.5.

• Large quantum → behaves like FCFS. Very small quantum → too many context switches.
• Round Robin gives good response time, which is ideal for time-sharing systems.

Comparison#