Shortest Job First Algorithm
Shortest Job First (SJF) is an algorithm in which the process having the smallest execution time is chosen for the next execution. This scheduling method can be preemptive or non-preemptive. It significantly reduces the average waiting time for other processes awaiting execution. The full form of SJF is Shortest Job First.
Characteristics
- It is associated with each job as a unit of time to complete.
- This algorithm method is helpful for batch-type processing, where waiting for jobs to complete is not critical.
- It can improve process throughput by making sure that shorter jobs are executed first, hence possibly have a short turnaround time.
- It improves job output by offering shorter jobs, which should be executed first, which mostly have a shorter turnaround time.
Advantages
- It is optimal for minimizing the queuing time.
- It is easy to implement in batch systems as we know in this we know the required CPU time.
- It’s average waiting time, or AWT is minimum amongst all the scheduling algorithms.
Disadvantages
- It is challenging to implement in the interactive system as we don’t know the required CPU time here.
- Usually, run times are not known in this scheduling.
- If the arrival time of the processes is different, i.e. different processes arrive at different time for the execution, then sometimes, the process which has shortest burst time will have to wait so that the current process can finish its performance. The reason behind this is its non-preemptive mode as in this the current process is not halted in between on arrival of shortest burst process.This brings the starvation problem which is solved by the process of ageing.
Example
| Process |
Arrival Time |
Burst Time |
| P1 |
2 |
6 |
| P2 |
5 |
2 |
| P3 |
1 |
8 |
| P4 |
0 |
3 |
| P5 |
4 |
4 |
Working
- Step 0) At time=0, P4 arrives and starts execution.
- Step 1) At time= 1, Process P3 arrives. But, P4 still needs 2 execution units to complete. It will continue execution.
- Step 2) At time =2, process P1 arrives and is added to the waiting queue. P4 will continue execution.
- Step 3) At time = 3, process P4 will finish its execution. The burst time of P3 and P1 is compared. Process P1 is executed because its burst time is less compared to P3.
- Step 4) At time = 4, process P5 arrives and is added to the waiting queue. P1 will continue execution.
- Step 5) At time = 5, process P2 arrives and is added to the waiting queue. P1 will continue execution.
- Step 6) At time = 9, process P1 will finish its execution. The burst time of P3, P5, and P2 is compared. Process P2 is executed because its burst time is the lowest.
- Step 7) At time=10, P2 is executing and P3 and P5 are in the waiting queue.
- Step 8) At time = 11, process P2 will finish its execution. The burst time of P3 and P5 is compared. Process P5 is executed because its burst time is lower.
- Step 9) At time = 15, process P5 will finish its execution.
- Step 10) At time = 23, process P3 will finish its execution.
Gantt Chart
| P4 |
P1 |
P2 |
P5 |
P3 |
| 0 - 3 |
3 - 9 |
9- 11 |
11 - 15 |
15 - 23 |
Final Table
| Process |
Arrival Time |
Burst Time |
Completion Time |
Turn Around Time |
Waiting Time |
Response Time |
| P1 |
2 |
6 |
9 |
7 |
1 |
1 |
| P2 |
5 |
2 |
11 |
6 |
4 |
4 |
| P3 |
1 |
8 |
23 |
22 |
14 |
14 |
| P4 |
0 |
3 |
3 |
3 |
0 |
0 |
| P5 |
4 |
4 |
15 |
11 |
7 |
7 |