Scheduler

Purpose

kernel/sched/ is the CPU scheduler. It decides which task runs on which CPU at which time. The scheduler is structured as a small core (core.c) that delegates to one of several "scheduling classes" — fair (the bulk of workloads), real-time (rt), deadline (deadline), idle, and BPF-extended (ext).

The default fair scheduling class is EEVDF (Earliest Eligible Virtual Deadline First), which replaced CFS as the default in 6.6 (October 2023). The implementation still lives in kernel/sched/fair.c.

Directory layout

kernel/sched/
├── core.c              # The class dispatcher, runqueue, context switch
├── fair.c              # EEVDF (formerly CFS) — the fair class
├── rt.c                # SCHED_FIFO / SCHED_RR
├── deadline.c          # SCHED_DEADLINE (EDF + CBS)
├── idle.c              # SCHED_IDLE class and the idle task
├── stop_task.c         # The stop scheduler class (highest priority)
├── ext.c               # sched_ext (BPF-programmable scheduler)
├── topology.c          # Sched-domain hierarchy
├── pelt.c              # Per-Entity Load Tracking
├── psi.c               # Pressure Stall Information
├── cputime.c           # Per-task CPU accounting
├── cpufreq.c           # cpufreq integration (schedutil)
├── cpufreq_schedutil.c # The schedutil cpufreq governor
├── debug.c             # /proc/sched_debug, sched stats
├── completion.c        # struct completion
├── wait.c, wait_bit.c  # waitqueues
├── swait.c             # simple waitqueues
├── autogroup.{c,h}     # Per-tty autogrouping (controversial, optional)
├── stats.{c,h}         # /proc/schedstat
├── cpupri.{c,h}        # RT priority bookkeeping
├── cpudeadline.{c,h}   # Deadline cpu-pickier
├── core_sched.c        # Core scheduling (cookie-based smt isolation)
├── build_policy.c, build_utility.c  # Compiler shimss
├── isolation.c         # nohz_full / housekeeping CPU mask
├── membarrier.c        # The membarrier syscall
└── sched.h             # The big internal header

Key abstractions

Symbol	File	Purpose
struct task_struct	include/linux/sched.h	The schedulable entity.
struct sched_class	kernel/sched/sched.h	The vtable each class implements (pick_next_task, enqueue_task, etc.).
struct rq (runqueue)	kernel/sched/sched.h	Per-CPU scheduler state.
struct sched_entity	include/linux/sched.h	The entity tracked by the fair class.
struct sched_dl_entity	include/linux/sched.h	The entity tracked by the deadline class.
__schedule()	kernel/sched/core.c	The function that picks the next task and switches to it.
try_to_wake_up()	kernel/sched/core.c	The wakeup path.
pick_next_task_fair()	kernel/sched/fair.c	EEVDF pick.

How it works

graph TD
    EVENT[Tick / preempt / wakeup / yield] --> SCHED["__schedule() in core.c"]
    SCHED --> PICK[Walk sched_classes in priority order]
    PICK -->|stop / dl / rt / fair / idle| CLASS[Class.pick_next_task]
    CLASS --> CTX[context_switch into next task]
    CTX --> RUN[Task runs]
    RUN -->|tick or block| EVENT

Scheduling classes (in priority order)

1. stop — internal use (CPU hotplug, migration). Highest priority.
2. dl (deadline) — SCHED_DEADLINE. Runtime + period guarantee under EDF + CBS bandwidth enforcement.
3. rt — SCHED_FIFO and SCHED_RR. POSIX real-time, fixed-priority.
4. ext (sched_ext) — when enabled, BPF programs implement scheduling. Slots between rt and fair when active.
5. fair (EEVDF) — SCHED_NORMAL, SCHED_BATCH, SCHED_IDLE. The default for almost everything.
6. idle — runs when nothing else wants the CPU.

The dispatcher in core.c walks classes from highest to lowest and asks each one if it has a task ready. The first that says yes wins.

EEVDF (fair class)

