Non-Preemptive SJF Scheduling and the Efficacy of FIFO in Mitigating Starvation
EasyChair Preprint 14076
12 pages•Date: July 22, 2024Abstract
Task scheduling is critical for operating system performance,
determining task execution order on the CPU. The Non-preemptive
Shortest Job First (SJF) algorithm aims to enhance efficiency by min-
imizing average waiting and turnaround times. However, SJF can lead
to issues like deadlock and starvation, where tasks are indefinitely de-
layed. This case study models SJF behaviors to simulate and demonstrate
these pitfalls. By defining axioms, functions, and properties, the study
formalizes SJF scenarios and their negative implications. The study also
examines the First-In-First-Out (FIFO) algorithm, showing its effective-
ness in preventing deadlock and starvation by executing tasks in arrival
order. Formal verification of these algorithms ensures system reliability
and guides the development of robust scheduling policies.
Keyphrases: Shortest Job First, Starvation, deadlock, first-in-first-out