Linux 内核进程调度器深度解析：从 CFS 到 EEVDF 的演进之路

进程调度是操作系统内核最核心的组件之一。它负责决定哪个进程在何时获得 CPU 时间片，直接影响系统的吞吐量、响应速度和公平性。Linux 内核的调度器经历了从简单的 O(n) 调度器，到 O(1) 调度器，再到完全公平调度器（CFS），以及最新的 EEVDF（Earliest Eligible Virtual Deadline First）的演进。本文将深入剖析 Linux 进程调度器的核心机制与最新发展。

一、调度器的基本职责

CPU 是计算机最宝贵的资源之一。在单核系统中，任何时刻只能有一个进程在运行，调度器需要在多个就绪进程之间做出选择；在多核系统中，调度器还需要考虑负载均衡、CPU 亲和性、缓存局部性等复杂因素。

调度器的核心目标可以概括为以下三点：

• 高吞吐量：在单位时间内完成尽可能多的工作
• 低延迟：交互式任务能够快速响应用户输入
• 公平性：所有进程按权重合理分配 CPU 时间

这三个目标往往相互矛盾。例如，最大化吞吐量可能需要减少上下文切换，但这会损害交互式应用的响应延迟。优秀的调度策略需要在不同场景下取得平衡。

二、CFS：完全公平调度器

2.1 核心思想

CFS（Completely Fair Scheduler）自 Linux 2.6.23 内核（2007 年）起成为默认的进程调度类。它的设计灵感来自"理想多任务处理器"的概念：如果有 N 个进程，每个进程应该获得 1/N 的 CPU 时间。

CFS 引入了虚拟运行时间（vruntime）的概念。每个进程维护一个 vruntime 值，表示该进程在虚拟时钟下的运行时间。调度器每次选择 vruntime 最小的进程运行，从而实现"完全公平"。

vruntime  = 实际运行时间 / 进程权重

权重越高的进程（nice 值越低），vruntime 增长越慢，从而获得更多的实际 CPU 时间。

2.2 红黑树数据结构

CFS 使用红黑树（Red-Black Tree）来组织所有可运行进程。红黑树是一种自平衡二叉搜索树，能够以 O(log n) 的时间复杂度完成插入、删除和查找最小值操作。

• 树的键值：进程的 vruntime
• 最左侧节点：vruntime 最小的进程，即下一个被调度的进程
• 插入/删除：进程唤醒或阻塞时更新树结构

这种设计使得 CFS 可以高效地从成千上万个进程中挑选出最适合运行的那一个。

2.3 调度粒度与抢占

CFS 不是严格轮转的。它通过时间片分配和抢占机制来实现公平：

• 目标延迟（target_latency）：默认为 20ms，所有可运行进程应在此周期内至少运行一次
• 最小粒度（min_granularity）：默认为 1ms，避免过度上下文切换
• 当前进程用完了分配的时间后，如果存在 vruntime 更小的进程，则发生抢占

2.4 组调度（Group Scheduling）

CFS 支持组调度，可以将 CPU 资源在不同用户组之间按比例分配。每个组拥有自己的带宽配额（bandwidth quota），通过 cgroup 的 cpu 子系统进行配置。

# 设置组在周期 100ms 内最多使用 50ms CPU 时间
echo 50000