📚 课程目录第4章进程调度

4、进程调度：CFS调度器原理、调度策略（SCHED_NORMAL、SCHED_FIFO、SCHED_RR）、调度实体与虚拟运行时间、负载均衡与调度域

进程调度是Linux内核中最核心的子系统之一，它决定了哪个进程在何时、在哪个CPU上获得执行权。Linux内核自2.6.23版本起，以完全公平调度器（CFS，Completely Fair Scheduler）取代了原有的O(1)调度器，成为默认的调度类。CFS的设计哲学并非追求的“最快响应”，而是基于“理想多任务处理器”模型，力求让每个进程获得与其优先级（权重）成比例的CPU时间。本章将深入剖析CFS的核心原理、三种主要调度策略、调度实体与虚拟运行时间的关系，以及多核环境下负载均衡与调度域的运作机制。

4.1 CFS调度器核心原理

4.1.1 核心原理：从“时间片”到“虚拟时间”

传统调度器（如O(1)）为每个进程分配固定的时间片，时间片耗尽则切换到下一个进程。这种方式存在明显缺陷：时间片大小难以动态调整，交互式进程（I/O密集）与计算密集型进程的体验难以兼顾。CFS彻底摒弃了“时间片”概念，转而引入“虚拟运行时间”（vruntime）作为调度决策的唯一依据。

CFS维护一棵以vruntime为键值的红黑树，每次调度时选择vruntime最小的进程（即红黑树最左节点）运行。vruntime的增长速率与进程的优先级（权重）成反比：高优先级进程的vruntime增长慢，因此能获得更多的CPU时间；低优先级进程的vruntime增长快，运行时间被压缩。这种设计使得所有进程的vruntime在宏观上趋于相等，从而实现“完全公平”。

  关键公式：

  vruntime += delta_exec * NICE_0_LOAD / se.weight

  其中 delta_exec 为实际运行时间，NICE_0_LOAD 为nice值0对应的权重（1024），se.weight 为当前进程的权重。权重越大，vruntime增长越慢。

4.1.2 调度周期与最小粒度

CFS通过调度周期（sched_period）和最小粒度（min_granularity）两个参数控制调度频率。调度周期保证每个可运行进程至少获得一次运行机会，其计算公式为：

sched_period = max(min_granularity * nr_running, sysctl_sched_latency)
// sysctl_sched_latency 默认6ms，min_granularity 默认0.75ms

当运行进程数较少时，调度周期固定为6ms；当进程数增多时，调度周期按比例扩展，但每个进程获得的时间片不低于0.75ms，以避免频繁切换带来的开销。

4.1.3 新进程与睡眠进程的vruntime处理

新创建的进程其vruntime初始值并非0，而是当前运行队列中vruntime的最小值，防止新进程抢占过多CPU时间。当进程睡眠（I/O等待）时，其vruntime保持不变；唤醒后，由于vruntime较小，会优先获得CPU，这保证了交互式进程的响应速度。但为了防止睡眠进程长期霸占CPU，内核会在唤醒时对vruntime进行一定的补偿或惩罚（通过sched_vslice计算）。

4.1.4 常见误区与调优方向

误区：认为nice值直接决定CPU时间百分比。实际上nice值映射为权重，影响的是vruntime的增长速率，最终效果是CPU时间的比例分配，而非值。
误区：认为CFS没有优先级。CFS的优先级体现在权重上，nice值范围-20~19，对应权重从88761到15，差距巨大。
调优：对于延迟敏感型应用（如数据库），可适当调低sysctl_sched_min_granularity，但需注意增加上下文切换开销。

4.2 调度策略：SCHED_NORMAL、SCHED_FIFO、SCHED_RR

4.2.1 三种策略的定位与区别

Linux内核将进程分为两类：普通进程（使用CFS调度）和实时进程（使用RT调度）。实时进程的优先级（0~99）始终高于普通进程（100~139）。三种调度策略的对比见表4-1。

策略	调度类	优先级范围	时间片	适用场景
SCHED_NORMAL	CFS	100~139 (nice -20~19)	动态（基于vruntime）	普通应用、交互式进程
SCHED_FIFO	RT	0~99	无（运行直到阻塞或主动让出）	工业控制、紧急任务
SCHED_RR	RT	0~99	固定（默认100ms）	需要轮转的实时任务

4.2.2 SCHED_FIFO与SCHED_RR的行为差异

SCHED_FIFO（先入先出）一旦获得CPU，除非自身阻塞、主动调用sched_yield()或被更高优先级的实时进程抢占，否则将一直运行。这保证了最低的调度延迟，但若进程陷入死循环，则可能饿死同优先级的其他进程。SCHED_RR（轮转）在FIFO基础上增加了时间片限制，时间片耗尽后进程被放入同优先级队列尾部，实现轮流执行。

风险提示：实时进程优先级高于普通进程，若实时进程占用CPU时间过长，会导致普通进程（包括系统关键进程如sshd）无法运行，系统可能“假死”。务必谨慎使用实时调度策略。

4.2.3 实时进程的调度时机

实时进程的调度遵循“优先级最高的就绪进程先运行”原则。内核维护一个位图（rt_priority）来快速查找最高优先级的实时进程。当实时进程被唤醒时，会立即检查是否可抢占当前进程；若可抢占，则触发调度。实时进程的vruntime机制不适用，其调度完全基于优先级。

4.2.4 案例：实时策略的误用与恢复

场景：某嵌入式设备中，开发人员将采集线程设置为SCHED_FIFO优先级50，但该线程因bug陷入死循环，导致系统控制台无响应。

