# Shortest Job First (SJF) Scheduling

> Shortest Job First (SJF) scheduling is a CPU scheduling algorithm that always runs the ready process with the shortest burst time next. Clearing short jobs first gives the lowest possible average waiting time, but a long process can starve if shorter jobs keep arriving. Its preemptive form is called Shortest Remaining Time First (SRTF).

Canonical: https://devsunite.com/resources/core-subjects/operating-systems/sjf-scheduling
Last updated: 2026-11-22

Subject: Operating Systems · Category: Process Scheduling · 5 min read

Shortest Job First, usually written as SJF, is a CPU scheduling algorithm that always picks the process with the smallest remaining burst time to run next. Burst time here means how long a process needs the CPU before it either finishes or has to wait on something else, like disk I/O. The idea is simple: get the short jobs out of the way first so fewer processes are stuck waiting behind a long one.

## How SJF actually works

Every time the CPU becomes free, the scheduler looks at every process currently sitting in the ready queue and picks the one with the shortest burst time. There are two flavors of this:

**Non-preemptive SJF** lets a process run to completion once it starts, even if a shorter job shows up while it's running. The scheduler only makes a new decision when the CPU is free.

**Preemptive SJF**, also called Shortest Remaining Time First (SRTF), can interrupt a running process the moment a shorter job arrives. It constantly re-checks "is there something shorter than what I'm running right now?"

Most courses teach non-preemptive SJF first because it's easier to trace by hand, so that's what the worked example below uses.

## Why SJF is considered optimal

Among all scheduling algorithms that don't preempt, SJF produces the lowest possible average waiting time for a given set of processes. The reasoning is straightforward: every time you let a short job jump ahead of a longer one, you save more total waiting time across all the processes stuck behind it than you lose by making the long job wait a bit more. Do that consistently and the average comes out lower than any other ordering.

That optimality comes at a real cost, though: **starvation**. If short jobs keep arriving, a long process can sit in the ready queue indefinitely because there's always something shorter to run first. Real operating systems that care about fairness (which is most of them) don't use pure SJF for exactly this reason.

There's also a practical problem: the OS doesn't actually know a process's burst time in advance. It has to predict it, usually using a technique called exponential averaging, which estimates the next burst as a weighted average of the process's past bursts. Get that prediction wrong and SJF's whole advantage falls apart.

## A worked example

Say four processes arrive in the ready queue like this:

| Process | Arrival Time | Burst Time |
|---------|---------------|------------|
| P1 | 0 | 7 |
| P2 | 2 | 3 |
| P3 | 4 | 1 |
| P4 | 5 | 6 |

