Today! We are going to explain all possible stuffs about what is SRTF scheduling algorithm in OS; involving with many examples and programs in C, C++, and Java with their outputs. After reading this article, you will be getting fully understood about Shortest Remaining Time First Scheduling with ease.

What is SRTF Scheduling Algorithm in OS?

SRTF (Shortest Remaining Time First) scheduling algorithm is a non-preemptive CPU scheduling algorithm in which the process with the smallest amount of time remaining to complete is selected for execution.

In this algorithm, when a new process arrives, it is compared with the currently running process in terms of the time required for completion. If the new process has a smaller burst time than the currently running process, then the new process is executed immediately, and the currently running process is preempted. If the new process has a larger burst time, it is placed in the ready queue.

Once a process starts executing, it runs until it completes or until a new process arrives with a smaller burst time. This algorithm ensures that the process with the shortest remaining time is always executed first, which minimizes the average waiting time and turnaround time of the processes.

SRTF algorithm is an improvement over the SJF (Shortest Job First) scheduling algorithm, as it takes into account the remaining time of the processes, which makes it more efficient. However, this algorithm may cause starvation of long processes as they have to wait for shorter processes to complete.

‘SRTF Scheduling’ Tutorial Headlines:

In this section, we will show you all headlines about this entire article; you can check them as your choice; below shown all:

What is SRTF Scheduling Algorithm in OS?
SRTF Scheduling Algorithm Example with Gantt Chart
Real Life Example of Shortest Remaining Time First scheduling
SRTF Scheduling Algorithm Implementation
What are the Advantages and Disadvantages of SRTF Scheduling Algorithm?

Advantages of Shortest Remaining Time First Scheduling
Disadvantages of Shortest Remaining Time First Scheduling

SRTF Scheduling Program in C with Arrival Time
SRTF Scheduling Program in C++
SRTF Scheduling Program in Java

Let’s Get Started!!

SRTF Scheduling Algorithm Example with Gantt Chart

SRTF scheduling algorithm is a pre-emptive variant of the SJF (Shortest Job First) algorithm, where the scheduler always chooses the process with the shortest remaining burst time to execute next.

Also Read: Multilevel Queue (MLQ) Scheduling with Examples and Programs!!

Let’s consider an example with four processes, P1, P2, P3, and P4, with the following burst times and arrival times:

Process Arrival Time Burst Time

P1 0 4

P2 1 3

P3 2 1

P4 3 2

At time t=0, P1 arrives, so it is added to the ready queue. The shortest remaining burst time is 4, so P1 starts executing.

At t=1, P2 arrives, and its burst time is 3, which is less than P1’s remaining burst time of 3. So, P1 is preempted, and P2 starts executing.

At t=2, P3 arrives, and its burst time is 1, which is less than P2’s remaining burst time of 2. So, P2 is preempted, and P3 starts executing.

At t=3, P4 arrives, and its burst time is 2, which is less than P3’s remaining burst time of 3. So, P3 is preempted, and P4 starts executing.

At t=5, P4 finishes executing, and there are no more processes in the ready queue.

The Gantt chart for this example would look like:

Time 0 1 2 3 4 5

P1 X X X X

P2 X X

P3 X X

P4 X X X

Here, ‘X’ denotes the execution of a process. As you can see, the SRTF algorithm selects the process with the shortest remaining burst time, resulting in a shorter average waiting time and turnaround time than other scheduling algorithms.

Real Life Example of Shortest Remaining Time First scheduling

A real-life example of SRTF scheduling can be seen in a restaurant where multiple orders are received, and the chef needs to prioritize which order to prepare first. The chef can use SRTF scheduling to determine which order to start with by comparing the time remaining to prepare each order.

Also Read: Multilevel Feedback Queue Scheduling (MLFQ) Algorithm with Examples & Programs!!

For example, if there are two orders: Order A takes 10 minutes to prepare, and Order B takes 5 minutes to prepare, but Order A was started first and has 8 minutes remaining, while Order B has just been placed, the chef will prioritize Order B as it has a shorter remaining time. This ensures that the order with the shortest remaining time is completed first, resulting in faster order processing times and better customer satisfaction.

SRTF Scheduling Algorithm Implementation

START

Read the arrival time and burst time for each process
Initialize the remaining time for each process as the burst time
Set the current time to 0
Repeat until all processes have completed:
Find the process with the shortest remaining time (i.e. the process that will complete next)
Set the start time for this process as the current time
Decrement the remaining time for this process by 1
If the remaining time for this process is 0, calculate its turnaround time and waiting time and move to the next process
Calculate the average waiting time and average turnaround time for all processes
Display the results

END

What are the Advantages and Disadvantages of SRTF Scheduling Algorithm?

Shortest Remaining Time First scheduling algorithm is a pre-emptive CPU scheduling algorithm, in which the process with the shortest remaining burst time is given priority. Here are some advantages and disadvantages of shortest remaining time first scheduling algorithm:

Advantages of Shortest Remaining Time First Scheduling

Here are some of the advantages of SRTF scheduling, as follow them:

Also Read: Priority Scheduling Algorithm in OS with Examples & Programs!!

Shorter Waiting Time: SRTF scheduling provides the shortest average waiting time compared to other scheduling algorithms, such as First-Come-First-Served (FCFS) and Round Robin (RR). This is because the processes with the shortest remaining burst time are executed first, which reduces the waiting time of other processes in the queue.

Better Throughput: SRTF scheduling can achieve a higher throughput than other scheduling algorithms because it minimizes the turnaround time of processes. This means that the CPU is used more efficiently and more processes can be completed within a given time frame.

Reduced Response Time: The response time for short processes is minimized in SRTF scheduling. This is because the shortest process in the queue is executed immediately, which reduces the time taken for a process to get a response from the CPU.

Improved Fairness: SRTF scheduling ensures fairness among the processes. The shorter processes are executed first, and longer processes are executed later, which prevents longer processes from monopolizing the CPU.

Effective for Interactive Systems: SRTF scheduling is ideal for interactive systems where users expect a quick response time. This is because the shorter processes are executed first, which reduces the response time of the system.

Overall, SRTF scheduling can provide better performance than other scheduling algorithms, especially in situations where short processes are frequent and response time is critical.

Disadvantages of Shortest Remaining Time First Scheduling

While this algorithm has some advantages, such as reducing average waiting time, it also has several disadvantages, including:

Also Read: Round Robin Scheduling Algorithm with Examples and Programs!!

Pre-emption Overhead: SRTF scheduling requires frequent pre-emption of running processes, which incurs overhead due to the context switching and the cost of saving and restoring the process state.

Starvation: The algorithm may lead to starvation of long-running processes, as shorter processes constantly pre-empt them. This can lead to a situation where a process never gets a chance to complete its execution.

Complexity: SRTF scheduling requires the scheduler to maintain a list of all the running processes sorted by their remaining execution time. This can be complex and time-consuming, especially when there are many processes.

Predictability: SRTF scheduling is not a predictable algorithm, as it is based on the assumption that the smallest remaining time is always the best choice. However, this may not always be the case, and the scheduler may end up making suboptimal decisions.

No Fairness: SRTF scheduling favors shorter processes, which means that longer processes may not get a fair share of the CPU time. This can lead to a situation where some processes are always waiting for a long time to get CPU time, while others get it frequently.

SRTF Scheduling Program in C with Arrival Time

Sure, here’s an example program in C for Shortest Remaining Time First (SRTF) scheduling algorithm with arrival time:

#include <stdio.h>

struct process {

int pid; // process ID

int arrival_time; // arrival time

int burst_time; // burst time

int remaining_time; // remaining time

};

