Scheduling

A server with 8 cores may have 400 threads. Every few milliseconds the scheduler decides which of the runnable ones get the 8 cores, and for how long. Every policy it could follow trades response time against throughput and fairness against simplicity, and the classic policies have names older than most programming languages.

This topic teaches those ideas and the queueing curve that makes a busy machine slow long before it is full. The settings of any one kernel stay with Linux Deep Dive. What stays here is the reasoning that tells you what a setting could possibly buy.

The Scheduler's Job

Each core keeps a queue of threads that are ready to run. A hardware timer interrupts the core at regular intervals and hands control to the kernel, which makes one decision each time: who runs next, and for how long. A thread that blocks, waiting on a disk read, a network reply or a lock, leaves the queue entirely and rejoins it only when the thing it waited for arrives.

That is why a thread count says almost nothing about load. Four hundred threads that spend nearly all their time waiting on the network make a lightly loaded machine. Twelve threads that each want a core all the time, on 8 cores, make an overloaded one: at every moment four of them are ready and waiting for no reason but the lack of a core.

First In, First Out, and Shortest Job First

The simplest policy runs threads in the order they became ready and lets each run until it blocks. Put a 10-second batch job ahead of a 1-millisecond request and the request waits 10 seconds for work it could have finished almost instantly. This is the convoy effect: one long job at the front of a queue drags every short job behind it.

Running the shortest job first is provably the best order for average waiting time. The figure takes three jobs of 8, 2 and 1 seconds. In arrival order their waits are 0, 8 and 10 seconds, an average of 6. Shortest first, the waits are 0, 1 and 3, an average of about 1.3. The catch is that the policy needs to know how long each job will run, which is the future. Real schedulers estimate it from each thread's past behaviour instead.

Round Robin and the Time Slice

Round robin gives each runnable thread a slice of time, a few milliseconds or less, then preempts it, moves it to the back of the queue and runs the next one. Nobody waits behind a convoy for long, because the long job is interrupted after every slice. The price is switching: every slice ends in a context switch, with the direct and cache costs of the previous topic.

The slice length reduces the trade to one number. Short slices make interactive work feel responsive and spend more of the machine on switching. Long slices waste less and make everything feel sluggish when the machine is busy. No slice length is right for both a video call and a compile job, and real schedulers do not stop at round robin.

Priorities, Starvation and Feedback

Strict priority always runs the highest-priority ready thread. It lets a busy high-priority thread starve everything below it, forever. The classic fix is ageing: a thread's priority rises the longer it waits, so it eventually runs whatever is above it.

A cleverer family of fixes learns from behaviour. A thread that uses its whole slice is probably batch work, so it drops a level. A thread that blocks early, after a keystroke or a short request, is probably interactive, so it stays high. This is the multi-level feedback queue, and its logic survives inside most general-purpose schedulers: favour whatever looks interactive, and let the batch work soak up the rest.

Fair Share

Instead of fixed priorities, a fair-share scheduler gives every thread a share of the processor and always runs the one that has received the least time relative to its share. It tracks this as a per-thread "virtual time" that advances while the thread runs, faster for threads with smaller shares, and picks the thread with the smallest.

One real implementation was Linux's Completely Fair Scheduler, which kept runnable threads in a red-black tree ordered by virtual time, one of the balanced trees of Chapter 6, so the next thread to run was always the leftmost node. Linux 6.6 replaced it in 2023 with a scheduler called EEVDF, which keeps the same fair-share accounting and adds deadlines for latency. The names are here for recognition; the idea is the part that lasts.

Many Cores, Queueing and CPU Limits

Each core keeps its own queue, because one shared queue would be a point every core fights over. Moving a thread to an idle core costs the warm cache it leaves behind, so schedulers rebalance lazily. A container with a hard limit on its processor use is scheduled against a budget per period, commonly 100 milliseconds. A service that spends its budget early in the period is paused for the rest of it, even with the machine otherwise idle, and that shows up as latency spikes at a low average processor use.

Queueing makes all of this worse than the averages suggest. In the simplest queueing model, a server busy half the time makes the average request wait one service time before it starts. At 70% busy the wait is about 2.3 service times, at 90% it is 9, and at 99% it is 99. Waiting grows slowly and then all at once, and the knee sits somewhere past 80%. To watch and tune a real kernel's scheduler, see Linux Deep Dive, chapters Processes and Signals and The Kernel and Containers.