📚 课程目录第3章调度器核心数据结构

3. 调度器核心数据结构

Linux 内核调度器的实现依赖于一组精心设计的数据结构。这些数据结构构成了调度决策的“骨架”与“血液”，贯穿于进程生命周期、CPU 资源分配以及负载均衡的全过程。本章将深入剖析四个核心数据结构：task_struct 中的调度字段、调度实体（sched_entity）、运行队列（rq）以及调度域（sched_domain）。理解这些结构是掌握调度器架构的基石。

学习提示： 本章涉及的数据结构之间存在明确的层级关系。建议读者在阅读时，从“单个进程”出发，逐步扩展到“单个 CPU 的运行队列”，最后上升到“多 CPU 的调度域拓扑”，形成全局视角。

3.1 task_struct 中的调度相关字段

每个进程在内核中都由一个 task_struct 结构体表示，它是进程控制块（PCB）的实现。其中包含了数十个与调度直接相关的字段，这些字段共同决定了进程的调度行为、优先级、时间片以及状态。

下表列出了 task_struct 中最关键的调度字段及其作用：

字段名	类型	作用描述
`state`	unsigned int	进程状态（TASK_RUNNING, TASK_INTERRUPTIBLE 等），是调度器判断进程是否可运行的首要依据。
`prio`	int	动态优先级，调度器在运行时实际使用的优先级值。数值越小，优先级越高。
`static_prio`	int	静态优先级，由用户通过 nice 值设定（范围 -20 ~ 19），是计算动态优先级的基础。
`normal_prio`	int	常规优先级，基于静态优先级和调度策略计算得出，通常等于 `static_prio`。
`rt_priority`	unsigned int	实时优先级（0 ~ 99），仅用于实时调度类（SCHED_FIFO, SCHED_RR）。数值越大，优先级越高。
`policy`	unsigned int	调度策略（如 SCHED_NORMAL, SCHED_FIFO, SCHED_BATCH 等），决定进程属于哪个调度类。
`se`	struct sched_entity	CFS 调度类的调度实体，是 CFS 调度器操作的基本单位。
`rt`	struct sched_rt_entity	实时调度类的调度实体。
`dl`	struct sched_dl_entity	Deadline 调度类的调度实体。
`sched_class`	const struct sched_class *	指向进程所属调度类的指针，是调度器实现多态调度的关键。
`cpus_allowed`	cpumask_t	CPU 亲和性掩码，限制进程可以在哪些 CPU 上运行。
`on_rq`	int	标记进程是否在运行队列上（1 表示在队列中，0 表示不在）。

  关键点： sched_class 字段是调度器架构中“策略模式”的体现。调度器通过调用 p->sched_class->task_tick(p) 或 p->sched_class->dequeue_task(rq, p, flags) 等函数，无需关心具体调度逻辑，实现了核心调度代码与调度类实现的解耦。

以下代码片段展示了 task_struct 中调度相关字段的简化定义：

// 来自 include/linux/sched.h (简化)
struct task_struct {
    /* 进程状态与调度策略 */
    unsigned int            state;
    int                     prio;
    int                     static_prio;
    int                     normal_prio;
    unsigned int            rt_priority;
    unsigned int            policy;

    /* 调度实体 */
    struct sched_entity     se;      // CFS 调度实体
    struct sched_rt_entity  rt;      // 实时调度实体
    struct sched_dl_entity  dl;      // Deadline 调度实体

    /* 调度类与运行队列状态 */
    const struct sched_class *sched_class;
    struct sched_entity     *sched_entity; // 指向当前活跃的调度实体
    int                     on_rq;

    /* CPU 亲和性 */
    cpumask_t               cpus_allowed;

    /* ... 其他字段 ... */
};

3.2 调度实体（sched_entity）

调度实体是调度器进行资源分配的基本单位。它抽象了“一个可调度的任务”，这个任务可以是一个普通进程、一个线程组，甚至是一个 cgroup。引入调度实体的主要目的是为了支持组调度（Group Scheduling），使得调度器能够对一组进程进行整体控制。

对于 CFS 调度类，其调度实体为 struct sched_entity，定义在 include/linux/sched.h 中。其核心字段如下：

load：调度实体的负载权重，决定了该实体在 CFS 红黑树中的位置以及获得 CPU 时间的比例。
run_node：红黑树节点，用于将调度实体插入到 CFS 运行队列的红黑树中。
on_rq：标记该实体是否在运行队列上。
exec_start：当前实体开始执行的时间戳，用于计算已运行的物理时间。
sum_exec_runtime：该实体在 CPU 上执行的总物理时间。
vruntime：虚拟运行时间，CFS 调度器的核心指标。调度器总是选择 vruntime 最小的实体来运行。
prev_sum_exec_runtime：上次被切换出 CPU 时的总执行时间。
my_q：指向该实体所属的 CFS 运行队列。对于组调度，一个调度实体可以拥有自己的运行队列。

