Run Queues and the Cost of a Context Switch

A machine with eight CPUs and forty runnable threads must answer one question several thousand times a second: which eight run now. Everything else in this cluster, from fairness accounting and priority classes to deadline admission and migration between cores, is machinery built around that decision and around the cost of changing it. The data structure that holds the candidates is the run queue, and the operation that swaps one candidate for another is the context switch.

The two are worth studying together because the queue’s design is dominated by the switch’s price. If switching were free, a single global queue with a global lock would be the obvious implementation: one list, one pick, no per-CPU bookkeeping. Switching is not free. On current hardware a switch between two threads of the same process costs on the order of a few microseconds once the direct work and the resulting cache disturbance are counted, which is roughly the same magnitude as several thousand arithmetic instructions. At a few thousand switches per second per CPU that is already a percent or two of the machine. Make the queue global and the lock protecting it becomes a contention point that grows with core count, so the very structure that made the decision simple makes the decision expensive. Per-CPU queues are the answer, and the rest of the scheduler’s complexity follows from keeping those queues in balance.

The runnable set and the run queue

A thread is runnable when it could execute on a CPU immediately if one were free. It is not blocked on I/O, not waiting on a lock, not stopped, not sleeping. Runnable threads sit in a run queue; blocked threads do not, and moving between the two states is what makes a thread visible to the scheduler at all.

The queue therefore holds exactly the threads competing for CPU time, and its length is the load signal. A queue with one entry needs no policy: run that thread. A queue with twenty needs a rule for which one goes next and, just as importantly, a rule for how long the current one may keep the CPU before it is forced back into the queue. That second rule is preemption, and without it a run queue is only a hint that a cooperative thread may consult when it feels like yielding.

Two numbers describe the queue’s state at any instant: the number of runnable threads (often called the load, and tracked as a weighted sum rather than a raw count once priorities enter) and the number of CPUs available to serve them. Their ratio is the pressure. At 0.5, half the machine is idle and latency is bounded only by the work itself. At 4, every thread waits roughly four times its own service time before it starts, and no policy can hide that; the scheduler can only choose whom the delay falls on.

What a switch actually does

The visible part of a switch is small. The kernel saves the outgoing thread’s callee-saved registers, stack pointer, and instruction pointer into its saved context, selects the incoming thread, and restores the same set from the incoming thread’s context. On x86-64 the state a switch must save and restore is the full general-purpose register set, which runs to sixteen registers in total; the floating-point and vector state lives in a separate area and is either restored eagerly or left in the hardware until the incoming thread touches it, an optimisation that pays off because most threads never execute a vector instruction between switches.

The address space switch is the expensive part when the incoming thread belongs to a different process. The page-table root must be loaded into the control register that names it, and unless the processor tags translation entries with an address-space identifier, every cached translation for the old address space becomes invalid and the new process pays a page-walk for each of its first accesses. Tagging schemes exist precisely to avoid this: an identifier field in each TLB entry lets entries from several address spaces coexist, so a switch between two processes with distinct tags costs no flushing. Where the hardware does not tag, the kernel flushes the entries on a context switch and the incoming thread’s first accesses miss together rather than one by one.

Threads of the same process share a page-table root, so a switch between them skips that step entirely, which is why user-level threading runtimes can multiplex many logical threads onto few kernel threads at a fraction of the kernel’s switch price.

/* The register-save half of a switch, stripped to the essentials.
   struct thread holds the stack pointer and the callee-saved set. */
struct thread {
    void   *sp;          /* kernel stack pointer while descheduled */
    uint64_t rbx, rbp, r12, r13, r14, r15;
    uint64_t rip;
};

/* switch_to(new) runs on the outgoing thread's kernel stack and returns
   on the incoming thread's, so the caller must treat it as a barrier:
   locals in registers are not preserved across the call. */
void switch_to(struct thread *new);

