Lesson 5.3: Shortest-Job-First and Shortest-Remaining-Time-First

01 Introduction

Lesson 5.2 ended with the convoy effect: a long CPU-bound process at the head of the ready queue delays every process behind it, and the average waiting time suffers. The natural response is to run the short processes first, and that is exactly what Shortest-Job-First (SJF) scheduling does. The rule is simple to state — always pick the process with the smallest next CPU burst — and it has a remarkable property: it minimizes the average waiting time for a given set of processes. No other non-preemptive algorithm can do better.

Its preemptive variant, Shortest-Remaining-Time-First (SRTF), goes further. When a new process arrives with a shorter remaining time than the currently running process, SRTF preempts the running process and switches to the new one. This produces an even lower average waiting time than SJF, and among all preemptive algorithms, SRTF is optimal for that metric.

The catch is that neither algorithm can be implemented exactly as described, because the scheduler does not know in advance how long a process's next CPU burst will be. The burst time is a property of the process's future behaviour, and the scheduler only learns it after the fact. SJF and SRTF are therefore theoretical benchmarks — useful for understanding what is achievable, and useful as a target for approximation, but not directly implementable. The central practical question is how to estimate burst lengths well enough that an approximation to SJF captures most of its benefit.

This lesson covers the SJF and SRTF algorithms, the optimality result and its precise statement, the burst-length prediction problem and the exponential averaging technique used to solve it, the starvation risk that comes with prioritizing short jobs, and the ways in which real systems approximate SJF without ever being able to compute it exactly.

Prerequisites

This lesson builds directly on Lesson 5.2. The convoy effect and the average-waiting-time formula from section 4.7 of that lesson are the motivation for everything that follows. If the derivation (1/n) * Σ (n−k) * BT(P_k) is unfamiliar, review it before continuing.

02 Learning objectives

By the end of this lesson you will be able to

Describe the SJF and SRTF algorithms and distinguish them.
Trace SJF and SRTF schedules and compute the standard metrics.
Explain why SJF minimizes average waiting time and state the precise conditions.
Apply exponential averaging to estimate CPU burst lengths.
Explain the starvation risk of SJF and how aging mitigates it.

This lesson contributes to U5.2, U5.3, and U5.5, and to course learning outcomes CLO1, CLO3, and CLO8.

03 Required reading

OSTEP — Chapter 7, Scheduling: Introduction, through the sections on Shortest Job First and Shortest Time-to-Completion First. OSTEP's treatment of SJF is the clearest short introduction available, and its discussion of the optimality result is the basis for the worked example in this lesson.
Operating System Concepts — Chapter 5, Sections 5.3.2 and 5.3.3, Shortest-Job-First Scheduling and Shortest-Remaining-Time-First Scheduling. The formal definitions and the worked examples with the Gantt charts.
Tanenbaum & Bos — Modern Operating Systems, Chapter 2, Section 2.4.3, Shortest Job First. A complementary treatment that places SJF in the context of batch scheduling and discusses the estimation problem.
Silberschatz et al. — Chapter 5, Section 5.3.2. The exponential averaging formula appears here in its standard form. Read the derivation carefully; it is the basis for the treatment in section 4.6 of this lesson.
Linux man pages: man 7 sched. Read the description of the Completely Fair Scheduler and note how it differs from SJF while sharing the same objective of minimizing waiting time.

Reading strategy

Read OSTEP first for the intuition and the optimality argument. Then read Silberschatz for the formal definitions and the exponential averaging formula. Pay attention to the precise statement of the optimality result — it applies to a specific setting (all processes available at the same time, for SJF) and it does not apply in every situation. The worked example in section 5 of this lesson will let you verify your understanding on a concrete workload.

04 Core content

4.1 The shortest-job-first idea

The convoy effect is a consequence of running a long process before a short one. If the scheduler could simply run the short process first, the long process would be delayed by a small amount and the short process would not be delayed at all. Because the average waiting time is dominated by the many short processes, this rearrangement reduces the average substantially. Shortest-Job-First scheduling does exactly this: when the CPU becomes available, the scheduler selects the process with the smallest next CPU burst.

The rule has a natural interpretation in terms of the average-waiting-time formula from Lesson 5.2:

Average WT = (1/n) * [ (n−1)b₁ + (n−2)b₂ + … + 0·bₙ ]

The first process's burst is counted n − 1 times, the second n − 2 times, and so on. To minimize the sum, the smallest burst should receive the largest coefficient, and the largest burst should receive the smallest. That is, the burst times should be ordered from shortest to longest. SJF does this whenever a scheduling decision is made.

