🚑

SRTF Scheduling — Shortest Remaining Time First

The preemptive twin of SJF: at every arrival, compare remaining times and let the shortest job seize the CPU — even mid-execution. Solved step-by-step with animated Gantt charts and marked preemptions.

Preemptive Gantt Charts 3 Numericals Starvation & Aging

Press Next → or use ← → arrow keys

Section 01

The Story That Explains SRTF

🚑 ANALOGY · THE EMERGENCY ROOM

A triage nurse is treating a heart-attack patient who needs 40 minutes. Midway, a patient with a small cut (5 minutes) arrives — and then someone needing just 2 minutes of oxygen. The nurse pauses the long case, clears the 2-minute patient, then the 5-minute one, then returns to the long case.

That is SRTF: always give the CPU to the job with the shortest remaining time, even if it means interrupting one already in progress.

⚡

Preemptive by Nature

SRTF is the preemptive version of SJF. Where SJF only chooses when the CPU falls idle, SRTF re-evaluates the instant a new process arrives — and will preempt the running job if the newcomer's burst is shorter than what's left of the current one.

Section 02

Where SRTF Sits in the Family

🌳

Two Big Families

Non-preemptive schedulers (FCFS, SJF, non-preemptive Priority) never interrupt a running job. Preemptive ones — SRTF, Round Robin, preemptive Priority, MLFQ — can. SRTF is simply SJF that's allowed to interrupt.

Section 04

The SRTF Algorithm — Step by Step

🔁 The preemptive loop

1

At each decision point, list every process that has arrived and still has work left.

2

Pick the one with the smallest remaining time (ties → earliest arrival, then PID).

3

Run it, decrementing its remaining time as the clock advances.

4

On a new arrival, compare its burst with the running job's remaining time — preempt if shorter.

5

When a process finishes, record its completion time and pick the next shortest.

6

If nothing is ready, the CPU goes idle until the next arrival.

🎯

Preemption Fires on Only Two Events

The scheduler does not re-sort every clock tick — only when a process arrives or the current one completes. Those are the only two moments the decision can change. Metrics are the same as always: TAT = CT − AT, WT = TAT − BT.

Numerical 1

The Classic Galvin Problem

Proc	AT	BT	CT	TAT	WT
P1	0	8	17	17	9
P2	1	4	5	4	0
P3	2	9	26	24	15
P4	3	5	10	7	2
Averages →			13.00	6.50

📐

Read the Chart, Then Compute

P1 starts, is preempted by P2 at t=1, and only resumes at t=10 after P2 and P4 clear. Completion times come straight off the chart; then TAT = CT − AT and WT = TAT − BT. Avg WT = 6.50 units.

Numerical 1 · Trace

The Second-by-Second Decisions

🔍 Remaining-time comparison at every event

t=0

P1 arrives (rem 8), alone → run P1.

t=1

P2 arrives (4); P1 now rem 7 → 4 < 7, preempt P1, run P2.

t=2,3

P3 (9) and P4 (5) arrive, but P2's remaining (3, then 2) is still smallest → keep P2.

t=5

P2 completes. Ready {P1:7, P3:9, P4:5} → run P4 (5 is smallest).

t=10

P4 completes. Ready {P1:7, P3:9} → P1 resumes its remaining 7.

t=17

P1 completes. Only P3 remains → run it to t=26. Done.

💡

Only the Two Events Matter

Every decision above happens at an arrival or a completion — never in between. That's what keeps SRTF tractable to solve by hand: you only redraw the queue at those moments.

Numerical 2

Ties & Two Sharp Preemptions

Proc	AT	BT	CT	TAT	WT
P1	0	7	16	16	9
P2	2	4	7	5	1
P3	4	1	5	1	0
P4	5	4	11	6	2
Averages →			7.00	3.00

⚡

Preempted Twice in a Row

P1 is preempted by P2 at t=2, then P2 is immediately preempted by the tiny P3 (burst 1) at t=4. After P3 finishes, P2 resumes, then P4, then P1 — the longest — runs last. Avg WT = 3.00 units.

Numerical 3

Real Scenario — A Bank Server

Request	Task	AT	BT	CT	TAT	WT
P1	Balance query	0	6	12	12	6
P2	UPI transfer	1	3	4	3	0
P3	Statement PDF	2	8	20	18	10
P4	Login OTP	3	2	7	4	2
P5	Card block	4	1	5	1	0
Averages →				7.60	3.60