The comment matters more than the code. Because the function returns on a different stack, any compiler assumption about the caller’s frame is void; real implementations mark the routine so the compiler spills everything live and does not reorder loads across it. Getting this wrong produces bugs that appear only under optimisation, at low frequency, and on one architecture.

Where the cost lands

The direct cost, comprising registers, control registers, and a few hundred instructions of bookkeeping, is the smaller half. The larger half is the state left behind in caches and predictors.

The outgoing thread has been filling L1 and L2 with its own data and its own instructions. The incoming thread will miss on essentially all of it, and on a core with a 32 KiB L1 data cache and an L2 of a few hundred kilobytes the refill of a working set larger than the private caches costs the miss latency of each cache line multiplied by the number of lines touched, which mounts to tens of microseconds once the hot data no longer fits. Branch predictor state and the return-address stack are likewise per-thread in effect; a switch presents the predictor with an unfamiliar instruction stream and mispredictions rise until it re-learns.

This is why the scheduler’s choice of when to switch is as consequential as whom to run. Switching on every wakeup, the obvious policy, maximises responsiveness and pays the cache cost constantly. Batching wakeups, running the current thread for a short grace period while a newly woken thread waits in the queue, trades a little latency for a large reduction in switch count. The batching window is a tunable that appears in every general-purpose scheduler under some name, and its effect on interactive latency is the reason it is tuned conservatively rather than aggressively.

There is a third cost that is easy to overlook: the switch itself runs kernel code that touches shared structures, so a switch on one CPU can invalidate a cache line another CPU is using. At high switch rates on many cores this shows up as coherence traffic rather than as time inside the switch routine.

Why one queue per CPU, and what it costs

A per-CPU run queue with a per-CPU lock means the common operation, picking the next thread, touches only local data. No other CPU writes to that queue, so its lock is almost always uncontended and the pick is a few tens of nanoseconds of pointer work plus whatever policy the queue implements.

The price is that the queues drift. Threads are created on one CPU, wake on another, and the work they do is uneven. A CPU with an empty queue cannot help a CPU with thirty entries without reaching into another CPU’s structures, which reintroduces the lock the design was avoiding, now in a rarer but more delicate form. Load balancing is therefore periodic and batched rather than continuous: a CPU that notices its own queue is empty pulls a batch of threads from the busiest queue, taking the lock once for many migrations instead of once per thread.

Migration is not free either, and its cost is the same cache disturbance as a switch, plus a possible change of NUMA node. Pulling a thread to a core whose memory is two hops away converts a scheduling gain into a memory-latency loss, so balancing decisions weigh topology, not just counts. The machinery that does so is described in Load Balancing and Thread Migration on Symmetric Multiprocessors.

The other consequence of per-CPU queues is that fairness becomes approximate. A thread that happens to be alone on a CPU accrues time at a different rate from one sharing a busy queue, and the accounting that reconciles them has to be defined in terms of virtual time rather than wall time. That is the subject of Virtual Runtime and Weighted Fair Queuing.

When the model breaks

Two degenerate cases expose the assumptions. The first is a queue holding one thread that never blocks and never yields: preemption by timer is the only thing that ever produces a scheduling event, so the granularity of the timer bounds how quickly any newly woken thread can run. A kernel built without a periodic tick must generate an event from a programmable timer set to fire exactly when the running thread’s slice expires, and the resolution of that timer becomes the latency floor.

The second is a switch storm: many threads waking and blocking faster than their slices, so the CPU spends its time in the switch path rather than in user code. The queue’s length stays small while throughput collapses, which is why load average computed from queue length is a poor indicator of this condition and why kernels count switches and involuntary preemptions separately.

Finally, the run queue is not the whole scheduling state. A thread that is runnable but pinned to a CPU it cannot currently use is in no queue at all from the perspective of the others, and a thread holding a resource another runnable thread needs can make the queue’s order irrelevant, a hazard that priority inheritance exists to fix, covered in Priority Inversion and Inheritance.