SJF scheduling, step by step

0 / 6

Shortest Job First (SJF) Scheduling

The process with the shortest run time in the ready queue runs first. It is non-preemptive, so even if a shorter process arrives while one is running, it waits until the current process finishes. Handling short jobs first lowers the average waiting time.

At a bank: when the person at the counter is done, the next one called is the waiting customer whose errand will take the least time.

1 / 6

0ms: P1 starts running

P1 is the only one in line, so it runs right away. Even if a shorter process arrives later, P1 runs to the end because this is non-preemptive.

2 / 6

1–3ms: P2, P3 and P4 join the line

P2 arrived at 1ms, P3 at 2ms and P4 at 3ms. P2 and P4 are shorter than P1, but because this is non-preemptive, all three wait until P1 finishes.

3 / 6

5ms: the shortest, P4, runs first

P1 has finished, so the next one is picked. Run times are P2 3ms, P3 8ms and P4 2ms, so P4 is the shortest. It arrived last but runs first.

4 / 6

7ms: P4 finishes and P2 runs

Of the remaining P2 (3ms) and P3 (8ms), the shorter P2 runs.

5 / 6

10ms: P2 finishes and P3 runs

The longest, P3, is last. If short processes keep coming in, a long process like P3 can be pushed back indefinitely (starvation). HRN was created to reduce this problem.

6 / 6

18ms: all done

Waiting times are P1 0ms, P2 6ms, P3 8ms and P4 2ms, an average of 4ms. That is shorter than FCFS (average 5.75ms), but longer than the preemptive SRT (average 3.5ms), because the short P2 and P4, which arrived while P1 was running, had to wait until P1 finished.

Figure showing SJF scheduling: each time a process finishes, the one with the shortest run time in the ready queue is picked to run, and how long each process waited

CPU Scheduling at a glance

Figure showing SJF scheduling: each time a process finishes, the one with the shortest run time in the ready queue is picked to run, and how long each process waited