What is Shortest-Job-First (SJF) Scheduling?
Learn Shortest-Job-First scheduling — how it minimizes waiting time, burst-time estimation, and starvation risk — with OS interview questions.
Expected Interview Answer
Shortest-Job-First (SJF) is a scheduling algorithm that always dispatches the ready process with the smallest total CPU burst time next, which provably minimizes average waiting time among non-preemptive algorithms for a given set of arrivals.
In its non-preemptive form, SJF picks the process with the shortest known burst time from the ready queue whenever the CPU becomes free, and lets it run uninterrupted to completion; a preemptive variant, Shortest-Remaining-Time-First, additionally interrupts the running process if a new arrival has a shorter remaining burst. The mathematical appeal is strong: because short jobs finish and leave the queue quickly, the processes behind them accumulate far less waiting time than under FCFS, giving SJF the minimum possible average waiting time for a fixed set of burst times. The catch is that SJF requires knowing (or accurately estimating) each process’s burst time in advance, which is generally impossible for interactive or general-purpose workloads — real implementations estimate it using exponential averaging of past bursts. Without safeguards, SJF also risks starving long processes indefinitely if a steady stream of short jobs keeps arriving, since a long job can always be pushed behind newer short arrivals.
- Minimizes average waiting time among non-preemptive algorithms
- Reduces queue buildup by clearing short jobs quickly
- Foundation for the preemptive SRTF variant
- Illustrates the fundamental trade-off between optimality and predictability
AI Mentor Explanation
SJF scheduling is like a coach sending in the batter with the shortest planned innings next — a quick-single specialist batting before a player set to occupy the crease for a marathon session. This clears batters through the order fastest on average, so the team as a whole gets through more turns sooner. The downside is a batter with a genuinely long, patient innings planned could keep getting pushed behind newer quick-turn players indefinitely.
Step-by-Step Explanation
Step 1
Estimate burst time
The scheduler obtains or estimates each ready process’s remaining CPU burst time, often via exponential averaging of past bursts.
Step 2
Select shortest job
Among all processes currently in the ready queue, the one with the smallest burst time estimate is chosen.
Step 3
Dispatch non-preemptively
The selected process runs to completion without interruption in the classic non-preemptive SJF variant.
Step 4
Repeat selection
Once it finishes, the scheduler again scans the ready queue and picks the new shortest job, repeating until the queue is empty.
What Interviewer Expects
- Correct statement that SJF minimizes average waiting time
- Recognition that burst time must be known or estimated in advance
- Awareness of the starvation risk for long processes
- Ability to distinguish non-preemptive SJF from preemptive SRTF
Common Mistakes
- Assuming SJF is always practical without acknowledging the burst-time-prediction problem
- Confusing SJF with priority scheduling
- Forgetting that SJF can starve long processes
- Not knowing SJF and SRTF are different (non-preemptive vs preemptive)
Best Answer (HR Friendly)
“SJF scheduling always runs whichever waiting job will take the least time next, which mathematically gives the best possible average wait across everyone. The catch is you need to know how long each job will take in advance, which is rarely true in real systems, and a job that keeps needing a lot of time can get pushed back again and again by a stream of shorter newcomers.”
Code Example
struct process {
int pid;
int arrival_time;
int burst_time;
int completed;
};
int pick_shortest_job(struct process procs[], int n, int current_time) {
int idx = -1;
int shortest = INT_MAX;
for (int i = 0; i < n; i++) {
if (!procs[i].completed &&
procs[i].arrival_time <= current_time &&
procs[i].burst_time < shortest) {
shortest = procs[i].burst_time;
idx = i;
}
}
return idx; /* -1 means no process is ready yet */
}Follow-up Questions
- How does SJF differ from Shortest-Remaining-Time-First (SRTF)?
- How do real schedulers estimate burst time without knowing it in advance?
- Why does SJF risk starving long processes, and how can aging help?
- Why is SJF considered provably optimal for average waiting time?
MCQ Practice
1. What does SJF scheduling optimize for, among non-preemptive algorithms?
Given a fixed set of burst times, dispatching the shortest job first provably minimizes the average waiting time among non-preemptive policies.
2. What is the biggest practical obstacle to using SJF?
SJF needs each process’s CPU burst time ahead of time, which is generally unknowable for interactive workloads and must be estimated.
3. What risk does SJF introduce for long-running processes?
A long process can be repeatedly passed over if shorter jobs keep arriving, potentially delaying it indefinitely without a fairness safeguard.
Flash Cards
What is SJF scheduling? — A policy that dispatches the ready process with the smallest burst time next.
What does SJF minimize? — Average waiting time, among non-preemptive scheduling algorithms.
What does SJF require to work? — Knowledge or an estimate of each process’s CPU burst time in advance.
What is SJF’s main weakness? — It can starve long processes if short jobs keep arriving ahead of them.