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.

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.

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.

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.