3.3 Shortest Job First (SJF) & Shortest Remaining Time First (SRTF)

Back to Operating Systems Notes

📚Module 03: CPU Scheduling AlgorithmsTopic 3.3⏱️14 min read

🎯High-Yield For:Computer Science Foundations • Systems Engineering • Technical Interviews

💡 Core Intuition

🍳 The Everyday Analogy: Hospital Emergency Room Triage

Imagine an emergency outpatient department staffed by one trauma surgeon (the CPU) with patients of varying treatment complexity:

Architecture Flow

The Emergency Triage Analogy Pipeline

Mapping surgical triage strategies to SJF and SRTF CPU scheduling

💡 Hover or click any card for deep-dive operational details

🏥Admission

Triage Assessment

Ready Queue Arrival

Patients arrive with varying estimated procedure times.

→

Triage Decision

⏱️SJF Policy

Shortest Case First

Non-Preemptive SJF

The surgeon completes the current surgery, then takes the quickest case.

→

Preemption Check

⚡SRTF Policy

Emergency Interrupt

Preemptive SRTF

Surgeon pauses an ongoing procedure if an even quicker emergency arrives.

• Non-Preemptive SJF: Once the surgeon starts a procedure, they finish it to completion. When selecting the next patient, they always choose the one with the shortest expected duration.
• Preemptive SRTF: If a patient arrives whose procedure takes less time than the surgeon's remaining time on the current patient, the surgeon halts the current procedure and treats the new arrival immediately.

---

💻 Bridging to Computer Science

In operating systems, Shortest Job First (SJF) selects the process from the Ready Queue that has the smallest CPU burst time requirement.

• If two processes have identical burst times, FCFS order is used to break the tie.
• SJF exists in two distinct execution modes:
  1. Non-Preemptive SJF: The running process retains the CPU until it voluntarily releases it.
  2. Preemptive SJF (Shortest Remaining Time First - SRTF): A newly arriving process with a shorter remaining burst time immediately preempts the currently running process.

---

📑Table of Contents

• 💡 Core Intuition
• 📚 Core Deep-Dive & Concepts
  • 1. Non-Preemptive SJF Architectural Principles
  • 2. Comprehensive Problem: Non-Preemptive SJF Step-by-Step Derivation
  • 3. Preemptive SJF: Shortest Remaining Time First (SRTF)
  • 4. Advantages, Disadvantages & Starvation
  • 5. Predicting Future CPU Bursts: Exponential Averaging
• 📐 Architecture / Visual Blueprint
  • The SRTF Preemption & State Migration Lifecycle
• 🏭 In The Real World: Production Case Study
  • Distributed Stage Scheduling in Apache Spark & Database Query Planners
• 🎯 Exam & Interview Pitfall Check

---

📚 Core Deep-Dive & Concepts

1. Non-Preemptive SJF Architectural Principles

Definition: Whenever the scheduler makes a decision of selecting the next process for CPU execution among all available processes, the CPU is assigned to the process having the smaller burst time requirement. If there is a tie, FCFS is used to break the tie.

Non-Preemptive SJF vs. Preemptive SRTF

Contrasting cooperative completion against dynamic preemption

Non-Preemptive

Shortest Job First (SJF)

🤝

Dominant Architecture / DomainCooperative Short-Burst Priority

• •Scheduling Trigger: Evaluated strictly when the running process terminates or blocks for I/O.
• •Zero Preemption Overhead: A process is never context-switched out against its will.
• •Tie-Breaking Rule: When burst times are equal, FCFS arrival order decides.
• •Convoy Protection: Prevents small tasks from getting trapped behind new large arrivals.

"CPU assigned to the process having smaller burst time requirement among available processes."

Preemptive (Optimal)

Shortest Remaining Time First (SRTF)

⚡

Dominant Architecture / DomainMathematically Optimal Waiting Time

• •Scheduling Trigger: Evaluated on process arrival, timer ticks, and state changes.
• •Dynamic Preemption: A running process is evicted if a newcomer has a shorter remaining burst.
• •Provably Optimal: Mathematically guarantees the minimal average waiting time for any given set of processes.
• •Starvation Risk: Long-burst processes can starve indefinitely if shorter jobs continuously arrive.

"SRTF is called optimal as it guarantees minimal average waiting time."

---

2. Comprehensive Problem: Non-Preemptive SJF Step-by-Step Derivation

