Shortest Remaining Time First (SRTF) Scheduling Algorithm

Introduction

SRTF stands for Shortest Remaining Time First. It is also known as preemptive SJF because it allows a shorter newly arrived process to interrupt the currently running process.

The key idea is remaining time. Instead of comparing only original burst time, SRTF compares how much CPU time each available process still needs.

Core Rule of SRTF Scheduling

In SRTF scheduling, the operating system always selects the available process with the least remaining CPU time. If a new process arrives with a shorter remaining time than the currently running process, the current process is preempted.

This makes SRTF different from non-preemptive SJF. In SJF, a running process continues once selected. In SRTF, the scheduler can change its decision whenever a better short job becomes available.

SRTF is more dynamic than non-preemptive SJF, so it needs a few extra conditions:

• Preemption: The operating system must be able to interrupt a running process.

• Context switching: The OS must save one process state and load another process state.

• Remaining-time estimate: The scheduler needs to know or predict how much CPU time each process still requires.

Because of these requirements, SRTF can give better average performance, but it also creates more scheduling overhead.

SRTF Scheduling Example

Consider five processes with arrival time and burst time:

The compact scheduling flow is:

• Time 0: Only P1 has arrived, so P1 starts.

• Time 1: P2 arrives with burst time 4, while P1 has 7 units remaining, so P2 preempts P1.

• Time 5: P2 completes, and P4 has the shortest remaining time among available processes.

• Time 7: P5 arrives with burst time 2, while P4 has 3 units remaining, so P5 preempts P4.

• After P5: P4 resumes, then P1, and finally P3.

Metric Calculation

The main formulas are:

• CT: finish time of the process

• TAT: CT - AT

• WT: TAT - BT

• RT: first start time - AT

Average TAT = 12.0, average WT = 6.4, and average RT = 3.8.

Why Waiting Time and Response Time Differ

In SRTF, a process may start once, get preempted, and then wait again before completing. Because of this, waiting time and response time are not always the same.

For example, P1 starts immediately at time 0, so its response time is 0. But after being preempted at time 1, it waits until time 12, so its total waiting time becomes much larger.

Strengths and Weaknesses of SRTF

Summary

SRTF scheduling runs the process with the least remaining CPU time. It is preemptive, so a newly arrived short process can interrupt the currently running process.

It usually improves average waiting time and turnaround time, especially for short jobs. However, it needs remaining-time prediction, increases context-switching overhead, and may cause starvation for long processes.