Scheduling Algorithms Compared
The scheduler needs an algorithm to decide which process runs next. Different algorithms make different trade-offs. Let's walk through the most common ones, using a simple example to see how each behaves.
Imagine five processes arrive at the following times with these burst times (how long each needs the CPU):
- P1: arrives at 0, needs 24ms
- P2: arrives at 1, needs 3ms
- P3: arrives at 2, needs 3ms
- P4: arrives at 3, needs 1ms
- P5: arrives at 4, needs 2ms
First-Come, First-Served (FCFS)
The simplest algorithm: processes are executed in the order they arrive. No priority, no preemption — just a queue.
How it works: P1 runs first (arrived at 0), then P2, P3, P4, and P5 in sequence.
FCFS Gantt Chart:
0 24 27 30 31 33
├────────┤────────┤────────┤────────┤────────┤
│ P1 │ P2 │ P3 │ P4 │ P5 │
│ 24ms │ 3ms │ 3ms │ 1ms │ 2ms │
└────────┘────────┘────────┘────────┘────────┘
Average Wait Time = (0 + 23 + 25 + 27 + 29) / 5 = 20.8ms
The problem: If P1 takes 24ms, every other process waits 24ms just for P1 to finish. This is called the convoy effect — short processes get stuck behind long ones. It's like a slow truck blocking a highway — everyone behind is stuck.
FCFS is fair in principle but terrible in practice for interactive systems.
Shortest Job First (SJF)
SJF picks the process with the shortest burst time next. It's optimal for minimizing average waiting time — mathematically proven to be the best for that metric.
How it works: Among the waiting processes, P4 (1ms) would go first, then P5 (2ms), then P2 or P3 (3ms each), and finally P1 (24ms).
SJF Gantt Chart:
0 1 3 6 9 33
├────────┤────────┤────────┤────────┤────────┤
│ P4 │ P5 │ P2 │ P3 │ P1 │
│ 1ms │ 2ms │ 3ms │ 3ms │ 24ms │
└────────┘────────┘────────┘────────┘────────┘
Average Wait Time = (9 + 5 + 3 + 0 + 1) / 5 = 3.6ms ← Optimal!
The problem: How do you know how long a process will take before it runs? In practice, you don't. The OS has to estimate burst times based on history. And if a short process keeps arriving, long processes can starve — never getting a chance to run.
Round Robin (RR)
Round Robin gives each process a fixed time quantum (say, 4ms). When the quantum expires, the process is preempted and moved to the back of the ready queue. Every process gets a turn.
How it works: P1 runs for 4ms, then P2 runs for 3ms (finishes), then P3 for 3ms (finishes), then P4 for 1ms (finishes), then P5 for 2ms (finishes), then P1 gets another turn, and so on.
Round Robin (quantum = 4ms) Gantt Chart:
0 4 7 10 11 13 17 21 25 29 33
├────┤────┤────┤────┤────┤────┤────┤────┤────┤────┤
│ P1 │ P2 │ P3 │ P4 │ P5 │ P1 │ P1 │ P1 │ P1 │ P1 │
│ 4ms│ 3ms│ 3ms│ 1ms│ 2ms│ 4ms│ 4ms│ 4ms│ 4ms│ 4ms│
└────┘────┘────┘────┘────┘────┘────┘────┘────┘────┘
↑P2 ↑P3 ↑P4 ↑P5
done done done done
Average Wait Time = (0 + 4 + 7 + 8 + 11) / 5 = 6ms
The trade-off: Round Robin is very fair and responsive — no process waits too long. But if the time quantum is too small, the overhead of context switching becomes significant. If it's too large, it degenerates into FCFS. Choosing the right quantum is crucial.
Priority Scheduling
Each process is assigned a priority, and the CPU is given to the highest-priority ready process. High-priority processes run before low-priority ones.
The problem: Starvation — low-priority processes might never run if high-priority processes keep arriving. The solution is aging — gradually increasing the priority of waiting processes so they eventually get a turn.
Priority scheduling is used in most real systems. Windows, Linux, and macOS all assign priorities to processes and threads, with interactive processes typically getting higher priority than background tasks.
Multilevel Queue Scheduling
Some systems divide processes into groups (queues) based on their nature — foreground (interactive), background (batch), system processes, real-time processes. Each queue has its own scheduling algorithm.
For example, the foreground queue might use Round Robin for responsiveness, while the background queue uses FCFS for throughput. The queues might have different priorities — foreground processes might always be preferred over background processes.
This approach recognizes that not all processes are equal. A video call needs immediate attention; a file backup can wait.