The algorithm was first analysed in the 1960s in the context of batch processing, where jobs were submitted with known run-time estimates. It is still the benchmark against which every other scheduling algorithm is measured for average waiting time.

4.2 Non-preemptive SJF

In its non-preemptive form, SJF works as follows:

When the CPU becomes free — because the running process has terminated or blocked — the scheduler selects the ready process with the smallest next CPU burst.
The selected process runs until it blocks or terminates. It is not interrupted, even if a process with a shorter burst arrives while it is running.

The algorithm is non-preemptive, like FCFS. The difference is in the selection rule: FCFS selects by arrival order, while SJF selects by predicted burst length. When two processes have the same predicted burst length, the tie-break is typically by arrival time (FCFS) or by process identifier; the choice affects the schedule but not the average waiting time in the common case where the tie-break preserves FIFO order.

A trace of non-preemptive SJF on a simple workload is given in the worked example. The essential behaviour is that short processes run first, long processes run last, and the average waiting time is lower than under FCFS whenever the arrival order does not already put the short processes first.

4.3 Preemptive SJF: shortest remaining time first

Non-preemptive SJF has a limitation: once a long process has started, a short process that arrives immediately afterward must wait for the entire long burst. If the scheduler could preempt the long process and run the short one, the average waiting time would be lower still. That is the idea behind Shortest-Remaining-Time-First (SRTF), also called preemptive SJF.

The rule is:

At every scheduling decision point — when a process arrives, when a process blocks, when a process terminates — compare the remaining time of the running process with the next CPU burst of the arriving process.
If the arriving process has a shorter remaining time, preempt the running process and switch to the arriving one.

The result is a schedule in which the currently running process is always the one with the least work left to do. SRTF produces an even lower average waiting time than SJF, and among all preemptive algorithms it is optimal for that metric.

Figure 5.3 — SRTF scheduling on a mixed workload. P1 is preempted at time 1 when P2 arrives with a shorter remaining time. P1 resumes at time 10 once the shorter jobs have completed. The average waiting time is 6.5 units, the lowest of the three algorithms compared in this lesson.

SRTF produces more context switches than non-preemptive SJF, because preemption is triggered whenever a shorter job arrives. The extra switches are the cost of the improved average waiting time. Whether the trade is worthwhile depends on the workload and on the cost of a context switch in the system.

4.4 Why SJF is optimal for average waiting time

The optimality of SJF is a classical result, and the argument is an exchange argument. Suppose two adjacent processes in the ready queue, A and B, with A scheduled before B, and suppose that the burst time of A is greater than the burst time of B. Consider the effect of swapping them.

Before the swap, the waiting time of A is the sum of the burst times of everything ahead of it, and the waiting time of B is that sum plus the burst time of A. The contribution of these two processes to the total waiting time is 2 × (sum ahead) + BT(A).
After the swap, the same two processes contribute 2 × (sum ahead) + BT(B).

Because BT(B) < BT(A), the sum after the swap is smaller. Repeating this exchange for every adjacent pair that is out of order eventually produces a schedule in which the processes are in order of increasing burst time, and no further swap can reduce the total. This is exactly the SJF schedule.