Consider five processes arriving with the following arrival and burst times:

Process ID	Arrival Time ($AT$)	Burst Time ($BT$)
$P_0$	$1\text{ ms}$	$7\text{ ms}$
$P_1$	$2\text{ ms}$	$5\text{ ms}$
$P_2$	$3\text{ ms}$	$1\text{ ms}$
$P_3$	$4\text{ ms}$	$2\text{ ms}$
$P_4$	$5\text{ ms}$	$8\text{ ms}$

Execution Walkthrough:

• $[0, 1]$: No process has arrived. The CPU sits idle for $1\text{ ms}$.
• At $t = 1$: Only $P_0$ is available ($AT = 1, BT = 7$). Since no other process is in the queue, $P_0$ is scheduled. Because scheduling is non-preemptive, $P_0$ runs uninterrupted from $t = 1 \to 8$.
• At $t = 8$: $P_0$ completes. During $[1, 8]$, all remaining processes ($P_1, P_2, P_3, P_4$) have entered the Ready Queue:
  • $P_1: BT = 5$
  • $P_2: BT = 1$
  • $P_3: BT = 2$
  • $P_4: BT = 8$
  • Smallest burst is $P_2$ ($BT = 1$). $P_2$ executes from $t = 8 \to 9$.
• At $t = 9$: $P_2$ completes. Remaining: $P_3(2), P_1(5), P_4(8)$. Smallest is $P_3$ ($BT = 2$). $P_3$ executes from $t = 9 \to 11$.
• At $t = 11$: $P_3$ completes. Remaining: $P_1(5), P_4(8)$. Smallest is $P_1$ ($BT = 5$). $P_1$ executes from $t = 11 \to 16$.
• At $t = 16$: $P_1$ completes. Only $P_4$ remains ($BT = 8$). $P_4$ executes from $t = 16 \to 24$.
• At $t = 24$: All processes finished.

⏱️

Non-Preemptive SJF Execution Gantt Chart

Timeline showing initial CPU idle gap and non-preemptive burst selection

IDLEIdle: 1ms

P0Burst: 7ms

P2Burst: 1ms

P3Burst: 2ms

P1Burst: 5ms

P4Burst: 8ms

01

8

9

11

16

24

Avg Turnaround10.6 ms

Avg Waiting Time6.0 ms

Throughput0.208 jobs/ms

CPU Utilization95.83%

Tabulation of Non-Preemptive SJF Metrics:

Process	Arrival ($AT$)	Burst ($BT$)	Completion ($CT$)	Turnaround ($TAT = CT - AT$)	Waiting ($WT = TAT - BT$)	Response ($RT$)
$P_0$	$1$	$7$	$8$	$8 - 1 = \mathbf{7}$	$7 - 7 = \mathbf{0}$	$1 - 1 = \mathbf{0}$
$P_1$	$2$	$5$	$16$	$16 - 2 = \mathbf{14}$	$14 - 5 = \mathbf{9}$	$11 - 2 = \mathbf{9}$
$P_2$	$3$	$1$	$9$	$9 - 3 = \mathbf{6}$	$6 - 1 = \mathbf{5}$	$8 - 3 = \mathbf{5}$
$P_3$	$4$	$2$	$11$	$11 - 4 = \mathbf{7}$	$7 - 2 = \mathbf{5}$	$9 - 4 = \mathbf{5}$
$P_4$	$5$	$8$	$24$	$24 - 5 = \mathbf{19}$	$19 - 8 = \mathbf{11}$	$16 - 5 = \mathbf{11}$

$\overline{TAT} = \frac{7 + 14 + 6 + 7 + 19}{5} = \frac{53}{5} = \mathbf{10.6\text{ ms}}$ $\overline{WT} = \frac{0 + 9 + 5 + 5 + 11}{5} = \frac{30}{5} = \mathbf{6.0\text{ ms}}$

---

3. Preemptive SJF: Shortest Remaining Time First (SRTF)

Definition: Shortest Remaining Time First (SRTF) is the preemptive version of Shortest Job First. It is called optimal because it mathematically guarantees the minimal average waiting time for any given set of processes.

Applying preemption to the exact same five processes:

Step-by-Step Chronological Execution:

