Shortest Job First Algorithm in operating system

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:

Process Waiting Time
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.
Scroll to Top