vault

Wakeup Balancing and select_task_rq

14 min read

Wakeup Balancing and select_task_rq

When a sleeping task is woken — by another task releasing a lock, by data arriving on a socket, by a timer firing — the kernel must answer one question before it can run: which CPU should it run on? This is wakeup balancing, and the fair class implements it in select_task_rq_fair() (kernel/sched/fair.c, Linux 6.12 LTS). The decision is a tug-of-war between two goods that usually conflict: cache affinity (run the wakee where its data is still hot, ideally on the CPU that woke it or the CPU it last ran on) and spreading (don’t pile tasks onto a busy CPU when an idle one sits next door). The kernel resolves it with a stack of cheap heuristics — wake_wide(), wake_affine(), and select_idle_sibling() on the fast path; sched_balance_find_dst_group()/sched_balance_find_dst_cpu() on the slow path — each consulting the scheduling-domain hierarchy (Scheduling Domains and CPU Topology) to know which CPUs share a cache. This is placement at wakeup, distinct from but complementary to the periodic Scheduler Load Balancing that runs later to correct accumulated imbalance.

This note pins to Linux 6.12 LTS (released 2024-11-17). The relevant code lives in kernel/sched/fair.c; wake-flag definitions are in kernel/sched/sched.h. Names matter here: the load-balancing helpers were systematically renamed in Linux 6.10 (released July 2024) — find_idlest_group/find_idlest_cpu became sched_balance_find_dst_group/sched_balance_find_dst_cpu, and the busiest-side equivalents changed too. This was verified by diffing the v6.9 and v6.10 fair.c blobs (v6.9 still has find_idlest_group, v6.10 has only sched_balance_find_dst_group). Older write-ups use the pre-6.10 names for the same functions.

Mental Model — affinity versus spread

Think of a waking task as a parcel that needs delivering to a CPU. Two delivery strategies compete. The affine strategy says: deliver it close to where it came from — to the waking CPU (the CPU running the code that issued the wakeup) or the previous CPU (prev_cpu, where the task last ran), because that CPU’s L1/L2 cache and the shared last-level cache (LLC) probably still hold the task’s working set, and a migration throws that away plus dirties two caches. The spread strategy says: a busy CPU means the parcel waits in a queue; an idle CPU two desks over could start it immediately, and one idle CPU running hot is better for the CPU-frequency governor than two half-loaded ones.

The kernel’s resolution is layered. First a gate, wake_wide(), decides whether affinity even makes sense for this waker/wakee pair — a one-to-many dispatcher (one thread waking hundreds of workers) should not keep dragging every worker onto its own LLC, so wake_wide() returns true and disables affinity. If affinity is still wanted, wake_affine() picks between the waking CPU and prev_cpu. Whichever CPU that yields becomes the target, and select_idle_sibling() then scans that target’s LLC for an actually-idle CPU to land on — because the target might be busy, but a hyperthread sibling or sibling core sharing its cache might be free.

flowchart TB
  TTWU["try_to_wake_up()<br/>sets WF_TTWU (+WF_SYNC?)"] --> STRQ["select_task_rq_fair(p, prev_cpu, wake_flags)"]
  STRQ --> CURCPU{"WF_CURRENT_CPU<br/>and allowed?"}
  CURCPU -->|yes| RETCUR["return waking CPU"]
  CURCPU -->|no| EAS{"EAS active and<br/>rd not overutilized?"}
  EAS -->|yes| FEEC["find_energy_efficient_cpu()"]
  EAS -->|no| WW["want_affine =<br/>!wake_wide(p) && cpu allowed"]
  WW --> LOOP["for_each_domain: find affine-capable<br/>SD_WAKE_AFFINE domain spanning prev_cpu"]
  LOOP -->|found| WA["wake_affine(): pick<br/>waking CPU vs prev_cpu"]
  LOOP -->|sd_flag set, no affine| SLOW["slow path:<br/>sched_balance_find_dst_cpu()"]
  WA --> SIS["select_idle_sibling():<br/>scan target's LLC for idle CPU"]
  SLOW --> RET["return new_cpu"]
  SIS --> RET
  FEEC --> RET

The control flow of select_task_rq_fair() in Linux 6.12. What it shows: the entry conditions (current-CPU override, then Energy-Aware Scheduling if the root domain is not over-utilized), the want_affine gate driven by wake_wide(), the domain walk that finds the largest SD_WAKE_AFFINE domain containing both CPUs, wake_affine()’s waking-vs-previous choice, and the final select_idle_sibling() scan. The insight to take: the common case (WF_TTWU with affinity) takes the fast path ending in select_idle_sibling(); the slow path (sched_balance_find_dst_cpu()) is normally reached only for fork/exec wakeups, because ordinary domains do not set SD_BALANCE_WAKE.

