CONCEPTS-Shortest Remaining Time First(SRTF)

Algorithm


Shortest Remaining Time First Algorithm

Shortest Remaining Time First (SRTF) is the preemptive version of Shortest Job Next (SJN) algorithm, where the processor is allocated to the job closest to completion. This algorithm requires advanced concept and knowledge of CPU time required to process the job in an interactive system, and hence can’t be implemented there. But, in a batch system where it is desirable to give preference to short jobs, SRT algorithm is used.

However, SRT involves more overheads than SJN, as the OS is required to frequently monitor the CPU time of the jobs in the READY queue and perform context switching.

What is SRTF (Shortest Remaining Time First) Scheduling Algorithm?

Shortest remaining time, also known as shortest remaining time first (SRTF), is a scheduling method that is a preemptive version of shortest job next scheduling. In this scheduling algorithm, the process with the smallest amount of time remaining until completion is selected to execute. Since the currently executing process is the one with the shortest amount of time remaining by definition, and since that time should only reduce as execution progresses, the process will either run until it completes or get preempted if a new process is added that requires a smaller amount of time.

Algorithm:

>> Example :

The following chart shows the arrival time and burst time of processes P1,P2,P3.



  1. At the 0th unit of the CPU, there is only one process that is P1, so P1 gets executed for the 1 time unit.
  2. At the 1st unit of the CPU, Process P2 arrives. Now, the P1 needs 6 more units more to be executed, and the P2 needs only 3 units. So, P2 is executed first by preempting P1.
  3. At the 3rd unit of time, the process P3 arrives, and the burst time of P3 is 4 units which is more than the completion time of P2 that is 1 unit, so P2 continues its execution.
  4. Now after the completion of P2, the burst time of P3 is 4 units that means it needs only 4 units for completion while P1 needs 6 units for completion.
  5. So, this algorithm picks P3 above P1 due to the reason that the completion time of P3 is less than that of P1
  6. P3 gets completed at time unit 8, there are no new processes arrived.
  7. So again, P1 is sent for execution, and it gets completed at the 14th unit.


    8. The waiting time(turn around time-burst time) of P1,P2,P3 are 7,0,1 respectively. So the average waiting time = (7+0+1)/3 = 2.66 ms