Scheduling and preemption

2.4 Sharing the core: the scheduler and its clock

A box has more runnable threads than cores, and the first promise the operating system makes is that every one of them will get a turn. The scheduler is the part that keeps the promise. This section is how it does that, why keeping it requires interrupting your thread whether or not anyone else wants the core, and what each of those interruptions costs.

Run queues, blocking and preemption

The scheduler keeps one run queue per core: the threads that are ready to run and are allowed to run there. Every thread carries an affinity mask, the set of cores it may use, and by default that is all of them, so by default every runnable thread on the box is a candidate for every core. A thread leaves a core in one of two ways. It blocks: it asks for something that is not there yet, a packet, a lock, a timer, and the kernel parks it on a wait queue for that thing and runs someone else. Or it is preempted: it was still running, and the scheduler took the core away to give another thread a turn.

Most threads block most of the time, and a kernel designed only for them would need no clock. But a thread in user mode that never blocks never gives control back; a loop is a loop. If the scheduler is to take the core from it, something must bring the kernel back onto that core at intervals, and nothing in user space can be trusted to do it. So the kernel programs the core’s local timer to interrupt it CONFIG_HZ times a second: the tick. 250 a second on Debian’s and Ubuntu’s generic kernels, 1,000 on Red Hat’s and on Ubuntu’s lowlatency kernel. On each tick the kernel updates its clocks and the running thread’s accounting, fires any timers that have expired, and asks the scheduler whether the running thread has had its share. For a shared machine that is the right design: nothing can hog a core for longer than a tick without the scheduler getting a say. A core with nothing to run stops its tick, since there is nothing to take the core from. A core running exactly one thread keeps it, although there is equally nothing to decide; that asymmetry is a design choice, and later versions of the kernel let it be changed.

Who gets the turn

The share is set by the scheduling class. The normal fair class weights runnable threads by nice value. Older kernels use CFS’s virtual-runtime selection; Linux began moving to EEVDF in 6.6, which selects eligible tasks by virtual deadline rather than simply choosing the least runtime. The EEVDF documentation describes that distinction. Above fair tasks are SCHED_FIFO and SCHED_RR, then SCHED_DEADLINE and the kernel’s stop class. Real-time bandwidth control, where enabled, commonly reserves 50 ms of each one-second period for other work (sched_rt_runtime_us=950000), so an always-spinning real-time thread can be throttled. Removing that cap requires keeping housekeeping work runnable elsewhere.

Waking is the other half of blocking. When the packet arrives or the lock is released, the kernel takes the waiting thread off its wait queue, puts it on a run queue, and, if that queue’s core is idle or running something less important, sends the core an interrupt so that it reschedules now rather than at its next tick. That inter-processor interrupt, an IPI, is the RES row of /proc/interrupts. From user space the primitive underneath every Mutex, Condvar, park and channel is futex, the fast user-space mutex: the uncontended case is one atomic instruction with no kernel at all, and only a thread that must wait, or must wake a waiter, makes the system call.

Last, the load balancer. Every few milliseconds, and whenever a core goes idle, the scheduler compares run-queue lengths across cores and moves threads to even them out. For a web server that is free capacity. For a thread whose L1, L2 and TLB were warm on the core it just left, it is a migration, and the first thing it does on the new core is miss on everything.

The kernel’s own threads

Some of the kernel’s work cannot run inside an interrupt: it may need to sleep, wait for a lock, or run for milliseconds. For that the kernel has threads of its own, shown in square brackets by ps, scheduled by the same scheduler on the same run queues as yours, and most of them come one per core because a per-core queue of work needs no locking. kworker/<n>:<m> run the workqueues, the kernel’s general mechanism for “do this later”, which carries writeback of dirty page-cache pages, driver housekeeping and much else. ksoftirqd/<n> runs deferred interrupt work when there is too much of it, which the next section explains. migration/<n>, the highest-priority thread on the box, exists to push a running thread off its core when the balancer asks. A few are global: kswapd<node> reclaims memory when one socket’s DRAM (a NUMA node) runs low, kcompactd<node> defragments it, khugepaged collapses small pages into huge ones. They run only when they have work; when they have work they run on your core, through your caches, and the fair class gives them their share.

One more mechanism rides on the tick and deserves a paragraph, because it reappears whenever the tick is discussed. The kernel is full of shared structures that are read constantly and changed rarely: the routing table, the list of processes, every open file’s description. Locking them for every read would serialise hundreds of cores on a handful of cache lines. Read-copy-update, RCU, lets readers read with no lock at all: a writer builds a modified copy, swaps one pointer so that new readers see the new copy, and frees the old one only after a grace period, a point by which every core has passed through a quiescent state, a context switch, a spell in idle, or a return to user mode. The frees are queued as callbacks and run after the grace period, by default on the core that queued them, in a softirq or an rcuc/<n> thread. Two things follow. Grace-period detection needs every core to report that it has been quiescent, and the tick is how an ordinary core reports. And the callbacks are work that lands on a core because that core once asked the kernel for something, whether or not it has time now.

What it costs

Each tick costs the core 1–5 µs: the interrupt, the clock and accounting updates, any expired timers, the scheduler’s check, the return, and the cache lines all of that touched on the way through. On a core running one thread the decision is always “keep running”, and the whole cost is overhead, 250–1,000 times a second.

A preemption has three parts, and the one everybody names is the smallest. The switch itself, saving your registers, switching stacks and page tables and restoring the other thread’s, is 1–2 µs. The slice is the other thread’s turn: it runs until it blocks or until its slice ends, 1–4 ms, during which every packet for your thread queues in the socket buffer, and the first thing the thread does on return is work through a backlog whose age is the slice. The return is the indirect cost: the other thread’s code and data have replaced yours in L1, L2 and the TLB, and the predictor has learnt its branches; rebuilding a working set of a few hundred kilobytes is thousands of misses, 10–100 µs, spread over the messages that follow. A migration costs the third part without the first two.

Worked example: one loop, one shared core

A message loop does one iteration per microsecond, pinned to core 3 of a stock box with HZ=250, and nothing else on the box is busy. Over a second the tick lands 250 times, each costing 3 µs, so 250 of a million iterations take 4 µs instead of 1: 0.075% of the core’s time, invisible at p50 and p99, present from about p99.97 upwards, with a p99.99 of 4 µs and a max of 4 µs. Now a monitoring agent wakes once a second on core 3, because its affinity mask includes core 3 and the balancer saw an idle-looking core there, and runs for 3 ms. One iteration in a million now takes 3,000 µs, the max is 3 ms, and the thousand or so iterations after it each run slower while the caches refill. The p50 did not move. The histogram’s max moved by a factor of a thousand, from an event that happens once a second and that nothing in the loop’s code caused.

Nothing in the loop’s code caused either event, and nothing in it can see them coming: the tick and the slice are the scheduler keeping its promise to the other threads allowed on the core. On a shared core, then, a thread’s tail is set by who else may run there and by how often the clock fires, and both are facts about the box rather than the program.

Seeing it

The thread’s own counters tell you whether any of this happened. /proc/<pid>/task/<tid>/status has nonvoluntary_ctxt_switches, the number of times the thread was preempted while it still wanted the core, and voluntary_ctxt_switches, the number of times it gave the core up by blocking. /proc/<pid>/task/<tid>/sched has nr_migrations, the number of times the balancer moved it. LOC in the core’s column of /proc/interrupts counts the ticks. ps -eo pid,psr,comm | awk '$2 == 3' lists what last ran on core 3, kernel threads included. Reading the counters before and after a run is the cheapest jitter test there is, and Lab 2.1 puts a histogram next to them.