操作系统中的进程调度算法：完全公平调度器（Completely Fair Scheduler, CFS）详解
字数 2086 2025-12-07 21:46:49

操作系统中的进程调度算法：完全公平调度器（Completely Fair Scheduler, CFS）详解

1. 知识点描述
完全公平调度器（CFS）是Linux内核中默认的进程调度算法，用于普通进程（非实时进程）的调度。它的核心设计理念是模拟“理想多任务处理器”，让每个进程都能公平地获得CPU时间。与传统的基于时间片轮转或静态优先级的调度器不同，CFS不直接分配时间片，而是通过维护每个进程的虚拟运行时间（vruntime）来衡量其已获得的CPU量，并总是选择vruntime最小的进程来运行，从而实现近似完美的公平性。

2. 核心概念：公平性与虚拟运行时间

  • 公平性目标：如果有n个优先级相同的进程，每个进程应获得1/n的CPU时间。
  • 虚拟运行时间（vruntime）：CFS为每个进程维护一个vruntime值，表示该进程在CPU上已运行的“虚拟时间”。虚拟时间的流逝速度与进程的优先级（nice值）成反比：高优先级进程的vruntime增长更慢，低优先级进程增长更快。这样，CFS通过比较vruntime来选择“最需要CPU”的进程（即vruntime最小的进程）。

3. CFS的数据结构：红黑树

  • CFS使用红黑树（一种自平衡二叉搜索树）来组织可运行进程。树中的节点按键值（vruntime）排序。
  • 每个CPU核心维护一棵红黑树，树中最左侧的节点（即vruntime最小的进程）是下一个要调度的进程。
  • 进程被加入红黑树时，按其当前vruntime插入；当进程被调度运行时，会从树中移除，运行一段时间后更新vruntime并重新插入（如果仍可运行）。

4. 调度过程循序渐进解析
步骤1：选择下一个进程
调度器查看当前CPU的红黑树，取出最左侧节点对应的进程（即vruntime最小的进程）。这保证了所有可运行进程中“最欠CPU时间”的进程获得运行机会。

步骤2：计算实际运行时间
CFS不预设固定时间片，而是根据以下因素动态计算目标运行时间：

  • 调度延迟：所有可运行进程至少运行一次的目标时间间隔（默认6ms）。
  • 进程数量：如果系统有n个可运行进程，每个进程的目标运行时间为“调度延迟 / n”。
  • 最小粒度：为防止过多上下文切换，进程至少运行0.75ms（可配置）。
    实际运行时间取目标运行时间和最小粒度中的较大值。

步骤3：更新vruntime
进程运行实际时间后，更新其vruntime：
vruntime += 实际运行时间 * (NICE_0_LOAD / 进程权重)

  • NICE_0_LOAD：标准优先级（nice=0）的权重。
  • 进程权重：由进程的nice值映射而来（nice值越小，优先级越高，权重越大）。
  • 公式效果：高权重进程的vruntime增长更慢，未来更易被选中；低权重进程增长更快，未来被选中机会减少。

步骤4：重新插入红黑树

  • 如果进程仍可运行（未睡眠或退出），将其按新vruntime重新插入红黑树。
  • 如果进程进入睡眠（如等待I/O），其vruntime不变，唤醒后插入红黑树时，vruntime较小，能快速获得CPU（体现交互式进程友好性）。

5. 处理新进程和唤醒进程

  • 新进程创建：初始vruntime设为当前红黑树中最小vruntime值，避免新进程因vruntime=0而长期垄断CPU。
  • 睡眠进程唤醒：vruntime保持不变，但CFS会将其与当前最小vruntime比较，如果差值超过阈值，则重置为最小vruntime，防止过度追赶导致饥饿。

6. 优先级处理（nice值映射）
CFS将用户空间的nice值（-20到19）映射为权重。nice值每降低1（优先级升高），权重增加约10%，使高优先级进程多获得约10%的CPU时间。通过权重调节vruntime增长速度，间接实现优先级区分。

7. 多处理器负载均衡
CFS与Linux的调度域机制结合，通过定期检查各CPU负载，将进程从繁忙CPU迁移到空闲CPU，保持多核间的负载均衡。

8. 优点总结

  • 公平性：长期看，所有进程获得CPU时间比例由其权重决定。
  • 低开销：红黑树操作复杂度为O(log n)，高效选择进程。
  • 交互性：睡眠进程（如I/O密集型）唤醒后能快速响应。
  • 可配置：通过调度参数（如调度延迟、最小粒度）调节权衡公平性与吞吐量。

9. 实例说明
假设系统有3个优先级相同的进程A、B、C，调度延迟为6ms。

  • 目标运行时间 = 6ms / 3 = 2ms（大于最小粒度0.75ms）。
  • 初始A运行2ms，vruntime增加2ms；接着B运行2ms，vruntime增加2ms；然后C运行2ms。此时三者的vruntime接近，A再次成为最小vruntime进程，继续循环。
  • 如果A优先级更高（权重更大），其vruntime增长更慢（如1ms虚拟时间对应1.5ms实际运行），从而获得更多CPU时间。

