Consider an arbitrary set of CPU-bound processes with unequal CPU burst lengths submitted at the same time to a computer system. Which one of the following process scheduling algorithms would minimize the average waiting time in the ready queue?

Option 1 : Shortest remaining time first

Concept:

Waiting time:

It is the total time spent by the process in the ready state waiting for CPU.

Shortest remaining time first:

This algorithm is the pre-emptive shortest job first algorithm and optimal. In this process having small running time remaining until completion are selected to execute first, this can also cause starvation. But in shortest remaining time first algorithm, turnaround time, waiting time is minimum and CPU utilization is high.

Example:

For shortest remaining time first,

Gantt chart:

0            1               2              3              5              9            15

Average waiting time in SRTF = 3.67 ms (Burst time are in ms)

For round robin scheduling with TQ = 1

Gantt chart:

0     1      2      3      4      5      6      7      8      9     10    11    12   15

Average waiting time in RR = 6.33 ms

For uniform random (say FCFS)

Gantt chart:

0               5               12             15

Average waiting using FCFS = 4.67 ms

Priority scheduling algorithm:

In this example, average waiting time for this = 4.67 ms

Therefore, Shortest remaining time first algorithm has minimum average waiting time.