Placement, Balancing, and Power

The last chapter answered which task runs on a given CPU. This one answers which CPU — and then the question that turns out to be the same question: at what frequency.

Three concepts in the six-part treatment: wakeup placement, load balancing and topology, and utilization, frequency, and sched_ext.

Concept 1: Wakeup Placement

1. What problem it solves

When a task becomes runnable, it must be put on some CPU's runqueue. That single decision has more effect on real-world performance than anything else in this chapter, because it happens millions of times a second and it is made with almost no information.

The tension is exact and unresolvable:

   RUN IT WHERE ITS DATA IS          RUN IT WHERE THERE IS A FREE CPU
   (cache locality: the waker's       (latency: an idle CPU can start it
    L2/LLC probably has the data)      immediately, a busy one cannot)

   Getting this wrong in one direction: cache misses on every access.
   Getting it wrong in the other: the task sits runnable while a CPU idles.

2. Where it exists in the kernel

rg -n "select_task_rq_fair" -A 60 kernel/sched/fair.c | head -70
rg -n "wake_affine|select_idle_sibling|select_idle_cpu|select_idle_core" kernel/sched/fair.c | head
rg -n "select_task_rq\b" kernel/sched/core.c | head

3. Who owns or interacts with it

4. The decision, in order

   try_to_wake_up(p)
     └── select_task_rq(p, prev_cpu, wake_flags)
           └── select_task_rq_fair()
                 │
                 ├── 1. Is the task pinned to one CPU?  → done, no choice
                 │
                 ├── 2. wake_affine(): should p run near the WAKER instead of
                 │      near where it ran last?
                 │        - producer/consumer pairs benefit enormously
                 │        - WF_SYNC ("I am about to sleep") makes this likelier
                 │        - compares load on both CPUs, and cache distance
                 │
                 ├── 3. select_idle_sibling(): within the chosen CPU's LLC
                 │      domain, is there an IDLE CPU?
                 │        - prefer a fully idle CORE over an idle SMT thread
                 │          (an SMT sibling shares execution resources)
                 │        - the scan is COST-LIMITED: on a 128-CPU machine it
                 │          does not look at all 128. It samples.
                 │
                 └── 4. Otherwise: find_idlest_cpu() walks the domain
                        hierarchy for the least loaded group

Two things about step 3 are worth internalizing, because they explain a lot of otherwise-mysterious behavior:

The idle search is deliberately incomplete. Scanning every CPU in a large LLC costs more than the placement is worth, so the scan is bounded and gives up. On big machines you will observe a task placed on a busy CPU while an idle one existed. That is not a bug; it is the cost limit.

An idle SMT sibling is not an idle CPU. Two hyperthreads on one core share execution units. The search prefers a fully idle core, and this is why performance on SMT machines is sometimes better with SMT disabled.

lscpu | grep -E 'Thread|Core|Socket|NUMA|L3'
cat /sys/devices/system/cpu/cpu0/topology/thread_siblings_list
cat /sys/devices/system/cpu/cpu0/cache/index3/shared_cpu_list   # the LLC domain

5. Experiment

CLAIM. Wakeup placement prefers cache locality, and you can see the preference change with the WF_SYNC hint and with load.

METHOD.

# Watch every placement decision on a busy system:
sudo bpftrace -e '
  tracepoint:sched:sched_wakeup {
    @placed[args.target_cpu] = count();
  }
  tracepoint:sched:sched_migrate_task {
    @migrations[args.orig_cpu, args.dest_cpu] = count();
  }' &

# A ping-pong pair: two processes waking each other through a pipe.
# This is the shape wake_affine exists for.
python3 - <<'EOF' &
import os
r1,w1 = os.pipe(); r2,w2 = os.pipe()
if os.fork()==0:
    for _ in range(200000): os.read(r1,1); os.write(w2,b'x')
    os._exit(0)
for _ in range(200000): os.write(w1,b'x'); os.read(r2,1)
EOF
sleep 10; kill %1 %2 2>/dev/null

PREDICT FIRST: will the two processes end up on the same CPU, on two CPUs sharing an L3, or spread across sockets? Then run it again with the machine loaded (stress-ng --cpu $(nproc)) and predict again.

Also measure the cost directly:

# Same CPU vs. different CPU, for a producer/consumer pair:
taskset -c 0     perf stat -e cache-misses,context-switches -- <your pingpong>
taskset -c 0,1   perf stat -e cache-misses,context-switches -- <your pingpong>

6. Failure mode

Concept 2: Load Balancing and Topology

1. What problem it solves

Per-CPU runqueues make the fast paths fast and make imbalance possible: one CPU with five runnable tasks while another idles. Something must periodically look across CPUs and move work — while knowing that moving a task across a NUMA boundary can cost more than the imbalance it fixes.

That knowledge is the scheduling domain hierarchy: a description of what each level of the machine shares.

2. Where it exists in the kernel

rg -n "struct sched_domain \{" -A 40 include/linux/sched/topology.h
rg -n "load_balance\b|find_busiest_group|calculate_imbalance" kernel/sched/fair.c | head
rg -n "newidle_balance|nohz_idle_balance|run_rebalance_domains" kernel/sched/fair.c | head
ls /sys/kernel/debug/sched/domains/cpu0/ 2>/dev/null
$EDITOR Documentation/scheduler/sched-domains.rst

3. The hierarchy

   NUMA        ← whole machine; migration here means remote memory. Expensive.
     │           balance interval: hundreds of ms
   PKG / DIE   ← a socket
     │
   MC          ← cores sharing a last-level cache. The important level:
     │           migration within it is cheap, so the balancer is aggressive.
   SMT         ← hyperthreads on one core. Sharing execution units.
     │           balance interval: a few ms
   CPU

   Each level has: a span (which CPUs), FLAGS (what they share), a balance
   interval, and an imbalance threshold. The balancer walks from the bottom
   up, doing the cheap levels often and the expensive ones rarely.

# The real hierarchy on your machine:
for d in /sys/kernel/debug/sched/domains/cpu0/*/; do
  echo "== $(basename "$d") name=$(cat "$d/name" 2>/dev/null)"
  echo "   cpus=$(cat "$d/cpumask" 2>/dev/null) flags=$(cat "$d/flags" 2>/dev/null)"
done
rg -n "SD_SHARE|SD_NUMA|SD_ASYM" include/linux/sched/sd_flags.h | head -20

Note: The SD_* flag names have changed during the 6.x series (the flag for "shares a last-level cache" was renamed, among others). Grep include/linux/sched/sd_flags.h on your tree rather than trusting any name written down elsewhere — including here.

4. The three kinds of balancing

   load_balance(this_cpu, domain)
     ├── find_busiest_group()     which group in this domain is overloaded?
     │      classifies each group: has_spare / fully_busy / overloaded /
     │      misfit_task / imbalanced
     ├── calculate_imbalance()    how much load should move?
     ├── find_busiest_queue()     which CPU in that group?
     ├── detach_tasks()           pick tasks, respecting:
     │      - affinity (cpus_ptr)
     │      - cache hotness (task_hot(): ran recently => leave it)
     │      - migration cost vs. the imbalance being fixed
     └── attach_tasks()           enqueue them here

task_hot() is where the tension from Concept 1 reappears: a task that ran very recently is probably still in cache, and moving it costs more than the imbalance. The threshold is sysctl_sched_migration_cost.

cat /proc/sys/kernel/sched_migration_cost_ns 2>/dev/null
grep -E 'CONFIG_SCHEDSTATS|CONFIG_SCHED_DEBUG' ~/kernel/build/.config
head -3 /proc/schedstat        # per-CPU, per-domain balancing statistics

5. Experiment

CLAIM. Balancing is real, measurable, and asymmetric across the topology levels.

METHOD.

# Start N busy loops on one CPU and watch them spread.
for i in $(seq "$(nproc)"); do taskset -c 0 sh -c 'while :; do :; done' & done
sleep 1;  ps -o pid,psr,comm | grep -c ' 0 '     # how many still on CPU 0?
sleep 5;  ps -o pid,psr,comm | grep -c ' 0 '
sleep 30; ps -o pid,psr,comm | grep -c ' 0 '
jobs -p | xargs kill

# And the migrations themselves, by topology distance:
sudo bpftrace -e 'tracepoint:sched:sched_migrate_task {
    @[args.orig_cpu, args.dest_cpu] = count(); }'

PREDICT FIRST: after 1 second, how many of the N tasks are still on CPU 0? After 5? Most people expect instant spreading; measure how long it actually takes and then explain the number in terms of balance intervals.

6. Failure mode

Concept 3: Utilization, Frequency, and sched_ext

1. What problem it solves

"Which CPU" and "how fast should that CPU run" used to be answered by two subsystems that did not talk to each other: the scheduler placed tasks, and a cpufreq governor sampled load afterwards and guessed. The governor was always reacting to information the scheduler already had.

Modern Linux closes the loop: the scheduler computes a utilization signal and hands it directly to frequency selection.

2. Where it exists in the kernel

ls kernel/sched/pelt.c kernel/sched/cpufreq_schedutil.c
rg -n "struct sched_avg \{" -A 12 include/linux/sched.h
rg -n "cpufreq_update_util" kernel/sched/ | head
ls drivers/cpufreq/ drivers/cpuidle/
cat /sys/devices/system/cpu/cpu0/cpufreq/scaling_governor 2>/dev/null
$EDITOR Documentation/scheduler/sched-energy.rst

3. PELT — the signal everything consumes

Per-Entity Load Tracking maintains, for every entity and every runqueue, a geometrically decaying average of recent behavior:

The decay has a half-life of roughly 32 ms. That number explains a lot of observed behavior: a task that has been idle for 100 ms looks nearly idle to PELT, so a periodic task that wakes, works briefly, and sleeps gets a low util_avg — and would therefore get a low frequency, which is exactly why util_est was added.

sudo cat /proc/sched_debug 2>/dev/null | grep -E 'util_avg|load_avg' | head

4. From utilization to frequency and idle states

   scheduler event (enqueue, dequeue, tick)
         │
         ├── update PELT for the entity and the runqueue
         │
         └── cpufreq_update_util(rq, flags)
                 │
                 └── SCHEDUTIL governor
                       target_freq = 1.25 * max_util * max_freq / capacity
                       (clamped by uclamp; the 1.25 is headroom so the
                        frequency is not always exactly at the edge)
                       │
                       └── the cpufreq DRIVER sets it
                           (intel_pstate, amd-pstate, cppc, or platform-specific)

   And in the other direction, when nothing is runnable:
   cpuidle governor (menu / teo) predicts how long the CPU will be idle and
   picks a C-state: deeper = less power, longer to wake up. Guess too deep
   and you have added wakeup latency to the next task.

uclamp lets a task or cgroup constrain the utilization signal it contributes, which is how you say "this task should run at a high frequency even though it looks small" or the reverse:

rg -n "sched_util_min|sched_util_max" include/uapi/linux/sched/types.h
cat /sys/fs/cgroup/<path>/cpu.uclamp.min 2>/dev/null

On asymmetric machines (big.LITTLE), Energy Aware Scheduling uses the same utilization signal plus an energy model to choose the CPU that completes the work for the least energy, rather than the fastest CPU:

grep -E 'CONFIG_ENERGY_MODEL|CONFIG_SCHED_(MC|SMT)' ~/kernel/build/.config
ls /sys/kernel/debug/sched/ | grep -i energy

5. sched_ext — the scheduler as a BPF program

Since 6.12, a BPF program can be the fair-class scheduler. This is the single biggest change to how one can experiment here.

grep -E 'CONFIG_SCHED_CLASS_EXT' ~/kernel/build/.config
rg -n "struct sched_ext_ops \{" -A 60 include/linux/sched/ext.h 2>/dev/null | head -40
ls tools/sched_ext/ 2>/dev/null
$EDITOR Documentation/scheduler/sched-ext.rst

That last pair of rows is why this matters for a newcomer: experimenting with scheduling policy no longer requires being able to safely modify fair.c. Writing a sched_ext scheduler, measuring it honestly, and reporting the result is a genuinely valuable contribution that does not require maintainer trust you have not yet earned.

6. Experiment

CLAIM. Utilization drives frequency, and you can watch the loop close.

METHOD. On real hardware (this does not work in a VM):

cat /sys/devices/system/cpu/cpu0/cpufreq/scaling_governor
watch -n0.5 'grep MHz /proc/cpuinfo | head -4'

# In another terminal: a 50%-duty-cycle task.
taskset -c 0 sh -c 'while :; do end=$((SECONDS+1)); while [ $SECONDS -lt $end ]; do :; done; sleep 1; done' &

sudo bpftrace -e 'kprobe:cpufreq_update_util { @ = count(); }'
sudo cat /sys/kernel/debug/sched/debug 2>/dev/null | grep -m5 util_avg

PREDICT FIRST: for a task with a 50% duty cycle, does the CPU sit at ~50% of maximum frequency, at maximum, or oscillate? Then explain your answer in terms of PELT's 32 ms half-life and util_est.

7. Failure mode

Validation / Self-check

1. State the wakeup-placement tension in one sentence. Which two functions embody the two sides?
2. Why is the idle-CPU search deliberately incomplete, and what behavior does that explain on large machines?
3. Why is an idle SMT sibling not equivalent to an idle CPU?
4. Draw the scheduling-domain hierarchy for your machine, with the command that produced it.
5. Name the three kinds of load balancing and say why each exists.
6. What is task_hot() protecting, and which tunable controls it?
7. Why does balancing not happen instantly? Give the mechanism, not just "intervals".
8. Name PELT's three signals and one consumer of each.
9. What is PELT's approximate half-life, and what problem does util_est solve that follows from it?
10. Trace the path from a task waking up to the CPU changing frequency, naming each function.
11. What does uclamp clamp, and give one use case in each direction.
12. What is sched_ext, what are its two safety mechanisms, and why does it lower the barrier to contributing here?
13. You measure a 4% improvement from a scheduler change. Name four things that must be true before that number means anything.

Next: Lab 10 — Trace a Wakeup — follow one wakeup from a write() to a task running on a CPU you can name.