🛒

SJF Scheduling — Step-by-Step With Animated Numericals

Shortest Job First — run the smallest burst next and provably minimise average waiting time. Both flavours (non-preemptive SJF and preemptive SRTF), solved with animated Gantt charts — plus the starvation trap.

Shortest First Gantt Charts SRTF Preemption Starvation

Press Next → or use ← → arrow keys

Section 01

The Story That Explains SJF

🛒 ANALOGY · THE SUPERMARKET EXPRESS LANE

Two customers reach the till: one has a trolley of 200 items, the other holds a single loaf. Serve them by arrival order and the bread customer waits 15 minutes for a 20-second transaction. That's why shops invented the Express Lane — serve the short one first. Do the same with CPU bursts and you minimise the total waiting time for everyone. That is SJF.

Section 02

The Two Flavours of SJF

🛑

Non-Preemptive SJF

run to completion

When the CPU frees up, pick the ready process with the smallest burst and let it finish — even if a shorter job arrives midway. One decision per dispatch.

⚡

Preemptive SJF (SRTF)

shortest remaining time first

On every arrival, compare the newcomer's burst to the running process's remaining time. If the newcomer is shorter, preempt and switch.

🏆

Provably Optimal

minimum average WT

For a given set of jobs, running the shortest first gives the minimum possible average waiting time. No other non-preemptive order can beat it.

📐

Same Metrics as FCFS

CT = start + burst, TAT = CT − AT, WT = TAT − BT, RT = start − AT. Only the selection rule changes — shortest burst, not arrival order.

Section 03

SJF Algorithm — Six Steps

🔁 The non-preemptive loop

1

At each decision point, gather all processes that have arrived and are ready.

2

Among them, pick the one with the smallest burst time (break ties by arrival, then PID).

3

Dispatch it; record its start time.

4

Let it run to completion — no preemption (in plain SJF).

5

Advance the clock to its completion; if the queue is empty, jump to the next arrival.

6

Repeat until every process is done.

⚡

For SRTF, Add One Check

The preemptive version re-runs the selection at every arrival, comparing remaining times instead of full bursts — so a short newcomer can snatch the CPU from a longer running job.

Numerical 1

Basic SJF — All Arrive at t = 0

Order	Proc	AT	BT	Start	CT	TAT	WT
1	P3	0	1	0	1	1	0
2	P2	0	4	1	5	5	1
3	P4	0	4	5	9	9	5
4	P1	0	7	9	16	16	9
Averages →						7.75	3.75

📉

Half the Waiting Time of FCFS

Sorting by burst (1, 4, 4, 7) runs the tiny P3 first, so short jobs stop waiting behind the long one. Avg WT = 3.75 ms versus FCFS's 7.50 ms on the same data — a 50% improvement.

Numerical 2

Non-Preemptive SJF, Different Arrivals

Order	Proc	AT	BT	Start	CT	TAT	WT
1	P1	0	6	0	6	6	0
2	P4	3	3	6	9	6	3
3	P3	2	7	9	16	14	7
4	P2	1	8	16	24	23	15
Averages →						12.25	6.25

🧮

P1 Runs First Because It's Alone

Only P1 has arrived at t=0, so it runs 0→6. By t=6 all four are present, and SJF picks by burst: P4·3, then P3·7, then P2·8. Non-preemptive means each finishes before the next choice. Avg WT = 6.25 ms.

Numerical 3 · SRTF

Preemptive SJF — Preemption Steals the CPU at t = 1

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

⚡

At t=1, P2 (rem 4) Beats P1 (rem 7)

P1 starts, but the instant P2 arrives with a shorter burst it preempts P1. P2 finishes, then P4 (5), then P1 resumes its remaining 7, then P3. SRTF's Avg WT = 6.50 ms beats non-preemptive SJF's 7.75 ms on the very same data.

Numerical 3 · Compare

Preemptive vs Non-Preemptive, Same Data

7.75Non-preemptive SJF · Avg WT

6.50SRTF · Avg WT

14.25Non-preemptive · Avg TAT

13.00SRTF · Avg TAT

🔍 The second-by-second preemption decision

t=0

P1 alone (rem 8) → dispatch P1.

t=1

