CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 6 of 7 · 4 min read

Boost

Gaming the scheduler and the boost

In plain words: Rule 4 has a weakness. A program that wants more than its share can compute for almost a full quantum, then do a tiny I/O (such as writing one byte) just before the quantum ends. It gives up the processor early every time, so it never moves down, and it monopolises the top queue. The fix is to count the total time a process uses at one level, whatever the number of times it gives up the processor, and to demote when this total is used up. This is the allotment.

There is a second weakness, with starvation again. If many interactive processes keep the top queue busy, the long jobs at the bottom may never run. Also, a process that changes from CPU-bound to interactive (a compiler that finishes and waits for input) stays at the bottom for ever. The cure is the priority boost: after some fixed time, every process is moved back to the top queue. This restores fairness (nobody starves, since all get to the top) and gives a changed process another chance to prove itself.

Two settings need care. If the interval for the boost is too long, long jobs starve a little. If it is too short, interactive processes lose some of their advantage to the long jobs. The numbers are found by experience and measurement, not by a formula.

Real systems use these ideas. BSD Unix and Windows use priority levels with adjustments from recent behaviour. Linux uses a different design, described on page 5.

Priority boost

A priority boost is the periodic action of moving all processes to the highest-priority queue of a multilevel feedback queue, which stops starvation of long jobs and lets a process whose behaviour has changed be classified again.

Example: every 50 ms, a scheduler puts all processes back in the top queue, and any compute-bound process sinks again within a few quanta.

Common mistake

Treating a priority number as a share of the CPU. A higher priority means "served first". It does not mean "gets twice as much", and a high-priority process that never waits can take every cycle (Linux handles shares differently, page 5).

Interview angle

Answer in your head first, then open it.

What is starvation, and how does aging help?

A ready process that never runs. Aging raises priority with waiting time until it is the best.

What is priority inversion?

A high-priority process waits for a lower one, because of a lock and a medium-priority process that preempts the holder.

How does priority inheritance fix it?

The lock holder temporarily takes the priority of the highest waiter.

How does an MLFQ decide which processes are interactive?

A process that gives up the processor early stays high, one that uses full quanta sinks.

Why does an MLFQ need a boost?

To stop starvation and to reclassify processes that change behaviour.

Check yourself: 1. How does a program game rule 4? 2. How does counting total time at a level stop the gaming? 3. Why can the boost interval not be too short or too long?

Words you will meet

Word Meaning
Priority A number that ranks a process
Aging Raising priority as a process waits
Priority inversion A high-priority process blocked by a lower one
Priority inheritance The lock holder temporarily takes the waiter's priority
MLFQ Several queues, with processes moved by behaviour
Allotment The total time allowed at one level before demotion
Priority boost Moving all processes to the top queue now and then

Quick notes

  • Priority scheduling is a policy in which every process has a numeric priority and the processor always goes to the ready process with the highest priority, with ties broken by.
  • Aging is a technique that gradually raises the priority of a process the longer it waits in the ready queue, so that every process eventually becomes the highest priority and cannot be starved.
  • Priority inversion is a situation in which a high-priority process is made to wait by a lower-priority process, usually because the lower one holds a resource that the higher one.
  • A multilevel feedback queue is a scheduler with several ready queues of different priorities, where new processes start in the highest queue, a process that uses its whole quantum moves.
  • A priority boost is the periodic action of moving all processes to the highest-priority queue of a multilevel feedback queue, which stops starvation of long jobs and lets a process whose behaviour has changed be classified again.