At time 0, only P1 has arrived, so it starts running (there's nothing shorter to compare it against yet). It runs non-preemptively, so even though P2 and P3 arrive with shorter bursts while P1 is executing, they simply wait.

P1 finishes at time 7. At that point P2 (burst 3), P3 (burst 1), and P4 (burst 6) are all waiting. The scheduler picks the shortest: P3 (burst 1), which finishes at time 8. Next shortest available is P2 (burst 3), finishing at time 11. Finally P4 runs, finishing at time 17.

Execution order: P1, P3, P2, P4.

Turnaround time (completion time minus arrival time):
- P1: 7 - 0 = 7
- P2: 11 - 2 = 9
- P3: 8 - 4 = 4
- P4: 17 - 5 = 12

Average turnaround time = (7 + 9 + 4 + 12) / 4 = 8

Waiting time (turnaround time minus burst time):
- P1: 7 - 7 = 0
- P2: 9 - 3 = 6
- P3: 4 - 1 = 3
- P4: 12 - 6 = 6

Average waiting time = (0 + 6 + 3 + 6) / 4 = 3.75

Compare that to running the processes in plain arrival order (P1, P2, P3, P4), which gives an average waiting time of 8.5 for the same four processes. SJF cuts the average wait by more than half here, which is the whole point of the algorithm.

## Where this shows up in real systems

Pure SJF is rare in general-purpose operating systems like Linux or Windows, because interactive systems care more about responsiveness and fairness than raw average wait time, and Linux's own scheduler (CFS) is built around fair CPU-time sharing rather than picking the shortest job.

But the underlying idea, favor small jobs to reduce average wait, shows up constantly in batch and cluster computing. HPC job schedulers such as Slurm use backfilling, where the scheduler looks ahead in the queue and lets a smaller job run in a gap while a larger job waits for enough nodes to free up, specifically to avoid leaving compute capacity idle. Print spoolers historically did something similar too: a short one-page print job would be dispatched before a 200-page report sitting ahead of it in the queue, because there was no reason to make dozens of small jobs wait behind one big one.

## What interviewers actually ask about SJF

- **"Is SJF preemptive or non-preemptive?"** The honest answer is both exist; the exam-style version (what's usually just called "SJF") is non-preemptive, and the preemptive version has its own name, SRTF.
- **"Why is SJF called optimal, and optimal for what exactly?"** Make sure to say specifically: minimum average waiting time, not minimum turnaround time or fairness.
- **"What's the biggest problem with SJF in practice?"** Two answers expected: starvation of long processes, and the fact that burst time isn't actually known ahead of time and has to be predicted.
- **"How would you fix starvation in SJF?"** Aging is the standard answer: gradually increase the priority of a process the longer it waits, so it eventually becomes the shortest-effective-time choice regardless of its real burst time.
- **"Walk me through a Gantt chart for these four processes."** Be ready to do exactly the kind of hand-trace worked out above, including computing turnaround and waiting times, not just naming the algorithm.

## Key takeaways

- SJF always selects the process with the smallest burst time from the ready queue.
- It's the theoretically optimal algorithm for minimizing average waiting time.
- Non-preemptive SJF runs a process to completion once started; the preemptive version is called SRTF.
- Its two real weaknesses are starvation of long processes and the need to predict burst time in advance.
- Aging is the standard fix for starvation in SJF-style scheduling.

## Related

- [Previous: FCFS (First Come First Served) Scheduling](https://devsunite.com/resources/core-subjects/operating-systems/fcfs-scheduling)
- [Next: SRTF (Shortest Remaining Time First) Scheduling](https://devsunite.com/resources/core-subjects/operating-systems/srtf-scheduling)
- [More in Process Scheduling: Process Scheduling](https://devsunite.com/resources/core-subjects/operating-systems/process-scheduling)
- [More in Process Scheduling: Scheduling Queues](https://devsunite.com/resources/core-subjects/operating-systems/scheduling-queues)
- [More in Process Scheduling: Preemptive vs Non-Preemptive Scheduling](https://devsunite.com/resources/core-subjects/operating-systems/preemptive-vs-non-preemptive-scheduling)
- [More in Process Scheduling: Scheduler vs Dispatcher](https://devsunite.com/resources/core-subjects/operating-systems/scheduler-vs-dispatcher)
- [More in Process Scheduling: Scheduling Criteria](https://devsunite.com/resources/core-subjects/operating-systems/scheduling-criterias)
- [More in Process Scheduling: Priority Scheduling](https://devsunite.com/resources/core-subjects/operating-systems/priority-scheduling)
- [More in Process Scheduling: Round Robin Scheduling](https://devsunite.com/resources/core-subjects/operating-systems/round-robin-scheduling)
- [More in Process Scheduling: Multilevel Queue Scheduling](https://devsunite.com/resources/core-subjects/operating-systems/multilevel-queue-scheduling)
- [More in Process Scheduling: Multilevel Feedback Queue Scheduling](https://devsunite.com/resources/core-subjects/operating-systems/multilevel-feedback-queue-scheduling)
- [More in Process Scheduling: Starvation and Aging in Scheduling](https://devsunite.com/resources/core-subjects/operating-systems/starvation-and-aging)
- [All 205 OS interview questions](https://devsunite.com/resources/core-subjects/operating-systems)
