shortestjobfirst

Shortest Job First (SJF) is a CPU scheduling algorithm that selects the process with the shortest estimated CPU burst time to execute next. There are non-preemptive and preemptive variants; the latter is commonly called Shortest Remaining Time First (SRTF).

In non-preemptive SJF, once a process starts, it runs to completion. The scheduler keeps the ready queue ordered by estimated burst length, and when the CPU becomes free, the front of the queue is executed.

In the preemptive form (SRTF), a newly arriving process can preempt the current one if it has a shorter remaining time. The scheduler then switches to the shorter job.

SJF aims to minimize average waiting time when burst times are known or well estimated. However, it can cause starvation of long processes if short jobs keep arriving. Aging or other policies can mitigate this problem. SJF requires knowledge or estimation of burst times, which can be difficult in general-purpose systems.

Implementation typically uses a priority queue keyed by burst time, giving insert and selection times of O(log n). In practice, SJF is more common in batch systems with predictable workloads and is rarely used as the sole scheduler in general-purpose operating systems.