📚 课程目录第2章 Linux内核调度器基础

2. Linux内核调度器基础：CFS调度器原理、调度实体与调度类、调度域与调度组概念

在NUMA架构下，理解Linux内核调度器的核心机制是进行负载均衡优化的前提。本章深入剖析完全公平调度器（CFS）的设计哲学、调度实体与调度类的层次结构，以及调度域与调度组的拓扑抽象，为后续章节的NUMA感知调度奠定理论基础。

2.1 CFS调度器原理

完全公平调度器（Completely Fair Scheduler, CFS）自Linux 2.6.23引入以来，取代了原有的O(1)调度器，成为主流调度算法。CFS的核心思想是模拟“理想的多任务处理器”——假设系统中有N个可运行进程，每个进程应获得1/N的CPU时间。

2.1.1 虚拟运行时间（vruntime）

CFS通过虚拟运行时间（vruntime）来衡量进程的执行进度。vruntime是进程实际运行时间经过优先级加权后的结果，其计算公式为：

vruntime = 实际运行时间 × (NICE_0_LOAD / 进程权重)

其中，NICE_0_LOAD是nice值为0时的基准权重（1024），进程权重由nice值决定。权重越高（nice值越低），vruntime增长越慢，进程获得更多CPU时间。

nice值	权重（weight）	vruntime增长速率	CPU时间占比（相对nice=0）
-20	88761	极慢	约86.7倍
-10	9548	慢	约9.3倍
0	1024	基准	1倍
10	335	快	约0.33倍
19	15	极快	约0.015倍

2.1.2 红黑树与最小vruntime选择

CFS将所有可运行进程按vruntime组织在一棵红黑树中，树的最左节点（vruntime最小）即为下一个被调度执行的进程。这种设计保证了O(log N)的调度开销，同时天然实现了公平性——vruntime最小的进程（即“最受亏待”的进程）优先获得CPU。

  关键指标：CFS的调度周期（sched_latency）默认值为6ms，在调度周期内，所有可运行进程至少被调度一次。当进程数超过一定阈值时，调度周期会按比例扩展，以保证每个进程获得的最小运行时间（min_granularity）不低于0.75ms。

NUMA关联：在NUMA系统中，CFS的vruntime计算会考虑NUMA节点间的内存访问延迟差异。当进程被迁移到远程节点时，其vruntime会获得一定的补偿（credit），以抵消远程内存访问带来的性能损失，避免频繁迁移。

2.2 调度实体与调度类

Linux内核调度器采用面向对象的设计思想，通过调度实体（Scheduling Entity）和调度类（Scheduling Class）实现不同调度策略的灵活组合。

2.2.1 调度实体（struct sched_entity）

调度实体是内核调度器调度的基本单位，它封装了进程的调度相关信息。每个进程（task_struct）内嵌一个或多个调度实体，用于参与不同调度类的调度。

// 调度实体核心字段（简化版）
struct sched_entity {
    struct load_weight      load;           // 调度权重
    struct rb_node          run_node;       // 红黑树节点
    unsigned int            on_rq;          // 是否在运行队列中
    u64                     vruntime;       // 虚拟运行时间
    u64                     prev_sum_exec_runtime; // 上次调度时的总执行时间
    u64                     sum_exec_runtime;      // 总执行时间
    struct sched_entity     *parent;        // 组调度时的父实体
    struct cfs_rq           *cfs_rq;        // 所属CFS运行队列
    struct cfs_rq           *my_q;          // 组调度时子CFS运行队列
};

字段	类型	作用
`load`	struct load_weight	包含weight和inv_weight，用于vruntime计算和负载均衡
`run_node`	struct rb_node	红黑树节点，将调度实体组织到CFS运行队列中
`vruntime`	u64	虚拟运行时间，决定调度优先级
`sum_exec_runtime`	u64	进程累计执行时间，用于统计和负载计算
`parent`	struct sched_entity *	指向父调度实体，用于组调度（task_group）

2.2.2 调度类（struct sched_class）

调度类定义了不同调度策略的操作函数表。Linux内核支持以下调度类，按优先级从高到低排列：

stop_sched_class：最高优先级，用于停止CPU的线程，不可抢占
dl_sched_class：Deadline调度类，使用Earliest Deadline First（EDF）算法
rt_sched_class：实时调度类，支持SCHED_FIFO和SCHED_RR
fair_sched_class：CFS调度类，实现完全公平调度
idle_sched_class：空闲调度类，运行idle线程

  调度类优先级规则：内核在调度时，按照stop → dl → rt → fair → idle的顺序检查每个调度类是否有可运行进程。只有高优先级调度类没有可运行进程时，才会选择低优先级调度类中的进程。这种设计保证了实时任务和Deadline任务的及时响应。

