【操作系统 OS】什么是Linux CFS？完全公平调度器是什么？

Linux CSF 简介

Linux 中 CFS 的全称是 Completely Fair Scheduler，完全公平调度器，是 Linux 内核中的一种进程调度算法。

CFS 的主要特性：

• 公平性
  • CFS 的核心理念是通过确保所有进程能够公平地获得 CPU 时间来实现公平调度。使用一个虚拟时钟（Virtual Runtime）来跟踪每个进程使用 CPU 的时间。理论上，所有进程的虚拟时钟应该接近相等。
• O(log N) 复杂度
  • CFS 通过红黑树（red-black tree）数据结构管理进程，确保调度操作的复杂度为 O(log N)，其中 N 是系统中可调度的进程数量。
• 精确调度
  • CFS 通过使用微观调度周期（调度片）来精细控制每个进程的 CPU 使用时间。每个调度周期内，进程可以运行一小段时间，这段时间称为时间片。
• 优先级支持
  • CFS 支持传统的静态优先级（nice 值）和实时优先级。静态优先级影响进程的虚拟运行时间，使得具有较高静态优先级的进程相对于低优先级进程获得更多的 CPU 时间。

CFS 的工作原理

1. 虚拟运行时间（vruntime）：
   1. CFS 为每个进程分配一个虚拟运行时间，记录进程使用的 CPU 时间。虚拟运行时间是调度决策的关键指标，具有较少虚拟运行时间的进程将优先获得 CPU 时间。
2. 红黑树调度：
   1. 所有可调度的进程按虚拟运行时间存储在红黑树中，树的根节点是虚拟运行时间最小的进程。当 CFS 需要调度一个新的进程时，它从红黑树的最左节点（虚拟运行时间最小的节点）选择。
3. 调度决策：
   1. CFS 定期检查当前正在运行的进程和红黑树中下一个进程的虚拟运行时间。如果发现红黑树中有虚拟运行时间更少的进程，则进行上下文切换，将 CPU 分配给该进程。
4. 时间片计算：
   1. CFS 动态计算每个进程的时间片，根据系统负载和进程优先级调整。时间片越长，进程能在一次调度中运行的时间越长。

使用和配置

CFS 自动管理大多数调度任务，无需用户干预。但用户可以通过调整一些调度相关的内核参数（如 sched_latency_ns, sched_min_granularity_ns）来影响调度行为。这些参数控制调度周期的长度和最小时间片的大小。

优势和应用场景

• 多任务处理：CFS 适用于需要公平分配 CPU 资源的多任务环境。
• 桌面和服务器应用：因其公平性和低复杂度，CFS 在桌面系统和服务器中广泛应用，适合多种工作负载，包括交互式应用和后台服务。
• 实时应用的支持：虽然 CFS 主要设计用于普通进程调度，它也支持实时调度类（如 SCHED_FIFO 和 SCHED_RR），这些类有更高的优先级，但需要更细粒度的控制。

CFS 中如何使用红黑树？

红黑树存储着系统中所有就绪进程（处于可运行状态但未在运行的进程），按照每个进程的虚拟运行时间（vruntime）排序。vruntime是一个概念上的时间度量，用来衡量进程在系统中运行了多长时间。较小的vruntime意味着进程运行时间较短，需要获得更多的 CPU 时间。

CFS 如何定期检查红黑树

CFS 定期检查红黑树的主要目的是确定是否需要进行上下文切换（即更换运行中的进程）。这种检查过程涉及以下几个关键步骤：

1. 时钟中断：CFS 的调度决策主要由系统的时钟中断（通常是周期性发生的定时中断）驱动。每当时钟中断发生时，系统会进入调度程序，这个过程被称为“时钟滴答”。
2. 更新 vruntime：时钟中断发生时，CFS 会更新当前正在运行的进程的vruntime，因为该进程已经使用了一段 CPU 时间。vruntime的增长速度由进程的优先级决定，优先级较高的进程增长速度较慢，优先级较低的增长速度较快。
3. 检查红黑树：CFS 会检查红黑树的根节点，这个节点是vruntime最小的可运行进程。这是因为在红黑树的性质下，树的根节点始终是最小值（最左边的节点）。
4. 比较 vruntime：调度器将当前运行进程的vruntime与红黑树根节点（下一个要运行的进程）的vruntime进行比较。如果当前运行的进程的vruntime显著大于红黑树中的最小vruntime，调度器会认为需要进行进程切换，以确保系统中的所有进程都能公平地获得 CPU 资源。
5. 进行上下文切换：如果需要切换，CFS 会将当前进程移入红黑树，并从红黑树中选择vruntime最小的进程作为下一个运行的进程。

关键点总结

• 时钟中断驱动：CFS 的调度检查主要由时钟中断触发，定期执行。
• 红黑树的角色：红黑树帮助 CFS 快速找到最需要 CPU 时间的进程。
• vruntime：是调度决策的核心指标，反映进程的 CPU 使用时间。
• 公平性：通过不断地选择vruntime最小的进程，CFS 尽可能地实现 CPU 时间分配的公平性。

CFS 通过这种机制平衡了系统中所有进程的 CPU 使用，使得所有进程都能按照其优先级和需要公平地获得运行机会。