• $[0, 1]$: CPU is idle.
• At $t = 1$: $P_0$ arrives ($BT = 7$). Starts execution.
• At $t = 2$: $P_1$ arrives ($BT = 5$).
  • $P_0$'s remaining burst is $7 - 1 = 6\text{ ms}$.
  • Since $P_1$'s burst ($5$) is less than $P_0$'s remaining burst ($6$), $P_1$ preempts $P_0$!
  • $P_1$ begins executing ($t = 2 \to 3$).
• At $t = 3$: $P_2$ arrives ($BT = 1$).
  • $P_1$'s remaining burst is $5 - 1 = 4\text{ ms}$.
  • Since $P_2$'s burst ($1$) is less than $P_1$'s remaining burst ($4$), $P_2$ preempts $P_1$!
  • $P_2$ executes ($t = 3 \to 4$).
• At $t = 4$: $P_2$ completes ($CT = 4$). $P_3$ arrives ($BT = 2$).
  • Active processes in Ready Queue: $P_3$ ($BT = 2$), $P_1$ (remaining $= 4$), $P_0$ (remaining $= 6$).
  • Smallest remaining is $P_3$ ($2$). $P_3$ executes ($t = 4 \to 6$).
  • (Note: At $t = 5$, $P_4$ arrives with $BT = 8$. Since $P_4$'s burst $8 > P_3$'s remaining burst $1$, $P_3$ continues uninterrupted until $t = 6$).
• At $t = 6$: $P_3$ completes ($CT = 6$).
  • Ready Queue: $P_1$ (remaining $= 4$), $P_0$ (remaining $= 6$), $P_4$ (remaining $= 8$).
  • Smallest remaining is $P_1$ ($4$). $P_1$ executes to completion ($t = 6 \to 10$).
• At $t = 10$: $P_1$ completes ($CT = 10$).
  • Ready Queue: $P_0$ (remaining $= 6$), $P_4$ (remaining $= 8$).
  • Smallest remaining is $P_0$ ($6$). $P_0$ executes to completion ($t = 10 \to 16$).
• At $t = 16$: $P_0$ completes ($CT = 16$).
  • Only $P_4$ remains ($8$). $P_4$ executes to completion ($t = 16 \to 24$).
• At $t = 24$: All processes finished.

⏱️

Preemptive SRTF Execution Gantt Chart

Visualizing dynamic preemption points at t = 2 and t = 3 leading to optimal wait time

IDLEIdle: 1ms

P0P0 (run 1ms)

P1P1 (run 1ms)

P2P2 finishes

P3P3 finishes

P1P1 finishes

P0P0 finishes

P4P4 finishes

01

2

3

4

6

10

16

24

Avg Turnaround9.0 ms

Avg Waiting Time4.4 ms

Optimality Gain26.7% vs SJF

CPU Utilization95.83%

Tabulation of Preemptive SRTF Metrics:

Process	Arrival ($AT$)	Burst ($BT$)	Completion ($CT$)	Turnaround ($TAT = CT - AT$)	Waiting ($WT = TAT - BT$)	Response ($RT$)
$P_0$	$1$	$7$	$16$	$16 - 1 = \mathbf{15}$	$15 - 7 = \mathbf{8}$	$1 - 1 = \mathbf{0}$
$P_1$	$2$	$5$	$10$	$10 - 2 = \mathbf{8}$	$8 - 5 = \mathbf{3}$	$2 - 2 = \mathbf{0}$
$P_2$	$3$	$1$	$4$	$4 - 3 = \mathbf{1}$	$1 - 1 = \mathbf{0}$	$3 - 3 = \mathbf{0}$
$P_3$	$4$	$2$	$6$	$6 - 4 = \mathbf{2}$	$2 - 2 = \mathbf{0}$	$4 - 4 = \mathbf{0}$
$P_4$	$5$	$8$	$24$	$24 - 5 = \mathbf{19}$	$19 - 8 = \mathbf{11}$	$16 - 5 = \mathbf{11}$

$\overline{TAT} = \frac{15 + 8 + 1 + 2 + 19}{5} = \frac{45}{5} = \mathbf{9.0\text{ ms}}$ $\overline{WT} = \frac{8 + 3 + 0 + 0 + 11}{5} = \frac{22}{5} = \mathbf{4.4\text{ ms}}$

Direct Metric Comparison on Identical Workload

