You are at a supermarket with a full trolley. The person behind you is holding just one packet of bread. Most people would say, "Go ahead, you'll only take a minute." You lose one minute, but they save ten. Overall, people spend less time waiting.
That small act of kindness is exactly the idea behind Shortest Job First (SJF) scheduling.
SJF scheduling gives the CPU to the process with the smallest next CPU burst. Its preemptive version, Shortest Remaining Time First (SRTF), switches to a newly arrived process if that process needs less time than what the running process has left.
In FCFS Scheduling we saw how one long job at the front of the queue makes everyone wait (the convoy effect). SJF fixes that problem so well that it is provably optimal for average waiting time. But it comes with two serious catches: the OS does not actually know burst times in advance, and long jobs can starve. This chapter covers all of it.
Two Versions: SJF and SRTF
SJF (non-preemptive) | SRTF (preemptive SJF) | |
|---|---|---|
Decision point | Only when the CPU becomes free | When the CPU becomes free and whenever a new process arrives |
Compares | Full burst times of waiting processes | Remaining time of the running process vs bursts of waiting processes |
Running process can be interrupted? | No | Yes, by a process with a strictly shorter remaining time |
Also called | Shortest Job Next (SJN), Shortest Process Next | Shortest Remaining Time Next (SRTN), Shortest Remaining Processing Time (SRPT) |
A small but important point: the name says "job", but what matters is the length of the next CPU burst, not the total running time of the program. A program that runs for hours but does a lot of I/O has many short CPU bursts.
Tie-breaking rule used in this chapter: if two processes have the same burst (or remaining) time, the one that arrived earlier goes first, and SRTF does not preempt on a tie.
Example 1: SJF When Everyone Arrives at Time 0
Process | Arrival Time | Burst Time |
|---|---|---|
P1 | 0 | 6 |
P2 | 0 | 2 |
P3 | 0 | 8 |
P4 | 0 | 3 |
P5 | 0 | 4 |
When all processes are available together, SJF simply sorts them by burst time: 2, 3, 4, 6, 8.
| P2 | P4 | P5 | P1 | P3 |
0 2 5 9 15 23
Process | BT | CT | TAT | WT |
|---|---|---|---|---|
P1 | 6 | 15 | 15 | 9 |
P2 | 2 | 2 | 2 | 0 |
P3 | 8 | 23 | 23 | 15 |
P4 | 3 | 5 | 5 | 2 |
P5 | 4 | 9 | 9 | 5 |
SJF : Average WT = (9 + 0 + 15 + 2 + 5) / 5 = 31 / 5 = 6.2
Average TAT = 54 / 5 = 10.8
FCFS on the same data (order P1, P2, P3, P4, P5):
| P1 | P2 | P3 | P4 | P5 |
0 6 8 16 19 23
Average WT = (0 + 6 + 8 + 16 + 19) / 5 = 49 / 5 = 9.8
Same work, same finishing time (23), but the average wait drops from 9.8 to 6.2.
Why SJF Is Optimal
This is a favourite interview and exam question, and the reasoning is short and elegant.
When all processes are ready at time 0 and run one after another, the waiting time of a process is the sum of the bursts ahead of it. If the bursts in running order are b1, b2, ..., bn:
WT(1st) = 0
WT(2nd) = b1
WT(3rd) = b1 + b2
...
WT(nth) = b1 + b2 + ... + b(n-1)
Total WT = (n-1)·b1 + (n-2)·b2 + ... + 1·b(n-1) + 0·bn
The first burst is counted n-1 times, the second n-2 times, and so on. To make the total as small as possible, the biggest multiplier must go with the smallest burst. That means sorting bursts in increasing order, which is exactly SJF.
Another way to see it is the exchange argument: take any schedule where a longer job L runs just before a shorter job S. Swap them. S now finishes L units earlier, while L finishes only S units later. Because S < L, the total waiting time goes down. Keep swapping until no such pair remains, and you end up with SJF.
Non-preemptive SJF gives the minimum average waiting time when all processes are available together. When processes arrive at different times, its preemptive form SRTF gives the minimum average waiting time (assuming burst times are known and context switches are free).
Be careful with the wording in exams: with different arrival times, non-preemptive SJF is not always optimal. It may start a long job just before a very short one arrives, and it cannot change its mind. SRTF can.
Example 2: SJF With Different Arrival Times
We will use the same data for SJF, SRTF and FCFS so you can compare them directly.
Process | Arrival Time | Burst Time |
|---|---|---|
P1 | 0 | 8 |
P2 | 1 | 5 |
P3 | 2 | 3 |
P4 | 3 | 1 |
P5 | 4 | 6 |
P6 | 5 | 2 |
The key rule: SJF only chooses among processes that have already arrived.
Step-by-step trace (non-preemptive SJF)
t = 0 : ready = {P1(8)} → only choice, P1 runs to 8
(P2..P6 arrive meanwhile, but SJF cannot interrupt P1)
t = 8 : ready = {P2(5), P3(3), P4(1), P5(6), P6(2)}
shortest = P4(1) → runs 8 to 9
t = 9 : ready = {P2(5), P3(3), P5(6), P6(2)}
shortest = P6(2) → runs 9 to 11
t = 11 : ready = {P2(5), P3(3), P5(6)}
shortest = P3(3) → runs 11 to 14
t = 14 : ready = {P2(5), P5(6)}
shortest = P2(5) → runs 14 to 19
t = 19 : ready = {P5(6)} → runs 19 to 25
| P1 | P4 | P6 | P3 | P2 | P5 |
0 8 9 11 14 19 25
Process | AT | BT | CT | TAT | WT |
|---|---|---|---|---|---|
P1 | 0 | 8 | 8 | 8 | 0 |
P2 | 1 | 5 | 19 | 18 | 13 |
P3 | 2 | 3 | 14 | 12 | 9 |
P4 | 3 | 1 | 9 | 6 | 5 |
P5 | 4 | 6 | 25 | 21 | 15 |
P6 | 5 | 2 | 11 | 6 | 4 |
Average TAT = 71 / 6 ≈ 11.83
Average WT = 46 / 6 ≈ 7.67
Notice how P1, the longest job, grabbed the CPU at time 0 simply because it was the only one there. Every short job then had to wait until time 8. That is the weakness SRTF removes.
Example 3: SRTF (Preemptive SJF)
Same data. Now, every time a process arrives, we compare its burst with the remaining time of the running process. If the newcomer is strictly shorter, it takes over.
Step-by-step trace
Time Event Remaining times (ready + running) Runs
---- ----------------- --------------------------------------- ----
0 P1 arrives P1=8 P1
1 P2 arrives P1=7, P2=5 5 < 7 → preempt P1 P2
2 P3 arrives P1=7, P2=4, P3=3 3 < 4 → preempt P2 P3
3 P4 arrives P1=7, P2=4, P3=2, P4=1 1 < 2 → preempt P4
4 P4 done, P5 arr. P1=7, P2=4, P3=2, P5=6 shortest = P3 P3
5 P6 arrives P1=7, P2=4, P3=1, P5=6, P6=2 P3
P6 (2) is not shorter than P3 (1)
6 P3 done P1=7, P2=4, P5=6, P6=2 shortest = P6 P6
8 P6 done P1=7, P2=4, P5=6 shortest = P2 P2
12 P2 done P1=7, P5=6 shortest = P5 P5
18 P5 done P1=7 P1
25 P1 done
| P1 | P2 | P3 | P4 | P3 | P6 | P2 | P5 | P1 |
0 1 2 3 4 6 8 12 18 25
Process | AT | BT | CT | TAT | WT | RT |
|---|---|---|---|---|---|---|
P1 | 0 | 8 | 25 | 25 | 17 | 0 |
P2 | 1 | 5 | 12 | 11 | 6 | 0 |
P3 | 2 | 3 | 6 | 4 | 1 | 0 |
P4 | 3 | 1 | 4 | 1 | 0 | 0 |
P5 | 4 | 6 | 18 | 14 | 8 | 8 |
P6 | 5 | 2 | 8 | 3 | 1 | 1 |
Average TAT = 58 / 6 ≈ 9.67
Average WT = 33 / 6 = 5.5
Average RT = 9 / 6 = 1.5
Two things to notice:
Waiting time is not the same as response time any more. P1 started at 0 (RT = 0) but spent 17 units waiting in total, because it was preempted and sat in the ready queue from 1 to 18. Always compute WT with
WT = TAT - BT, which automatically adds up every waiting period.A process can be preempted several times. P2 ran for just 1 unit before P3 took over, then waited until 8.
Comparing All Three on the Same Data
Algorithm | Avg TAT | Avg WT | Avg RT | Preemptions |
|---|---|---|---|---|
FCFS | 14.50 | 10.33 | 10.33 | 0 |
SJF (non-preemptive) | 11.83 | 7.67 | 7.67 | 0 |
SRTF | 9.67 | 5.50 | 1.50 | 3 |
(The FCFS schedule here is P1, P2, P3, P4, P5, P6 with completion times 8, 13, 16, 17, 23, 25.)
SRTF wins on every average, and it pays for it with extra context switches. In this example only 3 preemptions happened, but with many short arrivals the number can grow quickly.
SRTF in C
This program simulates SRTF one time unit at a time. At every tick it picks the arrived process with the smallest remaining time. It uses the data from Example 3.
#include <stdio.h>
#define N 6
int main(void) {
const char *name[N] = {"P1", "P2", "P3", "P4", "P5", "P6"};
int at[N] = {0, 1, 2, 3, 4, 5};
int bt[N] = {8, 5, 3, 1, 6, 2};
int rem[N], ct[N], first[N];
for (int i = 0; i < N; i++) {
rem[i] = bt[i];
first[i] = -1; /* not started yet */
}
int time = 0, finished = 0, prev = -2;
printf("Gantt:");
/* Simulate one time unit at a time. At every tick pick the
arrived process with the smallest REMAINING time. */
while (finished < N) {
int pick = -1;
for (int i = 0; i < N; i++) {
if (at[i] <= time && rem[i] > 0 &&
(pick == -1 || rem[i] < rem[pick]))
pick = i; /* strict '<' : ties go to the
lower index (earlier arrival) */
}
if (pick == -1) { /* nobody ready: CPU idle */
if (prev != -1) printf(" [%d]IDLE", time);
prev = -1;
time++;
continue;
}
if (pick != prev) /* a new segment starts */
printf(" [%d]%s", time, name[pick]);
prev = pick;
if (first[pick] == -1) first[pick] = time;
rem[pick]--;
time++;
if (rem[pick] == 0) {
ct[pick] = time;
finished++;
}
}
printf(" [%d]\n\n", time);
double sum_tat = 0, sum_wt = 0, sum_rt = 0;
printf("Proc AT BT CT TAT WT RT\n");
for (int i = 0; i < N; i++) {
int tat = ct[i] - at[i];
int wt = tat - bt[i];
int rt = first[i] - at[i];
sum_tat += tat; sum_wt += wt; sum_rt += rt;
printf("%-4s %3d %3d %3d %4d %3d %3d\n",
name[i], at[i], bt[i], ct[i], tat, wt, rt);
}
printf("\nAverage TAT = %.2f\n", sum_tat / N);
printf("Average WT = %.2f\n", sum_wt / N);
printf("Average RT = %.2f\n", sum_rt / N);
return 0;
}Output:
Gantt: [0]P1 [1]P2 [2]P3 [3]P4 [4]P3 [6]P6 [8]P2 [12]P5 [18]P1 [25]
Proc AT BT CT TAT WT RT
P1 0 8 25 25 17 0
P2 1 5 12 11 6 0
P3 2 3 6 4 1 0
P4 3 1 4 1 0 0
P5 4 6 18 14 8 8
P6 5 2 8 3 1 1
Average TAT = 9.67
Average WT = 5.50
Average RT = 1.50It matches the hand trace exactly. Simulating tick by tick is the easiest way to get preemptive algorithms right. A real kernel would not scan an array every tick; it would keep processes in a min-heap keyed on remaining time, so picking the shortest costs O(log n).
Turning this into non-preemptive SJF is a one-line idea: once a process is picked, let it run until rem becomes 0 before choosing again.
The Big Problem: Nobody Knows the Burst Time
All of our examples were given burst times. A real OS is not. When a process becomes ready, the scheduler has no way of knowing how long its next CPU burst will last. It depends on the program's input, branches, cache behaviour and when it decides to do I/O.
So pure SJF is impossible to implement exactly for short-term CPU scheduling. It serves as a benchmark: the best you could do with perfect knowledge.
Two practical workarounds:
Batch systems (long-term scheduling): users submit a time limit with each job. The scheduler can use that as the "burst", and users are motivated to be honest because exceeding the limit kills the job.
Prediction: guess the next burst from the lengths of previous bursts. Programs tend to behave similarly from one burst to the next.
Predicting the Next Burst: Exponential Averaging
The standard prediction formula is:
τ(n+1) = α · t(n) + (1 - α) · τ(n)
t(n) = actual length of the most recent (nth) CPU burst
τ(n) = what we had predicted for that burst
τ(n+1) = prediction for the next burst
α = weight, 0 ≤ α ≤ 1
The new prediction is a blend of "what just happened" and "what we believed before".
α = 0: recent behaviour is ignored, the prediction never changes.α = 1: only the last burst counts, history is ignored.α = 1/2(common choice): recent behaviour and history are weighted equally.
Worked example
Let α = 0.5 and the initial guess τ0 = 10. The process then has actual bursts of 6, 8, 2 and 4.
τ1 = 0.5 × 6 + 0.5 × 10 = 3 + 5 = 8
τ2 = 0.5 × 8 + 0.5 × 8 = 4 + 4 = 8
τ3 = 0.5 × 2 + 0.5 × 8 = 1 + 4 = 5
τ4 = 0.5 × 4 + 0.5 × 5 = 2 + 2.5 = 4.5
n | Prediction τ(n) | Actual t(n) |
|---|---|---|
0 | 10 | 6 |
1 | 8 | 8 |
2 | 8 | 2 |
3 | 5 | 4 |
4 | 4.5 | (not yet known) |
Why is it called "exponential"? If you expand the formula, each older burst gets multiplied by one more factor of (1 - α):
τ(n+1) = α·t(n) + (1-α)·α·t(n-1) + (1-α)²·α·t(n-2) + ... + (1-α)^(n+1)·τ0
Since (1 - α) < 1, old bursts fade away exponentially. The predictor adapts when a process changes behaviour, but one unusual burst does not throw it off completely.
Starvation in SJF and SRTF
SJF always favours short jobs. If short jobs keep arriving, a long job may never get the CPU. That is starvation (also called indefinite blocking).
t = 0 : ready = {Long(50), A(2)} → A runs
t = 2 : B(3) arrives → B runs
t = 5 : C(2) arrives → C runs
t = 7 : D(1) arrives → D runs
... : as long as short jobs keep coming, Long waits forever
SRTF makes it worse: even a long job that has already started can be pushed out again and again.
Notice that this is different from FCFS. In FCFS a process may wait a long time, but the wait is always finite. In SJF the wait can be unbounded.
A Fix: Highest Response Ratio Next (HRRN)
HRRN is a non-preemptive variant that still prefers short jobs but also rewards waiting. Each time the CPU becomes free, compute for every ready process:
Response Ratio = (Waiting time so far + Burst time) / Burst time
= 1 + Waiting time / Burst time
The process with the highest ratio runs next.
A short job gets a high ratio quickly (small denominator), so short jobs are still favoured.
A long job's ratio keeps growing as it waits, so eventually it wins. No starvation.
Let's compare SJF and HRRN on this data:
Process | AT | BT |
|---|---|---|
P1 | 0 | 4 |
P2 | 1 | 6 |
P3 | 3 | 3 |
P4 | 5 | 5 |
P5 | 7 | 2 |
SJF keeps pushing P2 (burst 6) back:
| P1 | P3 | P5 | P4 | P2 |
0 4 7 9 14 20
WT: P1=0, P2=13, P3=1, P4=4, P5=0 → Average = 18 / 5 = 3.6, worst = 13
HRRN trace:
t = 0 : only P1 → P1 runs 0-4
t = 4 : P2 = (3+6)/6 = 1.50, P3 = (1+3)/3 = 1.33 → P2 runs 4-10
t = 10 : P3 = (7+3)/3 = 3.33, P4 = (5+5)/5 = 2.00,
P5 = (3+2)/2 = 2.50 → P3 runs 10-13
t = 13 : P4 = (8+5)/5 = 2.60, P5 = (6+2)/2 = 4.00 → P5 runs 13-15
t = 15 : P4 only → P4 runs 15-20
| P1 | P2 | P3 | P5 | P4 |
0 4 10 13 15 20
WT: P1=0, P2=3, P3=7, P4=10, P5=6 → Average = 26 / 5 = 5.2, worst = 10
HRRN gives a slightly higher average (5.2 vs 3.6) but a lower worst case (10 vs 13), and it can never starve anyone. This trade-off between average performance and fairness appears again and again in scheduling. The general version of "increase priority as a process waits" is called aging, and you will see it in Priority Scheduling.
Advantages and Disadvantages
Advantages | Disadvantages |
|---|---|
Minimum average waiting time (SJF with simultaneous arrivals, SRTF in general) | Needs burst times, which are unknown; must be predicted |
High throughput: many short jobs finish quickly | Long processes can starve |
Removes the convoy effect of FCFS | SRTF causes more context switches |
SRTF gives excellent response time for short interactive bursts | Unfair to CPU-bound processes; the order is unpredictable for users |
Common Mistakes
Choosing a process that has not arrived yet. At time 0 in Example 2, P4 (burst 1) is the shortest overall, but it arrives at 3. SJF can only pick from processes already in the ready queue.
Comparing the newcomer with the original burst instead of the remaining time in SRTF. At t = 3, P3 had 2 units left, not 3.
Using
RTas waiting time in SRTF. For preempted processes, WT includes every gap. UseWT = TAT - BT.Preempting on a tie. The standard rule is to preempt only when the newcomer is strictly shorter, which avoids a useless context switch. If a question uses a different rule, it will say so.
Saying non-preemptive SJF is always optimal. It is optimal only when all processes are available at the same time.
Thinking SJF is used directly in modern OSes. It is used as a model and approximated through prediction and feedback (see Multilevel Queue & Feedback Queue Scheduling).
Interview Questions
What is the difference between SJF and SRTF?
SJF is non-preemptive: once a process starts its burst, it finishes it. SRTF is preemptive: when a new process arrives with a burst shorter than the running process's remaining time, the running process is preempted.
Why is SJF called optimal?
Because running shorter bursts first minimises the total (and hence average) waiting time. Moving a short job ahead of a long one saves the short job more than it costs the long one.
Can SJF be implemented exactly in a real OS?
Not for short-term CPU scheduling, because the length of the next CPU burst is unknown. It is approximated by predicting bursts, usually with exponential averaging.
What does α control in exponential averaging?
How much weight the most recent burst gets. α = 0 ignores recent behaviour, α = 1 uses only the last burst, and α = 0.5 weights both equally.
Does SJF suffer from starvation?
Yes. A long job can wait forever if shorter jobs keep arriving. Aging, or HRRN, solves it.
How does HRRN avoid starvation?
Its ratio (W + S) / S grows as waiting time W grows, so a long-waiting process eventually has the highest ratio and gets the CPU.
In SRTF, are waiting time and response time equal?
Not in general. A process may start immediately (RT = 0) and then be preempted and wait later, so WT can be larger than RT.
The Main Idea
SJF picks the ready process with the shortest next CPU burst. SRTF does the same but also preempts the running process whenever a shorter one arrives.
CPU free (SJF) / new arrival or CPU free (SRTF)
↓
Look only at processes that have arrived
↓
Pick the smallest burst (SJF) / remaining time (SRTF)
↓
Run it
Key facts:
SJF → non-preemptive, optimal avg WT when all arrive together
SRTF → preemptive, optimal avg WT in general
Both → need burst estimates, risk starvation
Fix → exponential averaging to predict, aging / HRRN to stop starvation
Shortest first minimises waiting, but only if you can guess "shortest" well, and only if you make sure long jobs are not forgotten.
SJF is really a special case of a more general idea: give the CPU to the "most important" process. In the next chapter, Priority Scheduling, importance is set by a priority number instead of burst length.