Shortest Job First (SJF)

When the CPU frees up, look at every process that has already arrived, and dispatch the one with the smallest burst time. Ties are broken FCFS. This version is non-preemptive: a process that gets the CPU keeps it even if a shorter job shows up a moment later. (The preemptive version is a separate topic — SRTF.)

“Already arrived” is the rule that decides most exam answers. SJF cannot pick a process that has not shown up yet, however short it is.

The claim is precise: for a fixed set of processes available at the same time, SJF minimises average waiting time. The argument is a swap argument. Suppose a long job runs before a short one. Swapping them lowers the short job's waiting time by the long job's burst, and raises the long job's by the short one's — a smaller amount. Every such swap improves the average, so the sorted-by-burst order must be the best one.

Concretely, four processes all arriving at t = 0 with bursts 6, 8, 7 and 3:

A scheduler does not know how long the next burst will be. So real systems predict it from history, on the assumption that a process which has been short tends to stay short. The standard method is an exponential moving average:

τ(n+1) = α · t(n) + (1 − α) · τ(n) — where t(n) is the burst just observed, τ(n) was the previous prediction, and α (commonly 0.5) sets how heavily recent behaviour counts. α = 0 ignores history's latest entry entirely; α = 1 predicts purely from the last burst.

Arrival time

When the process shows up in the ready queue. The scheduler cannot pick something that has not arrived yet — that single rule decides most exam answers.

Burst time

How long this process needs the CPU for, uninterrupted, before it would block or finish. Also called CPU burst.

Ready queue

Every process that could run right now but does not have the CPU. Scheduling is entirely the question of who gets pulled out of here next.

Preemptive vs non-preemptive

A non-preemptive scheduler cannot take the CPU back — once dispatched, a process runs until it blocks or finishes. A preemptive one can interrupt it mid-burst.

Context switch

Saving one process's registers and loading another's. Pure overhead: real work stops while it happens, typically a few microseconds.

Starvation

A process that stays runnable but never gets picked, because something more attractive keeps arriving. The classic fix is ageing — slowly raising the priority of anything that has waited a long time.

If short jobs keep arriving, a long job can sit in the ready queue indefinitely — it is never the shortest. It is not deadlocked and nothing is broken; it is simply never chosen. Systems that use burst-based scheduling in practice add ageing so waiting time eventually beats shortness.