• Non-Preemptive SJF Average Waiting Time: $6.0\text{ ms}$
• Preemptive SRTF Average Waiting Time: $\mathbf{4.4\text{ ms}}$ (Optimal!)
• SRTF slashed average waiting time by $26.7\%$ compared to non-preemptive SJF, and achieved an immediate response time of $0\text{ ms}$ for four out of five processes.

---

4. Advantages, Disadvantages & Starvation

Advantages of SRTF:

1. Guarantees Minimal Average Waiting Time: Provably optimal; provides the theoretical standard benchmark against which all other scheduling algorithms are evaluated.
2. Superior Response Time: New short tasks receive immediate CPU access, drastically lowering initial response latency compared to FCFS.

Disadvantages of SRTF:

1. Unimplementable in Pure Practice: An operating system kernel cannot know the exact execution length of an upcoming CPU burst in advance.
2. Indefinite Blocking (Starvation): Processes with large CPU burst requirements may starve indefinitely if a continuous stream of short-burst processes enters the Ready Queue.
3. No Support for Priority: A mission-critical kernel daemon with a large burst will be starved by trivial user-space tasks with short bursts.
4. Poor Response Time for Long Processes: Long-running computational processes suffer severe turnaround and response latency degradation.

---

5. Predicting Future CPU Bursts: Exponential Averaging

Because the operating system cannot foresee how many milliseconds a process will compute before its next system call, practical systems estimate the next burst using Exponential Averaging (Exponential Smoothing):

$\mathbf{\tau_{n+1} = \alpha \cdot t_n + (1 - \alpha) \cdot \tau_n}$

Where:

• $t_n$: Actual duration of the $n^{\text{th}}$ (most recent) CPU burst.
• $\tau_n$: Predicted duration for the $n^{\text{th}}$ CPU burst.
• $\tau_{n+1}$: Predicted duration for the upcoming $(n+1)^{\text{th}}$ CPU burst.
• $\alpha$: Smoothing weighting factor ($0 \le \alpha \le 1$).

Exponential Smoothing Factor Boundary Analysis

Analyzing how the weighting parameter alpha governs scheduler memory

Pure History

Alpha = 0 (No Adaptation)

🏛️

Dominant Architecture / Domaintau_{n+1} = tau_n

• •Recent behavior is completely ignored: t_n has 0 weight.
• •The predicted value never adapts to changing process phases.
• •The forecast remains locked to the initial system default tau_0.

"Recent burst duration has no effect on upcoming predictions."

Pure Recency

Alpha = 1 (Zero History)

⚡

Dominant Architecture / Domaintau_{n+1} = t_n

• •Past history is completely discarded: tau_n has 0 weight.
• •The next burst is predicted to be exactly identical to the last observed burst.
• •Highly volatile: susceptible to extreme noise from occasional brief I/O spikes.

"Only the most recent burst matters; prior historical trends are discarded."

Expanding the Historical Horizon:

By repeated algebraic substitution: $\tau_{n+1} = \alpha t_n + (1 - \alpha)\alpha t_{n-1} + (1 - \alpha)^2 \alpha t_{n-2} + \dots + (1 - \alpha)^j \alpha t_{n-j} + \dots + (1 - \alpha)^{n+1} \tau_0$

Because both $\alpha$ and $(1 - \alpha)$ are less than or equal to $1$, each successive historical term $(1 - \alpha)^j$ decreases exponentially. More recent bursts contribute heavily to the prediction, while ancient bursts fade into negligible background weight. In production implementations, $\alpha$ is commonly tuned to $0.5$ to balance historical stability with responsiveness.

---

📐 Architecture / Visual Blueprint

The SRTF Preemption & State Migration Lifecycle

The diagram below maps the runtime decision loop of the Short-Term Scheduler under SRTF when a new process arrives:

Architecture Flow

SRTF Dynamic Preemption & State Migration Engine

The kernel decision loop comparing newcomer burst against currently running remaining time

📥Job Admission (Memory)

⚖️Short-Term Scheduler (Arbiter)

⚡Execution Core

1Interrupt Check

2If Shorter

3Switch Core

📥Burst = BT_new

Process Arrival

Newcomer P_new

⚖️Kernel Comparison

Remaining Time Test

BT_new < Remaining(P_curr)?

🔄Save PCB State

Context Preemption

Evict P_curr to Queue

⚡CPU Granted

Dispatch Shortest

Execute P_new

