SJF Scheduling - Shortest Job First

Introduction

Imagine you are a cashier at a supermarket with a long queue. You notice that some customers have just one item while others have full carts. If you could magically rearrange the queue so customers with fewer items go first, the average time everyone spends waiting would decrease dramatically. That is exactly the idea behind SJF scheduling.

Shortest Job First (SJF) is a CPU scheduling algorithm that selects the process with the smallest burst time next. It is provably optimal — no other algorithm can produce a lower average waiting time for a given set of processes. However, this optimality comes with a significant practical challenge: how do you know in advance how long each process will take?

How SJF Works

Non-Preemptive SJF

In non-preemptive SJF, once a process starts executing, it runs to completion. The scheduler only makes decisions when a process finishes and the CPU becomes free. At that point, it examines all processes in the ready queue and picks the one with the shortest burst time.

Preemptive SJF (SRTF — Shortest Remaining Time First)

In preemptive SJF, whenever a new process arrives, the scheduler compares its burst time with the remaining time of the currently executing process. If the new process has a shorter burst time, the current process is preempted (paused) and the new shorter process takes over the CPU.

Non-Preemptive SJF Example

Gantt Chart (Non-Preemptive)

At time 0, only P1 is available, so P1 starts. When P1 finishes at time 7, processes P2 (burst=4), P3 (burst=1), and P4 (burst=4) are all waiting. P3 has the shortest burst, so it goes next. Then P2 and P4 are tied (both burst=4), so FCFS breaks the tie.

Calculations

Average Waiting Time = (0 + 6 + 3 + 7) / 4 = 4 ms Average Turnaround Time = (7 + 10 + 4 + 11) / 4 = 8 ms

Preemptive SJF (SRTF) Example

Using the same processes but with preemption:

Gantt Chart (Preemptive / SRTF)

Step by step:

• Time 0: Only P1 available, starts executing (remaining = 7)
• Time 2: P2 arrives (burst=4). P1 remaining = 5. Since 4 < 5, preempt P1, run P2
• Time 4: P3 arrives (burst=1). P2 remaining = 2. Since 1 < 2, preempt P2, run P3
• Time 5: P3 finishes. P4 arrives (burst=4). Ready: P1(rem=5), P2(rem=2), P4(burst=4). P2 has shortest, runs
• Time 7: P2 finishes. Ready: P1(rem=5), P4(burst=4). P4 shorter, runs
• Time 11: P4 finishes. Only P1 left (rem=5), runs
• Time 16: P1 finishes

Average Waiting Time = (9 + 1 + 0 + 2) / 4 = 3 ms (even better than non-preemptive!)

Implementation in C

The Prediction Problem

The fundamental challenge with SJF is that we need to know burst times in advance. In reality, we cannot predict exactly how long a process will use the CPU. Operating systems use exponential averaging to estimate future burst times based on past behavior:

If α = 0.5, the prediction weighs recent history and older predictions equally. A process that consistently uses 4 ms of CPU time will have predictions converging toward 4 ms.

Advantages and Disadvantages

Advantages

• Optimal average waiting time — Mathematically proven minimum for non-preemptive case
• Favors short processes — Interactive jobs get quick response
• Efficient throughput — More short jobs complete per unit time

Disadvantages

• Starvation — Long processes may never execute if short ones keep arriving
• Burst time prediction — Requires knowing future CPU bursts (impossible in general case)
• Overhead — Must compare all ready processes to find the shortest
• Not suitable for interactive systems — Cannot guarantee response time

Real-World Analogy

SJF is like the "10 items or fewer" express lane at a supermarket, but taken to the extreme — imagine the cashier always serves the customer with the fewest items in their basket, regardless of when they joined the queue. Great for people with small baskets, but someone with a full cart might wait all day if a steady stream of express customers keeps arriving.

Key Takeaways

• SJF selects the process with shortest burst time, giving optimal average waiting time
• Non-preemptive SJF waits for the current process to finish before scheduling
• Preemptive SJF (SRTF) interrupts if a shorter process arrives — even more optimal
• The main practical problem is predicting burst times (solved by exponential averaging)
• Starvation is a real risk — long processes can be indefinitely delayed
• SJF is optimal in theory but impractical for real interactive systems due to prediction difficulty