Shortest Remaining Time First Scheduling Algorithm

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.

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

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

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;

}

You can also try this code with Online C++ Compiler

Run Code

Output

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:

• Operating System
• Unix File System
• File System Routing
• File Input/Output
• FCFS Scheduling
• Shortest Job First Scheduling Algorithm
• Shortest Job First(Non-Preemptive)
• Open Source Operating System
• Free Space Management in OS
• Yarn vs NPM
• Multiprocessing in Operating System

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!