The Program That Waits Gets Served First, and It Is Not Being Rewarded

Last timeWhat a Process Actually Is

The scheduler picks whoever has had least so far. That one rule explains why interactive programs feel fast, why a busy loop does not starve anybody, and what the time slice is trading.

The tick and the runnable set

A machine with three hundred processes and eight processors is not running

three hundred things. It is running eight, and the other two hundred and

ninety-two are in one of two situations: ready to run and not currently chosen,

or not ready at all because they are waiting for something.

That distinction is the first thing to get straight, because only the ready

ones are candidates. On a typical idle desktop the number of runnable processes

is between zero and three. The scheduler is not sorting hundreds of

contenders; most of the time it is choosing between two.

A decision happens at specific moments and not continuously. A timer interrupt

arrives, a few hundred times a second, and the kernel asks whether the running

process should continue. Something becomes runnable, perhaps because a disk

read finished, and the kernel asks whether it should displace what is running.

Or the running process gives up voluntarily, by making a request that cannot be

satisfied immediately. Between those moments nothing is decided and the running

process runs.

FIG 1What happens at a tick

Note that two of the three paths through this diagram end without a switch, which is the common case and the reason the overhead is tolerable. The branch at the fourth node is where interactivity comes from, and nothing in it mentions interactivity: it compares two numbers.

Whoever has had least

The selection rule on a modern general-purpose system is close to this: keep a

running total of processor time each process has received, and always run the

one whose total is lowest.

Priority enters as a weight on how fast the total accumulates. A high-priority

process is charged less than the time it actually used; a low-priority one is

charged more. Nobody computes a share, and yet the shares come out right,

because a process charged at half rate ends up running twice as much before its

total catches up.

FIG 2How priority turns into a share, without anybody dividing

: what the process is charged, which is what gets compared
: the processor time it actually used
: its weight, higher for a higher priority

Everything about priority is in this one division. Two processes competing will settle at charged totals that stay close together, because whichever is behind gets picked, so their actual times end up in the ratio of their weights. A process with twice the weight runs twice as much, and the scheduler never calculated a percentage of anything. The practical reading is that priority on a fair-share scheduler is a ratio rather than a rank, so a low-priority process is slowed rather than starved.

Why waiting earns a turn

Here is where the rule pays for itself, and the derivation needs no new ideas.

Consider two processes. One computes continuously: a compile, a render, a

training run. The other handles a keystroke, which takes it two hundred

microseconds, and then waits for the next one, which might be half a second

away.

The computing process accumulates charged time constantly. The waiting process

accumulates almost none, because while it is blocked it is not running, and a

process that is not running is not charged. Its total falls further and further

behind.

The lesson stops here

3 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents