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

3. NUMA感知调度核心数据结构：位图与cpumask、sched_domain与sched_group结构体分析

在NUMA架构下，Linux内核调度器需要感知内存访问延迟的差异，并据此做出智能的负载均衡决策。这一切的基石，是一套精心设计的数据结构。本章将深入剖析其中最核心的四个部分：位图与cpumask、调度域（sched_domain）与调度组（sched_group）。理解这些数据结构，是掌握NUMA感知调度的第一步。

3.1 位图与cpumask：CPU的“身份证”与“集合”

在Linux内核中，CPU的编号从0开始。为了高效地表示“一组CPU”或“某个CPU的属性”，内核广泛使用了位图（bitmap）。一个位图中的每一位（bit）代表一个CPU，位为1表示该CPU属于这个集合，为0则表示不属于。

cpumask是内核为操作CPU位图而封装的一个类型和一套API。它本质上是一个位图，但提供了类型安全和便捷的操作函数。

  核心概念： cpumask 是内核中表示CPU集合的标准方式。它比简单的整型位图更安全、更易读，并且能自动适应不同大小的CPU拓扑。

3.1.1 核心数据结构定义

cpumask的定义非常简洁，它基于一个固定大小的位图数组。

// 位于 include/linux/cpumask.h
typedef struct cpumask { DECLARE_BITMAP(bits, NR_CPUS); } cpumask_t;

// DECLARE_BITMAP 宏展开后，本质上是一个 unsigned long 数组
// #define DECLARE_BITMAP(name, bits) unsigned long name[BITS_TO_LONGS(bits)]

其中，NR_CPUS是编译时可配置的常量，表示系统支持的最大CPU数量。BITS_TO_LONGS宏用于计算需要多少个unsigned long才能容纳NR_CPUS个比特位。

3.1.2 常用API与操作

内核提供了一系列内联函数和宏来操作cpumask，这些API是调度器进行CPU集合运算的基础。

API 函数	功能描述	典型使用场景
`cpumask_set_cpu(cpu, mask)`	将指定CPU加入mask集合	初始化某个调度域的CPU列表
`cpumask_clear_cpu(cpu, mask)`	将指定CPU从mask集合中移除	CPU热插拔时移除离线的CPU
`cpumask_test_cpu(cpu, mask)`	测试CPU是否在mask集合中	判断当前CPU是否属于某个调度组
`cpumask_and(dst, src1, src2)`	计算两个mask的交集，结果存入dst	计算两个调度域共享的CPU集合
`cpumask_or(dst, src1, src2)`	计算两个mask的并集，结果存入dst	合并多个调度组的CPU列表
`cpumask_weight(mask)`	返回mask中CPU的数量（即置1的位数）	计算调度组中CPU的个数，用于负载均衡
`for_each_cpu(cpu, mask)`	遍历mask中的所有CPU	遍历调度域内的所有CPU进行负载统计

性能提示： cpumask操作是高度优化的。例如，cpumask_weight通常使用CPU指令popcnt（人口计数）来实现，单条指令即可完成，效率极高。

3.1.3 cpumask与NUMA拓扑的关系

在NUMA系统中，每个内存节点（NUMA node）都关联一个cpumask，表示该节点上的所有CPU。这个关系是构建调度域的基础。

// 获取NUMA节点 nid 上的所有CPU
const struct cpumask *cpumask_of_node(int nid);

// 示例：遍历NUMA节点0上的所有CPU
int cpu;
for_each_cpu(cpu, cpumask_of_node(0)) {
    printk("CPU %d belongs to NUMA node 0\n", cpu);
}

下图展示了cpumask如何映射到物理CPU和NUMA节点。

3.2 sched_domain：CPU拓扑的层级抽象

调度域（sched_domain）是内核用来描述CPU拓扑层级关系的关键数据结构。它将CPU按照物理距离（如共享缓存、共享总线、跨内存节点）组织成树状结构。调度器在进行负载均衡时，会从最底层的域开始，逐级向上，直到所有CPU的负载达到平衡。

3.2.1 数据结构定义

每个调度域代表一个“共享某种资源”的CPU集合。例如，一个物理核上的超线程（SMT）构成一个域，一个物理CPU的所有核构成一个域，一个NUMA节点内的所有CPU构成一个域，整个系统构成一个顶级域。

// 位于 include/linux/sched/topology.h (简化版)
struct sched_domain {
    /* 该域包含的CPU集合 */
    struct cpumask span;

    /* 指向下一级（更底层）的调度域 */
    struct sched_domain *child;

    /* 指向上一级（更顶层）的调度域 */
    struct sched_domain *parent;

    /* 该域内的调度组链表 */
    struct sched_group *groups;

    /* 该域在拓扑中的层级（如：SMT, MC, NUMA, NUMA_NODE） */
    int level;

    /* 负载均衡相关标志和参数 */
    unsigned long flags;
    unsigned int imbalance_pct;
    unsigned int cache_nice_tries;
    // ... 其他字段
};

关键理解： span字段是一个cpumask，它精确地定义了哪些CPU属于这个域。child和parent指针将不同层级的域串联起来，形成一棵树。调度器总是从叶子节点（最底层域）开始进行负载均衡。

