Non-Preemptive SJF Scheduling and the Efficacy of FIFO in Mitigating Starvation

EasyChair Preprint 14076

Abstract

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

@booklet{EasyChair:14076,
  author    = {Krisha Anne Chan and Enrico Baratang and Henry Adorna and Alfonso Labao},
  title     = {Non-Preemptive SJF Scheduling and the Efficacy of FIFO in Mitigating Starvation},
  howpublished = {EasyChair Preprint 14076},
  year      = {EasyChair, 2024}}