Operating System - Shortest Job First (SJF) Scheduling Algorithm

Shortest Job First (SJF) is a CPU scheduling algorithm that selects the process with the smallest execution time (burst time) to execute next. It is a non-preemptive scheduling algorithm (though there's a preemptive version called Shortest Remaining Time First, or SRTF).

Characteristics:

Non-preemptive: Once a process starts execution, it runs till completion.
Optimal in terms of average waiting time (but hard to implement in practice because it requires knowledge of future burst times).
May cause starvation for longer processes if short ones keep arriving.

Terminology:

Arrival Time (AT): Time when a process arrives in the ready queue.
Burst Time (BT): Time required by a process for execution.
Waiting Time (WT): Time a process waits in the ready queue.
Turnaround Time (TAT): Time from arrival to completion.

TAT = Completion Time - Arrival Time
WT = Turnaround Time - Burst Time

Example:

Let’s consider the following set of processes:

Process	Arrival Time (AT)	Burst Time (BT)
P1	0	8
P2	1	4
P3	2	9
P4	3	5

Step 1: Sort by Arrival Time

Already sorted.

Step 2: Start scheduling based on SJF

Time 0:

Only P1 is available → Execute P1.

Time 8:

P2, P3, and P4 have arrived.
Among them, P2 (BT=4) is the shortest → Execute P2.

Time 12:

P3 (BT=9) and P4 (BT=5) remain.
P4 is shorter → Execute P4.

Time 17:

Only P3 remains → Execute P3.

Schedule Order:

P1 → P2 → P4 → P3

Calculate Completion, Turnaround, and Waiting Time:

Process	AT	BT	Completion Time	TAT = CT - AT	WT = TAT - BT
P1	0	8	8	8	0
P2	1	4	12	11	7
P4	3	5	17	14	9
P3	2	9	26	24	15

Average Waiting Time:

$0+7+9+154=314=7.75\frac{0 + 7 + 9 + 15}{4} = \frac{31}{4} = 7.75$

Average Turnaround Time:

$8+11+14+244=574=14.25\frac{8 + 11 + 14 + 24}{4} = \frac{57}{4} = 14.25$

Pros:

Minimizes average waiting time (theoretically optimal).

Cons:

Hard to predict exact burst times.
Long processes can suffer starvation.