vault

Scheduling Classes and the sched_class Interface

13 min read

Scheduling Classes and the sched_class Interface

The Linux scheduler is not a single algorithm but a stack of pluggable policies layered behind one polymorphic interface, struct sched_class. Each class — stop, deadline, real-time, fair (EEVDF), sched_ext, and idle — implements the same table of function pointers (enqueue_task, dequeue_task, pick_next_task, task_tick, select_task_rq, …), and the core scheduler treats them all identically through that vtable. The documentation for the fair scheduler states the design goal exactly: scheduling classes are “an extensible hierarchy of scheduler modules [that] encapsulate scheduling policy details and are handled by the scheduler core without the core code assuming too much about them” (sched-design-CFS). The classes are ordered by strict priority, and that order is fixed not by an array or a comparison function but by where each class’s instance lands in a dedicated linker section — the lower the address, the higher the priority. As of the 6.12 LTS kernel (released 2024-11-17) and unchanged in 6.18 LTS (2025-11-30), that order is stop → deadline → rt → fair → ext → idle, verified directly against SCHED_DATA in include/asm-generic/vmlinux.lds.h (v6.12 vmlinux.lds.h).

This note covers the interface and its ordering mechanism. The routine that consumes the chain to actually choose a task — pick_next_task() and its walk — is its own concern, owned by Scheduler Entry Points and pick_next_task; the container that the methods operate on is Per-CPU Run Queues and struct rq; the master loop that calls into all of it is The Core Scheduler and __schedule. This note explains why the design is a vtable, what methods that vtable contains, and how the priority order is established at link time.

Mental Model — One Interface, Many Policies

Think of struct sched_class as the C equivalent of an abstract base class or a Go interface: a table of function pointers that every concrete scheduling policy must fill in. The core scheduler never asks “is this an EEVDF task or a real-time task?” — it asks “what does this task’s sched_class say to do?” and dispatches through the pointer. A task carries its class in task_struct->sched_class; the policy is chosen when the task is created or when sched_setscheduler() changes its policy.

flowchart TB
  CORE["core scheduler<br/>core.c — policy-agnostic"]
  subgraph VTABLE["struct sched_class (the vtable)"]
    M1["enqueue_task / dequeue_task"]
    M2["pick_task / pick_next_task"]
    M3["put_prev_task / set_next_task"]
    M4["task_tick / task_fork"]
    M5["select_task_rq / migrate_task_rq (SMP)"]
    M6["wakeup_preempt / prio_changed"]
  end
  CORE -->|"p->sched_class->pick_task(rq)"| VTABLE
  subgraph IMPL["concrete implementations (by linker-section priority)"]
    direction TB
    S["stop_sched_class"]
    D["dl_sched_class"]
    R["rt_sched_class"]
    F["fair_sched_class (EEVDF)"]
    E["ext_sched_class (BPF)"]
    I["idle_sched_class"]
  end
  VTABLE -.->|"highest priority"| S
  S --> D --> R --> F --> E --> I

The polymorphism at the heart of the scheduler. What it shows: the core scheduler (top) holds no policy logic — it dispatches every per-task decision through the struct sched_class function-pointer table (middle), which each concrete class (bottom) fills in. The classes are totally ordered, stop highest, idle lowest. The insight to take: adding a policy means filling in one more vtable and slotting it into the order — the core code does not change. This is exactly how sched_ext (ext_sched_class) was added in 6.12 without rewriting the core: it is just another implementation of the same interface, placed below fair and above idle.

The Interface — What Lives in struct sched_class

The full definition at v6.12 lives in kernel/sched/sched.h (line 2378 onward) (v6.12 sched.h). The methods group into a few responsibilities:

Run-queue membership. enqueue_task(rq, p, flags) adds a now-runnable task p to this CPU’s run queue under that class’s data structure; dequeue_task(rq, p, flags) removes it when it blocks or migrates. A version-specific detail worth pinning: at 6.12 dequeue_task returns bool (it can fail/defer, e.g. for the DELAY_DEQUEUE EEVDF feature), whereas in older kernels it returned void. The mechanics of these two calls are detailed in Runnable State Enqueue and Dequeue.

