Download PDFOpen PDF in browser

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

EasyChair Preprint 14076

12 pagesDate: July 22, 2024

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

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
@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}}
Download PDFOpen PDF in browser