Shortest Remaining Time First Scheduling Algorithm

Greetings!
We have recently published 100+ articles on android tutorials with kotlin and java. If you need, you may visit Android Tutorial for beginners page. You can also check Kotlin Tutorial for beginners. Also, if you are interested in content writing, you can mail us at tutorialwing@gmail.com.

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

Tutorialwing Shortest Job First Scheduling Example of Shortest Job First Example

Shortest Job First Scheduling Example

Explanation:

We can represent above processes execution as below –

Tutorialwing Shortest Job First Gantt Chart Example of Non Preemptive Shortest Job First Scheduling

Shortest Job First Gantt Chart

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

Tutorialwing Preemptive Shortest Job First Example of preemptive Shortest job first example

Preemptive Shortest Job First Example

Explanation:

We can also represent execution of above processes using GANTT chart as below –

Tutorialwing GANTT chart Representation of Preemptive Shortest Job First Scheduling

GANTT chart Representation

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.

Support Us

If you like Tutorialwing and would like to contribute, you can email an article on any educational topic at tutorialwing@gmail.com. We would love to publish your article. See your article on Tutorialwing and help others with your knowledge. Follow Facebook, LinkedIn, Google+, Twitter, Youtube for latest updates.
Greetings!
We have recently published 100+ articles on android tutorials with kotlin and java. If you need, you may visit Android Tutorial for beginners page. You can also check Kotlin Tutorial for beginners