EEVDF schedules entities by their virtual deadline. Each entity has:

• vruntime — accumulated runtime weighted by inverse share.
• slice — its requested execution slice.
• deadline = vruntime + slice / weight.

The scheduler picks the eligible entity with the earliest deadline. "Eligible" means vruntime <= virtual time of the runqueue. This produces fair scheduling with bounded latency and lets requests for a smaller slice get serviced sooner. See kernel/sched/fair.c and the comment block at the top.

CFS (Completely Fair Scheduler), the predecessor, used a red-black tree keyed on vruntime and always picked the leftmost entity. Much of the EEVDF code reuses CFS's cfs_rq data structures.

sched_ext

A BPF-programmable scheduler. A user-space loader compiles a BPF object into the kernel; the BPF program implements enqueue, dispatch, runnable, etc., callbacks. The kernel side is in kernel/sched/ext.c. The intent is letting researchers, distributions, and workloads experiment with custom policies without forking the kernel.

Load tracking

Per-Entity Load Tracking (PELT) in kernel/sched/pelt.c maintains an exponentially-decayed estimate of how much each entity loads its CPU. Used for SMP load balancing and frequency scaling.

Frequency scaling

The schedutil cpufreq governor in kernel/sched/cpufreq_schedutil.c drives cpufreq directly from PELT signals. This is the modern integration point between the scheduler and DVFS.

PSI

Pressure Stall Information in kernel/sched/psi.c measures how much time tasks spent stalled on CPU, IO, or memory. Exposed at /proc/pressure/. Useful for QoS frameworks and OOM policy.

Topology and load balancing

kernel/sched/topology.c builds the sched-domain hierarchy (SMT siblings → cores → packages → NUMA). Load balancing in fair.c uses this to migrate tasks between CPUs while preserving cache locality.

Core scheduling

kernel/sched/core_sched.c implements cookie-based core scheduling: tasks tagged with the same cookie are allowed to run together on SMT siblings; otherwise the sibling is forced idle. Originally a mitigation for L1TF/MDS sibling attacks; now a tool for QoS isolation.

Integration points

• arch/: per-arch context-switch (switch_to), cpu_relax, low-level scheduler clocks.
• kernel/locking/: the scheduler is the consumer of mutex / wait_event / completion semantics.
• kernel/time/: timer wheel and hrtimer feed into the tick handler.
• drivers/cpufreq/, drivers/cpuidle/: scheduler emits hints; these subsystems realize them.
• mm/: numa balancing in mm/memory.c interacts with the scheduler.
• kernel/cgroup/: the CPU controller maps cgroups to scheduling-group entities.

Key source files

File	Purpose
kernel/sched/core.c	The dispatcher, runqueues, wakeup, context switch.
kernel/sched/fair.c	EEVDF + load balancing. The largest file.
kernel/sched/rt.c	Real-time class.
kernel/sched/deadline.c	SCHED_DEADLINE.
kernel/sched/ext.c	sched_ext.
kernel/sched/pelt.c	PELT signal computation.
kernel/sched/psi.c	Pressure Stall Information.
kernel/sched/topology.c	Sched-domain hierarchy and balancing topology.
kernel/sched/cpufreq_schedutil.c	The schedutil governor.
kernel/sched/sched.h	Big internal header — many invariants documented in comments here.

Entry points for modification

• Tweaking fair scheduling: probably kernel/sched/fair.c. Read recent commits and Documentation/scheduler/sched-design-CFS.rst (still relevant for EEVDF mechanics).
• New BPF-programmable policy: write a sched_ext program (see tools/sched_ext/).
• New cpufreq integration: extend cpufreq_schedutil.c or work with the cpufreq driver in drivers/cpufreq/.
• New scheduling class: very rare. The bar is high; sched_ext is the recommended escape hatch for new policies.
• New load metric: see how PELT is computed in kernel/sched/pelt.c.

Related pages

• Kernel core — the rest of kernel/.
• Architecture support — per-arch context switch.
• Drivers — cpufreq and cpuidle drivers.