Task selection. Two related hooks exist. pick_task(rq) returns the task this class would run next without committing the switch; pick_next_task(rq, prev) is the older combined form that both picks and performs the put_prev/set_next bookkeeping. The header comment notes pick_next_task is “Optional! When implemented [it] should be equivalent to” pick_task() followed by put_prev_task(prev); set_next_task_first(next). The split exists so that core scheduling (CONFIG_SCHED_CORE, the SMT co-scheduling feature) can call pick_task across sibling run queues without side effects before deciding.

Switch bookkeeping. put_prev_task(rq, p, next) is called on the outgoing task to let its class save state (e.g. update vruntime); set_next_task(rq, p, first) prepares the incoming task. These bracket every context switch.

The periodic tick. task_tick(rq, p, queued) is invoked from the scheduler’s timer path on the currently running task — this is where the fair class accrues vruntime and the RR class decrements its time slice and may set need_resched. Note the entry point that drives this was renamed: it is sched_tick() at 6.12 (kernel/sched/core.c line 5584), not the older scheduler_tick(). See The need_resched Flag and Preemption Points.

Wakeup preemption. wakeup_preempt(rq, p, flags) decides whether a newly-woken task p should preempt the current task. This method was renamed from check_preempt_curr in a recent cleanup; at 6.12 the field is wakeup_preempt (sched.h line 2389) and the dispatcher wakeup_preempt() in core.c (line 2136) simply calls rq->curr->sched_class->wakeup_preempt(rq, p, flags). Mentioning the old name matters because most secondary write-ups still use it.

Lifecycle and priority changes. task_fork(p) lets a class initialize a newly-forked child; task_dead(p) cleans up; switched_from/switched_to/prio_changed fire when a task moves between classes or changes priority (e.g. via priority inheritance — see Real-Time Priorities and Priority Inversion). update_curr(rq) brings the current task’s accounting up to date on demand.

SMP placement (under CONFIG_SMP). select_task_rq(p, task_cpu, flags) answers “which CPU should this waking task run on?” — the entry point to wakeup balancing, owned by Wakeup Balancing and select_task_rq. migrate_task_rq, task_woken, set_cpus_allowed, rq_online/rq_offline, and find_lock_rq round out the multiprocessor hooks that Scheduler Load Balancing leans on.

Not every class implements every method; an unset pointer simply means “this class has nothing to do here,” and the core checks for NULL (as in the pick_next_task ? : pick_task branch in __pick_next_task).

The Priority Order and the Linker-Section Trick

The single most distinctive piece of engineering here is how the classes are ordered. There is no enum of priorities and no int prio field compared at run time. Instead, each class instance is emitted into its own named ELF section, and the kernel’s linker script concatenates those sections in priority order. The DEFINE_SCHED_CLASS macro (sched.h line 2499) does the placement:

