Load Balancing and Thread Migration on Symmetric Multiprocessors

Per-CPU run queues remove the global lock and create an imbalance problem. Threads are created on one CPU, wake on another after an I/O completion, and finish at different times; nothing in the queue structure notices or corrects the drift. A machine can have four CPUs idle while four others each hold a dozen runnable threads, and every one of those twelve threads gets a quarter of the CPU it would get if the load were spread.

Balancing is the machinery that notices and corrects. It is inherently a background activity because the useful moments, a thread blocking or a CPU going idle, are exactly the moments when the scheduler has no reason to spend cycles on global bookkeeping. The result is a design that samples, batches, and tolerates imprecision, and whose hardest part is not the movement of threads but the decision of whether a move is worth making at all.

What “balanced” means

The naive objective is equal run-queue lengths. It is the wrong objective for two reasons.

First, queue length ignores weight. Two threads at nice 0 and one thread at nice 19 are not equivalent load, and moving the nice-19 thread to a queue holding a single nice-0 thread makes the first queue lighter by count and heavier by weighted demand. Balancing therefore operates on weighted load, the sum of the threads’ weights, not on the number of threads.

Second, queue length ignores what the threads are doing. A CPU with eight threads that each run for a microsecond and block is mostly idle; a CPU with two compute-bound threads is saturated. Weighted load that uses observed CPU utilisation, the fraction of the recent past spent executing rather than idle, is a better proxy than a count of runnable entities, and most implementations track both because each is misleading in a different regime.

The practical definition used by balancing code is comparative: a queue is a candidate for pulling from if its load exceeds the pulling queue’s load by more than some margin, where the margin is large enough that noise and short-term bursts do not trigger migration. A margin is necessary because migration costs more than the imbalance it corrects when the imbalance is small.

The three moments balancing runs

Balancing is triggered by events rather than by a clock, because the events are free signals.

The first is a CPU about to go idle. When the idle thread is selected and there is other work in the system, the CPU can afford to look for it: the alternative is to halt, which wastes the entire core. This is the highest-value balancing point because the cost of a failed search is small and the cost of not searching is a fully idle core while another has a queue.

The second is a periodic rebalance on a busy CPU. A CPU that never goes idle will never trigger the idle path, so a busy CPU also checks its queue against its neighbours’ on a schedule of its own and pushes a batch of threads away when it is unreasonably longer. The period is on the order of milliseconds, long enough that the check is negligible and short enough that an imbalance does not persist for a noticeable fraction of a second. This path runs only when the CPU is busy, so its cost competes with the work it is trying to protect, and the reason it is tolerable at all is that a busy CPU is exactly the one that can afford to shed load rather than to spend cycles hunting for it.

The third is a newly woken thread. On wakeup the scheduler chooses a queue, and the choice is a load balancing decision in miniature: place the thread on the CPU it last ran on if that CPU is not overloaded, otherwise on an idle CPU, otherwise on the least loaded. Placing on the previous CPU is preferred because the caches and TLB entries still hold the thread’s data, the same locality argument that makes migration expensive.

/* Idle-path pull. Take up to nr_move threads from the busiest queue whose
   weighted load exceeds ours by more than imbalance_pct. The lock on the
   source queue is taken once for the whole batch. */
static int pull_tasks(struct rq *self, int nr_move)
{
    struct rq *busiest = find_busiest(self, imbalance_pct);
    if (!busiest)
        return 0;

    int moved = 0;
    raw_spin_lock(&busiest->lock);
    while (moved < nr_move && !list_empty(&busiest->queue)) {
        struct thread *t = detach_eligible(busiest, self);
        if (!t)
            break;
        attach(self, t);          /* vruntime normalised on migration */
        moved++;
    }
    raw_spin_unlock(&busiest->lock);
    return moved;
}

The batch size is the whole point of the lock discipline. Taking the source lock once to move eight threads costs one acquisition; taking it eight times costs eight, and each acquisition is a chance for the source CPU to be spinning on the same line. Batches also reduce the chance that the move is undone immediately by the source CPU pulling them back.

Why a moved thread may be worse off