Mechanical Walk-through

Wake flags: what kind of wakeup is this?

select_task_rq_fair() takes wake_flags, a bitmask defined in kernel/sched/sched.h. The first three flags deliberately share bit values with scheduling-domain balance flags so the code can mask wake_flags & 0xF and get a matching SD_* flag (static_assert(WF_TTWU == SD_BALANCE_WAKE) enforces this):

  • WF_EXEC (0x02) — a wakeup after exec(); maps to SD_BALANCE_EXEC. The task has just replaced its address space, so its old cache footprint is worthless — a good moment to rebalance freely.
  • WF_FORK (0x04) — a freshly fork()ed task being placed for the first time; maps to SD_BALANCE_FORK. It has no prior CPU history at all.
  • WF_TTWU (0x08) — an ordinary wakeup of an existing, previously-running task; maps to SD_BALANCE_WAKE. This is the overwhelmingly common case.
  • WF_SYNC (0x10) — “the waker is about to go to sleep.” This is the sync wakeup hint (see below).
  • WF_MIGRATED (0x20) — internal: the task was already migrated.
  • WF_CURRENT_CPU (0x40) — prefer placing the wakee on the current CPU.
  • WF_RQ_SELECTED (0x80) — bookkeeping that select_task_rq() was called.

The caller is try_to_wake_up() (see Wakeups and try_to_wake_up), which sets WF_TTWU and adds WF_SYNC when the waker indicates it will block immediately after.

Step 0 — the early exits

The function opens with a cheap special case: if WF_CURRENT_CPU is set and the current CPU is in the task’s allowed mask (p->cpus_ptr), return the current CPU outright. Next, if Energy-Aware Scheduling (EAS) is active — i.e. the root domain is not over-utilized (!is_rd_overutilized(this_rq()->rd)) — it defers to find_energy_efficient_cpu(), which on heterogeneous (Arm big.LITTLE) systems picks the CPU that fits the task at the lowest energy cost. EAS and the capacity machinery are covered in Capacity-Aware and Energy-Aware Scheduling; this note follows the non-EAS path, which is what runs on a symmetric server.

Step 1 — wake_wide(): should affinity even apply?

static int wake_wide(struct task_struct *p)
{
	unsigned int master = current->wakee_flips;
	unsigned int slave  = p->wakee_flips;
	int factor = __this_cpu_read(sd_llc_size);
 
	if (master < slave)
		swap(master, slave);
	if (slave < factor || master < slave * factor)
		return 0;
	return 1;
}

Each task carries a wakee_flips counter (maintained by record_wakee()): every time a task wakes a different task than the one it last woke, the counter increments; it decays by half roughly once per second so stale relationships fade. factor is sd_llc_size, the number of CPUs sharing the last-level cache (a socket-sized number). wake_wide() returns true — meaning spread, don’t be affine — only when both partners flip frequently: the busier partner must flip at least factor times and be at least factor× more flippy than the quieter one. That detects a genuine one-to-many fan-out (a dispatcher with more workers than the LLC can hold). For a monogamous pair (a client and its one server thread), wakee_flips stays near zero and wake_wide() returns false, so affinity stays on. In select_task_rq_fair(), want_affine = !wake_wide(p) && cpumask_test_cpu(cpu, p->cpus_ptr) — affinity is wanted unless the relationship is wide or the current CPU is not even allowed for the task.

Step 2 — the domain walk

With want_affine decided, the code walks the scheduling-domain hierarchy of the current CPU from the bottom up (for_each_domain(cpu, tmp)). It is looking for the largest domain that (a) has the SD_WAKE_AFFINE flag and (b) spans prev_cpu — i.e. both the waking CPU and the task’s previous CPU live in the same affine domain, so an affine move between them is sensible:

if (want_affine && (tmp->flags & SD_WAKE_AFFINE) &&
    cpumask_test_cpu(prev_cpu, sched_domain_span(tmp))) {
	if (cpu != prev_cpu)
		new_cpu = wake_affine(tmp, p, cpu, prev_cpu, sync);
	sd = NULL;	/* Prefer wake_affine over balance flags */
	break;
}

