FCFS, SJF, SRTF, and Round Robin | Operating Systems

First-Come, First-Served (FCFS)

The simplest scheduler: processes are run in the order they arrive, without preemption. Implemented with a FIFO queue of ready processes.

Convoy effect: A long CPU-bound process arrives first. All subsequent short (possibly I/O-bound) processes queue behind it. The CPU-bound job monopolises the CPU; the I/O-bound processes complete their brief CPU bursts quickly but then find I/O devices idle because the CPU-bound job isn’t issuing I/O requests.

FCFS is non-preemptive and provides no starvation — every process eventually runs — but average waiting time can be arbitrarily bad.

Example: Processes P1(24 ms), P2(3 ms), P3(3 ms) arrive in order:

Turnaround: P1=24, P2=27, P3=30, average = 27 ms.

If they arrived in reverse order: P3(3), P2(3), P1(24): average turnaround = (3 + 6 + 30)/3 = 13 ms. FCFS is sensitive to arrival order.

Shortest-Job-First (SJF)

Pick the process with the shortest next CPU burst. SJF is provably optimal for minimising average waiting time (for a given set of processes arriving simultaneously). For the example above: P2(3), P3(3), P1(24) gives average waiting time (0 + 3 + 6)/3 = 3 ms — the minimum possible.

SJF can be non-preemptive (once a process starts, it runs to completion) or preemptive. The preemptive version is called Shortest-Remaining-Time-First (SRTF).

The fatal flaw: the kernel cannot know the next CPU burst length. It must predict it, typically using exponential averaging:

$\tau_{n+1} = \alpha \cdot t_n + (1 - \alpha) \cdot \tau_n$

where $t_n$ is the actual $n$ -th burst, $\tau_n$ was the prediction for it, and $\alpha$ (typically 0.5) controls how quickly the estimate adapts.

Shortest-Remaining-Time-First (SRTF)

Preemptive SJF: when a new process arrives with a shorter remaining time than the currently running process, the running process is preempted.

SRTF optimises waiting time even when processes arrive at different times, but it suffers the same prediction problem as SJF and can cause starvation — a long process may never run if short processes keep arriving.

Round Robin (RR)

Each process gets a fixed quantum $q$ of CPU time. After the quantum, a timer interrupt preempts the process and moves it to the back of the ready queue. The CPU rotates through processes cyclically.

Performance: If there are $n$ processes with quantum $q$ , each process gets $1/n$ of the CPU, and the maximum wait before a CPU allocation is $(n-1) \cdot q$ . Response time is bounded.

Choosing $q$ : If $q$ is large, RR approaches FCFS. If $q$ is very small (e.g., 1 ms), the context-switch overhead dominates — a process might spend more time being switched than executing. A rule of thumb: $q$ should be large relative to context-switch time (say 100×), but small enough that most CPU bursts complete within one quantum.

RR provides no starvation and good response time for interactive workloads. It does not optimise turnaround — a job requiring 10 quanta must wait through $(n-1)$ quanta for each of its 10 turns.

Comparison table

Algorithm	Preemptive?	Starvation?	Optimal for…	Drawbacks
FCFS	No	No	Simplicity	Convoy effect, poor average wait
SJF	Optional	Yes	Minimum avg waiting (known bursts)	Must predict burst lengths
SRTF	Yes	Yes	Minimum avg waiting (dynamic arrival)	Must predict; starvation risk
RR	Yes	No	Response time, fairness	Throughput depends on quantum

Summary

FCFS is simple but suffers from the convoy effect.
SJF/SRTF are optimal for waiting time but require burst prediction and risk starvation.
RR guarantees fairness and bounds response time; its performance is quantum-sensitive.
Real schedulers (CFS) blend preemption with fair proportional-share allocation rather than strict SJF or RR.