通过上述机制，CFS在保证公平性的同时，兼顾了优先级、交互性和多核扩展性，成为现代Linux系统的核心调度算法。

操作系统中的进程调度算法：完全公平调度器（Completely Fair Scheduler, CFS）详解 1. 知识点描述 完全公平调度器（CFS）是Linux内核中默认的进程调度算法，用于普通进程（非实时进程）的调度。它的核心设计理念是模拟“理想多任务处理器”，让每个进程都能公平地获得CPU时间。与传统的基于时间片轮转或静态优先级的调度器不同，CFS不直接分配时间片，而是通过维护每个进程的虚拟运行时间（vruntime）来衡量其已获得的CPU量，并总是选择vruntime最小的进程来运行，从而实现近似完美的公平性。 2. 核心概念：公平性与虚拟运行时间 公平性目标 ：如果有n个优先级相同的进程，每个进程应获得1/n的CPU时间。 虚拟运行时间（vruntime） ：CFS为每个进程维护一个vruntime值，表示该进程在CPU上已运行的“虚拟时间”。虚拟时间的流逝速度与进程的优先级（nice值）成反比：高优先级进程的vruntime增长更慢，低优先级进程增长更快。这样，CFS通过比较vruntime来选择“最需要CPU”的进程（即vruntime最小的进程）。 3. CFS的数据结构：红黑树 CFS使用 红黑树 （一种自平衡二叉搜索树）来组织可运行进程。树中的节点按键值（vruntime）排序。 每个CPU核心维护一棵红黑树，树中最左侧的节点（即vruntime最小的进程）是下一个要调度的进程。 进程被加入红黑树时，按其当前vruntime插入；当进程被调度运行时，会从树中移除，运行一段时间后更新vruntime并重新插入（如果仍可运行）。 4. 调度过程循序渐进解析 步骤1：选择下一个进程 调度器查看当前CPU的红黑树，取出最左侧节点对应的进程（即vruntime最小的进程）。这保证了所有可运行进程中“最欠CPU时间”的进程获得运行机会。 步骤2：计算实际运行时间 CFS不预设固定时间片，而是根据以下因素动态计算目标运行时间： 调度延迟 ：所有可运行进程至少运行一次的目标时间间隔（默认6ms）。 进程数量 ：如果系统有n个可运行进程，每个进程的目标运行时间为“调度延迟 / n”。 最小粒度 ：为防止过多上下文切换，进程至少运行0.75ms（可配置）。 实际运行时间取目标运行时间和最小粒度中的较大值。 步骤3：更新vruntime 进程运行实际时间后，更新其vruntime： vruntime += 实际运行时间 * (NICE_0_LOAD / 进程权重) NICE_ 0_ LOAD ：标准优先级（nice=0）的权重。 进程权重 ：由进程的nice值映射而来（nice值越小，优先级越高，权重越大）。 公式效果：高权重进程的vruntime增长更慢，未来更易被选中；低权重进程增长更快，未来被选中机会减少。 步骤4：重新插入红黑树 如果进程仍可运行（未睡眠或退出），将其按新vruntime重新插入红黑树。 如果进程进入睡眠（如等待I/O），其vruntime不变，唤醒后插入红黑树时，vruntime较小，能快速获得CPU（体现交互式进程友好性）。 5. 处理新进程和唤醒进程 新进程创建 ：初始vruntime设为当前红黑树中最小vruntime值，避免新进程因vruntime=0而长期垄断CPU。 睡眠进程唤醒 ：vruntime保持不变，但CFS会将其与当前最小vruntime比较，如果差值超过阈值，则重置为最小vruntime，防止过度追赶导致饥饿。 6. 优先级处理（nice值映射） CFS将用户空间的nice值（-20到19）映射为权重。nice值每降低1（优先级升高），权重增加约10%，使高优先级进程多获得约10%的CPU时间。通过权重调节vruntime增长速度，间接实现优先级区分。 7. 多处理器负载均衡 CFS与Linux的调度域机制结合，通过定期检查各CPU负载，将进程从繁忙CPU迁移到空闲CPU，保持多核间的负载均衡。 8. 优点总结 公平性 ：长期看，所有进程获得CPU时间比例由其权重决定。 低开销 ：红黑树操作复杂度为O(log n)，高效选择进程。 交互性 ：睡眠进程（如I/O密集型）唤醒后能快速响应。 可配置 ：通过调度参数（如调度延迟、最小粒度）调节权衡公平性与吞吐量。 9. 实例说明 假设系统有3个优先级相同的进程A、B、C，调度延迟为6ms。 目标运行时间 = 6ms / 3 = 2ms（大于最小粒度0.75ms）。 初始A运行2ms，vruntime增加2ms；接着B运行2ms，vruntime增加2ms；然后C运行2ms。此时三者的vruntime接近，A再次成为最小vruntime进程，继续循环。 如果A优先级更高（权重更大），其vruntime增长更慢（如1ms虚拟时间对应1.5ms实际运行），从而获得更多CPU时间。 通过上述机制，CFS在保证公平性的同时，兼顾了优先级、交互性和多核扩展性，成为现代Linux系统的核心调度算法。