CPU and the Scheduler

Every other subsystem in this book is scheduled by this one. A driver that sleeps, a filesystem that waits for I/O, a network stack that wakes a reader — all of them end in a call into kernel/sched/, and all of them are affected by decisions made here.

It is also the hardest place in the kernel to make a first contribution, and it is worth understanding why: the code is small and readable, but every change affects every Linux machine in the world, the effects are statistical rather than binary, and the bar is not "is this correct" but "does this help enough to justify the risk". Reading it is enormously valuable. Patching it is a later goal.

Orient Yourself First

Run these before reading further. The tables in this chapter are a snapshot; your tree is the truth.

cd ~/kernel/linux

./scripts/get_maintainer.pl --scm --status -f kernel/sched/
git log --oneline --since="6 months ago" -- kernel/sched/ | head -30
git log --since="1 year ago" --format='%cN' -- kernel/sched/ | sort | uniq -c | sort -rn | head

ls kernel/sched/
ls Documentation/scheduler/
wc -l kernel/sched/*.c | sort -n | tail -12

Predict first: how many lines is kernel/sched/fair.c? How does that compare with a single mid-sized driver? Most people are surprised in both directions.

Why It Matters

Where the Code Is

ls kernel/sched/

Related, outside kernel/sched/:

ls kernel/cpu.c kernel/smp.c            # CPU hotplug, IPIs
ls drivers/cpufreq/ drivers/cpuidle/    # frequency and idle-state drivers
ls tools/sched_ext/                     # example BPF schedulers, if present

The Structures

Draw these before reading a single function.

   struct task_struct                      one per task
     ├── sched_class      ──────▶  which policy owns this task
     ├── se               (struct sched_entity)      ← fair class state
     │     ├── vruntime, deadline, slice, vlag       ← EEVDF's bookkeeping
     │     ├── load                                  ← weight, from nice
     │     └── avg        (struct sched_avg)         ← PELT: load_avg, util_avg
     ├── rt               (struct sched_rt_entity)   ← rt class state
     ├── dl               (struct sched_dl_entity)   ← deadline class state
     ├── prio / static_prio / normal_prio
     └── cpus_ptr, cpus_mask                          ← affinity

   struct rq                               ONE PER CPU. The runqueue.
     ├── cfs   (struct cfs_rq)  ── an rbtree of runnable sched_entities
     ├── rt    (struct rt_rq)   ── priority-indexed lists
     ├── dl    (struct dl_rq)   ── an rbtree by deadline
     ├── curr, idle, stop                             ← which task is on-CPU
     ├── clock, clock_task                            ← this CPU's notion of time
     └── lock                                         ← the runqueue lock

   struct sched_domain                     the machine's TOPOLOGY
     └── a hierarchy: SMT siblings -> a core's L2 -> a socket's LLC -> NUMA
         Load balancing walks this, cheapest level first.

rg -n "struct rq \{" -A 40 kernel/sched/sched.h
rg -n "struct sched_entity \{" -A 30 include/linux/sched.h
rg -n "struct sched_domain \{" -A 30 include/linux/sched/topology.h

The Verbs

The scheduler's polymorphism is one ops table, and finding it is finding the architecture.

rg -n "struct sched_class \{" -A 40 kernel/sched/sched.h
rg -n "DEFINE_SCHED_CLASS" kernel/sched/*.c

The classes are a priority-ordered chain, and pick_next_task() walks it in order: the first class with a runnable task wins. The order is established by linker section placement, not a linked list you can grep for directly:

rg -n "DEFINE_SCHED_CLASS" kernel/sched/          # each class, in section order
rg -n "for_each_class|pick_next_task\b" kernel/sched/core.c | head

Roughly: stop → deadline → rt → fair → (ext) → idle. Verify the order on your tree rather than trusting that sentence — sched_ext inserted itself into this chain in 6.12 and the arrangement is exactly the kind of thing that changes.

The Concepts

And Lab 10 makes you trace a single wakeup from write() to the target task running on a CPU you can name.

How to Read It

 1. Documentation/scheduler/ -- sched-design-CFS.rst, sched-ext.rst,
    sched-deadline.rst, sched-domains.rst. An hour, and it saves ten.

 2. kernel/sched/sched.h -- struct rq and struct sched_class. Do not read
    a .c file until you can draw these.

 3. ONE PATH: __schedule() in core.c.
       - who calls it (voluntary sleep, preemption, exit-to-user)
       - pick_next_task(): the class chain
       - context_switch(): the actual switch
    Follow it in GDB with a breakpoint and `bt`.

 4. THE OTHER PATH: try_to_wake_up() in core.c.
       - select_task_rq(): which CPU?
       - enqueue, then maybe an IPI to make that CPU reschedule
    This is where most of the interesting decisions are.

 5. Only then open fair.c, and only the part you need.

Tip: fair.c is large and it is the wrong place to start. core.c's __schedule() and try_to_wake_up() are the skeleton; the fair class is one implementation hanging off it. People who start in fair.c spend a week on vruntime arithmetic without knowing what calls it.

Observing It

Everything here is instrumented. Use it before reading code, not after.

T=/sys/kernel/tracing; [ -d "$T" ] || T=/sys/kernel/debug/tracing
ls $T/events/sched/                              # ~25 tracepoints

# The four that matter most:
#   sched_wakeup        a task became runnable, and on which CPU
#   sched_switch        a context switch, with both tasks' states
#   sched_migrate_task  a task moved between CPUs
#   sched_stat_*        time spent runnable-but-not-running (needs SCHEDSTATS)

sudo perf sched record -- sleep 5
sudo perf sched latency --sort max | head -20    # who waited longest
sudo perf sched timehist | head -30              # every switch, annotated

sudo bpftrace -e 'tracepoint:sched:sched_switch { @[args.prev_comm, args.next_comm] = count(); }'
sudo bpftrace -e 'tracepoint:sched:sched_migrate_task { @[args.orig_cpu, args.dest_cpu] = count(); }'

cat /proc/sched_debug 2>/dev/null | head -40     # per-runqueue internals
ls /sys/kernel/debug/sched/ 2>/dev/null
cat /proc/pressure/cpu 2>/dev/null               # PSI: time lost to CPU contention

What Is Moving

Read the last six months rather than believing a book:

git log --oneline --since="6 months ago" -- kernel/sched/ | head -40
git log --oneline --since="2 years ago" -- kernel/sched/ext.c | tail -20

The large changes of the recent past, each of which you should verify is still true:

grep -rn "EEVDF\|eevdf" kernel/sched/fair.c | head
ls Documentation/scheduler/sched-ext.rst 2>/dev/null && echo "sched_ext docs present"

What a Good First Contribution Looks Like

Realistically, in ascending order of ambition:

Warning: The failure mode here is specific and worth naming. A newcomer measures a workload, changes a heuristic, sees a 3% improvement, and sends it. The reply asks about the other twelve workloads, the other four topologies, and the tail latency — because every scheduler heuristic is a tradeoff someone already made deliberately. A scheduler patch is a measurement project with a small diff attached, and the measurement is 95% of the work.

Common Misconceptions

Validation / Self-check

1. Name the five scheduling classes in priority order, and the command that shows you the real order on your tree.
2. What is a runqueue, how many are there, and what protects one?
3. What is the difference between struct task_struct and struct sched_entity, and why are they separate?
4. Name six methods of struct sched_class and say when each is called.
5. Which two functions in core.c are the skeleton of the whole subsystem, and why is fair.c the wrong place to start?
6. Where does most placement happen — at wakeup or during periodic balancing? What follows from that?
7. What changed in 6.6, and what does it make stale in older documentation?
8. What is sched_ext and why does it lower the barrier to contributing here?
9. Name four scheduler tracepoints and what question each answers.
10. Why is a scheduler performance patch mostly a measurement project?
11. nice -n 5 on a fair-class task: what exactly does that change?
12. Give three plausible first contributions here and say why each is plausible.

Next: Scheduling Classes and the Pick Path — what runs next, and who decides.