Shortest Remaining Time First (SRTF) Scheduling

The Story That Explains SRTF

Shortest Remaining Time First (SRTF) is the preemptive version of Shortest Job First (SJF). At every instant a new process arrives, the scheduler compares its burst time to the remaining time of the currently running process. If the newcomer is shorter, the running process is thrown back into the ready queue and the new one takes the CPU.

Where SRTF Sits in the Scheduling Family

Before diving into SRTF you need the family tree. CPU scheduling algorithms split first by whether they can preempt — i.e. forcibly take the CPU away from a running process — and then by their selection rule.

Key Terminology (Galvin's Glossary)

The SRTF Algorithm — Step by Step

Numerical Example 1 — The Classic Galvin Problem

Let's schedule four processes using SRTF. This is the canonical example from Galvin's Operating System Concepts, chapter 6.

Step-by-Step Trace

Gantt Chart (SVG)

Computing TAT and WT

Animated Step-by-Step State (SVG)

The diagram below animates the ready queue and running process at each tick. Watch how the queue re-sorts as new processes arrive and how P1 gets kicked off at t=1.

Numerical Example 2 — Ties, Idle CPU, and Sharp Preemption

A trickier scenario: some processes arrive after a gap (CPU sits idle) and later a very short job appears and preempts a long-running one. Watch how idle time is handled.

Numerical Example 3 — Practical Scenario (Bank Server)

Trace

Python Implementation

def srtf_schedule(processes):
    """
    processes: list of dicts with keys 'pid', 'at' (arrival), 'bt' (burst).
    Returns: schedule (list of (time, pid)) and metrics dict.
    """
    n         = len(processes)
    remaining = {p['pid']: p['bt'] for p in processes}
    completion = {}
    schedule   = []
    t          = 0
    completed  = 0

    while completed < n:
        # find processes that have arrived AND still have work
        ready = [p for p in processes
                 if p['at'] <= t and remaining[p['pid']] > 0]

        if not ready:
            schedule.append((t, 'IDLE'))
            t += 1
            continue

        # pick shortest remaining time; ties -> earlier AT, then pid
        current = min(ready, key=lambda p: (remaining[p['pid']], p['at'], p['pid']))
        schedule.append((t, current['pid']))
        remaining[current['pid']] -= 1
        t += 1

        if remaining[current['pid']] == 0:
            completion[current['pid']] = t
            completed += 1

    # metrics
    tat = {p['pid']: completion[p['pid']] - p['at'] for p in processes}
    wt  = {p['pid']: tat[p['pid']] - p['bt']   for p in processes}

    return {
        'schedule':  schedule,
        'completion': completion,
        'tat':       tat,
        'wt':        wt,
        'avg_tat':   sum(tat.values()) / n,
        'avg_wt':    sum(wt.values()) / n
    }


# --- Example 1 (Galvin classic) ---
procs = [
    {'pid': 'P1', 'at': 0, 'bt': 8},
    {'pid': 'P2', 'at': 1, 'bt': 4},
    {'pid': 'P3', 'at': 2, 'bt': 9},
    {'pid': 'P4', 'at': 3, 'bt': 5},
]

result = srtf_schedule(procs)

print("Completion Times:", result['completion'])
print("Turnaround Times:", result['tat'])
print("Waiting Times:  ", result['wt'])
print(f"Avg TAT: {result['avg_tat']:.2f}")
print(f"Avg WT:  {result['avg_wt']:.2f}")

SRTF vs FCFS vs SJF — Head-to-Head

Using the same input from Example 1 (P1..P4, AT 0/1/2/3, BT 8/4/9/5), here is what each algorithm produces:

Advantages and Disadvantages

Burst Time Prediction — The Missing Piece

Real operating systems cannot see the future. To use SRTF in practice, Galvin describes the exponential averaging technique to predict the next CPU burst from historical data.

When to Use SRTF (and When Not To)

Solving the Starvation Problem — Aging

The classical fix is aging: gradually decrease the "effective remaining time" of a process as it waits. After some threshold its priority becomes so high it MUST run.

# Aging-based SRTF (pseudocode)
def effective_remaining(process, current_time, aging_factor=0.1):
    wait_time = current_time - process.last_run_time
    return process.remaining - aging_factor * wait_time

# A process waiting 100 units with factor 0.1 has its effective RT reduced by 10.
# Eventually even a huge burst gets scheduled.

Golden Rules — Galvin's SRTF Checklist