Course contentsShow
← Computer Science
Lesson 1253 of 2,87229. CPU SchedulingFree lesson

Shortest Job First (SJF) Scheduling

Understand how selecting the process with shortest CPU burst minimizes average waiting time but requires burst prediction.

Shortest Job First (SJF) Scheduling

What you'll learn: How picking the process with the shortest CPU burst first minimizes average waiting time—but requires predicting burst lengths.

The Core Idea

Shortest Job First (SJF) is a CPU scheduling algorithm that selects the process with the smallest next CPU burst to run first. Among all scheduling algorithms, SJF is provably optimal for minimizing average waiting time—if you always run the quickest job first, processes spend less time waiting overall.

Think of it like a grocery store checkout line: if someone with just one item goes before someone with a full cart, the total time everyone spends waiting goes down. The person with one item finishes quickly, and the person with the cart only waits a bit longer than they would have anyway.

The Challenge: Burst Prediction

Here's the catch: you can't know the future. The OS doesn't magically know how long each process's next CPU burst will be. Unlike FCFS, which just uses arrival time (a fact), SJF requires predicting or estimating burst length.

Common prediction techniques include:

  • Using historical averages of past bursts
  • Applying exponential averaging to weight recent behavior more heavily
  • Accepting user hints (e.g., a program declares its expected runtime)

Non-Preemptive vs Preemptive

SJF can be non-preemptive (once started, a process runs to completion) or preemptive (if a new process arrives with a shorter burst than the remaining time of the current process, switch to it—also called Shortest Remaining Time First).

Key Takeaway:
SJF minimizes average waiting time by running shortest bursts first, but real systems must estimate future burst lengths—prediction accuracy determines practical effectiveness.