💡Click or hover any card or transition arrow above to inspect deep-dive operational mechanics

---

🏭 In The Real World: Production Case Study

Distributed Stage Scheduling in Apache Spark & Database Query Planners

While OS kernels cannot predict arbitrary user program execution lengths, specialized production systems leverage SJF/SRTF principles where job sizes are deterministic:

Distributed DAG Task Engine: Stage Prioritization

Applying Shortest Job First principles to distributed compute stages

Scheduled First (SJF)

Stage A: Index Scan (10 KB)

⚡

Dominant Architecture / DomainEstimated Execution: ~2ms

• •Minimal Burst: Lightweight partition read finishes in single-digit milliseconds.
• •Early Materialization: Frees intermediate memory buffers for downstream map tasks.
• •Lowers Average Stage Latency: Dramatically cuts cluster-wide stage wait queues.

"Short stages are dispatched immediately to minimize overall DAG turnaround time."

Queued for Later

Stage B: Distributed Join (500 GB)

🐢

Dominant Architecture / DomainEstimated Execution: ~120s

• •Heavy Compute Burst: Involves cluster-wide shuffle network serialization and disk spill.
• •Deferred Execution: Runs in dedicated batch executor pool once quick queries clear.
• •Prevents Convoy Blocking: Avoids stalling hundreds of concurrent ad-hoc analytics tasks.

"Heavy batch stages are deferred behind quick analytical jobs to protect interactive SLAs."

Production Implementations:

1. Database Query Optimizers (PostgreSQL / BigQuery): When executing multiple sub-queries, cost-based optimizers estimate cost using table row counts and index metadata. Independent short scans run first to materialize quick intermediate buffers, reducing lock holding times.
2. Apache Spark Job Scheduling: In multi-tenant Spark clusters, the Fair Scheduler pools tasks. Short ad-hoc analytical queries are placed in high-priority queues with burst limits, ensuring quick business queries never sit starved behind massive 10-hour ETL batch jobs.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: Prove why Shortest Remaining Time First (SRTF) is provably optimal with respect to average waiting time. Answer:

1. Consider moving a shorter process ahead of a longer process in a non-preemptive schedule.
2. If process $P_A$ with burst $t_A$ runs before process $P_B$ with burst $t_B$ (where $t_A < t_B$), $P_A$ finishes at $t_A$ and $P_B$ waits $t_A$. Total wait contributed $= t_A$.
3. If their order is reversed ($P_B$ runs first), total wait contributed $= t_B$.
4. Since $t_A < t_B$, scheduling the shorter job first decreases the waiting time of the subsequent job by $(t_B - t_A)$, while the shorter job finishes earlier.
5. Under preemptive SRTF, this minimization is enforced continuously at every decision instant, yielding the absolute mathematical minimum for average waiting time.

Question 2: Explain the Starvation (Indefinite Blocking) problem in SJF/SRTF scheduling. What operational technique resolves it? Answer:

1. Starvation: If short-burst processes arrive continuously in the Ready Queue, long-burst processes will repeatedly be passed over or preempted, remaining in the Ready Queue indefinitely without ever completing.
2. Resolution via Aging: An operating system technique where the priority or virtual burst of an awaiting process is gradually adjusted over time. As a long process waits longer in the queue, its effective priority increases until it is guaranteed to execute.

Common Interview Traps

• The "SRTF has Zero Response Time for All Jobs" Fallacy: SRTF yields fantastic response times only for short jobs. Long jobs that arrive early may be preempted multiple times and sit in the queue for minutes, accumulating massive response delays.
• Assuming Preemption Occurs When Remaining Times are Equal: If running process $P_A$ has a remaining burst of $3\text{ ms}$ and newcomer $P_B$ arrives with $BT = 3\text{ ms}$, no preemption occurs. The running process keeps the CPU because $P_B$ does not have a shorter remaining burst time. Context switching incurs overhead and is only justified when the newcomer strictly reduces remaining time.
• Confusing Actual Burst ($t_n$) with Predicted Burst ($\tau_n$) in Formulas: In exponential smoothing questions, always distinguish $t_n$ (measured physical execution time) from $\tau_n$ (estimated model parameter).

---

🗺️View Complete Operating Systems Roadmap & Syllabus

← Previous Topic3.2 Non-Preemptive FCFS & Convoy EffectNext Topic →3.4 Priority Scheduling & Starvation (Aging)