Scheduling Classes and the Pick Path

Three concepts in the six-part treatment: the scheduling class, the runqueue, and the pick path — __schedule() itself.

By the end you should be able to answer, for any task on any machine: why is this the thing running right now?

Concept 1: The Scheduling Class

1. What problem it solves

Linux must serve workloads with incompatible requirements on the same machine. A video-conference process wants a bounded response time. A kernel build wants throughput. A watchdog must run now, whatever else is happening. A hard-real-time control loop needs a guarantee, not a preference.

No single algorithm serves all four. Rather than one scheduler with modes, Linux has several schedulers arranged in a strict priority chain, each implementing the same interface. The core knows nothing about fairness or deadlines; it asks each class, in order, "do you have anything to run?"

2. Where it exists in the kernel

kernel/sched/, one .c file per class, with the interface in sched.h.

rg -n "struct sched_class \{" -A 45 kernel/sched/sched.h
rg -n "DEFINE_SCHED_CLASS" kernel/sched/*.c
rg -n "for_each_class" kernel/sched/sched.h kernel/sched/core.c | head

The chain order is established by linker section placement — each DEFINE_SCHED_CLASS puts the struct in a named section, and the linker script orders them. That is why you cannot find a next pointer being assigned anywhere.

rg -n "sched_class" include/asm-generic/vmlinux.lds.h | head

3. Who owns or interacts with it

4. The classes, and what each guarantees

chrt -m                              # the priority ranges on your system
chrt -p $$                           # your shell's policy and priority
ps -eo pid,cls,rtprio,ni,comm --sort=-rtprio | head -15
cat /proc/sys/kernel/sched_rt_runtime_us /proc/sys/kernel/sched_rt_period_us

Note: sched_rt_runtime_us (default 950000 of a 1000000 µs period) is a throttle: RT tasks may consume at most 95% of a CPU, leaving 5% for the fair class. It exists because a runaway SCHED_FIFO busy loop would otherwise make the machine unrecoverable. When someone says "my RT task gets preempted", this is usually why.

5. Experiment

CLAIM. The class chain is strict: a runnable RT task always preempts a fair task, regardless of nice, and you can watch the throttle rescue the machine.

METHOD. In the guest, with -smp 1 so there is nowhere to hide:

# A fair-class busy loop at maximum niceness advantage.
nice -n -20 sh -c 'while :; do :; done' & FAIR=$!

# An RT busy loop at low RT priority.
sudo chrt -f 1 sh -c 'while :; do :; done' & RT=$!

sleep 5
ps -o pid,cls,rtprio,ni,pcpu,comm -p $FAIR,$RT
kill $FAIR $RT

PREDICT FIRST: what %CPU does each get? Write two numbers.

Then remove the safety net and see what it was for:

# DO THIS IN THE GUEST ONLY.
sudo sh -c 'echo -1 > /proc/sys/kernel/sched_rt_runtime_us'   # disable the throttle
sudo chrt -f 1 sh -c 'while :; do :; done' &
# ...try to type. Then recover:  Ctrl-A C  in QEMU, then `quit`.

PREDICT FIRST: with the throttle disabled, does your shell still respond? Does anything?

6. Failure mode

Concept 2: The Runqueue

1. What problem it solves

Scheduling decisions must be fast and must scale to hundreds of CPUs. A single global list of runnable tasks would be a cache-line battleground: every wakeup, every tick, every switch on every CPU contending for one lock.

So there is one runqueue per CPU, each with its own lock, and the price is that balance between them becomes a separate problem — which is the next chapter.

2. Where it exists in the kernel

rg -n "struct rq \{" -A 50 kernel/sched/sched.h
rg -n "DECLARE_PER_CPU_SHARED_ALIGNED\(struct rq, runqueues\)" kernel/sched/sched.h
rg -n "struct cfs_rq \{" -A 30 kernel/sched/sched.h

Per-CPU, cache-line aligned, and each embeds one sub-runqueue per class.

3. Who owns or interacts with it

   struct rq  (per CPU)
     ├── lock              ← a raw spinlock; scheduler code is atomic by nature
     ├── nr_running        ← total runnable tasks, all classes
     ├── curr, idle, stop  ← the current task, the idle task, the stopper
     ├── clock             ← updated on entry; do NOT read a stale one
     ├── clock_task        ← clock minus IRQ/steal time
     ├── cfs   ──▶ struct cfs_rq
     │              ├── tasks_timeline   an rbtree of sched_entities
     │              ├── min_vruntime / avg_vruntime
     │              ├── nr_running, load
     │              └── curr             the entity currently on-CPU
     ├── rt    ──▶ struct rt_rq   priority-indexed lists + a bitmap
     ├── dl    ──▶ struct dl_rq   an rbtree ordered by deadline
     └── sd    ──▶ struct sched_domain  this CPU's view of the topology

4. The bookkeeping that matters

Warning: rq->lock is a raw_spinlock_t, which means it stays a true spinning lock even under PREEMPT_RT. Everything under it is atomic in the strongest sense: no sleeping, no allocation, no copy_to_user, and every microsecond spent holding it is latency for that CPU. This is why scheduler code is written the way it is, and why "just add a mutex here" is never the answer.

5. Experiment

CLAIM. Runqueues are per-CPU and observable, and you can watch tasks accumulate on one.

METHOD.

# Per-runqueue state, if your kernel exposes it:
sudo cat /proc/sched_debug | sed -n '/^cpu#/,/^$/p' | head -60
ls /sys/kernel/debug/sched/

# Pin four busy loops to CPU 0 and watch nr_running there:
for i in 1 2 3 4; do taskset -c 0 sh -c 'while :; do :; done' & done
sleep 2
sudo grep -A 8 '^cpu#0' /proc/sched_debug | head -12
ps -o pid,psr,pcpu,comm --sort=psr | grep -c ' 0 '
jobs -p | xargs kill

PREDICT FIRST: with four busy loops pinned to CPU 0 and seven other CPUs idle, what does each get as a percentage? Does the scheduler migrate any of them away? Why or why not?

6. Failure mode

Concept 3: The Pick Path

1. What problem it solves

Something has to actually change which task is on the CPU, save the old one's state, restore the new one's, and switch the address space if they belong to different processes — correctly, from several very different calling contexts, without ever losing a task.

That is __schedule(), and it is the single most important function in kernel/sched/.

2. Where it exists in the kernel

rg -n "static void __sched notrace __schedule" -A 60 kernel/sched/core.c
rg -n "^static.*pick_next_task\(" -A 40 kernel/sched/core.c
rg -n "context_switch" -A 30 kernel/sched/core.c | head -40

3. Who calls it

This is the part people miss: the scheduler does not run periodically. It runs when something calls it, and there are exactly four kinds of caller.

TIF_NEED_RESCHED is the flag connecting everything: a wakeup, a tick, or a priority change sets it, and the next boundary crossing acts on it. Nothing preempts anything directly.

rg -n "set_tsk_need_resched|resched_curr" kernel/sched/core.c | head
rg -n "need_resched\(\)" kernel/ | head

4. The path, in order

   __schedule(sched_mode)
     │
     ├── rq_lock(rq)                     take this CPU's runqueue lock
     ├── update_rq_clock(rq)
     │
     ├── if the task is going to sleep (not just being preempted):
     │      dequeue it from its class
     │      (unless a signal arrived first -- then it stays runnable)
     │
     ├── pick_next_task(rq, prev, rf)
     │      │
     │      ├── OPTIMIZATION: if only fair tasks are runnable, go straight
     │      │   to the fair class and skip the chain walk. This fast path
     │      │   is why the chain's cost does not show up in profiles.
     │      │
     │      └── otherwise: for each class, highest priority first
     │              p = class->pick_next_task(rq)
     │              if (p) return p
     │          ...the idle class always returns something.
     │
     ├── if (prev != next):
     │      rq->curr = next
     │      context_switch(rq, prev, next, rf)
     │        ├── switch_mm()     ← address space, if the process changed
     │        │                     (skipped for threads of one process,
     │        │                      and for kernel threads, which borrow)
     │        ├── switch_to()     ← ARCHITECTURE ASSEMBLY: registers and
     │        │                     the stack pointer. Execution "returns"
     │        │                     inside a DIFFERENT task.
     │        └── finish_task_switch()   ← runs in the NEW task's context,
     │                                     and drops the old rq lock
     └── else: just unlock and carry on

The strangest and most important line is switch_to(). It does not return in the task that called it. It saves prev's stack pointer and registers, loads next's, and execution continues inside next — wherever that task last called switch_to(), possibly seconds ago. A task resumes inside schedule(), in the middle of a function it called long before.

That is why every task needs its own kernel stack (kernel C), and why finish_task_switch() exists: the cleanup for prev has to run in next's context, because prev is no longer on a CPU.

5. Experiment

CLAIM. You can watch the whole pick path for a single wakeup, and name every participant.

METHOD.

T=/sys/kernel/tracing; [ -d "$T" ] || T=/sys/kernel/debug/tracing
sudo sh -c "echo 0 > $T/tracing_on; echo > $T/trace"
sudo sh -c "echo 1 > $T/events/sched/sched_wakeup/enable"
sudo sh -c "echo 1 > $T/events/sched/sched_switch/enable"
sudo sh -c "echo 1 > $T/tracing_on"
sleep 0.05
sudo sh -c "echo 0 > $T/tracing_on"
sudo head -30 $T/trace

For each sched_wakeup line, identify: which CPU the waker was on, which CPU the target was placed on, and how long until the matching sched_switch made it run.

PREDICT FIRST: for a task woken on an idle CPU, how long between sched_wakeup and sched_switch? Microseconds, tens of microseconds, or milliseconds?

Then, in GDB on the guest:

(gdb) break __schedule
(gdb) continue
(gdb) bt                      ← who called it? one of the four kinds above
(gdb) p rq->nr_running
(gdb) p $lx_current().comm

Lab 10 does this properly, end to end.

6. Failure mode

Tip: The canonical sleep pattern is worth memorizing, because getting it wrong produces a hang that is very hard to diagnose:

for (;;) {
        set_current_state(TASK_INTERRUPTIBLE);  /* state BEFORE the test */
        if (condition)                          /* ...so a wakeup between */
                break;                          /*    them is not lost    */
        if (signal_pending(current)) { ret = -ERESTARTSYS; break; }
        schedule();
}
__set_current_state(TASK_RUNNING);

wait_event_interruptible() is this loop as a macro. Use the macro; read this once so you know what it is protecting you from.

Validation / Self-check

1. Why does Linux have several schedulers rather than one with modes?
2. Name the classes in priority order, and say what mechanism establishes that order in the source.
3. What does SCHED_DEADLINE guarantee that SCHED_FIFO does not, and what does the kernel do when it cannot make the guarantee?
4. What is sched_rt_runtime_us for, and what happens if you set it to -1?
5. Why one runqueue per CPU rather than one global one? What problem does that create?
6. What is the difference between rq->clock and rq->clock_task?
7. Why is rq->lock a raw_spinlock_t, and what does that forbid?
8. Name the four kinds of caller of __schedule(). Which one surprises people?
9. What does TIF_NEED_RESCHED do, and why does nothing preempt anything directly?
10. Explain what is strange about switch_to(), and what follows from it about kernel stacks.
11. Why must finish_task_switch() run in the next task's context?
12. Write the canonical sleep loop from memory and explain what each line protects against.
13. nice -n -20 on a fair task versus chrt -f 1 on another, on one CPU. Who wins, and why is the answer not "it depends on nice"?

Next: EEVDF and Fairness — what "fair" means, and what changed in 6.6.