FCFS, SJF and round robin

Why it matters

These three policies are the reference points every scheduler is described against, and they are a favourite exam and interview question because you can compute their behaviour on paper. More usefully, each one survives in modern systems: FIFO queues in message brokers and thread pools, shortest-first ideas in job schedulers and HTTP/2 stream handling, round robin in load balancers and time-sharing. Seeing their failure modes on a tiny example teaches you to spot them at scale.

The idea

Take three jobs that all arrive at time 0 needing the CPU for different amounts of time: A needs 24 ms, B needs 3 ms, C needs 3 ms. Each policy orders them differently, and the average waiting time changes dramatically.

First-come, first-served

Run jobs in arrival order, each to completion. Trivial to implement and perfectly fair in arrival order, with no starvation. Its weakness is the convoy effect: one long job at the head makes every short job behind it wait, so average waiting time depends on luck. In the example, B and C finish at 27 and 30 ms even though they needed only 3 ms each.

Shortest job first

Run the job with the shortest next CPU burst. It is provably optimal for average waiting time when all jobs are known in advance: moving a short job ahead of a long one helps the short job more than it hurts the long one. The preemptive version, shortest remaining time first, also switches when a newly arrived job is shorter than what remains of the current one. Two problems: you rarely know a job's length in advance (schedulers estimate it from past bursts with an exponential average), and a steady stream of short jobs can starve long ones indefinitely.

Round robin

Give each runnable job a fixed time slice (quantum), say 4 ms, in turn; when a slice ends, the job goes to the back of the queue. No starvation, and response time is bounded: with n runnable jobs and slice q, a job waits at most (n − 1) × q before it runs again. The slice length is the dial:

Slice length	Behaviour	Problem
Very long (longer than most bursts)	Degenerates into FCFS	Convoy effect returns
Moderate (a little longer than a typical interactive burst)	Interactive jobs finish within one slice; CPU-bound jobs rotate	The usual sweet spot
Very short (close to the switch cost)	Excellent responsiveness on paper	Context switches eat a large share of CPU time

Round robin's average turnaround is often worse than SJF's, because every job is stretched out by interleaving, but its response time is excellent and predictable, which is what interactive systems want.

Where they live today

FIFO is everywhere a queue preserves order: a Kafka partition, a thread pool's work queue, a TCP send buffer. Shortest-first appears in schedulers that know job sizes (build systems that run quick tests first, web servers that send small responses first to cut average latency, SRPT scheduling in data centres). Round robin is the basis of time-sharing, of DNS and load-balancer rotation, and of many fair-queuing schemes. Modern CPU schedulers blend all three ideas, as the next lessons show.

Trade-offs

FCFS is simple and fair by arrival but suffers convoys. SJF minimises average waiting time but needs size estimates and risks starvation. Round robin bounds response time and wastes some CPU on switching. Every real scheduler is a compromise built from these pieces, often with separate queues so each piece applies where it fits.

In an interview

Use the vocabulary on queues you design: "A single FIFO queue for all jobs gives us a convoy problem when a 2-hour export lands in front of 10-second reports. Splitting by size class, or scheduling shortest-first with aging, fixes average latency without starving the exports."