The precise statement of the result is important. For non-preemptive SJF, the optimality holds when all processes are available at the same time (or, more generally, when every process's arrival time is no later than the first time it could be scheduled). With arbitrary arrival times, a long process that arrives before a short one must run first under non-preemptive SJF, and the result may not be optimal. For SRTF, the optimality holds with arbitrary arrival times: at every decision point, choosing the process with the smallest remaining time produces the minimum possible average waiting time, and no preemptive schedule can do better.

Optimal for one metric, not for all

SJF and SRTF minimize the average waiting time. They do not minimize the maximum waiting time, they do not guarantee fairness, and they do not optimize response time in the sense that matters for interactive systems. A long process can wait a very long time under SRTF — potentially forever, if short processes keep arriving. The optimality result is about one statistic, not about the quality of the schedule as a whole.

4.5 The burst-length prediction problem

SJF and SRTF require the scheduler to know the length of the next CPU burst of every process. In a real system this information is not available. The burst length is a property of the process's future behaviour: how long the next computation will take before it issues an I/O request or terminates. The process itself does not know this in advance — it depends on the input data, the state of the caches, and the behaviour of the libraries the process calls. The scheduler, which only sees the process from the outside, has even less information.

There is a second complication. Even if burst lengths were known, they would not be constant. A process's burst pattern changes over time as its workload changes: a compiler compiling a large file has different burst lengths than the same compiler compiling a small one. A web server handling a request has different burst lengths depending on the request. A scheduler that used a static estimate would become progressively less accurate as the workload evolved.

The solution is to estimate burst lengths from past behaviour and to adapt the estimate as new bursts are observed. The standard technique is exponential averaging, described in the next section. The estimate is not perfect, but on real workloads it is good enough that an approximation to SJF captures most of the benefit of the exact algorithm.

4.6 Exponential averaging

Exponential averaging predicts the next CPU burst as a weighted combination of the most recent burst and the previous prediction. The formula is:

τ(n+1) = α · t(n) + (1 − α) · τ(n)

where:

t(n) is the actual length of the n-th CPU burst.
τ(n) is the prediction made before the n-th burst.
τ(n+1) is the prediction for the next burst.
α is a weighting factor in the range [0, 1].

Expanding the recurrence shows that the prediction is a weighted sum of all past bursts, with the weights decaying exponentially:

τ(n+1) = α·t(n) + (1−α)·α·t(n−1) + (1−α)²·α·t(n−2) + …

The most recent burst receives weight α, the one before it receives α(1−α), the one before that α(1−α)², and so on. The weights sum to 1, so the prediction is a weighted average of all past bursts. The parameter α controls how quickly the estimate adapts:

α = 1 — the prediction is simply the most recent burst. The estimate adapts instantly but is volatile: a single unusual burst changes the prediction completely.
α = 0 — the prediction never changes; it is the initial estimate. The estimate is stable but completely unresponsive to the workload.
α = 1/2 — a common default. The most recent burst and the previous prediction receive equal weight. The estimate adapts in a few bursts without overreacting to a single outlier.

The following table works through a sequence of bursts with α = 1/2 and an initial prediction of 10.

Exponential averaging with α = 1/2 and τ(0) = 10
n	Actual t(n)	Prediction τ(n)	Next τ(n+1)
1	6	10.0	8.0
2	4	8.0	6.0
3	6	6.0	6.0
4	4	6.0	5.0
5	13	5.0	9.0

The fifth burst — a sudden long burst of 13 — pulls the prediction up sharply, from 5.0 to 9.0. With α = 1/2 the estimate recovers quickly, but it also overreacts to the outlier. With a smaller α, such as 1/4, the same sequence would produce a smoother trajectory: the estimate would adapt more slowly and would be less disturbed by a single unusual burst. The choice of α is a trade-off between responsiveness and stability, and different systems choose different values depending on the workload.

Aging and anti-aging

The same exponential-averaging idea is used in the aging technique that prevents starvation in priority scheduling (Lesson 5.4) and in the multilevel-feedback queues of general-purpose schedulers (Lesson 5.6). The prediction machinery is the same; only the quantity being predicted changes.

4.7 Starvation and aging

The most serious problem with SJF and SRTF is starvation: a process with a long burst can be indefinitely postponed if short processes keep arriving. Because the scheduler always selects the shortest job, the long process never reaches the head of the queue as long as there is a shorter process ahead of it. On a busy system with a steady supply of short interactive jobs, a long batch job could wait hours or days.

The classical solution is aging: gradually increase the priority of a process the longer it waits. Eventually, a long-waiting process's priority exceeds that of the newly arriving short processes, and it is scheduled. Aging bounds the maximum waiting time, at the cost of occasionally running a long job ahead of a short one and therefore increasing the average waiting time.

Aging is used in many real schedulers, including the multilevel-feedback queues that approximate SJF in Linux, Windows, and macOS. The exponential-averaging machinery from section 4.6 is often reused: the priority adjustment is a weighted combination of the process's base priority and the time it has been waiting.

Starvation is not the same as deadlock

A starved process is ready to run and would make progress if it were scheduled; it simply never is. A deadlocked process is blocked waiting for a resource that will never become available. Starvation is a scheduling problem; deadlock is a resource-allocation problem. Unit 7 covers deadlock in detail.

4.8 SJF, SRTF, and the standard criteria

Applying the criteria from Lesson 5.1 to SJF and SRTF gives the following assessment.

SJF and SRTF against the standard scheduling criteria
Criterion	SJF	SRTF
Average waiting time	Optimal (non-preemptive)	Optimal (preemptive)
Average turnaround time	Optimal (follows from WT)	Optimal (follows from WT)
Response time	Good for short jobs, poor for long	Excellent for short jobs, very poor for long
CPU utilization	Good	Good (more switches)
Throughput	Good	Good, slightly lower due to preemption overhead
Fairness	Poor — long jobs can starve	Very poor — long jobs can starve
Predictability	Moderate — depends on burst estimates	Low — preemption points depend on arrivals

The pattern is the opposite of FCFS: excellent on the metrics that measure average performance, poor on the metrics that measure fairness and worst-case behaviour. The choice between the two families is a choice between average efficiency and worst-case guarantees. General-purpose systems need both, which is why they use hybrid schedulers rather than pure SJF or pure FCFS.

4.9 Real-world approximations

Pure SJF is not implemented in any general-purpose operating system, because the burst lengths cannot be known. But the idea — run short jobs first to reduce average waiting time — appears in many systems in approximate form.

Multilevel feedback queues. The scheduler maintains several queues with different priorities. New processes enter the highest-priority queue with a short time quantum. If a process uses its full quantum, it is demoted to a lower-priority queue with a longer quantum. Short jobs finish in the top queue and receive excellent service; long jobs sink to the bottom and run with long quanta. The behaviour approximates SJF without requiring burst estimates. This is the design of the classic Multics and UNIX schedulers, and of the O(1) scheduler that preceded CFS in Linux.
Web servers. A web server handling HTTP requests often uses a shortest-remaining-processing-time policy, sometimes called shortest-job-first with preemption or size-based scheduling. The request size can be estimated from the URL, the content-length header, or the request type. The policy reduces the average response time and is especially effective at reducing the tail latency experienced by users.
Batch schedulers. Cluster and batch schedulers sometimes use a shortest-job-first policy when the job sizes are known in advance, for example when jobs declare their expected runtime. Slurm's sched/builtin plugin offers a SHORTEST_JOB_FIRST policy among its options. The policy is combined with backfilling to preserve utilization.
Linux's CFS. The Completely Fair Scheduler is not SJF, but it shares the objective of minimizing waiting time and it uses a virtual-runtime metric that gives preference to tasks that have received less CPU time. The effect is similar in spirit: the task that is furthest behind runs next. The details are the subject of Lesson 5.6.
Database query schedulers. Database systems often schedule short queries ahead of long ones to reduce average response time. The query planner can estimate the cost of a query from statistics on the tables, and the scheduler uses that estimate to order the queue. This is a direct application of the SJF idea with a domain-specific burst estimate.

Estimation is the whole problem

In every one of these systems, the quality of the scheduling decision depends on the quality of the burst estimate. A web server that estimates request size poorly will schedule badly; a batch system whose users overstate their runtimes will accumulate long jobs at the front of the queue. SJF is only as good as its predictions.

4.10 Common misconceptions

"SJF is optimal, so it is the best scheduler."

SJF is optimal for average waiting time under specific conditions. It is poor on fairness, on maximum waiting time, and on response time for long jobs. "Optimal" is always relative to a metric.

"SRTF is always better than SJF."

SRTF gives a lower average waiting time, but it also performs more context switches. On a system where switch overhead is high, non-preemptive SJF may be preferable.

"SJF requires knowing the future."

Exact SJF does, but approximations do not. Exponential averaging predicts the next burst from past bursts, and the approximation captures most of the benefit of the exact algorithm.

"Exponential averaging is exact."

It is a heuristic. It produces a prediction, not a guarantee. The prediction can be badly wrong when the workload changes abruptly, and the scheduler must tolerate the resulting mis-scheduling.

"Long jobs never run under SRTF."

They do run, but only when no shorter job is available. If short jobs keep arriving, the long job can be postponed for a very long time — potentially forever. Aging is needed to bound the wait.

"SJF is used in Linux."

Linux does not implement SJF. CFS is a fair-share scheduler with a different design and a different objective. The similarity is thematic, not algorithmic.

05 Worked example

The following example compares FCFS, non-preemptive SJF, and SRTF on the same workload. The numbers illustrate the progression from the convoy effect of Lesson 5.2 to the optimal average waiting time of SRTF.

Three algorithms on the same workload

Four processes arrive at different times with the burst times shown. None of them performs I/O; each runs its entire burst in one go.

Process	Arrival	Burst
P₁	0	8
P₂	1	4
P₃	2	9
P₄	3	5

FCFS

Processes run in arrival order: P₁, P₂, P₃, P₄.

| P1      | P2  | P3      | P4  |
0         8     12       21   26

Process	Arrival	Burst	Start	Completion	Turnaround	Waiting	Response
P₁	0	8	0	8	8	0	0
P₂	1	4	8	12	11	7	7
P₃	2	9	12	21	19	10	10
P₄	3	5	21	26	23	18	18
Average					15.25	8.75	8.75

Maximum waiting time: 18 (P₄). The convoy effect is visible: P₄ has a burst of only 5, but waits 18 units because P₁ and P₃ run ahead of it.

Non-preemptive SJF

The scheduler makes a decision only when the CPU becomes free. At time 0, only P₁ is available, so it runs. At time 8, P₂ (4), P₃ (9), and P₄ (5) are available; the shortest is P₂. At time 12, P₃ (9) and P₄ (5) remain; the shortest is P₄. At time 17, only P₃ remains.

| P1      | P2  | P4  | P3      |
0         8     12   17       26

Process	Arrival	Burst	Start	Completion	Turnaround	Waiting	Response
P₁	0	8	0	8	8	0	0
P₂	1	4	8	12	11	7	7
P₄	3	5	12	17	14	9	9
P₃	2	9	17	26	24	15	15
Average					14.25	7.75	7.75

Maximum waiting time: 15 (P₃). The average waiting time improves from 8.75 to 7.75, because P₄ now runs before P₃. However, P₁ still runs to completion before any of the shorter jobs, because it was already running when they arrived.

SRTF (preemptive SJF)

The scheduler re-evaluates at every arrival. P₁ runs from 0 to 1. At time 1, P₂ arrives with a burst of 4, which is less than P₁'s remaining 7, so P₁ is preempted. P₂ runs from 1 to 5. At time 5, P₄ (5) is the shortest remaining, so it runs from 5 to 10. At time 10, P₁ (7 remaining) is shorter than P₃ (9), so P₁ resumes and runs from 10 to 17. Finally, P₃ runs from 17 to 26.

|P1|  P2   |  P4   |    P1     |   P3     |
0  1       5       10         17         26

Process	Arrival	Burst	Start	Completion	Turnaround	Waiting	Response
P₁	0	8	0	17	17	9	0
P₂	1	4	1	5	4	0	0
P₄	3	5	5	10	7	2	2
P₃	2	9	17	26	24	15	15
Average					13.0	6.5	4.25

Maximum waiting time: 15 (P₃). The average waiting time improves again, from 7.75 to 6.5. P₂ now runs immediately at time 1, and its waiting time is 0. P₁'s waiting time rises from 0 to 9, but because P₁ is a single long job and the other three are shorter, the average improves.

Comparison

Metric	FCFS	SJF	SRTF
Average turnaround	15.25	14.25	13.0
Average waiting	8.75	7.75	6.5
Average response	8.75	7.75	4.25
Maximum waiting	18	15	15

SRTF gives the best average waiting time and the best average response time. It also gives the worst maximum waiting time for the long job — P₁ waits 9 units under SRTF versus 0 under FCFS — but P₁'s burst is the longest, so it is also the job that can afford to wait.

The progression from FCFS to SJF to SRTF is the progression from ignorance of burst lengths, to knowledge of them at scheduling points, to knowledge of them at every instant. Each step buys a lower average waiting time at the cost of additional preemption and additional information. In a real system, the information is unavailable, and the scheduler must use estimates.

Applying exponential averaging

Suppose the scheduler has no prior knowledge of P₁'s burst and uses an initial estimate of τ(0) = 4 with α = 1/2. P₁'s first burst is actually 8.

τ(1) = 0.5 × 8 + 0.5 × 4 = 6.0

The estimate after the first burst is 6.0, closer to the actual value but still short. If P₁ ran again with another burst of 8, the next estimate would be:

τ(2) = 0.5 × 8 + 0.5 × 6 = 7.0

After two bursts, the estimate is 7.0, close to the actual 8. The exponential average converges to the true burst length as more bursts are observed, but it lags behind changes in the workload. The scheduler must balance the cost of a wrong initial estimate against the cost of adapting too quickly to a transient burst.

06 Interactive activity

Activity · implement SJF and SRTF, and predict burst lengths

This activity extends the FCFS simulator from Lesson 5.2 to SJF and SRTF, and adds exponential averaging. Work through the steps in your course VM.

Extend the simulator to non-preemptive SJF. Modify the FCFS simulator so that at each scheduling decision, it selects the ready process with the smallest remaining burst. The simulator must track which processes have completed and which are still ready.
```
/* Sketch:
   while (completed < n) {
       find ready processes with arrival <= time
       if none, advance time to next arrival
       select the ready process with the smallest burst
       run it to completion
       update metrics
   } */
```
Run the simulator on the workload from the worked example and verify the numbers match the table.
Extend the simulator to SRTF. Modify the simulator to preempt the running process whenever a new process arrives with a shorter remaining burst. The simulator must track the remaining time of every process and re-evaluate at every arrival.
```
/* Sketch:
   while (completed < n) {
       find ready processes with arrival <= time
       if none, advance time to next arrival
       select the ready process with the smallest remaining time
       run it for one time unit (or until the next arrival)
       decrement its remaining time
       if remaining == 0, mark completed
       advance time
   } */
```
Run the simulator on the worked-example workload and verify the numbers match the SRTF table.
Compare all three algorithms. Run FCFS, SJF, and SRTF on the same workload and produce a side-by-side table of the metrics. Compute the ratio of each algorithm's average waiting time to the optimal (SRTF) value. How much worse is FCFS? How much worse is SJF?
Demonstrate starvation. Create a workload in which a long process (burst 100) arrives at time 0 and twenty short processes (burst 1 each) arrive at times 1, 2, 3, … . Run SRTF and observe the long process's waiting time. What happens if the short processes keep arriving for a long time? Modify the simulator to implement a simple aging policy (increase the priority of a waiting process every 10 time units) and observe whether the long process now completes.
Implement exponential averaging. Add a prediction component to the SJF simulator. The simulator should maintain an estimate τ for each process, initialized to some value, and update it after each burst. The scheduler selects by the predicted burst, not the actual burst. Compare the predicted-SJF schedule to the exact-SJF schedule on a workload where the burst times vary.
```
double predict(double t_actual, double tau_old, double alpha) {
    return alpha * t_actual + (1 - alpha) * tau_old;
}
```
Try α = 1/4, 1/2, and 3/4. Which gives the best scheduling performance on your workload? Why?
Observe SJF-like behaviour in Linux. Linux does not implement SJF, but the CFS scheduler's virtual-runtime metric has a similar effect: tasks that have received less CPU time are scheduled sooner. Use /proc/<pid>/sched to inspect the virtual runtime of a running process, and observe how it changes over time.
```
cat /proc/$$/sched | grep -i vruntime
cat /proc/$$/sched | grep -i se.sum_exec_runtime
```
Compare the virtual runtime of a CPU-bound process with that of an I/O-bound process running at the same time. Which one advances faster? What does this tell you about how CFS approximates fairness?
Read the exponential averaging section of Silberschatz. Read section 5.3.2 carefully and work through the example in the text. Then derive the expanded form of the recurrence yourself, and verify that the weights sum to 1.

Reflect: SJF and SRTF are optimal for average waiting time but impossible to implement exactly. What is the cost of using an estimate instead of the true burst length? In what situations would you prefer a simpler algorithm with no estimation, such as FCFS or round robin? How would you decide?

07 Knowledge check

Check your understanding

Question 1

Describe the SJF and SRTF algorithms. What is the essential difference between them, and under what circumstances does the difference matter?

Show answer

SJF (non-preemptive) selects the ready process with the smallest next CPU burst whenever the CPU becomes free — that is, when the running process terminates or blocks. Once a process is running, it is not interrupted, even if a shorter process arrives. SRTF (preemptive SJF) also selects the process with the smallest remaining time, but it re-evaluates the decision at every arrival. If a newly arrived process has a shorter remaining time than the running process, SRTF preempts the running process and switches to the new one. The essential difference is preemption. It matters whenever a shorter process arrives while a longer process is running: under SJF, the shorter process must wait for the long burst to complete; under SRTF, it runs immediately. SRTF therefore gives a lower average waiting time, at the cost of more context switches. When all processes arrive at the same time, or when no process arrives while another is running, the two algorithms produce identical schedules.

Question 2

State the optimality result for SJF precisely. What exactly is optimized, and under what conditions does the result hold? Why does SRTF need a different statement?

Show answer

SJF minimizes the average waiting time for a given set of processes, among all non-preemptive scheduling algorithms, when all processes are available at the same time (or, more generally, when every process's arrival time is no later than the first time it could be scheduled). The result is proved by an exchange argument: swapping two adjacent processes so that the shorter one runs first never increases the total waiting time, and repeated swaps produce the SJF order. SRTF needs a different statement because SJF is not optimal when processes arrive at arbitrary times: a long process that arrives first must run first under non-preemptive SJF, even if a shorter process arrives immediately afterward. SRTF, by contrast, is optimal for average waiting time among all preemptive algorithms, with arbitrary arrival times. The preemption allows SRTF to correct an unfortunate initial decision, which non-preemptive SJF cannot do.

Question 3

Three processes arrive at time 0 with burst times 3, 6, and 9. Compute the average waiting time under FCFS (in the order P₁ = 3, P₂ = 6, P₃ = 9) and under SJF. Verify that SJF gives the lower average, and explain why.

Show answer

FCFS (3, 6, 9): completion times are 3, 9, 18. Turnaround times are 3, 9, 18. Waiting times are 0, 3, 9. Average waiting = (0 + 3 + 9) / 3 = 4.0.

SJF (3, 6, 9 — already in shortest-first order): the schedule is the same as FCFS because the arrival order already matches the burst order. Average waiting = 4.0.

To see SJF's advantage, reverse the order. FCFS (9, 6, 3): completion times are 9, 15, 18. Turnaround times are 9, 15, 18. Waiting times are 0, 9, 15. Average waiting = (0 + 9 + 15) / 3 = 8.0. SJF (3, 6, 9): average waiting = 4.0, as computed above. SJF gives the lower average because the short process's burst time is counted in the waiting time of every subsequent process. When the short process runs first, its small burst delays the others only slightly; when it runs last, its small burst does not help anyone. This is the exchange argument in concrete form.

Question 4

Why can SJF not be implemented exactly in a real operating system? Describe the exponential averaging technique and explain the role of the parameter α.

Show answer

SJF cannot be implemented exactly because it requires the scheduler to know the length of each process's next CPU burst in advance. The burst length is a property of the process's future behaviour, which depends on input data, cache state, and library behaviour. The process itself does not know it, and the scheduler has even less information. Exponential averaging solves this by predicting the next burst as a weighted combination of the most recent burst and the previous prediction:

τ(n+1) = α · t(n) + (1 − α) · τ(n)

where t(n) is the actual length of the n-th burst, τ(n) is the prediction made before it, and α is a weight in [0, 1]. Expanding the recurrence shows that the prediction is a weighted sum of all past bursts, with the weights decaying exponentially. The parameter α controls the trade-off between responsiveness and stability: α near 1 means the prediction follows the most recent burst closely, adapting quickly but overreacting to outliers; α near 0 means the prediction changes slowly, remaining stable but unresponsive to genuine changes in the workload. A common default is α = 1/2, which gives the most recent burst and the previous prediction equal weight. The estimate is not exact, but on real workloads it is good enough to capture most of the benefit of exact SJF.

Question 5

What is starvation, and why are SJF and SRTF especially vulnerable to it? Describe the aging technique and explain the trade-off it introduces.

Show answer

Starvation is the indefinite postponement of a process that is ready to run. The process never gets the CPU, not because it is blocked or deadlocked, but because the scheduler never selects it. SJF and SRTF are especially vulnerable because they always select the shortest job. If short jobs keep arriving, a long job never becomes the shortest, and it waits indefinitely. On a busy system with a steady stream of short interactive tasks, a long batch job could wait for hours or days. Aging is the standard fix: the scheduler gradually increases the priority of a process the longer it waits. Eventually the long-waiting process's priority exceeds that of newly arriving short processes, and it is scheduled. The trade-off is that aging introduces a bound on the maximum waiting time at the cost of occasionally running a long job ahead of a short one — which increases the average waiting time. The scheduler must choose the aging rate to balance these two effects. A slow aging rate preserves most of SJF's average-case advantage but allows long waits; a fast aging rate bounds the waits but degrades the average toward FCFS.

08 Unit discussion

Discussion prompt

SJF and SRTF minimize the average waiting time, but they can be catastrophically unfair to individual long-running processes. A web server that uses a shortest-remaining-processing-time policy will give excellent average response times — but a single large request (a video download, a large database query) can be delayed indefinitely while small requests are served ahead of it.

Is this acceptable? In some systems it clearly is: a search engine that answers millions of small queries quickly provides more value than one that answers each large query promptly at the expense of the small ones. In other systems it clearly is not: a hospital's patient records system must not indefinitely postpone a request for a large record while serving small ones. The same algorithm is right in one context and wrong in the other.

What principle should determine whether a system uses an average-optimizing scheduler like SJF or a fairness-preserving one like FCFS or round robin? Is the answer about the workload, about the users, or about the system's purpose? Give a concrete example from your own experience of a system where one choice would be right and the other wrong. Post your response to the Unit 5 discussion forum and reply to at least two classmates. Supports CLO1, CLO3, and CLO8.

09 Practice exercise

This ungraded exercise consolidates the lesson and prepares you for Lab 4. Aim to spend 60–90 minutes on it.

Trace SJF and SRTF by hand. For the workload below, construct the Gantt charts for non-preemptive SJF and for SRTF, compute the completion, turnaround, waiting, and response times for each process, and report the averages and the maximum waiting time for each algorithm. Then verify your answers using the simulator from the interactive activity.

Process	Arrival	Burst
P₁	0	10
P₂	1	3
P₃	2	6
P₄	3	2
P₅	4	4

Apply exponential averaging. A process has the following sequence of CPU bursts: 8, 4, 12, 6, 10. Using α = 1/2 and an initial prediction of 10, compute the prediction made before each burst and the updated prediction after each. Then repeat with α = 1/4 and α = 3/4. Plot or tabulate the three sequences and comment on the difference in responsiveness and stability.
Compare the optimality gap. For the workload in question 1, compute the average waiting time under FCFS (arrival order), non-preemptive SJF, and SRTF. Express each as a ratio to the SRTF value. Which algorithm is closest to optimal? What is the cost of not knowing the burst lengths exactly, if the scheduler used exponential averaging with α = 1/2 instead of the true values?
Construct a starvation scenario. Design a workload in which a long process never completes under SRTF because short processes keep arriving. Run the simulator to confirm. Then modify the simulator to implement a simple aging policy and show that the long process eventually completes. What aging rate is needed to bound the long process's waiting time to 100 units? To 50 units?
Measure the cost of preemption. Modify the switch-cost program from Lesson 5.1 so that one thread repeatedly preempts another using sched_yield, and measure the time for a million preemptions. Compare this to the cooperative handoff measurement. What is the extra cost of preemption? At what point does the improved average waiting time of SRTF stop justifying the extra preemptions?
Explore a real SJF-like system. Choose one of the real-world approximations from section 4.9 — a web server, a database query scheduler, or a batch scheduler. Find documentation or source code that describes how it estimates the "size" of a job and how it uses the estimate to order the queue. Write a short paragraph explaining the estimation method and the policy, and compare it to the exponential averaging technique from this lesson.
Reflect. In your own words, explain why the optimality of SJF for average waiting time does not make it the right scheduler for every system. Give one example of a system where SJF would be a poor choice, and explain what you would use instead.

10 Summary

Shortest-Job-First (SJF) selects the ready process with the smallest next CPU burst. It is non-preemptive: once a process is running, it is not interrupted.
Shortest-Remaining-Time-First (SRTF) is the preemptive version. It re-evaluates at every arrival and preempts the running process if a newly arrived process has a shorter remaining time.
SJF minimizes the average waiting time for a set of processes available at the same time, among non-preemptive algorithms. SRTF minimizes it for arbitrary arrival times, among preemptive algorithms. The proof is an exchange argument.
The optimality is for one metric only. SJF and SRTF are poor on fairness, on maximum waiting time, and on response time for long jobs.
SJF and SRTF cannot be implemented exactly because the scheduler does not know future burst lengths. Exponential averaging predicts the next burst as τ(n+1) = α · t(n) + (1 − α) · τ(n). The parameter α controls the trade-off between responsiveness and stability.
SJF and SRTF are vulnerable to starvation: a long process can be indefinitely postponed if short processes keep arriving. Aging gradually increases the priority of a waiting process, bounding the maximum wait at the cost of a slightly higher average.
Real systems approximate SJF rather than implementing it: multilevel feedback queues, web server shortest-remaining-processing-time policies, batch schedulers with declared runtimes, and Linux's CFS all capture part of the SJF idea without requiring exact burst lengths.
SRTF gives the lowest average waiting time of any preemptive algorithm; FCFS gives the highest of the algorithms covered so far; SJF sits between them. The choice among them depends on which metric matters most for the workload.

Looking ahead

SJF and SRTF prioritize short jobs. The next lesson examines a different basis for prioritization: priority scheduling, in which each process is assigned a priority by the system or by the user, and the scheduler always runs the highest-priority ready process. Priority scheduling generalizes SJF — SJF is priority scheduling with priority inversely proportional to burst length — and it introduces its own version of the starvation problem, along with the aging technique that solves it. Lesson 5.4 covers both the preemptive and non-preemptive forms, and the classic priority-inversion problem that appears in real-time systems.

11 References

Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapter 7. Available online at ostep.org.
Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 5, Sections 5.3.2 and 5.3.3.
Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 2, Section 2.4.3.
Love, R. Linux System Programming, 2nd ed., Chapter 3.
Linux man-pages: man 7 sched, man 2 sched_setscheduler, man 5 proc (the /proc/<pid>/sched interface).
Slurm Workload Manager documentation, Job Scheduling Policies — the SHORTEST_JOB_FIRST policy.
Harchol-Balter, M., Schroeder, B., Bansal, N., & Agrawal, M. Size-Based Scheduling to Improve Web Performance. ACM Transactions on Computer Systems, 2003. The canonical reference for shortest-remaining- processing-time scheduling in web servers.