shortest-job-first scheduling
/ SJF /
If you are at a copy machine and several people are waiting, letting the person with one page go before the person with five hundred makes everyone's average wait shorter. Shortest-job-first (SJF) scheduling applies this intuition to the CPU: among the ready processes, run the one with the smallest next CPU burst first.
Why it is special: SJF is provably optimal at minimizing average waiting time (and hence average turnaround time) for a given set of jobs, in the non-preemptive case. The reason is simple — putting a short job ahead of a long one reduces the short job's wait a lot while delaying the long one only a little, and that trade always lowers the average. So no other non-preemptive ordering can beat SJF on average waiting time.
The catch is the deal-breaker: SJF needs to know the length of each job's next CPU burst before it runs — and you cannot know the future. In practice the OS estimates the next burst from past behavior, usually with exponential averaging: a running guess that blends the most recent actual burst with the old estimate, so a process that has been bursting briefly is predicted to burst briefly again. SJF also risks starving long jobs: if short jobs keep arriving, a long one may never reach the front. It is more a benchmark and a building block than a literal everyday scheduler.
Four jobs ready at once with burst lengths 6, 8, 7, 3. SJF runs them shortest-first: 3, 6, 7, 8. Waiting times are 0, 3, 9, 16, averaging 7 ms — lower than any other order. Running them in arrival order (FCFS) gives a worse average; SJF is the optimum for this metric.
SJF gives the provably lowest average waiting time — if only you knew the burst lengths in advance.
SJF is optimal only on PAPER, because it requires knowing the next burst length, which is unknowable; real systems can only approximate it by predicting bursts, and even then it can starve long jobs.