int main() {

int n, i, j, time, min, index;

struct process p[10];

printf(“Enter the number of processes: “);

scanf(“%d”, &n);

for(i = 0; i < n; i++) {

printf(“\nEnter the arrival time for process %d: “, i+1);

scanf(“%d”, &p[i].arrival_time);

printf(“Enter the burst time for process %d: “, i+1);

scanf(“%d”, &p[i].burst_time);

p[i].pid = i+1;

p[i].remaining_time = p[i].burst_time;

}

time = 0;

for(i = 0; i < n; i++) {

min = 9999;

index = -1;

for(j = 0; j < n; j++) {

if(p[j].arrival_time <= time && p[j].remaining_time < min && p[j].remaining_time > 0) {

min = p[j].remaining_time;

index = j;

}

if(index == -1) {

time++;

i–;

continue;

}

p[index].remaining_time–;

min = p[index].remaining_time;

if(min == 0) min = 9999;

printf(“\nProcess %d at time %d completed, remaining time for this process = %d\n”, p[index].pid, time+1, p[index].remaining_time);

if(p[index].remaining_time == 0) {

p[index].remaining_time = min;

time++;

printf(“Process %d completed at time %d\n”, p[index].pid, time);

p[index].arrival_time = 9999;

}

return 0;

}

This program prompts the user to enter the arrival time and burst time for each process. It then uses the SRTF algorithm to schedule the processes and prints the completion time for each process. The ‘struct process’ contains the process ID, arrival time, burst time, and remaining time. The ‘for’ loop goes through each process and calculates the remaining time for each process.

The ‘if’ statement checks the arrival time of the process is less than or equal to the current time and if the remaining time for the process is less than the minimum time. If both conditions are met, the process with the shortest remaining time is selected. The ‘if’ statement checks if the process has been completed or not.

If it has not been completed, the remaining time is decremented and the program moves on to the next process. If the process has been completed, the remaining time is set to the minimum time, and the program moves on to the next process. The program terminates when all processes have been completed.

SRTF Scheduling Program in C++

Here, we will try to show an example program for Shortest Remaining Time First (SRTF) scheduling algorithm in C++:

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

struct Process {

int id, arrival_time, burst_time, remaining_time;

};

bool cmp(Process p1, Process p2) {

return p1.arrival_time < p2.arrival_time;

}

int main() {

int n;

cout << “Enter the number of processes: “;

cin >> n;

vector<Process> processes(n);

cout << “Enter the arrival time and burst time of each process:\n”;

for (int i = 0; i < n; i++) {

processes[i].id = i+1;

cin >> processes[i].arrival_time >> processes[i].burst_time;

processes[i].remaining_time = processes[i].burst_time;

}

sort(processes.begin(), processes.end(), cmp);

vector<int> completion_time(n), turnaround_time(n), waiting_time(n);

int current_time = 0, completed = 0, prev = 0;

bool done = false;

while (!done) {

done = true;

int shortest = -1;

for (int i = 0; i < n; i++) {

if (processes[i].arrival_time <= current_time && processes[i].remaining_time > 0) {

if (shortest == -1 || processes[i].remaining_time < processes[shortest].remaining_time) {

shortest = i;

}

done = false;

}

if (done) break;

processes[shortest].remaining_time–;

current_time++;

if (processes[shortest].remaining_time == 0) {

completed++;

int id = processes[shortest].id;

completion_time[id-1] = current_time;

turnaround_time[id-1] = completion_time[id-1] – processes[shortest].arrival_time;

waiting_time[id-1] = turnaround_time[id-1] – processes[shortest].burst_time;

}

if (current_time – prev >= 10) {

cout << “Current time: ” << current_time << endl;

prev = current_time;

}

double avg_turnaround_time = 0.0, avg_waiting_time = 0.0;

for (int i = 0; i < n; i++) {

avg_turnaround_time += turnaround_time[i];

avg_waiting_time += waiting_time[i];

}

avg_turnaround_time /= n;

avg_waiting_time /= n;

cout << “\nProcess\tArrival Time\tBurst Time\tCompletion Time\tTurnaround Time\tWaiting Time\n”;

for (int i = 0; i < n; i++) {

cout << “P” << processes[i].id << “\t\t” << processes[i].arrival_time << “\t\t” << processes[i].burst_time << “\t\t”

<< completion_time[i] << “\t\t” << turnaround_time[i] << “\t\t” << waiting_time[i] << endl;

}

cout << “\nAverage Turnaround Time: ” << avg_turnaround_time << endl;

cout << “Average Waiting Time: ” << avg_waiting_time << endl;

return 0;

}

SRTF Scheduling Program in Java

Here’s an example implementation of the Shortest Remaining Time First (SRTF) scheduling algorithm in Java:

import java.util.*;

public class SRTF {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

System.out.print(“Enter number of processes: “);

int n = scanner.nextInt();

int[] burstTime = new int[n];

int[] waitingTime = new int[n];

int[] turnaroundTime = new int[n];

boolean[] completed = new boolean[n];

int completedCount = 0;

int currentTime = 0;

int shortestIndex;

int shortestBurstTime;

for (int i = 0; i < n; i++) {

System.out.print(“Enter burst time for process ” + (i + 1) + “: “);

burstTime[i] = scanner.nextInt();

completed[i] = false;

}

while (completedCount < n) {

shortestIndex = -1;

shortestBurstTime = Integer.MAX_VALUE;

// find the process with the shortest remaining burst time

for (int i = 0; i < n; i++) {

if (!completed[i] && burstTime[i] < shortestBurstTime && burstTime[i] > 0) {

shortestIndex = i;

shortestBurstTime = burstTime[i];

}

if (shortestIndex == -1) {

// no process available to execute

currentTime++;

} else {

// execute the process with the shortest remaining burst time

burstTime[shortestIndex]–;

currentTime++;

if (burstTime[shortestIndex] == 0) {

// process has completed

completedCount++;

completed[shortestIndex] = true;

waitingTime[shortestIndex] = currentTime – burstTime[shortestIndex];

turnaroundTime[shortestIndex] = waitingTime[shortestIndex] + burstTime[shortestIndex];

}

System.out.println(“\nProcess\tBurst Time\tWaiting Time\tTurnaround Time”);

for (int i = 0; i < n; i++) {

System.out.println((i + 1) + “\t\t” + burstTime[i] + “\t\t” + waitingTime[i] + “\t\t” + turnaroundTime[i]);

}

// calculate average waiting time and average turnaround time

int totalWaitingTime = 0;

int totalTurnaroundTime = 0;

for (int i = 0; i < n; i++) {

totalWaitingTime += waitingTime[i];

totalTurnaroundTime += turnaroundTime[i];

}

double averageWaitingTime = (double) totalWaitingTime / n;

double averageTurnaroundTime = (double) totalTurnaroundTime / n;

System.out.println(“\nAverage Waiting Time: ” + averageWaitingTime);

System.out.println(“Average Turnaround Time: ” + averageTurnaroundTime);

}

This program takes input from the user for the burst time of each process, and then uses the SRTF algorithm to simulate the execution of the processes. The program outputs the waiting time and turnaround time for each process, as well as the average waiting time and average turnaround time for all processes.

Summing Up

Through this article, you have been fully learnt about what is SRTF scheduling algorithm in OS; involving with many examples and programs in C, C++, and Java with their outputs. If this content is helpful for you, then please share it along with your friends, family members or relatives over social media platforms like as Facebook, Instagram, Linked In, Twitter, and more.