Chapter 12 of 38

SJF & SRTF Scheduling

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.50

It 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 RT as waiting time in SRTF. For preempted processes, WT includes every gap. Use WT = 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.