Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024
Easy

Shortest Remaining Time First Scheduling Algorithm

gp-icon
Operating system track
Free guided path
14 chapters
83+ problems
gp-badge
Earn badges and level up

Introduction

SRTF (Shortest Remaining Time First) is an algorithm in computer scheduling. It prioritizes processes based on their remaining burst time, executing the one with the shortest time remaining first.

In this blog, we will discuss one of the most important scheduling policies namely, Shortest Remaining Time First Scheduling Algorithm. So, without wasting time, let’s get started.

Shortest Remaining Time First Scheduling Algorithm

What is Shortest Remaining Time First (SRTF) Algorithm?

This Algorithm is the preemptive variant/version of the SJF scheduling algorithm. If it is asked in the questions to solve a scheduling problem using the SJF scheduling algorithm and apply preemption as well, then the overall algorithm will turn out to be SRTF Scheduling Algorithm. The execution of a process in SRTF can be terminated after a given length of time. When a process arrives, the short-term scheduler selects the process with the shortest remaining burst time from the list of available processes and the running process.

No preemption will be performed after all processes are available in the ready queue, and the algorithm will operate as SJF scheduling. Why? Because, once all the processes are in the ready queue, the process with minimum burst time will continue to be the minimum after every unit of execution till it is completely executed.

When a process is removed from execution and the next process is scheduled, the context of the process is saved in the Process Control Block (PCB). On the next execution of this process, this PCB is accessed to reload necessary information like where to start execution, how much time is left, etc.

Criteria used when multiple processes are competing to be executed: Shortest Burst Time Left.

Recommended Topic, FCFS Scheduling Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Example

Consider the set of the following 4 processes with their arrival and burst times. The task is to compute the scheduling based on SRTF Scheduling Algorithm.

Process Number Arrival Time(AT) Burst Time(BT)
P0 0 5
P1 1 3
P2 2 4
P3 4 1

Major Points

Till all processes are not in the ready queue, after executing the current process for a unit time, we will check if any other process with a shorter burst time has arrived in the ready queue.
We will compute the Completion Time (CT), Turn-Around Time (TAT), Waiting Time (WT), and Response Time for each process.

Gantt Chart

Process P0 P1 P1 P3 P0 P2 P2
Execution Times                                                0                1 1             2 2             3 3            4 4              5 5          9 9          13

Note: In the case of two processes with equal burst times competing to be executed at the same time, we choose the process with lower Process Number.

Let us see in detail how these processes are being executed.

  • There is only one process, P0, at the 0th unit of the CPU, hence P0 runs for 1 time unit.
     
  • At 1 unit, process P1 arrives, and its burst time (i.e., 3) is less than the remaining burst time of P0 (i.e., 4). So process P0 is preempted from the CPU is P1 starts executing.
     
  • P1 executes for 2 units. At 2, process P2 comes. But the burst time of P2 (i.e., 4) is more than the burst time of P1. So P1 still executes.
  • Now, P1 is at 3 units, and no process is at 3. So P1 continues its execution.
     
  • At 4 units, P1 completes its execution. Here process P3 arrives. As its burst time is lower than processes P0 and P2, it starts executing.
  • P3 completes its execution at 5 units. 
     
  • Now, at 5 units, P0 starts its execution again because its remaining burst time is 4 units, and it arrived prior to P2. 
     
  • After P0 completes its execution at 9 units, P2 starts its execution and continues till 13 units. 

Important Parameters Calculation

Process Number Completion Time(CT) TAT=CT - AT WT= TAT - BT RT=CPY First TIme - AT
P0 9 9 4 0
P1 4 3 0 0
P2 13 11 7 7
P3 5 1 0 0

Note: CPU First Time is the time when it is first scheduled for execution by the Operating System.

Must Read Evolution of Operating System

Implementation

Now, let us see the implementation of SRTF Scheduling.

Code

  • C++

C++

