CPU Scheduling Policies: FCFS, SJF, Priority and Round Robin

The scheduler's trade-off

An operating system's CPU scheduler decides which of many ready processes gets the CPU next, for how long, and what happens when a higher-priority process shows up. Every scheduling policy is a trade-off between three numbers: waiting time (how long a process sits ready but not running), turnaround time (total time from arrival to completion) and response time (time until the first byte of output). Optimising hard for one of these tends to hurt the others, which is why real systems use different schedulers for batch servers, desktops and real-time controllers.

FCFS and SJF: the two extremes

First-Come, First-Served (FCFS) runs processes in arrival order to completion, no preemption. It is trivial to implement and perfectly fair in the naive sense, but it suffers the convoy effect: one long process at the front of the queue makes every short process behind it wait, tanking average waiting time even though the total work done is unchanged.

Shortest Job First (SJF) instead always picks whichever ready process has the smallest remaining burst time. This is provably optimal for minimising average waiting time among non-preemptive policies — a classical exchange-argument result — but it requires knowing burst times in advance, which real schedulers only estimate (typically via an exponentially weighted average of past bursts). Its preemptive version, Shortest Remaining Time First (SRTF), can starve long processes indefinitely if short ones keep arriving.

avg waiting time (non-preemptive) = (1/n) * sum(start_i - arrival_i)
SJF minimises this sum for a fixed, known set of burst times
— but a single misestimated burst can cascade delay onto everyone behind it

Round robin and time slices

Round robin gives every ready process a fixed time quantum (say 10–100 ms), then preempts it and moves it to the back of the queue if it hasn't finished. This bounds the worst-case response time to roughly (n − 1) × quantum for n ready processes, which is why it is the default for interactive systems. The quantum size is the whole game: too large and round robin degenerates toward FCFS with its convoy effect; too small and the system burns an increasing fraction of CPU time on context switches — saving and restoring registers, flushing pipelines and TLB entries — that do zero useful work.

Priority scheduling and starvation

Priority scheduling runs the highest-priority ready process first, static or dynamic. It maps naturally onto real needs (a mouse-cursor thread should preempt a batch compile), but a strict priority order can starve low-priority processes forever if higher-priority work keeps arriving. The standard fix is aging: gradually raise a waiting process's effective priority the longer it sits in the ready queue, guaranteeing it eventually runs no matter what.

effectivePriority(p) = basePriority(p) - k * waitingTime(p)
// lower number = higher priority; waitingTime grows every tick
// eventually even the lowest-priority process outranks new arrivals

Multilevel feedback queues

Production kernels (Linux's CFS lineage, Windows, classic Unix) use variants of a multilevel feedback queue: several round-robin queues at different priority levels and quantum sizes, where a process that uses its entire quantum (CPU-bound behaviour) gets demoted to a lower-priority, longer-quantum queue, while a process that yields early (I/O-bound, interactive behaviour) stays at or moves up to a higher-priority, short-quantum queue. The scheduler never needs to know a process's true nature in advance — it infers it from observed behaviour and adapts, combining the responsiveness of round robin with something close to SJF's efficiency for genuinely short bursts.

Frequently asked questions

Try it live

Everything above runs in your browser — open CPU Scheduling and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.