Linux 完全公平调度器简介（CFS）

一、发展历史：从“优先级时代”到“公平时代”

在计算机操作系统的发展历程中，进程调度始终是核心难题。早期的 Unix 系统（如 BSD）采用基于优先级和时间片轮转的调度策略：系统为每个进程分配固定优先级和时间片，高优先级进程能抢占低优先级进程。这种设计的优势是直观可控，但缺点明显：

• 交互式应用响应延迟：若未手动调整优先级，交互式应用（如文本编辑器）可能因时间片耗尽而卡顿。
• 公平性缺失：后台计算任务（如视频编码）可能长期霸占 CPU，导致系统整体响应性下降。

2003 年，Linux 引入 O(1) 调度器，通过优先级队列和动态时间片调整优化了扩展性，但仍未解决公平性问题。直到 2007 年，开发者 Ingo Molnar 提出完全公平调度器（CFS），彻底颠覆了传统设计理念，成为 Linux 内核（2.6.23 版本后）的核心调度器。

---

二、CFS 核心原理：虚拟时间的艺术

CFS 的核心理念是所有进程公平共享 CPU 资源，但并非简单均分时间，而是通过动态调整实现“公平补偿”。其核心机制包括：

1. 虚拟运行时间（vruntime）
   • 定义：每个进程的虚拟运行时间 = 实际运行时间 × 权重系数（权重由进程的 nice 值决定）。
   • 公平性逻辑：系统维护一个按 vruntime 排序的红黑树，优先调度 vruntime 最小的进程。例如：
     • 若文本编辑器（高交互性）和视频解码器（计算密集型）具有相同 nice 值，它们的初始权重相等，理想情况下各占 50% CPU。
     • 文本编辑器因频繁等待用户输入，实际运行时间远小于视频解码器，其 vruntime 增长缓慢，从而在唤醒时优先被调度。
2. 动态补偿机制
   • 睡眠进程补偿：当进程休眠时，其 vruntime 暂停增长。唤醒后，系统通过对比其 vruntime 与当前运行进程的 vruntime，决定是否立即抢占 CPU。
   • 案例：文本编辑器休眠时，视频解码器的 vruntime 持续增长；当用户输入到来，文本编辑器的 vruntime 显著低于视频解码器，触发抢占。
3. 时间粒度与精度
   CFS 采用纳秒级计时器和动态时间片，替代传统的固定时间片。进程每次运行的时间由系统负载和优先级动态计算，确保高精度调度。