🏦

Quick Requests Finish Fast

The one-off card-block (P5·1) and OTP (P4·2) slip through quickly while the big statement PDF (P3·8) waits — exactly what you want on an interactive server. Avg WT = 3.60 ms.

Section 10

SRTF vs FCFS vs SJF — Head to Head

8.25FCFS · Avg WT (Ex 1)

7.75Non-preemptive SJF · Avg WT

6.50SRTF · Avg WT

★SRTF wins on the same data

Property	FCFS	SJF (non-preempt)	SRTF (preempt)
Preemption	No	No	Yes
Average WT	Worst	Better	Best
Starvation risk	None	Possible	High for long jobs
Overhead	Zero	Low	High — context switches
Needs burst estimate	No	Yes	Yes
Convoy effect	Yes	No	No
Best for	Batch, simple	Batch, known burst	Short interactive jobs

Section 11

Advantages & Disadvantages

✅

Best Average WT

Provably minimal average waiting time among preemptive schedulers when bursts are known exactly.

✅

Snappy Short Jobs

A newly-arrived short job runs almost immediately — ideal for interactive, bursty workloads.

✅

No Convoy Effect

Long jobs can't block short ones — preemption breaks the queue-behind-a-truck problem.

❌

Starvation

A stream of short arrivals can keep a long job waiting indefinitely — needs aging.

❌

Context-Switch Cost

Frequent preemptions add overhead (1–10 µs each) that can erode the theoretical gains.

❌

Bursts Unknown

Real burst times aren't known in advance — they must be predicted, and predictions can be wrong.

Section 12

Burst Prediction — The Missing Piece

🧮

Exponential Averaging

Since a burst can't truly be known ahead of time, the OS predicts it: τₙ₊₁ = α·tₙ + (1 − α)·τₙ — blend the actual last burst tₙ with the previous prediction τₙ. With α = 0.5 both count equally.

Cycle	Actual tₙ	Predicted τₙ	τₙ₊₁ = 0.5·tₙ + 0.5·τₙ
0	—	10	—
1	6	10	8
2	4	8	6
3	6	6	6
4	—	6	6 (stabilises)

📈

Smooths Noise, Tracks Trends

The prediction absorbs one-off blips but still follows a genuine change in a process's behaviour — giving SRTF a usable estimate of "remaining time" without a crystal ball.

Section 14

Solving Starvation — Aging

🍽️

The Problem

Because SRTF always favours the shortest remaining time, a long job can be shoved aside every time a shorter one arrives. Under a steady stream of short jobs, that long job may never run — it starves.

⏳ Aging — the standard cure

Idea

The longer a process waits, the more its effective remaining time is reduced.

Formula

effective_RT = remaining − aging_factor × wait_time

Effect

A job waiting 100 units with factor 0.1 has its effective RT cut by 10 — eventually even a huge burst gets scheduled.

⚖️

Fairness Without Losing Efficiency

Aging keeps SRTF's short-job responsiveness while guaranteeing that long jobs make progress. It's the same fix used for priority scheduling's starvation problem.

Section 15

Seven Rules for Solving SRTF

🚑 SRTF · GALVIN'S CHECKLIST

1

Compare remaining times, not full bursts — that's what makes it SRTF, not SJF.

2

Re-decide only at two events: a new arrival or a completion.

3

On a new arrival, preempt the running job if the newcomer's burst is smaller than its remaining time.

4

Break ties by earliest arrival, then PID.

5

If nothing is ready, the CPU is idle — advance the clock to the next arrival.

6

SRTF gives the minimum average waiting time — but watch for long-job starvation.

7

Real bursts are unknown — predict them, and add aging to stay fair.

FINAL

Shortest Remaining Time First — Mastered

2Preemption events only

6.50Ex 1 avg WT

3.00Ex 2 avg WT

3.60Bank avg WT (ms)

α=0.5Burst prediction

🎯

You Can Now Solve Any SRTF Problem

Track remaining times, redraw the queue at each arrival and completion, mark every preemption, and read the metrics off the finished Gantt chart. You've seen a single preemption, a double preemption, and a real interactive workload.

📚

Where To Go Next

Next up: Round Robin (fair time-slicing regardless of burst) and Priority Scheduling (with aging to prevent starvation). Compare each against this SRTF baseline for waiting time and responsiveness.

🚑 End of tutorial · Press ← to review, or click Restart