Once such a domain is found, wake_affine() runs and the loop breaks with sd = NULL, which sends control to the fast path. If instead a domain has the relevant sd_flag set (the WF_FORK/WF_EXEC → SD_BALANCE_FORK/SD_BALANCE_EXEC case), sd is recorded and the slow path is taken. The comment in the source is explicit: ordinary domains do not set SD_BALANCE_WAKE, “so wakeup will usually go to the fast path.” The slow path is for placing tasks with no useful cache history.

Step 3 — wake_affine(): waking CPU or previous CPU?

wake_affine() chooses between this_cpu (the waking CPU) and prev_cpu. It tries two sub-heuristics in order, gated by scheduler feature flags WA_IDLE and WA_WEIGHT:

wake_affine_idle() — the “is anyone idle right now?” check. If the waking CPU is idle and shares a cache with prev_cpu, prefer prev_cpu if it is also idle (avoid a needless migration), else take the waking CPU. The source comment warns this guard against interrupt-context wakeups: “an interrupt intensive workload could force all tasks onto one node.” There is also a direct sync shortcut:

if (sync && cpu_rq(this_cpu)->nr_running == 1)
	return this_cpu;

If this is a sync wakeup (WF_SYNC) and the waking CPU has exactly one runnable task — namely the soon-to-sleep waker — then the waker is about to vacate the CPU, so stacking the wakee here is ideal: it inherits a warm cache with no contention.

wake_affine_weight() — the overloaded-system fallback, comparing effective load. It computes this_eff_load and prev_eff_load, each being a CPU’s cpu_load() adjusted by the task’s hierarchical load (task_h_load(p)) and cross-multiplied by the other CPU’s capacity (capacity_of), so the comparison is fair across CPUs of different capacity. A WA_BIAS feature multiplies both sides by 100 and tilts the previous side by half the domain’s imbalance_pct, biasing slightly toward keeping the task where it was. For a sync wakeup it subtracts the waker’s own load from this_eff_load (the waker is leaving) and adds 1 to prev_eff_load so a tie favours stacking on the waker. It returns the waking CPU when this_eff_load < prev_eff_load, else signals “no, keep prev.”

Crucially, wake_affine() returns either this_cpu or prev_cpu — it does not invent a third CPU. Its job is only to pick the affine anchor; the actual idle-CPU search is the next step.

Step 4 — select_idle_sibling(): find an idle CPU near the target

The chosen target feeds select_idle_sibling(p, prev_cpu, target), which scans the LLC domain for an idle CPU, in a deliberate preference order:

  1. If target itself is idle (or a SCHED_IDLE runqueue) and fits the task’s capacity (asym_fits_cpu), take it immediately.
  2. Else if prev_cpu is cache-affine to target and idle, take prev_cpu — “don’t be stupid,” as the comment puts it.
  3. A per-CPU kthread stacking case for IO completions: if the current thread is a per-CPU kworker and the wakee’s previous CPU is the current one with nr_running <= 1, treat it like a sync wakeup and return prev.
  4. A recently-used-CPU candidate (p->recent_used_cpu).
  5. Failing all of those, select_idle_cpu() does a bounded scan of the LLC (optionally finding a fully idle core, tracked by has_idle_core, on SMT systems) and select_idle_smt() looks at hyperthread siblings.

The bound on the scan matters: scanning every CPU in a large LLC on every wakeup would be a latency disaster, so the search is capped (historically by sched/features and the average idle time). This is the cache-affinity-vs-latency trade-off made concrete.

The slow path — sched_balance_find_dst_cpu()

When sd is non-NULL (fork/exec, or a domain explicitly set to balance on wake), the code calls sched_balance_find_dst_cpu(sd, p, cpu, prev_cpu, sd_flag). This walks down the domain sd looking for the idlest group via sched_balance_find_dst_group() (which classifies each group with update_sg_wakeup_stats() and group_classify() exactly as the periodic balancer does — see Scheduler Load Balancing for the group_type taxonomy), then sched_balance_find_dst_group_cpu() finds the least-loaded / shallowest-idle CPU in that group. It recurses into child domains until it bottoms out. This is more expensive than the fast path — it touches every group’s statistics — which is exactly why ordinary wakeups avoid it.

Configuration, Observability, and Tuning

Wakeup-placement behaviour is governed by scheduler feature flags exposed (with CONFIG_SCHED_DEBUG) under /sys/kernel/debug/sched/features:

# read current features
cat /sys/kernel/debug/sched/features
# typical: ... WA_IDLE WA_WEIGHT WA_BIAS SIS_UTIL ...
 
