In this tutorial, we will learn about shortest remaining time first scheduling algorithm. We will see different examples that demonstrates the use of shortest remaining time first scheduling.
As the name suggests, it selects the process for execution which has the smallest amount of time remaining until completion.
Shortest Remaining Time First Scheduling is a preempted version of SJF (Shortest Job First). In SJF, once a process begins execution, it runs till completion. In SRTF a running process may be preempted by a user process with a smallest estimated run time.
Let us take an example to understand
1.1 Non Preemptive Shortest Job First Scheduling
We can represent above processes execution as below –
In non-preemptive we consider the arrival time as 0 for all the processes.
The process which has the shortest burst time will be executed first. Here, the process P4 has the shortest burst time. It will run for 3 units of time and completes the execution.
Then the process P1 is executed for 6 units of time following which the process P3 is picked from the ready queue and finishes the execution.
Now the remaining process is P2 which will execute for 8 units of time and finish its execution. Thereby, in SJF the execution will focus on the process that has the smallest time.
1.2 Preemptive Shortest Job First Scheduling
We can also represent execution of above processes using GANTT chart as below –
At AT = 0, P1 Process is picked from the ready queue and executed for 1 unit of time. In SRTF a process should not be executed till completion. It is better to execute process per unit time and meanwhile check for any other processes is in queue.
At AT = 1, the processes P1 and P2 are in the queue. We need to check which process is taking less time. Here, P2 is taking less time. So, P2 will execute for 1 unit of time.
At AT = 2, the processes P1, P2 and P3 are in the queue. Since process P3 is taking lesser time compared to P1 and P2, process P3 will execute for 1unit time.
At AT = 3, P4 has 1 unit burst time. So, P4 will execute and finish the process execution.
At AT = 4, the processes P1, P2, P3 and P5 are in the queue. Here, the processes P3 and P5 have the same burst time. In this case, the process which is scheduled first will execute first. So, P3 will execute first and finish the process execution.
At AT = 5, all the processes are in queue except P4 and P3 as they have completed their execution. So now the process that has the least burst time will execute first. P6 will execute first after that P5, then P2 and at last P1 will execute.
Note: It is not going to be Convoy effect. Starvation doesn’t happen here because the shortest process will execute first.
Advantages of SRTF Scheduling
(i) Many processes execute in less amount of time. So, throughput is increased.
(ii) Processes which have short burst time run fast.
Disadvantages of SRTF Scheduling
(i) Practically it is not possible to predict the burst time.
(ii) Processes which have long burst time will have to wait for long time for execution.
That’s end of tutorial on Shortest Remaining Time First Scheduling.