Shortest Job First (SJF) scheduling, explained

Shortest Job First picks, from the processes that are waiting, the one that needs the least CPU time, and runs it to completion.

Letting short jobs go first gets many processes out of the way quickly, which brings the average waiting time down.

How it works

• Collect the processes that have arrived and are not finished.
• Pick the one with the shortest burst time. Ties go to the earlier arrival, then to the input order.
• Run it until it finishes. This version cannot be interrupted.
• Repeat until all processes are done.

A small example

Four processes, A to D:

Arrival times: 0 2 4 5
Burst times:   7 4 1 4

With SJF, A runs first because it is the only process at time 0. After it, C (1 unit) goes first, then B, then D. The average waiting time is:

4.0 time units

FCFS gave 4.75 on the same processes.

What to know about its cost

• When all processes are ready at the same time, running the shortest first gives the lowest possible average waiting time.
• It needs to know each burst time in advance, which real systems can only estimate.
• It is non-preemptive.

Where it works well

• Low average waiting time.
• Short jobs finish quickly.

Where it struggles

• Starvation: a long process can wait forever if short ones keep arriving.
• Burst times are not usually known in advance.

Try it yourself

Open the CPU Scheduling experiment, enter the processes from this post, choose Shortest Job First and step through the Gantt chart. Then try the other algorithms on the same processes and compare the averages.

Open the CPU Scheduling experiment