Operating System

SRTF Scheduling : Explained

Abstract

In the shortest remaining time first scheduling, jobs are scheduled according to the shortest remaining time. It is a preemptive scheduling algorithm.

Scope

This article talks about SRTF scheduling in detail.

Definition

In the shortest remaining time first scheduling, whenever the new job arrives we compare its burst time with the remaining time of the currently running job and if it is less, then we preempt the currently running job and schedule the newly arrived process. It is a preemptive version of SJF(Shortest Job First) scheduling.

Let us take an example 

PROCESS ARRIVAL TIME BURST TIME
        P0            0          8
        P1            1          4
        P2            2          9
        P3            3          5

The first P0 is scheduled at 0. At time 1 there is one more process that arrived. So when the new process arrives, the remaining burst time of the running process is compared with the burst time of the newly arrived process and if the remaining time of P0 is more than P0 is preempted and P1 is scheduled. It runs for 1 unit and then P2 arrives. The same comparison is done Since P1 has 3 remaining unit times which is less than P2, it is continued to be scheduled. Then P3 arrives whose burst time is 5. Its burst time is 2 more than the remaining time of P2 so P2 is continued to be scheduled until completion. Then P3 is scheduled whose burst time is 5. This runs till completion followed by P2. 

We can understand it further :

PROCESS ARRIVAL TIME BURST TIME
        P0            0        8  7
        P1            1        4   3   2
        P2            2          9
        P3            3          5

Gnatt chart for the process 

Final chart

PROCESSARRIVAL TIME BURST TIMECOMPLETION TIME TURN AROUND TIMEWAITINGTIME 
        P0            0          8      17      17      9
        P1            1          4      5      4      0
        P2            2          9      26    24      15
        P3            3          5      10    7        2

* Turn around time = Completion time – Arrival time 

*Waiting time = Turn around time – Burst time 

So, Average turn around time = (17+4+24+7)/4 = 52/4

and Average waiting time = (9+0+15+2)/4 = 26/4

Some important points 

  • The minimum average waiting time among all scheduling algorithms. The reason we schedule the processes which take less time first..
  • May cause high waiting and response times for CPU-bound processes.
  • It is impractical since it is not possible to know the burst time of every process in the ready queue in advance. 

Summary

SRTF is the preemptive version of SJF scheduling. In SRTF, processes are scheduled according to the shortest remaining time. It provides minimum average time among all scheduling algorithms.

Special thanks to Ami Jangid for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article