Whose turn, and who decides

Processes Threads and the Kernel · Open board

The kernel handing out turns on a few cores to many programs. This lesson asks the question the drawing takes for granted: when several programs are waiting, which one goes next?

Before you start. The CPU is the chip that runs a program’s instructions; a core is one of several copies of that machinery inside it, each running one program at a time. The kernel is the one program with full access to the hardware, and its scheduler gives each running program a short turn on a core, then takes it back and gives the next one a turn (Processes, Threads & the Kernel). Every swap from one program to another costs a little time, because the core has to save one program’s place and load the next one’s.

The idea in 30 seconds

When several programs want the processor, a part of the operating system called the scheduler picks who runs next, and every rule for picking trades one good thing for another.
Response time is how long a job waits before it first runs; turnaround time is how long it takes to finish. A person at a keyboard feels the first; a batch job cares about the second.
Running the shortest job first gives the best average turnaround, but it needs to know each job’s length in advance, which a kernel does not.
Taking turns with a time slice (a fixed turn length) gets a short job onto the CPU quickly; shorter turns answer sooner but lose more of the CPU to swapping between programs.
Since 2007, Linux runs whichever program has had the least processor time so far, instead of guessing which programs a person is waiting on. A program marked more important has its time counted as if it were less, so it runs more often.

Read the story · Skip to the numbers