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:
Time 8:
-
P2, P3, and P4 have arrived.
-
Among them, P2 (BT=4) is the shortest → Execute P2.
Time 12:
Time 17:
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:
Cons:
