CPU Scheduling: Why Every Algorithm Is a Trade-off, Not a Winner

Memorizing Gantt charts for FCFS, SJF, SRTF, and Round Robin isn't enough to answer a question that asks you to pick an algorithm for a scenario. The thing worth being able to say, for each one: what does it sacrifice to win on its one strong metric?

The metrics that trade off against each other

• Turnaround time = completion − arrival
• Waiting time = turnaround − burst
• Response time = time until first run — matters for interactive processes, barely for batch jobs
• Fairness — does everyone get a reasonable share, or can one process starve?
• Overhead — how expensive is the scheduling decision, and how many context switches does it cause?

No algorithm wins on all five.

FCFS — simplest, and the one that teaches the core problem

First-come-first-served: non-preemptive, whoever arrives first runs to completion. Trivial to implement, fair in the "arrived first, served first" sense. Its failure mode is the convoy effect — a short process arriving right after a long one is stuck waiting behind it for no reason related to its own size.

SJF and SRTF — optimal, with a catch

Shortest Job First always picks the smallest remaining job next. It's provably optimal for average turnaround time only when every process arrives at the same time — the caveat that gets dropped and shouldn't be. With staggered arrivals, non-preemptive SJF can still let a short job get stuck behind a long one that already started.

SRTF (Shortest Remaining Time First) is the preemptive fix: a newly-arrived process interrupts a running one if its burst is shorter than what's left of the current job. This avoids the convoy problem but costs more context switches — each roughly a microsecond, and a scheduler that preempts constantly pays that cost constantly.

Round Robin — optimizes the metric SJF ignores

Every process gets a fixed time slice, then cycles to the back of the queue, regardless of job length. The opposite trade-off from SJF/SRTF: bad for average turnaround time, good for response time and fairness. Quantum size is its own trade-off — too small and most of the time goes to context-switch overhead; too large and it degrades back into FCFS.

MLFQ — approximating SJF without knowing the future

SJF needs to know a process's burst time in advance; in a real OS, you don't. Multi-Level Feedback Queue (Linux uses a variant) is the practical answer:

• Multiple priority queues, high to low
• A new job starts at the highest priority
• A job that uses its full time slice without blocking gets demoted one level
• A job that blocks for I/O frequently (e.g. a text editor waiting on keystrokes) never burns through its slice, so it stays near the top
• Jobs get periodically promoted back to the top, so long-running jobs don't starve forever

MLFQ doesn't know which jobs are short — it infers it from behavior. A job that keeps giving up the CPU voluntarily gets treated like a short job would under SJF, without the OS ever knowing its total runtime ahead of time.

Algorithm	Non-preemptive	Preemptive
FCFS	Yes	—
SJF	Yes	—
SRTF	—	Yes
Priority	Yes	Yes
Round Robin	—	Yes
MLFQ	—	Yes (typically)

Quick recall

• FCFS: simplest, never preemptive, suffers the convoy effect
• SJF/SRTF: optimal average turnaround only if arrivals are equal; SRTF fixes staggered-arrival convoy problems preemptively, at the cost of more context switches
• Round Robin: optimizes response time/fairness over turnaround time; quantum size is its own trade-off
• MLFQ: approximates SJF without knowing burst times, by inferring them from I/O-blocking behavior
• FCFS is the only classic algorithm that cannot be made preemptive — it's defined by running to completion once started

What actually tells you whether someone understands scheduling: can they look at a new scenario and predict, before computing anything, which algorithm does well and why — not because they recognize the problem shape, but because they know what each algorithm is protecting.