Questions: Shortest Job First (SJF) CPU Scheduling

Question 1

Three processes arrive simultaneously with CPU burst times of 8ms, 2ms, and 5ms. What is the average waiting time under SJF (non-preemptive)?

• A. 5ms — the same as the FCFS average
• B. 3ms — SJF runs them in order 2ms, 5ms, 8ms: waiting times are 0, 2, and 7
• C. 7ms — the longest job dominates the wait
• D. 0ms — all jobs start immediately under SJF

Answer: (B)

SJF reorders by burst time: run 2ms first, then 5ms, then 8ms. Waiting times: job with 2ms burst waits 0ms; 5ms burst waits 2ms; 8ms burst waits 2+5=7ms. Average = (0+2+7)/3 = 3ms. Under FCFS in the original order (8, 2, 5), waiting times are 0, 8, 10 — average 6ms. SJF wins because short jobs finish quickly, stopping them from contributing to the wait of everyone behind them.

Question 2

Why can't a real operating system implement ideal SJF scheduling?

• A. SJF requires more memory than other scheduling algorithms
• B. SJF requires knowing each process's next CPU burst time in advance, which the OS cannot determine before the process runs
• C. SJF is only applicable in batch systems with no interactive users
• D. SJF violates POSIX scheduling standards used by modern operating systems

Answer: (B)

SJF's fundamental impracticality is that it requires knowing how long each process will use the CPU before it has used it. The OS cannot predict the future. Real systems approximate SJF by estimating burst times from historical data — typically using exponential averaging where recent bursts count more than older ones. These estimates enable approximate SJF behavior but introduce errors whenever a process's behavior changes. The algorithm is theoretically optimal but practically only realizable through approximation.

Question 3

Among all non-preemptive scheduling algorithms, SJF minimizes average waiting time.

• T. True
• F. False

Answer: True

This is a provable optimality result. The argument is by exchange: given any schedule that does not run the shortest available job next, swapping the shortest job earlier always reduces (or maintains) total waiting time across all processes. Repeating this argument produces the SJF order, which is therefore optimal. This is the same reasoning behind greedy sorting: always process the cheapest operation first to minimize accumulated overhead.

Question 4

Preemptive SJF (Shortest Remaining Time First) is typically preferable to non-preemptive SJF because it produces lower average waiting times.

• T. True
• F. False

Answer: False

While SRTF achieves lower or equal average waiting time, 'always preferable' is too strong. SRTF introduces additional context-switch overhead every time a shorter job arrives. More critically, SRTF severely worsens starvation: a long process can be perpetually preempted as short jobs keep arriving, potentially never completing. In systems where fairness or guaranteed progress matters, non-preemptive SJF or other algorithms may be preferred despite the slightly higher average wait time.

Question 5

Why does SJF cause starvation, and how do real operating systems address this problem?

Model answer: SJF always favors the shortest job, so a long process can be indefinitely postponed if a steady stream of shorter jobs keeps arriving — its wait time grows without bound. Real systems address this through aging: the effective priority of a waiting process gradually increases with elapsed wait time, so a long-waiting process eventually becomes the highest-priority job regardless of burst time. Multilevel feedback queues implement a similar idea by promoting processes to higher-priority queues the longer they wait, preventing starvation while still generally favoring short jobs.

Starvation is the fundamental fairness failure of any priority scheme that ignores elapsed waiting time. SJF is the clearest example: pure optimality for average wait time and fairness are in direct conflict. Real schedulers always make some tradeoff between efficiency and fairness — pure SJF is a theoretical benchmark, not a deployed policy.