Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 66 ยท CPU Scheduling

Starvation, Aging, Dispatcher and Scheduler

Understand starvation and aging, how starvation differs from deadlock and livelock, and the exact roles of the scheduler and the dispatcher, with simulations of both.

This lesson ties up four ideas that scheduling chapters and exams keep mixing up: starvation (a process that never gets what it needs), aging (the cure), the difference between starvation, deadlock and livelock, and the difference between the scheduler and the dispatcher. Each is simple, and each is easy to get wrong when the words sound alike.

You will measure starvation in a simulation, apply aging to fix it, and look at the steps of a dispatch with a latency estimate.

Three ways to not make progress

Starvation Others keep getting served first.
Deadlock Everyone waits for everyone, forever.
Livelock Everyone keeps reacting, nobody advances.

Only starvation can be cured by changing priorities.

1 / 2

Starvation

Starvation (indefinite blocking) means a process is ready, but the scheduler keeps choosing others, so it waits for an unbounded time. It is not an error in the process; it is a side effect of the scheduling policy or of resource allocation.

Which policies can starve a process?

Policy Starvation? Why
FCFS No Waiting is bounded by the jobs ahead
Round Robin No Everyone gets a turn within (n-1) ร— q
SJF / SRTF Yes A steady stream of shorter jobs delays a long job
Priority Yes A steady stream of higher-priority jobs
MLFQ without boost Yes Low queue only runs when higher queues are empty

Starvation can also happen outside CPU scheduling: a thread that always loses the race for a lock, a writer that can never get in because readers keep arriving (the readers-writers problem), or a disk request far from the head under shortest-seek-first.

The cure: aging

Aging gradually increases the priority of a process the longer it waits. Eventually its priority exceeds everybody else's and it runs. A simple rule: every T time units of waiting, raise the priority by one step (the exact numbers are a tuning decision). The simulation measures the worst waiting time of a long job with and without aging while a flow of short jobs arrives under SJF.

Python Starvation under SJF, cured by aging

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Without aging the long job is postponed until the arrivals stop (that is, "never" while the stream continues); with aging its score drops until it wins.

Starvation vs. deadlock vs. livelock

Starvation Deadlock Livelock
What happens One process is postponed indefinitely A set of processes wait for each other in a cycle Processes keep changing state but make no progress
Does the system progress? Yes, others run Not for the processes involved No useful work
Cause Unfair policy Resource cycle (circular wait) Too much politeness, such as both backing off identically
Cure Aging, fair policies Prevent, avoid, detect and recover Randomized back-off, a tie-breaker

Real-life image: starvation is a person at a busy counter whom the server keeps skipping; deadlock is two cars facing each other on a one-lane bridge, neither willing to back up; livelock is two people in a corridor who both step aside in the same direction again and again.

Python A livelock in six lines

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Deadlocks have their own chapter later in this course.

Scheduler vs. dispatcher

The two are neighbors in the kernel, but they do different jobs.

Scheduler Dispatcher
Question answered Which process should run next? How do I put that process on the CPU?
Work Applies the algorithm (FCFS, RR, priority...) to the ready queue Saves the old context, loads the new one, switches to user mode, jumps to the resume address
Input / output Ready queue in, chosen process out Chosen process in, running process out
Time Depends on the algorithm and queue length Fixed few microseconds: dispatch latency
Frequency Whenever a scheduling decision is needed Every time the CPU changes process

In short: the scheduler is the policy, the dispatcher is the mechanism (see context switching).

The dispatcher performs these steps:

  1. Switch context (save registers into the old PCB, load the new PCB's registers).
  2. Switch to user mode.
  3. Jump to the proper location in the user program to resume it.

Estimating dispatch latency

Dispatch latency adds to every switch and so shapes the choice of quantum. This demo splits a run into scheduling decisions and dispatches, and totals the overhead.

Python Scheduler picks, dispatcher switches

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

  • Convoy effect: short processes stuck behind a long one (FCFS).
  • Priority inversion: a high-priority process waits for a lock held by a low-priority one.
  • Fairness: every process gets a reasonable share; the opposite of starvation.
  • Throttling: deliberately slowing a process to protect others.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which scheduling algorithm cannot starve any process?

    Round Robin gives every ready process a turn within (n-1) quanta.
  2. 2. What is aging?

    Aging prevents indefinite postponement by making waiting processes more important.
  3. 3. What distinguishes deadlock from starvation?

    Deadlock is a circular wait; starvation is unfair treatment by the policy.
  4. 4. Which component performs the context switch and jumps to the chosen process?

    The scheduler only chooses; the dispatcher hands over the CPU.
  5. 5. What is dispatch latency?

    It is the switching overhead during which no user process runs.

Summary

  • Starvation is indefinite postponement caused by an unfair policy (SJF, priority); aging cures it.
  • Deadlock is a circular wait; livelock is busy-but-no-progress; neither is cured by aging.
  • The scheduler chooses the next process (policy); the dispatcher switches to it (mechanism).
  • Dispatch latency is pure overhead and influences the choice of time quantum.

Next: Real-Time and Multiprocessor Scheduling