📚 课程目录第3章 Linux调度器架构

3. Linux 调度器原理：CFS 调度器、调度域与负载均衡

在集群节点中，CPU 资源竞争的核心在于 Linux 调度器如何将就绪线程分配到物理核心上执行。本章深入剖析完全公平调度器（CFS）的数学模型、调度域（sched_domain）与调度组（sched_group）的层级结构，以及跨域负载均衡的触发机制与校准方法。

3.1 CFS 调度器：虚拟运行时间与红黑树

CFS 摒弃了传统的时间片轮转模型，引入 虚拟运行时间（vruntime） 作为公平性的唯一度量。每个就绪线程维护一个 vruntime，调度器总是选择 vruntime 最小的线程运行。

概念	公式 / 定义	说明
vruntime	`vruntime += 实际运行时间 × (1024 / 权重)`	权重越高，vruntime 增长越慢，获得更多 CPU 时间
nice 值	范围 [-20, 19]，映射到权重表	nice 0 权重为 1024；nice 每增减 1，权重约变化 10%
调度周期	`targeted_latency = 6ms × (nr_running / 8)`	保证所有线程在调度周期内至少运行一次
最小粒度	`min_granularity = 0.75ms`	防止频繁上下文切换导致开销过大

  校准要点： 在 NUMA 集群节点中，/proc/sys/kernel/sched_min_granularity_ns 和 sched_latency_ns 的默认值通常偏保守。对于高吞吐计算任务，适当增大最小粒度（如 2ms）可减少上下文切换开销，但会牺牲交互响应性。

CFS 使用 红黑树 组织就绪队列（rq）。所有可运行线程按 vruntime 排序，最左叶子节点即为下一个被调度线程。插入和删除操作的时间复杂度为 O(log n)，在数千线程并发时仍保持高效。

// 内核调度核心路径（简化）
static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq) {
    struct sched_entity *se = __pick_first_entity(cfs_rq);  // 红黑树最左节点
    struct sched_entity *left = se;

    // 检查是否可跳过当前最左节点（如 cgroup 带宽控制）
    if (cfs_rq->next && entity_before(cfs_rq->next, left))
        left = cfs_rq->next;
    return left;
}

3.2 调度域（sched_domain）与调度组（sched_group）

Linux 将 CPU 拓扑组织为树形 调度域，每个域包含多个 调度组。域与组是负载均衡的基本单元。

调度域标志位： 通过 /sys/kernel/debug/sched/domains/cpu0/domain*/flags 可查看每个域的标志。常见标志包括 SD_BALANCE_NEWIDLE（空闲时平衡）、SD_BALANCE_EXEC（exec 时平衡）、SD_BALANCE_FORK（fork 时平衡）和 SD_LOAD_BALANCE（周期性负载均衡）。

3.3 负载均衡算法与触发时机

负载均衡的核心目标是使每个调度组内的 CPU 利用率尽可能均衡。均衡过程分为三个步骤：检测不平衡 → 选择迁移任务 → 执行迁移。

检测不平衡： 计算每个调度组的平均负载（group_avg_load），若最大组负载与最小组负载之差超过 imbalance_pct（默认 125%）的阈值，则触发均衡。
选择迁移任务： 从最繁忙的组中选择 vruntime 最大（即运行时间最长）的任务，优先迁移到目标空闲 CPU 的缓存亲和域内。
执行迁移： 通过 stop_machine 机制或 active_load_balance 软中断，将任务从源 rq 移动到目标 rq。

均衡类型	触发条件	适用场景	性能影响
周期性均衡	每 1ms（HZ=1000）触发一次	通用场景，持续调整	低，但频繁扫描可能增加锁竞争
空闲时均衡	CPU 进入 idle 前	CPU 空闲时拉取任务	中等，涉及跨域迁移
唤醒时均衡	任务被唤醒时	短任务、交互型负载	低，仅影响唤醒路径
主动均衡	手动触发或负载严重倾斜	NUMA 节点间大迁移	高，可能引起缓存抖动

3.4 调度域配置与性能校准

在集群节点中，默认的调度域配置可能不适合高性能计算场景。以下校准参数直接影响负载均衡行为：

# 查看当前 CPU 的调度域层级
cat /proc/sys/kernel/sched_domain/cpu0/domain*/name
# 输出示例：SMT → MC → NUMA

# 调整负载均衡阈值（imbalance_pct）
echo 150 > /proc/sys/kernel/sched_domain/cpu0/domain0/imbalance_pct

# 关闭 NUMA 域内的自动均衡（适合绑定场景）
echo 0 > /proc/sys/kernel/sched_domain/cpu0/domain2/flags

校准陷阱： 在 NUMA 节点上，默认的 imbalance_pct 为 125%，意味着负载差异超过 25% 才会触发迁移。对于延迟敏感型任务，此阈值可能过高，导致 CPU 利用率不均。但若设置过低（如 110%），则可能引发频繁的跨 NUMA 迁移，造成缓存污染和内存访问延迟增加。

3.5 调度组负载计算与统计

调度组的负载由 PELT（Per-Entity Load Tracking） 机制计算。PELT 使用半衰期衰减算法，对每个调度实体（se）的历史负载进行加权求和，权重随时间指数衰减。

// PELT 负载更新公式（内核源码 kernel/sched/pelt.c）
// load = 负载贡献值，period = 1024us（约 1ms）
static u32 __accumulate_pelt_segments(u64 periods, u32 d1, u32 d3) {
    u32 c1 = d1;  // 当前周期剩余部分
    u32 c2 = LOAD_AVG_MAX * periods;  // 完整周期衰减和
    u32 c3 = d3;  // 下一周期开始部分
    return c1 + c2 + c3;
}

通过 /sys/kernel/debug/sched/debug 可以查看每个 CPU 的 PELT 负载值：

# 查看 CPU0 的负载统计
cat /sys/kernel/debug/sched/debug | grep -A 20 "cpu#0"
# 输出关键字段：
#   .avg_load: 512          # 平均负载（单位：1024 = 1 个满负载核心）
#   .nr_running: 3          # 当前运行队列线程数
#   .nr_switches: 1234567   # 上下文切换次数

  校准实践： 在 64 核双路 NUMA 节点上运行 MPI 通信密集型应用时，建议将 sched_domain 的 SD_BALANCE_NEWIDLE 标志关闭，避免空闲 CPU 从其他 NUMA 节点拉取任务导致跨节点通信延迟。同时将 imbalance_pct 调整为 130%，减少不必要的负载迁移。

3.6 本章小结

CFS 调度器 基于 vruntime 红黑树实现 O(log n) 的公平调度，权重与 nice 值直接关联 CPU 时间分配。
调度域 按 CPU 拓扑层级组织（SMT → MC → NUMA），每个域包含多个调度组作为负载均衡的基本单元。
负载均衡 通过周期性、空闲时、唤醒时和主动四种机制触发，核心指标是组间负载差异是否超过 imbalance_pct 阈值。
PELT 提供精细的负载跟踪，是调度域均衡决策的数据基础。
性能校准 需根据应用特征调整域标志、均衡阈值和最小粒度，在公平性与缓存局部性之间取得平衡。