How Shortest Job First works
Shortest Job First (SJF) makes one decision each time the CPU becomes free: out of the processes that are already waiting, it runs the one with the smallest burst. Once a process starts, it runs to the end, even if a shorter one arrives a moment later. This page covers that non-preemptive form. The version that interrupts for a shorter newcomer has its own page, Shortest Remaining Time First.
Only processes that have arrived are candidates. A 1-unit job arriving at time 5 cannot be chosen at time 4, however short it is. When two waiting processes have the same burst, Trace picks the one that arrived earlier, and if they also arrived together, the lower process number.
The idea behind SJF is that a short job finishing early shortens the wait of everyone queued behind it, while a long job finishing early helps nobody much. When all the processes are ready at the same moment, running them shortest first gives the lowest possible average waiting time of any order.
The catch is that the scheduler has to know each burst before it runs. Exercises give you the numbers, but a real system can only guess. Textbook treatments often estimate the next burst of a process from the lengths of its previous bursts, for example with an exponential average. SJF also risks starvation: if short jobs keep arriving, a long job can be passed over again and again.
Worked example
Four processes arrive at time 0 with bursts of 6, 8, 7 and 3. With everything ready at once, SJF simply sorts by burst: P4 (3), then P1 (6), P3 (7) and P2 (8).
SJF. Order of execution: P4 0 to 3, P1 3 to 9, P3 9 to 16, P2 16 to 24.
| Process | Arrival | Burst | Finished | Turnaround | Waiting | Response |
|---|---|---|---|---|---|---|
| P1 | 0 | 6 | 9 | 9 | 3 | 3 |
| P2 | 0 | 8 | 24 | 24 | 16 | 16 |
| P3 | 0 | 7 | 16 | 16 | 9 | 9 |
| P4 | 0 | 3 | 3 | 3 | 0 | 0 |
| Average | 13 | 7 | 7 |
The average waiting time is (3 + 16 + 9 + 0) / 4 = 7. Running the same four processes in arrival order, as FCFS would, gives waits of 0, 6, 14 and 21, an average of 10.25. The difference comes entirely from letting P4 go first instead of last.
Formulas
- Turnaround time
= finished - arrival - Waiting time
= turnaround - burst - Response time
= first run - arrival
In the example, P2 is the longest job and runs last: it finishes at 24, so its turnaround is 24 and its waiting time is 24 - 8 = 16. As in every non-preemptive algorithm, each process runs in one piece, so its response time equals its waiting time.
Strengths and weaknesses
Strengths
- The lowest average waiting time of any order when all jobs are ready together and their bursts are known.
- Short jobs finish quickly, which makes the system feel faster for them.
- No preemption, so each process runs in one piece with no switching cost.
Weaknesses
- Needs burst lengths in advance, which real systems can only estimate.
- Long jobs can starve if shorter ones keep arriving.
- A short job that arrives just after a long one has started must wait for all of it.
Common exam mistakes
- Interrupting the running job. In non-preemptive SJF a shorter arrival waits until the current job finishes. Switching on arrival is SRTF, a different algorithm with different answers.
- Choosing a job that has not arrived yet. At each decision, look only at processes whose arrival time is at or before the current time.
- Breaking ties by process number first. Between equal bursts, the earlier arrival goes first; the process number only decides when arrival times match too. Many courses break ties by arrival order, which is what Trace does. Check yours.
- Calling SJF optimal in every case. Its guarantee holds for average waiting time with known bursts. It says nothing about fairness, and long jobs can be delayed without limit.
Related
Spotted a mistake?
Tell me which number or sentence looks wrong, and include the link from "Copy link" if you changed the processes, so I can reproduce exactly what you saw.
Email: abdul at abmans dot com