#include <bits/stdc++.h> 
using namespace std;
struct process {
int pid;
int arrival_time;
int burst_time;
int start_time;
int completion_time;
int turnaround_time;
int waiting_time;
int response_time;
};
int main() {
int x;
struct process p[100];
float avg_turnaround_time;
float avg_waiting_time;
float avg_response_time;
float cpu_utilization;
int total_turnaround_time = 0;
int total_waiting_time = 0;
int total_response_time = 0;
int total_idle_time = 0;
float throughput;
int burst_remaining[100];
int is_completed[100];
memset(is_completed,0,sizeof(is_completed));
cout << setprecision(2) << fixed;
cout<<"Enter the number of processes: ";
cin>>x;
for(int i = 0; i < x; i++) {
cout<<"Enter arrival time of the process "<<i+1<<": ";
cin>>p[i].arrival_time;
cout<<"Enter burst time of the process "<<i+1<<": ";
cin>>p[i].burst_time;
p[i].pid = i+1;
burst_remaining[i] = p[i].burst_time;
cout<<endl;
}
int current_time = 0;
int completed = 0;
int prev = 0;
while(completed != x) {
int idx = -1;
int mn = 10000000;
for(int i = 0; i < x; i++) {
if(p[i].arrival_time <= current_time && is_completed[i] == 0) {
if(burst_remaining[i] < mn) {
mn = burst_remaining[i];
idx = i;
}
if(burst_remaining[i] == mn) {
if(p[i].arrival_time < p[idx].arrival_time) {
mn = burst_remaining[i];
idx = i;
}
}
}
}
if(idx != -1) {
if(burst_remaining[idx] == p[idx].burst_time) {
p[idx].start_time = current_time;
total_idle_time += p[idx].start_time - prev;
}
burst_remaining[idx] -= 1;
current_time++;
prev = current_time;

if(burst_remaining[idx] == 0) {
p[idx].completion_time = current_time;
p[idx].turnaround_time = p[idx].completion_time - p[idx].arrival_time;
p[idx].waiting_time = p[idx].turnaround_time - p[idx].burst_time;
p[idx].response_time = p[idx].start_time - p[idx].arrival_time;
total_turnaround_time += p[idx].turnaround_time;
total_waiting_time += p[idx].waiting_time;
total_response_time += p[idx].response_time;
is_completed[idx] = 1;
completed++;
}
}
else {
current_time++;
}
}
int min_arrival_time = 10000000;
int max_completion_time = -1;
for(int i = 0; i < x; i++) {
min_arrival_time = min(min_arrival_time,p[i].arrival_time);
max_completion_time = max(max_completion_time,p[i].completion_time);
}
avg_turnaround_time = (float) total_turnaround_time / x;
avg_waiting_time = (float) total_waiting_time / x;
avg_response_time = (float) total_response_time / x;
cpu_utilization = ((max_completion_time - total_idle_time) / (float) max_completion_time )*100;
throughput = float(x) / (max_completion_time - min_arrival_time);
cout<<endl<<endl;
cout<<"Process\t"<<"Arrival Time\t"<<"Burst Time\t"<<"ST\t"<<"CT\t"<<"TAT\t"<<"WT\t"<<"RT\t"<<"\n"<<endl;
for(int i = 0; i < x; i++) {
cout<<p[i].pid<<"\t"<<p[i].arrival_time<<"\t""\t"<<p[i].burst_time<<"\t""\t"<<p[i].start_time<<"\t"<<p[i].completion_time<<"\t"<<p[i].turnaround_time<<"\t"<<p[i].waiting_time<<"\t"<<p[i].response_time<<"\t"<<"\n"<<endl;
}
cout<<"Average Turnaround Time = "<<avg_turnaround_time<<endl;
cout<<"Average Waiting Time = "<<avg_waiting_time<<endl;
cout<<"Average Response Time = "<<avg_response_time<<endl;
cout<<"Throughput = "<<throughput<<" process/unit time"<<endl;

}

Output

Output of SRTF Scheduling

Advantages of SRTF Scheduling

SRTF algorithm reduces the processing time and makes the processing of the jobs faster as compared to the SJN algorithm.

  • SRTF scheduling minimizes the waiting time for processes by selecting the one with the shortest remaining burst time. This leads to faster turnaround times and improved system responsiveness.
     
  • It optimally utilizes the CPU by selecting the process with the shortest burst time, reducing idle time and enhancing overall system efficiency.
     
  • SRTF is well-suited for environments with dynamic workloads, where the length of CPU bursts varies. It adapts quickly to changing requirements, providing efficient scheduling in scenarios with frequent process arrivals and departures.
     
  • SRTF is responsive to changes in the state of processes. If a shorter job arrives while a longer one is executing, the scheduler can preempt the running job, minimizing the impact of long processes on shorter ones.

Disadvantages of SRTF Scheduling

As compared to the SJN algorithm, the SRTF algorithm does context switch more often, which adds up to the processing time and takes away the advantage of fast processing.

  • The main disadvantage of SRTF is the potential for starvation. If short processes continually arrive, long processes may be continuously delayed, leading to resource starvation and decreased fairness.
     
  • SRTF involves frequent preemptions as the scheduler selects the process with the shortest remaining time. This high level of context switching can result in increased overhead and may impact overall system performance.
     
  • Accurately predicting the remaining burst time for each process can be challenging. Inaccurate estimations may lead to suboptimal scheduling decisions and may not fully exploit the benefits of SRTF.
     
  • Implementing SRTF requires a sophisticated mechanism to track and manage the remaining time of each process accurately. This complexity can result in higher implementation and maintenance costs.

Frequently Asked Questions

What is SRTF in the operating system?

Shortest remaining time, also known as shortest remaining time first (SRTF), is a scheduling method that is a preemptive version of the shortest job next scheduling. In this scheduling algorithm, the process with the smallest amount of time remaining until completion is selected to execute.

What is the difference between SJF and SRTF?

SJF algorithm is generally used in the case of the non-preemptive kernel. We pick the shortest job and process it. But the SRTF algorithm is used in the case of the preemptive kernel. We pick the shortest job, which can be preempted in case a further shorter one arrives.

What is the most efficient scheduling algorithm?

The efficiency of scheduling algorithms depends on the system's characteristics. Shortest Job Next (SJN) or Shortest Job First (SJF) can be efficient for minimizing waiting times and improving turnaround.

Which scheduling is fastest?

The fastest scheduling algorithm is Shortest Job Next (SJN) or Shortest Job First (SJF) as it selects the process with the shortest burst time, minimizing execution time.

Conclusion

In this article, we have extensively discussed the Shortest Remaining Time First Scheduling Algorithm. We have discussed its efficiency in minimizing waiting times and optimizing CPU utilization. It is  also known as Shortest Job Next (SJN) or Preemptive Shortest Job First (PSJF), is a CPU scheduling algorithm in operating systems. It is a preemptive version of the Shortest Job First (SJF) algorithm. 

Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
FCFS Scheduling
Next article
Program for First Come First Serve Scheduling
Guided path
Free
gridgp-icon
Operating system track
14 chapters
83+ Problems
gp-badge
Earn badges and level up
Live masterclass