SJF & SRTF Scheduling
IntermediateShortest Job First (SJF) minimizes average waiting time by running the shortest process next, while its preemptive variant SRTF can interrupt a running process when a shorter job arrives.
Overview
Shortest Job First scheduling selects the process with the smallest CPU burst time from the ready queue. It is provably optimal for minimizing average waiting time among all non-preemptive algorithms. The preemptive version — Shortest Remaining Time First (SRTF) — preempts the running process if a new arrival has a shorter remaining burst. While optimal in theory, SJF has a fundamental practical problem: the OS cannot know the CPU burst time in advance. Real implementations use exponential averaging (aging) to predict the next burst from historical burst times. SJF can cause starvation: if short processes continuously arrive, long processes may never run.
SJF vs SRTF: Gantt Charts and Waiting Times
With the same process set, SJF (non-preemptive) and SRTF (preemptive) produce different schedules. SRTF always produces equal or lower average waiting time than SJF, at the cost of more context switches.
// Process set for both SJF and SRTF comparison:
// Process | Arrival | Burst
// P1 | 0 | 8
// P2 | 1 | 4
// P3 | 2 | 9
// P4 | 3 | 5
// Non-preemptive SJF:
// At t=0: only P1 — run P1 (burst=8) → finishes at t=8
// At t=8: P2(4), P3(9), P4(5) all available → pick P2 (shortest)
// At t=12: P3(9), P4(5) → pick P4 → At t=17: pick P3
// Gantt: | P1(0-8) | P2(8-12) | P4(12-17) | P3(17-26) |
// Waiting: P1=0, P2=7, P3=15, P4=9 → Avg = 7.75
// Preemptive SRTF:
// t=0: P1 starts (remaining=8)
// t=1: P2 arrives (burst=4) < P1 remaining (7) → preempt! Run P2
// t=2: P3 arrives (burst=9) > P2 remaining (3) → P2 continues
// t=3: P4 arrives (burst=5) > P2 remaining (2) → P2 continues
// t=5: P2 done → P4(5) vs P1(7) vs P3(9) → run P4
// t=10: P4 done → P1(7) vs P3(9) → run P1
// t=17: P1 done → run P3
// Gantt: |P1(0-1)|P2(1-5)|P4(5-10)|P1(10-17)|P3(17-26)|
// Waiting: P1=9, P2=0, P3=15, P4=2 → Avg = 6.5 ← better than SJF!
int[] arrival = {0, 1, 2, 3};
int[] burst = {8, 4, 9, 5};
// SRTF avg waiting = 6.5 vs SJF avg waiting = 7.75
System.out.println("SRTF consistently achieves lower or equal avg wait vs SJF");Burst Time Prediction: Exponential Averaging
Since the OS cannot know future burst times, it predicts them using exponential averaging (also called exponential moving average). The prediction τ(n+1) = α * t(n) + (1-α) * τ(n), where t(n) is the actual last burst and τ(n) is the previous prediction. Alpha (α) controls how much weight is given to recent history vs old history. Typically α = 0.5.
// Exponential averaging to predict next CPU burst
// τ(n+1) = α × t(n) + (1-α) × τ(n)
// α = 0.5 (equal weight to recent and history)
double alpha = 0.5;
double tau = 10.0; // initial prediction (e.g., 10ms)
// Actual burst times observed over time (milliseconds)
double[] actualBursts = {6, 4, 6, 4, 13, 13, 13};
System.out.printf("Initial prediction: %.1f ms%n", tau);
for (int i = 0; i < actualBursts.length; i++) {
double actual = actualBursts[i];
double nextPrediction = alpha * actual + (1 - alpha) * tau;
System.out.printf("Actual burst: %.0f ms → Prediction for next: %.2f ms%n",
actual, nextPrediction);
tau = nextPrediction;
}
// Predictions converge toward the true average burst time over time
// α=1.0: only last burst matters (no history)
// α=0.0: only initial estimate matters (no learning)
// α=0.5: balanced — standard choiceKey Points to Remember
- 1SJF is provably optimal for minimizing average waiting time among non-preemptive algorithms.
- 2SRTF (preemptive SJF) achieves equal or lower average waiting time than SJF, with more context switches.
- 3The fundamental problem with SJF: burst time is not known in advance — use exponential averaging to predict.
- 4SJF can cause starvation: long processes may wait indefinitely if short ones keep arriving.
- 5Exponential averaging: τ(n+1) = α × t(n) + (1-α) × τ(n); α=0.5 is the typical choice.
- 6SRTF is used in interactive OS schedulers combined with priority to balance optimality and fairness.
Interview Questions
Sign in to ask AriaWhy is SJF considered optimal for minimizing average waiting time?
What is the major practical limitation of SJF scheduling?
How does SRTF differ from SJF and when does it produce better results?
Explain exponential averaging for CPU burst prediction and its sensitivity to alpha.
Ask Aria about SJF & SRTF Scheduling
Your personal AI tutor — ask anything about this concept
Revision Status
Personal Notes
Sign in to save personal notes for this topic.
Discussion
Sign in to join the discussion.