2.3 调度域与调度组

在NUMA系统中，CPU和内存的拓扑结构复杂，不同层级的内存访问延迟差异显著。Linux内核通过调度域（Scheduling Domain）和调度组（Scheduling Group）来抽象CPU拓扑，实现层次化的负载均衡。

2.3.1 调度域（struct sched_domain）

调度域是CPU拓扑的层次化表示，每个调度域包含一组CPU，这些CPU在某一层级上具有相同的特性（如共享L2缓存、共享L3缓存、同一NUMA节点等）。调度域按层级组织，从底层（物理核心）到顶层（整个系统）。

// 调度域核心字段（简化版）
struct sched_domain {
    struct sched_domain *parent;    // 父调度域（更高层级）
    struct sched_domain *child;     // 子调度域（更低层级）
    struct sched_group *groups;     // 该域内的调度组链表
    unsigned long min_interval;     // 最小负载均衡间隔
    unsigned long max_interval;     // 最大负载均衡间隔
    unsigned int busy_factor;       // 繁忙因子
    unsigned int imbalance_pct;     // 不均衡百分比阈值
    unsigned int nr_balance_failed; // 负载均衡失败次数
    int flags;                      // 调度域标志
    int level;                      // 层级编号（0为最底层）
};

2.3.2 调度组（struct sched_group）

调度组是调度域内的CPU分组，每个调度组包含一个或多个CPU。负载均衡时，内核在调度域内的各个调度组之间迁移进程，以平衡各组之间的负载。

层级	调度域示例	调度组示例	负载均衡粒度
L0（SMT）	物理核心内的超线程	每个超线程为一个组	超线程间均衡
L1（MC）	共享L2缓存的CPU集群	每个物理核心为一个组	核心间均衡
L2（DIE）	同一NUMA节点内的所有CPU	每个L2集群为一个组	NUMA节点内均衡
L3（NUMA）	整个系统所有CPU	每个NUMA节点为一个组	跨NUMA节点均衡

NUMA负载均衡陷阱：跨NUMA节点的进程迁移虽然可以平衡CPU负载，但会导致内存访问延迟显著增加（通常为1.5~3倍）。内核通过调度域标志（如SD_NUMA、SD_SERIALIZE）控制跨节点迁移的频率，并优先在节点内部进行负载均衡。

2.3.3 调度域与调度组的关系

调度域和调度组共同构成了Linux内核的层次化负载均衡框架。每个调度域包含一个调度组链表，调度组之间通过组不平衡检测和进程迁移实现负载均衡。

2.4 调度域标志与NUMA感知

调度域通过标志位（flags）控制负载均衡的行为，其中与NUMA相关的标志尤为重要：

标志	值	含义	NUMA影响
SD_BALANCE_NEWIDLE	0x0001	CPU空闲时触发负载均衡	允许跨节点拉取进程
SD_BALANCE_EXEC	0x0002	进程exec()时触发负载均衡	优先选择本地节点
SD_BALANCE_FORK	0x0004	进程fork()时触发负载均衡	子进程优先分配本地CPU
SD_BALANCE_WAKE	0x0008	进程唤醒时触发负载均衡	唤醒者优先选择同节点CPU
SD_NUMA	0x4000	该域跨越NUMA节点	启用NUMA感知负载均衡
SD_SERIALIZE	0x8000	序列化负载均衡操作	防止多个CPU同时跨节点迁移

调试技巧：通过/proc/schedstat和/sys/kernel/debug/sched/domains可以查看当前系统的调度域拓扑和负载均衡统计信息。在NUMA系统中，重点关注sd_numa域的imbalance_pct和nr_balance_failed字段，它们反映了跨节点负载均衡的效率和瓶颈。

2.5 本章小结

本章深入剖析了Linux内核调度器的三大基础组件：

CFS调度器：通过vruntime和红黑树实现完全公平调度，是NUMA负载均衡的核心调度算法
调度实体与调度类：调度实体封装进程调度信息，调度类实现多策略调度，CFS是默认的公平调度类
调度域与调度组：层次化抽象CPU拓扑，调度域定义均衡范围，调度组作为均衡单位，共同实现NUMA感知的负载均衡