3.2.2 典型层级与标志

一个典型的NUMA系统，其调度域层级如下表所示。每个层级都有特定的标志（flags）来控制调度行为。

层级 (level)	名称	span 包含的CPU	关键标志 (flags)	说明
0	SMT (Simultaneous Multi-Threading)	同一个物理核上的所有逻辑CPU	`SD_SHARE_CPUCAPACITY`	共享执行资源，如ALU、缓存
1	MC (Multi-Core)	同一个物理CPU封装内的所有核	`SD_SHARE_PKG_RESOURCES`	共享最后一级缓存（LLC）
2	NUMA (Non-Uniform Memory Access)	同一个NUMA节点内的所有CPU	`SD_NUMA`	共享本地内存，访问延迟低
3	NUMA_NODE (跨节点)	整个系统中的所有CPU	`SD_SERIALIZE`	跨NUMA节点，访问远程内存延迟高

下图展示了一个4节点NUMA系统的调度域树状结构。

3.3 sched_group：负载均衡的基本单元

在每个调度域内部，CPU被划分为一个或多个调度组（sched_group）。调度组是负载均衡操作的基本单元。调度器在域内进行负载均衡时，会比较不同调度组之间的负载，并将任务从负载高的组迁移到负载低的组。

3.3.1 数据结构定义

一个调度组包含一组CPU，这些CPU在域内被视为一个整体。组与组之间通过链表连接。

// 位于 include/linux/sched/topology.h (简化版)
struct sched_group {
    /* 该组包含的CPU集合 */
    struct cpumask cpumask;

    /* 该组的计算能力（考虑频率、超线程等） */
    unsigned long sg_capacity;

    /* 指向下一个调度组，形成链表 */
    struct sched_group *next;

    /* 指向该组所在的调度域 */
    struct sched_domain *sd;

    /* 组内CPU的负载信息（用于均衡决策） */
    struct group_capacity *sgc;
    // ... 其他字段
};

  核心关系： 一个 sched_domain 包含一个 sched_group 链表。每个 sched_group 的 cpumask 是该域 span 的一个子集。所有组的 cpumask 的并集等于该域的 span。

3.3.2 分组策略与示例

分组策略决定了如何将一个域内的CPU划分到不同的组中。最常见的策略是：在NUMA域中，每个NUMA节点内的所有CPU构成一个组。

考虑一个2节点NUMA系统，每个节点有4个CPU（共8个CPU）。

NUMA域 (Domain 2): span = {0,1,2,3,4,5,6,7}
调度组1: cpumask = {0,1,2,3} (对应NUMA节点0)
调度组2: cpumask = {4,5,6,7} (对应NUMA节点1)

当调度器在NUMA域进行负载均衡时，它会比较组1和组2的总负载。如果组1的负载远高于组2，调度器会尝试将组1中的任务迁移到组2中。

下图展示了调度域与调度组之间的关系。

3.4 数据结构协同工作：从拓扑构建到负载均衡

这些数据结构并非孤立存在，它们在内核初始化时协同工作，构建出完整的CPU拓扑视图，并在运行时指导负载均衡决策。

3.4.1 初始化流程

内核启动时，会调用sched_init_domains()函数，根据硬件拓扑信息（通过ACPI或设备树获取）动态创建sched_domain和sched_group。

检测拓扑： 内核遍历所有CPU，确定它们之间的物理距离（是否共享缓存、是否在同一节点等）。
构建域树： 从最底层（SMT）开始，逐层向上创建sched_domain，并设置child和parent指针。
划分调度组： 在每个域内，根据策略（如按NUMA节点划分）创建sched_group，并初始化其cpumask和sg_capacity。
链接组： 将域内的所有sched_group通过next指针链接成循环链表。

3.4.2 在负载均衡中的应用

当调度器触发负载均衡（例如，周期性负载均衡或新任务唤醒时），它会执行以下步骤：

选择域： 从当前CPU所在的最底层域开始，逐级向上检查。
遍历组： 在选定的域内，遍历其groups链表，计算每个组的总负载。
比较负载： 找出最忙的组和最闲的组。如果负载差异超过阈值（imbalance_pct），则触发迁移。
执行迁移： 从最忙的组中选择一个任务，迁移到最闲的组中的某个CPU上。

NUMA感知的关键： 在跨NUMA节点进行负载均衡时，调度器会优先考虑将任务迁移到与任务内存所在节点相同的组中，以避免远程内存访问带来的性能损失。这是通过SD_NUMA标志和numa_group结构实现的。

3.5 本章小结

本章深入剖析了NUMA感知调度的四个核心数据结构：

cpumask： 高效表示CPU集合的位图，是构建所有拓扑结构的基础。
sched_domain： 描述CPU拓扑层级的树状结构，定义了负载均衡的范围。
sched_group： 域内负载均衡的基本单元，是任务迁移的源和目标。

这些数据结构共同构成了Linux内核感知NUMA拓扑、做出智能调度决策的基石。理解它们，是后续学习负载均衡算法和性能调优的必备前提。