P2 arrives (rem 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 done. Ready {P1:7, P3:9, P4:5} → shortest is P4, run it.

t=10

P4 done. Ready {P1:7, P3:9} → P1 resumes; then P3 last (t=17→26).

💡

More Responsive, More Overhead

SRTF gives the globally minimum average waiting time, but it must re-evaluate at every arrival and pays extra context-switch cost. Non-preemptive SJF is cheaper but can't react once a job is running.

Numerical 4

Starvation — Watch P1 Never Get to Run

Proc	AT	BT	Note
P1	0	20	Preempted 6×; finishes only at t=30 → TAT 30
P2…P6	1,3,5,7,9	2 each	Each short job jumps ahead of P1

🍽️

The Fix Is Aging

Every time a shorter job arrives, P1 is shoved aside. If short jobs kept coming forever, P1 would starve — never finishing. The cure is aging: gradually raise a waiting process's priority so that, eventually, even a long job must be scheduled.

Section 09

Predicting the Next CPU Burst

SJF needs to know a job's burst before it runs — impossible in general, so the OS predicts it from history with exponential averaging.

🧮

The Exponential Averaging Formula

τₙ₊₁ = α · tₙ + (1 − α) · τₙ — the next prediction blends the actual last burst tₙ with the previous prediction τₙ. A common choice is α = 0.5, weighting recent history and the running estimate equally.

Step	Predicted τ	Actual t	Updated τ (α=0.5)
0	10.00	6	8.00
1	8.00	4	6.00
2	6.00	6	6.00
3	6.00	4	5.00
4	5.00	13	9.00
5	9.00	13	11.00
6	11.00	13	12.00

📈

It Chases the Trend

Notice how the prediction glides toward 13 as the actual bursts jump up — smoothing noise while still tracking a real shift in behaviour. That's exactly what you want for scheduling decisions.

Section 11

SJF vs FCFS — Side by Side

Property	FCFS	SJF (non-preemptive)	SRTF (preemptive)
Selection	Arrival order	Shortest burst among ready	Shortest remaining time
Preemption	No	No	Yes
Avg waiting time	Often poor	Optimal (given arrivals)	Globally optimal
Starvation risk	None	Yes	Yes
Overhead	Very low	Low	High
Needs burst prediction	No	Yes	Yes
Convoy effect	Severe	Solves it	Solves it

🏆

SJF Cures the Convoy Effect

The very problem that wrecked FCFS — short jobs trapped behind a long one — disappears when you run the shortest job first. The price is needing to predict bursts and risking starvation of long jobs.

Section 12

Advantages & Disadvantages

✅

Minimum Avg WT

Provably optimal average waiting time for a given set of jobs — no ordering does better.

✅

Kills the Convoy

Short jobs never get stuck behind a long one — the FCFS flaw is gone.

✅

Great Throughput

Clearing many short jobs quickly raises the number completed per unit time.

❌

Starvation

A steady stream of short jobs can keep a long job waiting forever — needs aging.

❌

Burst Is Unknown

You can't truly know a burst ahead of time — you must estimate it and can be wrong.

❌

SRTF Overhead

Preemptive SRTF re-checks at every arrival and switches often — more context-switch cost.

Section 13

Seven Rules for Solving SJF

🛒 SJF / SRTF · PROBLEM-SOLVING RULES

1

At each decision, choose the smallest burst among the arrived processes — not all of them.

2

Break ties by arrival time, then by PID.

3

For SRTF, re-evaluate at every arrival and compare remaining times, not full bursts.

4

If the ready queue is empty, jump the clock to the next arrival (CPU idle).

5

SJF gives the minimum average waiting time — cite this when asked why it's "optimal".

6

Watch for starvation of long jobs; the standard cure is aging.

7

Real bursts are unknown — the OS predicts them with τₙ₊₁ = α·tₙ + (1−α)·τₙ.

FINAL

Shortest Job First — Mastered

2Flavours: SJF & SRTF

3.75N1 avg WT (ms)

6.50SRTF avg WT (ms)

50%Better than FCFS

α=0.5Burst prediction

🎯

You Can Now Solve Any SJF or SRTF Problem

Pick the shortest ready job, draw the Gantt chart, and compute the metrics — and for SRTF, re-check at every arrival. You've seen all four cases: simultaneous arrivals, staggered arrivals, live preemption, and starvation.

📚

Where To Go Next

Next come Priority Scheduling (with aging to prevent starvation) and Round Robin (fair time-slicing for interactive systems). Compare each one's average waiting time against this SJF baseline.

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