Mean Interleaved Round Robin Algorithm: A Novel CPU Scheduling Algorithm for Time Sharing Systems

摘要

In round robin scheduling algorithm, the scheduler preempts a process when time slice (δ) expires and picks up the next processes in the ready queue for execution. A potential problem that we observed with the traditional round robin scheduling algorithm is: when the time slice increases, both the average waiting time and the turnaround time are also increasing instead of decreasing. This paper proposes a remedy for the observed problem which works as follows calculate the mean burst time (m) of all the processes in the ready queue. Then insert m at its appropriate position in the sorted ready queue. With this the ready queue is divided into two parts: the first part contains the burst times, b1, b2,...bi-1, which are smaller than m and the second part contains burst times bi+1,bi+2....bn+1, which are greater than or equal to m. now pickup the process p1 with burst time b1 from the sorted ready queue,assign it to CPU and execute it for one time slice (δ). Next pickup the process pi+1 with burst time bi+1 from the sorted ready queue and execute it for another δ. This process is repeated until all the jobs in the ready queue complete their execution. Then average waiting time and average turnaround time of all the processes in the ready queue are computed. When the proposed method is applied, it observed that even if the time slice increases, both the average waiting time and the turnaround time are found to be also decreasing.