Shortest Job First Algorithm in operating system
- Shortest job first a non-preemptive, pre-emptive scheduling algorithm.
- shortest possible waiting time strategy.
- In Batch systems where the necessary CPU time is known, implementation is easy.
- In interactive systems where the necessary CPU time is unknown, implementation is impossible
- The time required for the procedure should be known in advance by the processor.
Given Table process have Execution time and Arrival time,
Waiting time of process:
|P0||0 – 0 = 0|
|P1||5 – 1 = 4|
|P2||14 – 2 = 12|
|P3||8 – 3 = 5|
Average Wait Time: (0 + 4 + 12 + 5)/4 = 21 / 4 = 5.25
Characteristics of SJF Scheduling
- The benefit of using Shortest Job First is that it has the shortest average waiting time out of all scheduling methods.
- This algorithm is greedy.
- It may cause starvation if shorter processes keep coming. This problem can be solved using the concept of ageing.
- OS may not know burst time and may not sort them. While it’s not possible to predict execution time. But several methods used t estimate execution time of job
- SJF used specialized environment where estimation of running time is available
Algorithm of SJF
- Sort every procedure in order of arrival time.
- Then choose the process with the shortest arrival time and burst time.
- Create a pool of processes that will arrive after the one that has just finished, and then choose the one from the pool that has the least amount of burst time.