Process states and CPU scheduling

Time slicing, in one paragraph

There are more runnable processes than cores, so the kernel switches the CPU between them fast enough that every process appears to be running continuously. The interval a process may hold the CPU before being switched out is a quantum (or time slice) — tens of milliseconds on a typical system. Two kernel components share the work: the short-term scheduler decides which process runs next, and the dispatcher performs the context switch that actually saves one process's registers and loads another's. Multiple cores change the arithmetic but not the problem: as soon as runnable processes outnumber cores, something must choose.

The five states

A process is always in exactly one of these:

• Ready — runnable, in memory, waiting only for a CPU.
• Running — currently holding a CPU.
• Waiting (also called blocked or sleeping) — cannot use a CPU even if offered one, because it is waiting for an event: a disk read, a keystroke, a child to exit, a sleep to expire.
• Swapped — ready to run, but its image has been moved out of main memory to make room. It must be brought back before it can run.
• Zombie — the process has called exit() and is gone from memory, but its entry in the kernel's process table survives, holding its PID and its exit status, because no parent has collected that status yet.

The zombie state is the one that surprises people, and it is examinable. A zombie is not a runaway process; it consumes no CPU and no memory. It occupies a process table slot and a PID, and it exists for exactly one reason: a child that exits must be able to report its status to its parent, so the kernel keeps the receipt until the parent calls wait(). When the parent does, the zombie disappears — this is called reaping. A parent that never waits leaves zombies accumulating; if that parent then dies, its zombies are adopted by init (PID 1), which waits in a loop and reaps them. Writing a server that forks per client and never reaps is the classic way to fill the process table, and it is the shape of Assignment 3's first question.

Worked example — one process around the graph

A text editor is started. It enters Ready. The scheduler picks it: Running. It draws a screen and calls read() on the keyboard; no key has been pressed, so it moves to Waiting and the CPU goes to someone else. You press a key; the event completes and the editor returns to Ready — not straight to Running, because a CPU may not be free. The scheduler dispatches it: Running. It redraws, and this time its quantum expires before it blocks, so it is preempted back to Ready. Eventually you quit; it calls exit() and becomes a Zombie until its parent shell's wait() returns, at which point it ceases to exist.

Notice that every return to Running goes through Ready. There is no edge from Waiting to Running.

The System V priority formula

System V computes a numeric priority value for each process, once per second:

priority value = threshold priority + nice value + (recent CPU usage / 2)

• threshold priority is a per-class base, typically 40 or 60.
• nice value defaults to 0 on Linux and ranges −20 to 19; a higher nice value means you are being nicer to everyone else, so it makes your own priority worse. Only the superuser may set a negative one.
• recent CPU usage is a count of clock ticks the process has recently consumed.

Under this convention, a lower priority value is better — the CPU goes to the smallest number, ties broken first-come-first-served.

Worked: threshold 60, nice 10, recent usage 30 ticks gives 60 + 10 + 15 = 85. The same process with the default nice would be 75, and would be dispatched ahead of the niced one.

The decay function, and why it is the interesting part

Before each recalculation the kernel halves every process's recent-usage counter. That one line is what makes the formula work. Without it, a process that ran hard for a minute an hour ago would carry that penalty forever, and a process that had never yet run would outrank every long-lived job on the machine permanently. Halving makes the influence of past CPU use decay exponentially, so the number in the formula means recent behaviour and nothing else.

The consequence is the behaviour you actually want from an interactive system: a CPU-bound job (a compile, a simulation) burns its quantum every time, accumulates ticks, and drifts to a worse priority value. An I/O-bound job (an editor, a shell) blocks after a millisecond, accumulates almost nothing, and stays near the threshold — so it is dispatched almost immediately every time you press a key. Nobody configured that. It falls out of the arithmetic.