4 — The scheduler picks the next task

When the current task stops running, how does the kernel choose the next one, and can you predict the choice from what it exposes?

Requirements: the machine from chapter 0, under KVM, since timing matters here. Do this chapter last among 1 to 6, because it has the most ways to mislead you.

Version matters. 6.12 is where EEVDF was completed and sched_ext landed (LWN), so many older explanations are out of date.

Vocabulary

Every runnable task carries a few numbers:

vruntime: a weighted clock. It advances by real run time, scaled by weight. A nice 19 task’s clock runs about 68× faster than a nice 0 task’s (1024/15), so it gets far less CPU (core.c).
lag: how much CPU a task is owed. A task with non-negative lag is eligible.
slice: how much it asks for at a time. The base slice is 750,000 ns, scaled by CPU count at boot (fair.c).
deadline: when its slice should finish, in virtual time:

$\text{deadline} = \text{vruntime} + \frac{\text{slice}}{\text{weight}}$

The source is se->deadline = se->vruntime + calc_delta_fair(se->slice, se) (fair.c).

The rule: among eligible tasks, run the one with the earliest deadline.

The path

Step 1: something asks for a reschedule. A task blocks and calls schedule() directly, or TIF_NEED_RESCHED is set. That flag comes from the tick (sched_tick, which reaches task_tick_fair, update_curr and resched_curr) or a wakeup, and it’s honoured on return to user mode or from an interrupt. Note that sched_tick was called scheduler_tick before 6.10.

Step 2: __schedule (kernel/sched/core.c). It disables interrupts and takes the runqueue lock. If the task is blocking, block_task calls dequeue_task, which may delay the dequeue. That’s a 6.12 detail covered below.

Step 3: charge the running task. update_curr adds run time to sum_exec_runtime and advances vruntime.

Step 4: pick. pick_next_task reaches pick_next_entity and pick_eevdf (kernel/sched/fair.c). The runqueue is an augmented rbtree sorted by deadline, with min_vruntime kept per subtree, so finding the earliest eligible deadline is O(log n) (fair.c).

There are shortcuts. Under RUN_TO_PARITY, the current task can keep running until its slice ends even if another task looks better (fair.c).

Step 5: place tasks on wakeup. place_entity sets a woken task’s vruntime, using its stored lag, clamped to 2*slice or TICK_NSEC.

Step 6: switch. context_switch calls prepare_task_switch, then switch_mm_irqs_off loads a new CR3 if the address space differs, and threads of one process skip that. switch_to saves and restores registers and the stack pointer. The sched:sched_switch tracepoint fires just before.

What’s new in 6.12

Delayed dequeue (DELAY_DEQUEUE). A sleeping task with negative lag stays queued until its lag decays, so it can’t shed debt by sleeping briefly (commit).
Custom slices. sched_setattr can request a slice from 100 µs to 100 ms (syscalls.c).
PREEMPT_SHORT. A waking task with a shorter slice can preempt more readily (features.h).
sched_ext. Policy 7 lets a BPF program be the scheduler. It sits between the fair and idle classes, and the kernel reverts to the fair class on error (sched-ext.rst).

Lazy preemption is not in 6.12.

Hands-on: read the scheduler’s state

Add isolcpus=1 to QEMU’s -append, and boot with -smp 2. That reduces outside noise, but doesn’t eliminate it.

Check the settings and start two busy tasks from one shell, so they share a cgroup. vruntimes only compare within one runqueue:

cat /sys/kernel/debug/sched/base_slice_ns
cat /sys/kernel/debug/sched/features | tr ' ' '\n' | grep -E 'RUN_TO_PARITY|DELAY|PREEMPT_SHORT'
taskset -c 1 sh -c 'while :; do :; done' & A=$!
taskset -c 1 sh -c 'while :; do :; done' & B=$!

Read their state:
```
grep -E "^ *(>R|R|S) +sh +($A|$B)" /sys/kernel/debug/sched/debug
```
Columns are vruntime, E or N for eligible, deadline, S flag, slice, sum-exec, switches and priority (debug.c). /proc/$A/sched has se.vruntime but no per-task slice.

Predict CPU share, then measure it. Renice one task:

renice -n 10 -p $B
a0=$(awk '/se.sum_exec_runtime/{print $3}' /proc/$A/sched); b0=$(awk '/se.sum_exec_runtime/{print $3}' /proc/$B/sched)
sleep 30
a1=$(awk '/se.sum_exec_runtime/{print $3}' /proc/$A/sched); b1=$(awk '/se.sum_exec_runtime/{print $3}' /proc/$B/sched)
echo "A=$(echo "$a1-$a0"|bc) B=$(echo "$b1-$b0"|bc)"

Expected: a ratio near 1024:110. If it’s far off, look for a third task on CPU 1 or separate autogroups.

Hands-on: predict the next pick

Read both tasks’ state from sched/debug, as above.
Apply the rule: among E tasks, take the earliest deadline, unless the current task still holds its slice under RUN_TO_PARITY.

Write down your prediction, then catch the switch:

bpftrace -e 'tracepoint:sched:sched_switch /cpu == 1/ {
  printf("%llu %s/%d -> %s/%d\n", nsecs, args.prev_comm, args.prev_pid, args.next_comm, args.next_pid); }'

Repeat ten times and keep score. Explain every miss. Likely causes are RUN_TO_PARITY, a stale reading of the current task, another task on the CPU, and the fact that your reads aren’t atomic.

Turn the shortcut off, compare, and restore it:

echo NO_RUN_TO_PARITY > /sys/kernel/debug/sched/features
echo RUN_TO_PARITY > /sys/kernel/debug/sched/features

Hands-on: change it

Custom slice. Write a small program calling syscall(SYS_sched_setattr, 0, &attr, 0) with SCHED_OTHER and sched_runtime in nanoseconds. Check that the S flag and new slice appear in sched/debug. Two CPU hogs are limited by tick length, so a clearer demonstration is a sleeper that wakes often. Compare its wakeup latency with a default-slice sleeper under the same load.

sched_ext. Build the example scheduler. It needs clang 16 or later and pahole 1.25 or later (README):

make -j"$(nproc)" -C tools/sched_ext
cat /sys/kernel/sched_ext/state
tools/sched_ext/build/bin/scx_simple &
cat /sys/kernel/sched_ext/state; cat /sys/kernel/sched_ext/root/ops
kill %1; cat /sys/kernel/sched_ext/state

Expected: state should change to enabled, then return to disabled when the scheduler exits.

If it fails

/sys/kernel/debug/sched is empty: debugfs isn’t mounted, or SCHED_DEBUG is off.
Ratios are far off: autogroups may be splitting the tasks. Start both from one shell.
sched_setattr returns EINVAL: check the size field.

The takeaway

Fairness is an accounting identity, not a feeling. Every task carries a weighted clock; the scheduler’s whole job is to keep those clocks as equal as it can, and every policy knob (nice, slice, cgroup CPU weight) is a change to the exchange rate. Once you can read the clocks, you can predict much of what the scheduler does. A system whose decisions you can predict from state it exposes is a system you can operate.