Shortest Remaining Time First (SRTF) Scheduling: A GATE 2011 Example Explained

Understand the Shortest Remaining Time First (SRTF) scheduling algorithm with this detailed example based on a GATE 2011 question. This tutorial demonstrates SRTF scheduling, calculates waiting times, and highlights its preemptive nature and efficiency in minimizing average waiting time.

Shortest Remaining Time First (SRTF) Scheduling: A GATE 2011 Example

Understanding the SRTF Algorithm

The Shortest Remaining Time First (SRTF) scheduling algorithm is a preemptive algorithm that aims to minimize the average waiting time for processes. It's a variation of the Shortest Job First (SJF) algorithm; unlike SJF (which is non-preemptive), SRTF can interrupt a running process if a new process with a shorter remaining burst time (time to complete execution) arrives. This makes it more responsive than SJF but adds some scheduling overhead.

GATE 2011 SRTF Example

Let's examine a GATE 2011 question on SRTF:

Question: Given the arrival and burst times below, calculate the average waiting time for processes P1, P2, and P3.

Process ID Arrival Time Burst Time Completion Time Turnaround Time Waiting Time
P1 0 9 13 13 4
P2 1 4 5 4 0
P3 2 9 22 20 11

Solving the Problem

  1. Time 0: P1 arrives and begins execution.
  2. Time 1: P2 arrives. P2 has a shorter burst time than P1's remaining time, so P1 is preempted, and P2 runs.
  3. Time 2: P3 arrives. P2's remaining time (3) is less than P3's burst time (9), so P2 continues.
  4. Time 5: P2 completes. P1 resumes.
  5. Time 13: P1 completes. P3 runs.
  6. Time 22: P3 completes.

Average waiting time: (4 + 0 + 11) / 3 = 5 units