The shortest job first algorithm prefers processes that arrive first and have the shortest burst times. It can be both a preemptive and non-preemptive algorithm.
Non-preemptive means that once a process has been removed from the waiting queue and given CPU time, it will execute until completed or terminated. The algorithm removes processes with minimum arrival time from the waiting queue and executes them until the process is completed. The process then shifts the CPU to other processes in the waiting queue.
Preemptive means that if another process arrives with an even shorter burst time after the process with the shortest burst time and arrival time is given CPU time, the CPU cycle is allocated to the process with the shorter burst time.
The following example will help clarify concepts regarding the shortest job first algorithm. For this we will need a list of processes with their arrival and burst times.
The following example makes use of non-preemptive shortest job first to allocate CPU time to each process:
At , the processes P1 and P2 are in the waiting queue. The algorithm selects the one with the shorter burst time, which in this case is P1, to allocate the CPU cycle for the whole duration of its burst time.
At , the burst time for P1 is over. By that time, P3 has also arrived in the waiting queue and has a smaller burst time compared to P2. P3 is given the CPU cycle for its burst time.
At , the burst time for P3 is over. By this time, P4 has also arrived in the waiting queue. As it has a shorter burst time than P2, P4 is given the CPU cycle.
At , the CPU cycle is given to P2 as it is the last process in the waiting queue.
The following example makes use of preemptive shortest job first to allocate CPU time to each process. The processes and their arrival and burst times are given below:
At , process P1 arrives into the waiting queue. As it is the only process, it is given the CPU cycle at this point.
At , the process P2 arrives into the waiting queue. Its burst time is 4, which is less than the remaining burst time of 5 seconds for P1. Hence, P2 is assigned the CPU cycle and P1 is placed back in the waiting queue as it’s not finished executing.
At , process P3 also arrives into the waiting queue. Now, the comparison is between P1, P2, and P3 for the shortest burst time. The remaining burst time for P1 is 5, P2 is 2, and P3 is 6. Hence, P2 is allowed to continue executing as it still has the shortest burst time. Process P3 is kept in the waiting queue.
At , the process P4 arrives in the waiting queue. Now, the comparison is between processes P1, P2, P3, and P4. The remaining burst times for each are 5, 2, 6, and 1, respectively. Having the shortest burst time, P4 is given the CPU cycle. The process P2 is added back to the waiting queue as it has not completed execution yet.
At , the process P4 completes execution. Now, the comparison of burst times for assigning the CPU cycle is between P1, P2, and P3. The processes have a remaining burst time of 5, 2, and 6, respectively. Hence, the CPU cycle is given to P2 for the rest of its burst time. This is because no new processes arrive in the waiting queue after 4 seconds.
At , the process P2 has completed execution. Now, the comparison between burst times is for P1 and P3. They have remaining burst times of 5 and 6, respectively. Hence, process P1 is given the CPU cycle for the rest of its burst time.
At , only process P3 is remaining in the waiting queue, as P1 is done executing. Hence, the CPU cycle is assigned to P3 for the rest of its burst time.
Following are some of the advantages and disadvantages of the shortest job first scheduling:
Advantages | Disadvantages |
Optimal in terms of average turnaround time | Burst time should be known beforehand |
Optimal for batch processes where burst time is known beforehand | Can lead to starvation of processes that arrive later with larger burst times |
Shorter waiting time compared to First In First Out Algorithm | Cannot be used for short term scheduling as one would have to predict the burst times |
Free Resources