下图展示了调度实体、task_struct 与 CFS 运行队列之间的关系：

易混淆点： 不要将 sched_entity 与 task_struct 混淆。一个 task_struct 可以包含多个调度实体（如 se, rt, dl），但在任意时刻，只有一个调度实体是“活跃”的，由 sched_entity 指针指向。对于普通进程，sched_entity 指针通常指向 se 字段。

3.3 运行队列（rq）

运行队列是每个 CPU 核心独有的核心调度数据结构。它管理着该 CPU 上所有可运行的进程。在 Linux 内核中，每个 CPU 都有一个独立的 struct rq 实例，这避免了多 CPU 并发访问时的全局锁竞争，是实现 SMP 可扩展性的关键。

struct rq 定义在 kernel/sched/sched.h 中，其核心字段按功能分类如下：

分类	字段名	作用描述
调度类子队列	`cfs`	CFS 调度类的运行队列（struct cfs_rq），管理普通进程。
	`rt`	实时调度类的运行队列（struct rt_rq），管理实时进程。
	`dl`	Deadline 调度类的运行队列（struct dl_rq），管理 Deadline 进程。
当前运行状态	`curr`	指向当前正在该 CPU 上运行的 task_struct。
	`idle`	指向该 CPU 的空闲进程（idle task）的 task_struct。
	`stop`	指向该 CPU 的停止进程（stop task），用于 CPU 热插拔等特殊场景。
负载与统计	`nr_running`	该 CPU 上所有调度类中可运行进程的总数。
负载与统计	`load`	该 CPU 的当前负载权重，用于负载均衡决策。
锁	`lock`	保护该运行队列的自旋锁，是调度器代码中最常使用的锁。

下图展示了运行队列的内部结构及其与调度类子队列的关系：

3.4 调度域（sched_domain）

在 SMP（对称多处理）系统中，CPU 之间的缓存层次和内存访问延迟并不相同（NUMA 架构）。调度域是内核用来描述 CPU 拓扑层次结构的数据结构，它使得负载均衡器能够理解 CPU 之间的“距离”关系，从而做出更优的迁移决策。

调度域是一个树形或层级结构，每个层级代表一个特定的 CPU 拓扑级别：

SMT 域（SMT Domain）：同一物理核心内的超线程（兄弟 CPU）。共享 L1 缓存，通信延迟最低。
MC 域（MC Domain）：同一物理封装内的所有核心（多核 CPU）。共享 L2 或 L3 缓存。
NUMA 域（NUMA Domain）：同一 NUMA 节点内的所有 CPU。共享本地内存，访问远程节点内存延迟较高。
NUMA 顶层域（NUMA Top-level Domain）：整个系统中的所有 CPU。

struct sched_domain 的核心字段包括：

字段名	作用描述
`span`	cpumask 位图，表示该调度域覆盖了哪些 CPU。
`level`	调度域的层级（如 SMT, MC, NUMA 等）。
`groups`	指向该域内调度组的链表。每个组包含一组 CPU，是负载均衡的基本单位。
`min_interval`	负载均衡的最小间隔时间。
`max_interval`	负载均衡的最大间隔时间。
`busy_factor`	用于计算繁忙时的均衡间隔。
`flags`	调度域特性标志（如是否允许跨域迁移等）。
`child`	指向下一级（更底层）的调度域。
`parent`	指向上一级（更顶层）的调度域。

下图展示了一个典型的 2 路 NUMA 系统（每路 4 核，每核 2 超线程）的调度域层次结构：

  负载均衡流程： 当某个 CPU 空闲时，调度器会触发负载均衡。均衡器从当前 CPU 所在的 SMT 域开始，检查同域内其他 CPU 的负载。如果无法平衡，则向上层 MC 域、NUMA 域寻找更合适的迁移目标。这种“从底向上”的策略最大限度地减少了跨域迁移带来的缓存和内存访问开销。

3.5 数据结构关系总结

上述四个数据结构共同构成了调度器的数据基础。它们之间的关系可以概括为：

task_struct 是进程的载体，通过 se、rt、dl 字段嵌入调度实体。
sched_entity 是调度器操作的基本单位，通过 run_node 插入到所属调度类的运行队列中。
rq 是每个 CPU 的调度中心，包含三个调度类子队列，管理所有在该 CPU 上可运行的进程。
sched_domain 描述了 CPU 的拓扑结构，指导负载均衡器在多个 rq 之间进行任务迁移。

下图以一张综合架构图总结四者关系：