Migration preserves nothing. The thread arrives on a new CPU with a cold L1 and L2, a cold TLB unless the hardware tags entries by address space, and a set of cache lines that are now in another core’s cache in a modified state. The first accesses after the move therefore pay coherence traffic as well as misses. On a machine where a thread’s working set is a few hundred kilobytes and the private caches are tens of kilobytes, that refill is the dominant cost of the move and it can exceed the benefit if the imbalance being corrected is small.

The asymmetry is sharpest for threads that were recently running. A thread that has been descheduled for a long time has already lost its cache footprint, so moving it costs little; a thread that just blocked on a lock still has its data in the old core’s cache, so moving it throws away warm state. Good balancing therefore prefers to move threads that are cold, which is why the wakeup path and the idle-path pull are better targets than the periodic push of a running thread.

NUMA adds a second dimension. On a machine with several memory nodes, a thread’s accesses to memory attached to a remote node cost more than local accesses by a factor that depends on the interconnect. Moving a thread to a less loaded CPU on a different node trades CPU contention for memory latency, and the trade is only favourable when the contention is severe. Balancing code handles this by preferring moves within a node and only crossing node boundaries when the imbalance exceeds a higher threshold, and by tracking each thread’s preferred node, usually the node its memory was allocated on, so that a thread is not moved away from its own data.

Affinity as a constraint

The user can pin a thread to a set of CPUs, and the scheduler must respect the mask even when it conflicts with balance. A thread whose mask names only CPU 3 cannot be pulled to CPU 5, and a queue that looks overloaded because of such threads cannot be relieved by moving them. This makes affinity a direct trade: it guarantees locality and it can produce permanent imbalance.

The classic failure is a set of threads each pinned to a different CPU, where one of them is the bottleneck and the others are idle. No amount of balancing helps, because the constraint is hard. Systems that offer affinity usually also offer a soft form, a preference that the scheduler may override under load, and the distinction between hard and soft is worth knowing when diagnosing a machine that refuses to use half its cores.

Affinity also interacts with the accounting normalisation described in Virtual Runtime and Weighted Fair Queuing. A pinned thread accumulates virtual runtime at its own queue’s rate for the entire run, so two threads with identical weights but different pins can diverge in virtual runtime by an amount that has nothing to do with their service. When the pin is later released, the thread that was on the busier CPU appears to have been favoured and is penalised.

Work stealing as an alternative

The pull-on-idle model has a weakness: a CPU with an empty queue must find work by looking at other queues, and the search is a global scan whose cost grows with core count. The alternative, work stealing, inverts the responsibility. Each CPU keeps a deque of its own work and pushes and pops at one end; a CPU with nothing to do steals from the other end of a randomly chosen victim’s deque. Choosing the victim at random makes the number of steals attempted scale with the total work rather than with the number of workers, and the opposite-end discipline means a steal takes the oldest work, which is the least likely to be cache-warm and the least likely to be immediately needed by the victim.

Work stealing is the standard design for user-space runtimes precisely because it avoids a global structure entirely and scales to hundreds of workers. In a kernel the fit is less clean, because threads are not created by a runtime that knows their dependency structure and because a kernel thread that blocks must be removed from the middle of a structure rather than from an end. The two designs are not mutually exclusive: a kernel can use per-CPU queues with pull-based balancing for its own threads while a user-space runtime layered on top uses stealing among its workers, with the kernel seeing only the small number of runtime threads.

Measuring whether it worked

Balance quality is not directly observable from any single counter. The signals that matter are the distribution of run-queue lengths over time, the rate of migrations, and the fraction of time each CPU spends idle while others have runnable threads. A machine with a high migration rate and persistent idle time is one where balancing is thrashing: threads move often enough to lose their caches but not often enough to fill the idle cores.

The pathological case is a small number of long-running compute threads on a machine with many cores and a bursty interactive load. The compute threads are cheap to keep in place and expensive to move; the interactive threads are the opposite. A policy that treats them identically will either move the compute threads unnecessarily or leave interactive threads queued behind them. This is the point where balancing stops being a load problem and becomes a classification problem, and it is the reason latency-sensitive classification of the kind a multi-level feedback structure provides, sits alongside balancing rather than inside it.