#define DEFINE_SCHED_CLASS(name) \
const struct sched_class name##_sched_class \
	__aligned(__alignof__(struct sched_class)) \
	__section("__" #name "_sched_class")

So DEFINE_SCHED_CLASS(fair) puts fair_sched_class into a section literally named __fair_sched_class. The linker script then dictates the concatenation order in include/asm-generic/vmlinux.lds.h (verbatim at v6.12, lines 129–138):

#define SCHED_DATA				\
	STRUCT_ALIGN();				\
	__sched_class_highest = .;		\
	*(__stop_sched_class)			\
	*(__dl_sched_class)			\
	*(__rt_sched_class)			\
	*(__fair_sched_class)			\
	*(__ext_sched_class)			\
	*(__idle_sched_class)			\
	__sched_class_lowest = .;

The two symbols __sched_class_highest and __sched_class_lowest bracket the array of class structs that now sit contiguously in memory, in this exact order: stop, deadline, rt, fair, ext, idle. Because they are contiguous and equally aligned, the core scheduler can walk them as a plain C array. The comment immediately above this block states the intent: “The order of the sched class addresses are important, as they are used to determine the order of the priority of each sched class in relation to each other.” Lower address = higher priority.

This is exactly the placement the task’s brief asked to verify: at 6.12 (and identically at 6.18, where the same SCHED_DATA lists fair then ext then idle), ext_sched_class sits below fair and above idle (v6.18 vmlinux.lds.h). A sched_ext BPF scheduler therefore cannot starve EEVDF tasks: a runnable SCHED_OTHER (fair) task is always picked before any sched_ext task. The two notes on the BPF layer — sched_ext and BPF-Defined Schedulers and Writing a sched_ext Scheduler with struct_ops — depend on this fact.

The header also leaves a famous warning at DEFINE_SCHED_CLASS: the classes are “laid out in REVERSE order!!!” The verifiable consequence (not the reasoning, which the comment does not fully spell out) is captured by the helpers in sched.h:

#define for_class_range(class, _from, _to) \
	for (class = (_from); class < (_to); class++)
 
#define for_each_class(class) \
	for_class_range(class, __sched_class_highest, __sched_class_lowest)
 
#define sched_class_above(_a, _b)	((_a) < (_b))

for_each_class starts at the highest-priority (lowest-address) class and increments toward idle; sched_class_above(a, b) is true when a’s address is below b’s. So “is the deadline class above the fair class?” reduces to a pointer comparison the compiler can fold to a constant.

Uncertain

Verify: the precise reason the DEFINE_SCHED_CLASS comment calls the layout “REVERSE order.” Reason: the comment in sched.h asserts it but does not fully explain it; the observable contract (section-order priority-order, lowest address highest priority, for_each_class increments from __sched_class_highest) is verified against the linker script and macros, but the “reverse” wording likely refers to a historical or per-toolchain section-emission detail not pinned here. To resolve: read the git history of the SCHED_DATA/DEFINE_SCHED_CLASS commit messages. uncertain

The ext Subtlety — Static Order vs. Runtime Walk

The static linker order is only half the story. sched_ext can be configured out entirely (CONFIG_SCHED_CLASS_EXT off), and even when compiled in it is inert until a BPF scheduler is loaded. The kernel handles this with a second iterator, for_each_active_class, built on next_active_class (sched.h lines 2531–2553):

static inline const struct sched_class *next_active_class(const struct sched_class *class)
{
	class++;
#ifdef CONFIG_SCHED_CLASS_EXT
	if (scx_switched_all() && class == &fair_sched_class)
		class++;
	if (!scx_enabled() && class == &ext_sched_class)
		class++;
#endif
	return class;
}

Reading this symbol by symbol: the walk advances one class (class++); if a BPF scheduler has taken over all fair tasks (scx_switched_all()), it skips fair; and if no BPF scheduler is loaded (!scx_enabled()), it skips ext entirely. So on a stock system with no sched_ext scheduler running, ext_sched_class is never even examined — it costs nothing. The documentation confirms this default: “sched_ext is used only when the BPF scheduler is loaded and running,” and “if a task explicitly sets its scheduling policy to SCHED_EXT, it will be treated as SCHED_NORMAL” (sched-ext). The same doc states fair “has higher sched_class precedence than SCHED_EXT,” matching the linker order.

This also explains the fast-path optimization in __pick_next_task (core.c line 5959): it begins with if (scx_enabled()) goto restart; — the shortcut that “the class after fair is idle” is only valid when no BPF scheduler is loaded, so when one is loaded the code falls into the full for_each_active_class walk instead. The walk itself belongs to Scheduler Entry Points and pick_next_task.

How a Task Gets Its Class

A task’s class is set at creation and whenever its policy changes. The mapping from POSIX policy to class is visible in __setscheduler_class / the policy switch in core.c (around line 4712):

if (rt_policy(p->policy))                 // SCHED_FIFO / SCHED_RR
	p->sched_class = &rt_sched_class;
else if (task_should_scx(p->policy))      // SCHED_EXT, BPF loaded
	p->sched_class = &ext_sched_class;
else
	p->sched_class = &fair_sched_class;    // SCHED_NORMAL/BATCH/IDLE

SCHED_DEADLINE tasks resolve to dl_sched_class separately; stop_sched_class and idle_sched_class are never assigned via sched_setscheduler — stop is attached to the per-CPU migration/stop kthread (stop->sched_class = &stop_sched_class in core.c), and idle belongs to the per-CPU idle task. When a task’s policy changes between classes, the old class’s switched_from and the new class’s switched_to hooks run so each can fix up its own bookkeeping. The end-to-end semantics of these policies live in Real-Time Scheduling SCHED_FIFO and SCHED_RR, SCHED_DEADLINE and Earliest Deadline First, and The EEVDF Scheduler.

Why This Design — Pluggable Policies Without Touching the Core

The payoff of the vtable-plus-linker-section design is separation of mechanism from policy. The core scheduler (__schedule, the tick, the balancer) is written once against struct sched_class and never has to know how EEVDF computes a virtual deadline or how EDF orders deadlines. A new policy is added by (1) defining a new struct sched_class instance with DEFINE_SCHED_CLASS, (2) adding its section to SCHED_DATA at the right priority rung, and (3) implementing the methods. That is precisely how sched_ext entered in 6.12: it is one more struct sched_class whose methods forward into BPF programs loaded through the struct_ops mechanism, slotted below fair. No core rewrite.

The cost of the design is indirect calls. Every per-task decision is a function-pointer call, which on modern CPUs is a potential branch-target misprediction and (with retpoline mitigations) can be expensive. The kernel mitigates this in the hottest path: __pick_next_task special-cases the common “everything is a fair task” situation and calls pick_next_task_fair directly, bypassing the vtable, before falling back to the generic for_each_active_class loop (core.c lines 5968–5982). So the abstraction is paid for only when the run queue actually holds tasks of mixed classes.

Common Misunderstandings

  • “The order is set by a priority number on each class.” No — there is no prio field on struct sched_class. The order is the memory layout fixed by the linker script. Comparing classes is a pointer comparison (sched_class_above).
  • “sched_ext can override real-time tasks.” No. ext sits below fair, which sits below rt and dl. A SCHED_EXT task cannot preempt a SCHED_FIFO task, and cannot even preempt an ordinary fair task. sched_ext replaces the fair-class role, not the real-time guarantees.
  • “check_preempt_curr is the wakeup-preemption hook.” That was the name; at 6.12 it is wakeup_preempt. Same role, renamed.
  • “Every class implements every method.” Many pointers are NULL. The core code branches on presence (e.g. pick_next_task ? : pick_task).
  • “Walking the classes is always six comparisons.” With no BPF scheduler loaded, for_each_active_class skips ext, and the all-fair fast path skips the walk entirely.

Alternatives and Contrast

The closest userspace analogue is the Go runtime’s scheduler, which also multiplexes many entities (goroutines) onto few OS threads but uses a single fixed policy rather than a stack of pluggable classes — see GMP Scheduler Model and Goroutine Preemption for the kernel-vs-userspace contrast. Other operating systems take different structural choices: classic Unix used a single multilevel-feedback-queue scheduler with no class abstraction; Solaris pioneered dispatch tables and a class-based design that influenced Linux. Within Linux, the historical alternative to today’s interface was the O(1) scheduler (pre-2.6.23), which hard-coded the real-time-vs-normal split into one monolithic scheduler before the sched_class abstraction generalized it; that lineage is covered in The Completely Fair Scheduler and Its History.

Production Notes

The class abstraction is why sched_ext could ship as a runtime-loadable policy with a safety net: because the BPF scheduler is just an ext_sched_class below fair, the kernel can detach it and fall back to EEVDF if the BPF watchdog fires, without ever endangering real-time or deadline tasks. Operationally, the most common confusion in production is engineers expecting a sched_ext scheduler to control all CPU time; by default it only governs tasks that would otherwise be fair-class, and only when explicitly switched. The other recurring gotcha is the renamed symbols (sched_tick, wakeup_preempt, bool dequeue_task): tracing scripts, bpftrace one-liners, and out-of-tree patches written against older kernels reference names that no longer exist at 6.12, and fail to attach.

See Also

Graph View

Backlinks