调度器类层级结构：Linux 如何决定下一个运行的任务
前置知识
- ›第 1 篇：architecture-and-directory-map
- ›第 2 篇：boot-sequence-and-initialization
- ›理解 C 语言函数指针与基于 struct 的多态机制
- ›基本并发概念（spinlock、per-CPU 数据）
调度器类层级结构：Linux 如何决定下一个运行的任务
Linux 调度器每秒需要回答数十亿次同一个看似简单的问题：下一个该运行哪个任务？要给出这个答案，背后涉及一套通过 C struct 函数指针实现的多态类层级结构、一种利用链接器 section 实现优先级排序的巧妙技巧、针对缓存行精心设计的 per-CPU 运行队列，以及一个近期新增的允许用 BPF 编写调度策略的框架。本文将逐一拆解这些机制。
在第 2 篇中我们已经看到，sched_init() 在 start_kernel() 的早期阶段被调用，用于启动调度器。本文将进一步探讨这一初始化过程究竟构建了什么，以及调度机制在运行时如何运作。
struct task_struct：进程描述符
系统中的每个进程和线程都由一个 struct task_struct 来表示。这个结构体超过 800 行，包含大量条件编译字段，是内核中最庞大的数据结构之一。
include/linux/sched.h#L820-L919
与调度相关的字段紧接在 thread_info 之后：
struct task_struct {
#ifdef CONFIG_THREAD_INFO_IN_TASK
struct thread_info thread_info;
#endif
unsigned int __state;
unsigned int saved_state;
randomized_struct_fields_start
void *stack;
...
int on_rq;
int prio;
int static_prio;
int normal_prio;
unsigned int rt_priority;
struct sched_entity se;
struct sched_rt_entity rt;
struct sched_dl_entity dl;
#ifdef CONFIG_SCHED_CLASS_EXT
struct sched_ext_entity scx;
#endif
const struct sched_class *sched_class;
...
classDiagram
class task_struct {
+unsigned int __state
+int prio
+int static_prio
+int on_rq
+sched_entity se
+sched_rt_entity rt
+sched_dl_entity dl
+sched_ext_entity scx
+sched_class* sched_class
}
class sched_entity {
+u64 vruntime
+u64 deadline
+struct load_weight load
}
class sched_rt_entity {
+struct list_head run_list
+unsigned int time_slice
}
class sched_dl_entity {
+u64 dl_deadline
+u64 dl_period
+u64 dl_runtime
}
task_struct --> sched_entity
task_struct --> sched_rt_entity
task_struct --> sched_dl_entity
这里有几点值得关注。第一，randomized_struct_fields_start 是一个 GCC 插件，它会对后续字段的内存布局进行随机化，从而增加漏洞利用的难度。第二，每个任务同时携带多个调度类的调度实体（se 对应 CFS，rt 对应实时调度，dl 对应截止期调度，scx 对应 sched_ext），但同一时刻只有一个处于激活状态，由 sched_class 指针指示。第三，scx 字段受 CONFIG_SCHED_CLASS_EXT 编译选项控制。
提示： 阅读
task_struct时，不必试图理解每一个字段。专注于你当前研究的子系统相关字段即可——无论是调度、内存、信号还是权限管理。
struct sched_class：调度虚函数表
调度器的可扩展性来自 struct sched_class——一张由各调度策略各自实现的函数指针表。这是贯穿整个内核的"C 虚函数表"模式。
kernel/sched/sched.h#L2497-L2658
struct sched_class {
#ifdef CONFIG_UCLAMP_TASK
int uclamp_enabled;
#endif
void (*enqueue_task)(struct rq *rq, struct task_struct *p, int flags);
bool (*dequeue_task)(struct rq *rq, struct task_struct *p, int flags);
void (*yield_task)(struct rq *rq);
void (*wakeup_preempt)(struct rq *rq, struct task_struct *p, int flags);
struct task_struct *(*pick_task)(struct rq *rq, struct rq_flags *rf);
void (*put_prev_task)(struct rq *rq, struct task_struct *p, struct task_struct *next);
void (*set_next_task)(struct rq *rq, struct task_struct *p, bool first);
int (*select_task_rq)(struct task_struct *p, int task_cpu, int flags);
void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);
void (*update_curr)(struct rq *rq);
...
};源码中每个操作都有注释说明其所需的加锁上下文（如 rq->lock、task_rq_lock），这是关键信息——在错误的时机调用这些函数会导致死锁或数据损坏。
核心操作包括：
enqueue_task/dequeue_task— 将任务加入或移出运行队列pick_task— 从当前调度类的队列中选出下一个要运行的任务wakeup_preempt— 判断一个即将唤醒的任务是否应抢占当前任务put_prev_task/set_next_task— 管理上下文切换时的簿记工作task_tick— 在每次定时器中断时调用，用于时间统计
类层级结构与链接器 section 技巧
Linux 共有六个调度类，它们的优先级顺序至关重要：实时任务必须始终抢占 CFS 任务，截止期任务必须抢占实时任务。这一顺序通过一个巧妙的链接器 section 技巧来实现。
kernel/sched/sched.h#L2706-L2709
#define DEFINE_SCHED_CLASS(name) \
const struct sched_class name##_sched_class \
__aligned(__alignof__(struct sched_class)) \
__section("__" #name "_sched_class")每个调度类通过 DEFINE_SCHED_CLASS(name) 将自己的 sched_class 实例放入一个具名链接器 section。链接器脚本随后按照固定顺序排列这些 section：
include/asm-generic/vmlinux.lds.h 第 153–162 行
__sched_class_highest = .;
*(__stop_sched_class)
*(__dl_sched_class)
*(__rt_sched_class)
*(__fair_sched_class)
*(__ext_sched_class)
*(__idle_sched_class)
__sched_class_lowest = .;
第 2702 行的注释特别提醒："注意，它们的排列顺序是反向的！！！" 这意味着 __sched_class_highest 指向 stop_sched_class（最高优先级），遍历时通过递增指针从高到低依次访问。
flowchart LR
stop["stop<br/>(highest)"] --> dl["deadline"]
dl --> rt["real-time"]
rt --> fair["CFS/fair"]
fair --> ext["sched_ext"]
ext --> idle["idle<br/>(lowest)"]
遍历宏利用了这一内存布局：
kernel/sched/sched.h#L2746-L2747
#define for_each_active_class(class) \
for_active_class_range(class, __sched_class_highest, __sched_class_lowest)这里"active"一词是关键。next_active_class() 函数会在运行时动态跳过某些调度类：
kernel/sched/sched.h#L2725-L2735
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;
}当 scx_switched_all() 返回 true 时，CFS 会被完全绕过——sched_ext 已全面接管公平调度。当 sched_ext 被禁用时，ext 类则直接跳过。正是这种动态的类跳过机制，使 sched_ext 能够在运行时实现热替换。
__schedule() 上下文切换路径
调度的核心函数是 __schedule()：
static void __sched notrace __schedule(int sched_mode)
{
struct task_struct *prev, *next;
bool preempt = sched_mode > SM_NONE;
...
cpu = smp_processor_id();
rq = cpu_rq(cpu);
prev = rq->curr;
...执行流程如下：
flowchart TD
A["__schedule(sched_mode)"] --> B["Get current CPU's rq"]
B --> C["Lock rq->__lock"]
C --> D["Handle prev task state<br/>(sleeping? yielding?)"]
D --> E["pick_next_task()<br/>iterates active classes"]
E --> F{"next != prev?"}
F -->|Yes| G["context_switch(rq, prev, next)"]
F -->|No| H["Unlock and return"]
G --> I["Switch stack, registers, address space"]
pick_next_task() 从最高优先级到最低优先级依次遍历活跃的调度类，第一个有可运行任务的类获胜。这意味着，只要有一个可运行的截止期任务，它就会始终优先于所有 CFS 任务被选中，无论等待中的 CFS 任务有多少。
最后的 context_switch() 执行真正的 CPU 上下文切换：保存和恢复寄存器、切换内存映射（如果两个进程拥有不同的地址空间），并更新 rq->curr 指针。
CFS 与 sched_ext
CFS：完全公平调度器
CFS 是普通任务（SCHED_OTHER）的默认策略。其核心思想是虚拟运行时间（vruntime）：每个任务累积的虚拟时间与其实际 CPU 时间除以权重成正比。每次都选择 vruntime 最小的任务运行，从而保证按比例的公平性。
CFS 在 DEFINE_SCHED_CLASS(fair) 中的实现是内核中最庞大的单一操作结构体之一：
kernel/sched/fair.c#L13955-L14001
DEFINE_SCHED_CLASS(fair) = {
.enqueue_task = enqueue_task_fair,
.dequeue_task = dequeue_task_fair,
.yield_task = yield_task_fair,
.wakeup_preempt = wakeup_preempt_fair,
.pick_task = pick_task_fair,
.pick_next_task = pick_next_task_fair,
.put_prev_task = put_prev_task_fair,
.set_next_task = set_next_task_fair,
.select_task_rq = select_task_rq_fair,
.task_tick = task_tick_fair,
.update_curr = update_curr_fair,
...
};sched_ext：基于 BPF 的可扩展调度
sched_ext 是一项革命性的新增特性：它允许将调度策略编写为 BPF 程序并在运行时动态加载。激活后，它可以完全取代 CFS（即类遍历中 scx_switched_all() 的作用），也可以与 CFS 并存运行。
调度类层级结构让 sched_ext 能够以固定的优先级插入到 CFS 与 idle 之间。BPF 程序实现 pick_task、enqueue_task 等操作，让研究人员和运维人员无需重新编译内核，就能灵活试验自定义调度策略。
提示： 查看
tools/sched_ext/目录可以找到示例 BPF 调度器，包括scx_simple和scx_layered，它们展示了如何编写一条命令即可加载的调度策略。
Per-CPU 运行队列与缓存行布局
每个 CPU 都有自己的 struct rq，该结构体的布局经过精心设计以优化缓存性能：
kernel/sched/sched.h#L1121-L1170
struct rq {
/* Hot read-mostly data loaded in update_sg_lb_stats() */
unsigned int nr_running;
...
unsigned long cpu_capacity;
struct task_struct __rcu *curr;
struct task_struct *idle;
/* Next cacheline: the hot lock */
u64 nr_switches ____cacheline_aligned;
raw_spinlock_t __lock;
...
#ifdef CONFIG_UCLAMP_TASK
struct uclamp_rq uclamp[UCLAMP_CNT] ____cacheline_aligned;
#endif
struct cfs_rq cfs;
struct rt_rq rt;
struct dl_rq dl;
#ifdef CONFIG_SCHED_CLASS_EXT
struct scx_rq scx;
#endif
flowchart LR
subgraph CL1["Cache Line 1 (read-mostly)"]
nr["nr_running"]
cap["cpu_capacity"]
curr["curr / donor"]
idle["idle"]
end
subgraph CL2["Cache Line 2 (lock + hot writes)"]
sw["nr_switches"]
lock["__lock (spinlock)"]
nohz["nohz fields"]
end
subgraph CL3["Cache Line 3+"]
cfs["cfs_rq"]
rt["rt_rq"]
dl["dl_rq"]
end
CL1 -.-> CL2 -.-> CL3
第 1123 行的注释解释了这一设计思路：nr_running 和 cpu_capacity 等字段"在极热的循环中，无需持有 rq->lock 就会被一起读取"。为此，它们被放置在独立的缓存行上，与锁字段分离，避免伪共享。锁本身位于下一条缓存行，通过 ____cacheline_aligned 进行对齐隔离。
这绝非过度优化——调度器在每个 CPU 上、每次上下文切换时、每次定时器中断时都会执行。减少哪怕一次缓存缺失，都能转化为整个系统可度量的吞吐量提升。
下一步
现在我们已经理解了调度器如何决定运行哪个任务。在下一篇文章中，我们将沿着相反的方向追踪执行路径——从用户空间进入内核，跟随一次系统调用从 x86-64 的 SYSCALL 指令，经过汇编入口、C 层分发，最终进入 VFS 层，探索内核中最重要的抽象模式如何在大规模场景下运作。