CSE Roadmap

Core tier · about 4 hours · 7 parts

Part 6 of 7 · 3 min read

Comparison

Starvation and the comparison

Put the three results on one table (the same four jobs):

Policy Average turnaround Average waiting Average response
FCFS 10.25 5.75 5.75
SJF 8.50 4.00 4.00
SRTF 8.00 3.50 2.25

Shortest-first policies are the best on averages, and they have two serious problems.

  1. They need the burst length, which a real kernel can only estimate (section 3).
  2. They can starve long jobs. Starvation is a process waiting for ever, or unreasonably long, though it is ready. If short jobs keep arriving, the 8-unit job C never reaches the front. In the trace, C ran last because every shorter job came before it. On a busy server that receives a short job every few units, C would never run.

FCFS never starves anyone, because each job's turn will come. The price is poor averages when a long job is early.

Starvation

Starvation is the condition in which a ready process is never, or only after an unreasonably long time, given the processor because the scheduling policy always prefers others.

Example: under SJF, a long job can wait indefinitely if shorter jobs keep arriving before its turn.

Common mistake

Calling SJF the best scheduler. It gives the lowest average waiting time among non-preemptive policies, but it needs data that does not exist, and it can starve long jobs.

Interview angle

Answer in your head first, then open it.

What is the convoy effect?

Short jobs waiting behind one long job in an FCFS queue.

Why is SJF optimal for average waiting time?

Swapping a longer job ahead of a shorter one only increases the sum of waits.

Why can SJF not be implemented exactly?

The next CPU burst length is unknown, so it is estimated, for example with an exponential average.

What is starvation?

A ready process that does not get the processor for a very long time.

What is the difference between SJF and SRTF?

SRTF is preemptive: a newly arrived shorter job can interrupt the running one.

Check yourself: 1. Which of FCFS, SJF and SRTF can starve a long job? 2. Which policy gave the lowest average response time? 3. Why do real systems estimate bursts instead of asking programs?

Words you will meet

Word Meaning
FCFS Run in order of arrival, without interruption
Convoy effect Short jobs delayed behind a long one
SJF Run the ready job with the shortest next burst
SRTF SJF with preemption on arrival
Exponential average A prediction that weights new data more than old
Starvation A ready process that never gets its turn

Quick notes

  • The convoy effect is the delay of many short processes that wait in a first come first served queue behind one long process, which lowers the average waiting time and keeps devices idle.
  • Shortest job first (SJF) is a scheduling policy that, whenever the processor is free, runs the ready process whose next CPU burst is shortest, without interrupting it, and that gives the least average waiting time of all non-preemptive policies.
  • An exponential average is a prediction rule that computes the next estimate as α times the latest measurement plus (1 − α) times the previous estimate, so that older measurements count less each step.
  • Shortest remaining time first (SRTF) is the preemptive form of shortest job first: whenever a process arrives, the processor goes to the process, running or ready, with the least CPU time still to run.
  • Starvation is the condition in which a ready process is never, or only after an unreasonably long time, given the processor because the scheduling policy always prefers others.