1. Introduction

Shortest Remaining Time First (SRTF) is the preemptive version of the Shortest Job First (SJF) scheduling algorithm. While SJF selects the process with the smallest CPU burst time and allows it to run until completion, SRTF continuously monitors the ready queue and always executes the process with the smallest remaining execution time.

The key difference is that SRTF supports preemption. If a new process arrives whose remaining execution time is smaller than that of the currently running process, the operating system immediately interrupts the running process and allocates the CPU to the newly arrived process.

Thus, SRTF makes scheduling decisions dynamically throughout execution rather than only when a process completes.

Because short jobs are always given preference, SRTF is one of the most efficient scheduling algorithms for minimizing:

• Average waiting time

• Average turnaround time

However, this improved performance comes at the cost of:

• Frequent context switching

• Increased scheduling overhead

• Potential starvation of long processes

SRTF is widely studied because it represents the theoretical optimum for minimizing average waiting time among preemptive scheduling algorithms.

2. Core Idea

The fundamental principle of SRTF is:

Always execute the process with the smallest remaining CPU burst time.

Unlike SJF, which makes a scheduling decision only when the CPU becomes free, SRTF reevaluates the scheduling decision whenever a new process arrives.

The scheduler continuously compares:

• Remaining time of the running process

• Burst times of newly arrived processes

If a shorter process appears:

Current Process Remaining = 7

New Process Burst = 3

3 < 7

Then:

Preempt Current Process

and allocate the CPU to the shorter process.

Core Principles

• Execute shortest remaining job

• Continuously monitor ready queue

• Allow dynamic preemption

• Prioritize short processes

3. Working Mechanism

The SRTF scheduler operates continuously throughout execution.

Whenever a scheduling event occurs:

1. Examine all ready processes.

2. Compute remaining burst times.

3. Select process with smallest remaining time.

4. Allocate CPU.

5. Repeat whenever a new process arrives.

Execution Rule

At Any Time

Select Process
With Minimum Remaining Time

Conceptual Example

Suppose:

Running Process Remaining = 8

Ready Queue:

P2 = 3
P3 = 5

Scheduler selects:

P2

because:

3 < 5 < 8

4. Example

Consider the following processes:

5. Step-by-Step Execution

Time = 0

Only P1 is available.

Execute P1

Remaining:

P1 = 8

Time = 1

P2 arrives.

Remaining times:

P1 = 7
P2 = 4

Since:

4 < 7

Preempt P1.

Execute:

P2

Time = 2

P3 arrives.

Remaining:

P2 = 3
P3 = 2

Since:

2 < 3

Preempt P2.

Execute:

P3

Time = 3

P4 arrives.

Remaining:

P3 = 1
P4 = 1

Tie condition.

Common rule:

Continue Current Process

Therefore P3 continues.

Time = 4

P3 completes.

Available:

P1 = 7
P2 = 3
P4 = 1

Smallest remaining time:

P4

Execute P4.

Time = 5

P4 completes.

Available:

P1 = 7
P2 = 3

Execute:

P2

Time = 8

P2 completes.

Remaining:

P1 = 7

Execute:

P1

Time = 16

P1 completes.

6. Gantt Chart

0    1    2    4    5      8          16

|P1|P2| P3 |P4|  P2  |     P1     |

7. Calculations

Completion Time (CT)

Turnaround Time (TAT)

Definition:

Calculations

P1

16 − 0 = 16

P2

8 − 1 = 7

P3

4 − 2 = 2

P4

5 − 3 = 2

Waiting Time (WT)

Definition:

Calculations

P1

16 − 8 = 8

P2

7 − 4 = 3

P3

2 − 2 = 0

P4

2 − 1 = 1

Average Waiting Time

Average WT = 3 units

Average Turnaround Time

Average TAT = 6.75 units

8. Key Characteristics

Preemptive Scheduling

Processes may be interrupted at any time.

Dynamic Decision-Making

Scheduling decisions occur continuously.

Remaining-Time Based

Selection depends on:

Smallest Remaining Burst

rather than original burst.

Frequent Context Switching

More scheduling decisions occur compared to SJF.

9. Advantages

9.1 Minimizes Average Waiting Time

Like SJF:

SRTF achieves the minimum average waiting time.

In practice it often performs even better than non-preemptive SJF because newly arriving short jobs receive immediate preference.

9.2 Better Responsiveness

Short jobs receive CPU quickly.

Example:

Long Job Running
      ↓
Short Job Arrives
      ↓
Immediate CPU Access

This improves responsiveness significantly.

9.3 Efficient Handling of Short Processes

Small processes are completed rapidly.

Benefits:

• Lower waiting time

• Faster turnaround

• Better throughput

10. Disadvantages

10.1 High Overhead

The biggest practical drawback is:

Frequent Context Switching

Example:

P1 → P2 → P3 → P4 → P2 → P1

Every switch requires:

• Saving registers

• Restoring registers

• Scheduler execution

Result:

Higher CPU Overhead

10.2 Starvation

SRTF may suffer from severe starvation.

Example

Suppose:

Long Process = 50 units

is running.

Then shorter jobs continuously arrive:

1,2,1,1,2,1...

The scheduler repeatedly selects short jobs.

Result:

Long Process Waits Indefinitely

Consequences

• Poor fairness

• Unbounded waiting time

Possible Solution

Use aging mechanisms:

Long Wait
    ↓
Priority Increase

10.3 Burst-Time Prediction Problem

SRTF requires knowledge of:

Remaining Execution Time

The operating system generally cannot know this exactly.

Therefore burst times must be:

• Predicted

• Estimated

using techniques such as exponential averaging.

This makes implementation more complex.

11. SJF vs SRTF

Key Difference

SJF

Choose Once
Run Till Completion

SRTF

Continuously Reevaluate
Preempt If Needed

Performance Summary