SJF, SRTF & Priority Scheduling: Optimal Turnaround & Starvation

Shortest Job First (SJF) associates with each process the length of its next CPU burst. When the CPU becomes available, it is assigned to the process that has the smallest burst time. If two processes have identical burst lengths, FCFS scheduling is used as a tiebreaker.

Provable Optimality: SJF is provably optimal in giving minimum average waiting time for a given set of stationary processes. Moving a short process before a long one reduces the waiting time of the short process by more than it increases the waiting time of the long one.

The Fundamental Limitation: SJF cannot be implemented in general-purpose long-term/short-term schedulers because the Operating System cannot predict the exact future CPU burst length of a user process.

Burst Prediction via Exponential Smoothing: The OS approximates the next burst \tau_{n+1} using historical actual bursts t_n and prior estimates \tau_n: \tau_{n+1} = \alpha \cdot t_n + (1 - \alpha) \cdot \tau_n, where 0 ≤ \alpha ≤ 1 (typically \alpha = 0.5).

SRTF is the preemptive version of SJF. When a new process arrives at the Ready Queue with a remaining CPU burst time strictly shorter than the currently running process's remaining time, the running process is preempted and moved back to the Ready Queue.

Key GATE Preemption Condition: Preemption occurs IF AND ONLY IF Remaining_Time(New) < Remaining_Time(Current). If Remaining_Time(New) Remaining_Time(Current)==, the CPU continues running the current process to avoid unnecessary context-switch overhead.

Trade-off: While SRTF yields the lowest theoretical average waiting time, every preemption incurs a CPU context switch. In practice, high context-switch frequency degrades effective throughput.

In Priority Scheduling, an integer priority is assigned to each process. By standard UNIX convention, smaller integer values indicate higher priority (e.g., priority 0 is higher than priority 10). The CPU is allocated to the process with the highest priority.

Starvation (Indefinite Blocking): A major hazard where low-priority processes may wait indefinitely if there is a steady stream of higher-priority processes.

The Solution — Aging: Aging is a technique of gradually increasing the priority of processes that wait in the system for a long time. For example, if priorities range from 127 (lowest) to 0 (highest), the kernel can decrement the priority value by 1 every 15 minutes of ready-queue waiting. Eventually, even the lowest-priority process climbs to the top.