Shortest Job First (SJF) Scheduling Algorithm

Introduction

SJF stands for Shortest Job First. It is a CPU scheduling algorithm that tries to reduce the delay caused when short jobs wait behind long jobs.

Unlike FCFS, SJF does not simply follow arrival order. It checks the burst time of the processes that are currently available and chooses the shortest one first.

Core Rule of SJF Scheduling

In SJF scheduling, the operating system selects the available process with the smallest CPU burst time. CPU burst time means the amount of CPU time a process needs before it finishes or blocks.

The version discussed here is non-preemptive SJF. Once a process starts running, it continues until completion or blocking, even if a shorter process arrives later.

SJF improves over FCFS by giving shorter available jobs a chance to finish earlier. This often reduces average waiting time and average turnaround time.

It can also reduce the convoy effect because short jobs are less likely to remain stuck behind long CPU-bound jobs. However, this benefit depends on knowing or predicting burst times accurately.

SJF Scheduling Example

Consider five processes with arrival time and burst time:

At time 0, only P1 has arrived, so P1 runs first. Since this is non-preemptive SJF, P1 continues until it finishes at time 8.

At time 8, P2, P3, P4, and P5 are available. The scheduler chooses the shortest burst time among them, so the order becomes P5, P2, P4, P3.

Metric Calculation

The main formulas are:

• CT: finish time of the process

• TAT: CT - AT

• WT: TAT - BT

• RT: first start time - AT

For example, P2 starts at time 10 and finishes at time 14. Its arrival time is 1 and burst time is 4, so TAT = 14 - 1 = 13, WT = 13 - 4 = 9, and RT = 10 - 1 = 9.

Average TAT = 13.2, average WT = 7.6, and average RT = 7.6.

Strengths and Weaknesses of SJF

Summary

SJF scheduling chooses the available process with the smallest CPU burst time. In the non-preemptive version, a selected process keeps the CPU until it finishes or blocks.

It often gives better average waiting time and turnaround time than FCFS, but it depends on burst-time prediction. Its main limitations are possible starvation of long jobs and weaker responsiveness for newly arrived interactive processes.