Start with the most obvious rule
From the previous guide you have the whole frame: given a ready queue, the scheduler must pick who runs next, and we judge its choice by the five yardsticks. So put yourself in the scheduler's seat and ask the laziest possible question: what is the simplest rule that could ever work? The answer is the one any fair-minded child would shout — whoever got here first goes first. That is first-come, first-served (FCFS), and it is exactly the queue at a bakery: take a numbered ticket, and you are served strictly in ticket order.
FCFS is non-preemptive (recall the preemptive versus non-preemptive split): once a process starts its CPU burst, it runs to the very end of that burst — until it blocks for I/O or finishes — and only then does the next ticket-holder get a turn. The implementation is almost embarrassingly cheap: a single first-in-first-out queue. A new process joins the back; the scheduler always takes from the front. No timers, no comparisons, no cleverness. That simplicity is FCFS's only real virtue, so let us see what it costs.
Trace FCFS and meet the convoy
Numbers make the flaw unforgettable. Suppose three processes all arrive at time 0, already in the ready queue, and we know their CPU-burst lengths: P1 needs 24, P2 needs 3, P3 needs 3 (in whatever time unit you like — call them milliseconds). They happen to arrive in the order P1, P2, P3, so FCFS runs them in exactly that order. Let us lay it on a timeline and compute each process's waiting time — the time it spends sitting in the queue before it first gets the CPU.
Order P1, P2, P3 (FCFS): 0 24 27 30 | P1 | P2 | P3 | wait: P1=0 P2=24 P3=27 avg wait = (0+24+27)/3 = 17 Order P2, P3, P1 (shortest first): 0 3 6 30 |P2 |P3 | P1 | wait: P2=0 P3=3 P1=6 avg wait = (0+3+6)/3 = 3
Look at what happened. In the first order, the two tiny jobs P2 and P3 were stuck behind the 24-unit monster P1, even though they each needed only 3 units of work. Their wait — and therefore their turnaround time — ballooned for no good reason. This is the famous convoy effect: one long process at the front of the queue makes every short process pile up behind it, like a single slow truck on a one-lane road forcing a whole convoy of fast cars to crawl. The cars are not slow; they are just trapped. In a real OS the trapped jobs are often the interactive ones you are waiting on, so the convoy is exactly what makes a busy machine feel like it has frozen.
Flip it around: shortest job first
The trace already hinted at the cure. The second ordering — P2, P3, then P1 — was not a trick; it was a policy: always run the process with the shortest next CPU burst first. That is shortest-job-first (SJF). Instead of honouring arrival order, the scheduler peeks at how much work each ready process needs and serves the smallest one next. Intuitively this is the supermarket express lane: letting the person with two items go ahead of the person with a full cart keeps the average wait down for everybody, because the quick ones clear out fast and stop blocking the line.
Here is the genuinely beautiful part, and it is not just a nice feeling — it is a theorem. SJF gives the minimum possible average waiting time for any fixed set of processes. No other ordering can beat it. The reasoning is short: average waiting time is dominated by how many jobs have to wait behind each job, so you want the jobs that block the fewest units of other-people's-time to go first — and those are precisely the shortest ones. Putting a short job ahead of a long one always helps more processes than it hurts. So among all schedulers that look only at burst length, SJF is provably optimal. That is a rare and lovely thing to be able to say in systems work.
The catch: SJF needs to know the future
If SJF is provably optimal, why does any real system ever use anything else? Because of one quietly devastating assumption hidden in the phrase shortest job. To run SJF you must know, before a process runs, how long its next CPU burst will be. But that number lives in the future — it depends on data the program has not read yet, branches it has not taken, loops whose counts it does not know. The scheduler cannot truly know it. SJF, taken literally, requires a fact that is unknowable at decision time. This is the honest heart of the algorithm: it is optimal and unimplementable, both at once.
So real schedulers do the only honest thing available: they guess, and they guess from history. A program's recent bursts are a decent clue to its next one — an editor waiting on keystrokes tends to keep having short bursts; a compiler grinding through code tends to keep having long ones. The standard trick is an exponential average, which blends the most recent measured burst with the running estimate, leaning on recent behaviour but never forgetting the past entirely. The result is not SJF; it is approximate SJF, a prediction. It is usually good, and sometimes wrong, and that gap between the provable ideal and the guessable reality is a theme you will meet again and again.
Adding teeth: SRTF and the danger of starvation
Plain SJF is non-preemptive: once a job starts, it finishes its burst even if a shorter job arrives mid-stream. We can make it sharper by letting new arrivals interrupt. The preemptive version is shortest-remaining-time-first (SRTF): at every moment, run the process whose REMAINING burst is smallest, and the instant a new process arrives with a shorter remaining time than what is running, preempt — yank the CPU away (remember, that is a clean preemption back to Ready, not a block). If a 2-unit job arrives while a job with 5 units left is running, SRTF stops the big one and runs the little one first. It pushes average waiting time even lower than non-preemptive SJF.
But sharper teeth bite somebody. Both SJF and SRTF share a dark side: a long job can wait forever. If short jobs keep streaming in — and on a busy server they do — a big job may never be the shortest, so it never gets the CPU. This is starvation: a process indefinitely denied service not because it is broken, but because the policy always finds someone more deserving. It is the patient elderly customer at the deli who is repeatedly skipped because someone with just one item keeps walking up. FCFS, for all its convoy misery, at least guarantees you will eventually reach the front; SJF and SRTF make no such promise.
So we end with an honest scorecard. FCFS is trivially simple and starvation-free but suffers the convoy effect and gives terrible average waiting time when a long job leads. SJF is provably optimal for average waiting time but needs an unknowable future and can starve long jobs. SRTF is even better on waiting time but preempts more and starves even more eagerly. Neither extreme is usable as-is. The next guide takes the missing idea — give everyone a fair, bounded turn instead of running anyone to completion — and turns it into round robin, where a single knob, the time quantum, lets us trade responsiveness against overhead.