Improved shortest job first CPU scheduling algorithm

Abstract

CPU scheduling is one of the most important tasks of the Operating System (OS). Among the traditional scheduling technique, Shortest Job First (SJF) scheduling is an excellent choice for minimizing the average waiting time of a group of available processes. It is notable for allocating less average waiting time to available processes and more waiting time to processes that require more time to complete execution. When small processes arrive in large numbers on a regular basis, long processes become starved. This paper proposed an improved scheduling strategy to aid task scheduling while minimizing the starvation problem associated with the shortest Job First algorithm thus providing a better and more efficient waiting time for processes with longer burst times. The method took an innovative approach by first giving the CPU the shortest burst time and then using the average of the remaining sorted burst timings. The proposed technique was built and compared against other algorithms utilizing two different statistical distributions (namely Poisson and Binomial distributions). When compared with other improved algorithms like SRDQ, HYRR, and ADRR, the proposed technique achieved better Average Waiting Time and Turnaround time for processes with longer burst times in all statistical distributions while reducing starvation. The implementation was done using simulation for observing the behavior of the CPU scheduling algorithms and the simulator was written in java, specifically in NetBeans IDE 6.9.1.