Shortest job first and shortest remaining time first

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. WT = ? from Lesson 2.1.1
2. Which IPC needs explicit synchronization? from Lesson 1.2.2
3. Where does a woken (I/O-finished) process go? from Lesson 1.1.1

1 · The Hook

At a photocopier, if someone with one page asks to go before someone with 200, everyone's average wait drops. Always serving the shortest job first gives the smallest average waiting time possible. Its pre-emptive version, SRTF, is the most frequently asked scheduling algorithm in GATE, because tracing it needs care at every arrival.

3 · Core Concept

Predict First — the answer

Shortest first: 2, 4, 6. Waits 0, 2, 6 → average 8/3 ≈ 2.67. Any other order gives a larger average.

In plain words

SJF: whenever the CPU becomes free, start the waiting job with the smallest burst, and let it finish. SRTF: the same idea, but if a new job arrives whose burst is smaller than what the running job still needs, switch to the new job immediately.

1. Shortest Job First (SJF), non-pre-emptive

When the CPU is free, pick the arrived process with the smallest burst (ties: earlier arrival). Running example: at 0 only P1 is there → P1 0–8. At 8, ready: P2 (4), P3 (9), P4 (5), P5 (2) → P5 8–10, P2 10–14, P4 14–19, P3 19–28. WT: P1 0, P2 9, P3 17, P4 11, P5 4 → average 41/5 = 8.2.

2. Shortest Remaining Time First (SRTF), pre-emptive SJF

At every arrival (and every completion), run the process with the smallest remaining time. Running example:

• t = 0: P1 starts (remaining 8).
• t = 1: P2 arrives with 4 < 7 → pre-empt P1; P2 runs 1–5 (P3, P4, P5 arrive meanwhile but none is shorter than P2's remaining time).
• t = 5: remaining: P1 7, P3 9, P4 5, P5 2 → P5 5–7, then P4 7–12, P1 12–19, P3 19–28.

Average WT = 33/5 = 6.6 (better than SJF's 8.2 and FCFS's 11.4).

3. Properties

• SJF is optimal for average waiting time among non-pre-emptive schedules (when all jobs are present); SRTF is optimal among pre-emptive ones.

• Starvation: a long job can wait forever if short jobs keep arriving.

• The OS cannot know future bursts. It predicts them by exponential averaging: τₙ₊₁ = α·tₙ + (1 − α)·τₙ (tₙ = last actual burst, τₙ = last prediction, 0 ≤ α ≤ 1).

  α = 0.5, τ₀ = 10, actual bursts 6, 4, 6 → predictions 8, 6, 6.

4 · Visual

SRTF on the running example

| P1 | P2      | P5 | P4      | P1             | P3                 |
0    1         5    7         12               19                   28
     ^ P2 (4) beats P1's remaining 7: pre-empt

5 · Worked Examples

Example 1 Easy

Bursts 6, 2, 4 at time 0 under SJF. Average turnaround time?

Solution

Run 2, 4, 6: completions 2, 6, 12 → average 20/3 ≈ 6.67.

Example 2 Medium

Running example under SJF: which process runs right after P1?

Solution

At t = 8 the shortest ready burst is P5's (2): P5.

Example 3 GATE

Running example under SRTF: average waiting time?

Solution

6.6 (see the table).

6 · GATE Traps

• In SRTF, re-check at every arrival: compare the newcomer's burst with the running job's remaining time.
• SJF (non-pre-emptive) never interrupts; a short job arriving just after a long one starts waits.
• Ties go to the earlier arrival (state your rule if the question doesn't).
• SJF/SRTF can starve long jobs.

7 · Memory Hook

"Shortest first wins on average; SRTF re-decides at every arrival."

8 · Connect the Dots

Burst length is one way to rank processes. The next lesson ranks them by priority, sees how low-priority processes starve, and fixes it with aging and the response-ratio rule.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 2 mark(s) — SJF

Running example under SJF (non-pre-emptive): average waiting time?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — SRTF

Running example under SRTF: average turnaround time?

Numerical answer: ________

Q3 · NAT · 2 mark(s) — SRTF

Processes (AT, BT): P1 (0, 8), P2 (1, 4), P3 (2, 9), P4 (3, 5). SRTF average waiting time?

Numerical answer: ________

Q4 · NAT · 1 mark(s) — Prediction

Exponential averaging with α = 0.5: previous prediction 10, actual burst 6. Next prediction?

Numerical answer: ________

Q5 · MCQ · 1 mark(s) — Optimality

Which algorithm minimises the average waiting time among non-pre-emptive algorithms (all jobs present at time 0)?

1. (A) Round robin
2. (B) Priority
3. (C) SJF
4. (D) FCFS

10 · Rule Card

• SJF: when free, pick the smallest burst; non-pre-emptive; optimal average WT.
• SRTF: at each arrival/completion, run the smallest remaining time; pre-emptive; optimal among pre-emptive.
• Both can starve long jobs; bursts predicted by τₙ₊₁ = αtₙ + (1 − α)τₙ.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

shortest job firstshortest remaining time firstoptimality for average waiting timestarvationexponential averaging prediction