分析：由于实时进程不降级，普通进程（包括shell）无法获得CPU，系统看似死机。

解决：通过内核魔法键（SysRq）或硬件看门狗重启系统，并在代码中增加超时退出机制。更安全的做法是使用SCHED_RR并设置合理的时间片，或使用SCHED_NORMAL配合nice值。

复盘：实时调度策略应仅用于经过严格测试的短小任务，且必须设置看门狗或超时保护。

4.3 调度实体与虚拟运行时间

4.3.1 调度实体的数据结构

在Linux内核中，task_struct内嵌了sched_entity结构体（通常称为se），它包含了调度所需的全部信息：

struct sched_entity {
    struct load_weight      load;       // 权重
    struct rb_node          run_node;   // 红黑树节点
    unsigned int            on_rq;      // 是否在就绪队列
    u64                     vruntime;   // 虚拟运行时间
    u64                     prev_sum_exec_runtime; // 上次运行累计时间
    // ... 其他字段
};

4.3.2 权重与nice值的映射

内核通过sched_prio_to_weight数组将nice值映射为权重。nice值每降低1（优先级提高），权重约增加1.25倍；nice值每增加1，权重约减少0.8倍。例如：

nice值	权重	相对CPU时间比例（与nice 0相比）
-20	88761	约86.7倍
-10	11084	约10.8倍
0	1024	1倍
10	95	约0.09倍
19	15	约0.015倍

4.3.3 虚拟时间的计算与更新

每次时钟中断（通常为1ms或4ms）时，内核调用update_curr()更新当前进程的vruntime。更新公式为：

delta_exec = now - curr->exec_start;
curr->vruntime += delta_exec * NICE_0_LOAD / curr->load.weight;
curr->exec_start = now;

当进程被调度走时，其prev_sum_exec_runtime会累加本次运行时间，用于统计和负载计算。

4.3.4 红黑树的操作与调度延迟

CFS就绪队列（cfs_rq）维护一棵红黑树，插入和删除操作的时间复杂度为O(log n)。调度器选择最左节点（vruntime最小）作为下一个运行进程。为了减少树的操作次数，内核引入了leftmost缓存指针，直接指向最左节点，使选择操作变为O(1)。

经验：在进程数极多（如数千个）的服务器场景下，红黑树的插入/删除开销不可忽视。可通过sched_autogroup特性将相关进程分组，减少调度实体数量。

4.4 负载均衡与调度域

4.4.1 调度域（Scheduling Domain）的层级结构

现代多核CPU具有复杂的缓存层次结构（L1/L2/L3）和NUMA拓扑。内核通过调度域描述CPU之间的亲缘关系，每个调度域包含多个调度组。典型的层级为：

SMT域：同一物理核的超线程兄弟CPU。
MC域：同一物理封装内的所有核（共享L3缓存）。
NUMA域：同一NUMA节点内的所有CPU（共享内存带宽）。

4.4.2 负载均衡的触发时机与策略

负载均衡分为周期性均衡和空闲时均衡。周期性均衡由调度器tick触发，检查当前CPU的负载是否与域内其他CPU差距过大（超过sysctl_sched_migration_cost阈值）。空闲时均衡发生在CPU进入空闲状态时，主动从其他繁忙CPU拉取任务。

均衡操作的核心是任务迁移，但迁移并非随意进行，需考虑以下因素：

缓存亲和性：优先迁移到共享缓存的CPU，避免缓存失效。
NUMA距离：跨NUMA节点迁移代价高，仅在负载严重不均时进行。
任务类型：实时任务通常不参与负载均衡（除非设置了SCHED_RR且允许迁移）。

4.4.3 负载均衡的算法：从“最忙组”拉取任务

内核使用find_busiest_group()和find_busiest_queue()函数定位最繁忙的调度组和CPU队列。然后通过load_balance()函数从该队列迁移一定数量的任务到当前CPU。迁移数量由group_imbalance和avg_load计算得出，避免过度迁移导致抖动。

4.4.4 案例：NUMA架构下的性能调优

背景：某数据库服务器采用2路NUMA架构（每路16核），运行OLTP负载。初期性能不佳，CPU利用率不均（Node0的CPU0~7利用率90%，Node1的CPU8~15利用率30%）。

分析：通过numastat和perf sched工具发现，大量内存分配在Node0，导致Node0的CPU因访问本地内存而繁忙，Node1的CPU因跨节点访问内存延迟高而空闲。

操作：1) 使用numactl --interleave=all启动数据库进程，使内存均匀分布；2) 调整内核参数kernel.numa_balancing=1启用自动NUMA均衡；3) 将数据库进程绑定到Node0的CPU，利用taskset固定CPU亲和性。

结果：CPU利用率趋于均衡（Node0约70%，Node1约65%），事务吞吐量提升22%。

复盘：负载均衡不仅考虑CPU负载，还需结合内存访问延迟。在NUMA系统中，sched_domain的配置直接影响均衡策略，必要时可通过sysctl调整sched_domain的busy_factor和imbalance_pct参数。

4.4.5 常见误区与总结

误区：认为负载均衡是“平均”。实际上，内核允许一定程度的负载不均（默认imbalance_pct为125%，即允许25%的偏差），以避免频繁迁移。
误区：忽略CPU隔离（isolcpus）。对于实时或高性能计算任务，可通过内核启动参数isolcpus=2,3将CPU从调度域中隔离，避免被普通任务抢占。
总结：CFS通过虚拟时间实现公平，实时策略提供确定性延迟，负载均衡则确保多核资源的高效利用。理解这三者的协同关系，是进行Linux性能调优的基础。