# disable the idle sub-heuristic of wake_affine (force the weight path)
echo NO_WA_IDLE > /sys/kernel/debug/sched/features
  • WA_IDLE / WA_WEIGHT / WA_BIAS gate the two wake_affine sub-heuristics and the bias described above.
  • SIS_UTIL controls how select_idle_sibling’s scan is bounded by utilization.

sd_llc_size (the wake_wide() factor) is derived from topology, not directly tunable; you change it by changing which CPUs share an LLC (cpusets, isolcpus, or hardware). The domain flags that drive the walk (SD_WAKE_AFFINE, SD_BALANCE_WAKE, SD_BALANCE_FORK, SD_BALANCE_EXEC) come from the topology setup described in Scheduling Domains and CPU Topology and can be inspected per-domain under /sys/kernel/debug/sched/domains/ or printed by booting with sched_verbose (CONFIG_SCHED_DEBUG).

To observe wakeup placement, the scheduler tracepoints are the primary tool:

# count how often a wakeup migrated the task to a different CPU
perf record -e sched:sched_wakeup -e sched:sched_migrate_task -a -- sleep 5
perf script | grep sched_migrate_task | wc -l

schedstat (CONFIG_SCHEDSTATS, /proc/schedstat and per-task /proc/<pid>/sched) records nr_wakeups_affine and nr_wakeups_affine_attempts, incremented inside wake_affine() — the ratio tells you how often affinity won.

Failure Modes and Common Misunderstandings

“The scheduler keeps bouncing my thread between CPUs.” Wakeup placement is the usual suspect, not the periodic balancer. If a request/response pair ping-pongs across two CPUs in different LLCs, every wakeup pays a cold-cache penalty. The sync-wakeup path and select_idle_sibling’s prev_cpu preference exist to prevent this, but a poorly-behaved wakeup (waker not actually sleeping, so the WF_SYNC hint is absent or wrong) can defeat them. Diagnose with sched:sched_migrate_task tracepoint frequency.

“My fan-out server piles all workers on one socket.” That is wake_wide() not triggering — the dispatcher’s wakee_flips has not crossed sd_llc_size, perhaps because the wakeups are too infrequent (the per-second decay halves the counter). The opposite failure — wake_wide() triggering on a genuinely affine pair and spreading them needlessly — is rarer but possible after a burst.

Confusing wakeup balancing with periodic balancing. They are different mechanisms at different times. select_task_rq_fair() runs once, synchronously, at the moment of wakeup, and is cheap by design (it looks at two CPUs plus an LLC scan). The periodic Scheduler Load Balancing runs from the timer tick / softirq and considers the whole domain hierarchy. A task placed “wrong” at wakeup is later corrected by the periodic balancer; conversely, aggressive periodic balancing can undo good wakeup placement.

The “current CPU is always best” fallacy. WF_CURRENT_CPU is a hint used by specific callers (e.g. some IO paths); it is not the default. The default for WF_TTWU is the wake_wide → wake_affine → select_idle_sibling pipeline, which frequently picks prev_cpu over the waking CPU to preserve the wakee’s own cache.

Alternatives and Relationship to Other Mechanisms

Wakeup balancing is one of three placement-time decisions, all in select_task_rq dispatch:

The fair-class wakeup logic above is the only one that optimizes for cache locality, because fair tasks are the only ones where throughput (not deadline) is the goal. When the system is heterogeneous and not over-utilized, EAS replaces this whole pipeline with find_energy_efficient_cpu() (Capacity-Aware and Energy-Aware Scheduling).

Production Notes

Wakeup placement is one of the most production-sensitive parts of the scheduler because it runs on the hot path of every wakeup — millions per second on a busy server. The historical tension is well documented: the wake_affine heuristic has been rewritten repeatedly (the WA_WEIGHT/WA_IDLE split, the introduction of wake_wide() in 2013 to handle fan-out, and the select_idle_sibling scan-bounding work) precisely because getting it wrong shows up as either cache thrashing (too much spreading) or idle CPUs while one core queues work (too much affinity). Latency-sensitive services often pin threads with CPU Affinity and sched_setaffinity specifically to take this decision out of the scheduler’s hands — if a thread can only run on one CPU, select_task_rq_fair() has nothing to decide. Databases and event-loop servers that already shard work per-core do this routinely. For the opposite workload — throughput batch jobs — leaving wakeup balancing on and letting the periodic balancer spread load is the right default.

See Also

Graph View

Backlinks