内核调度器debugfs调试接口与性能分析实践 - 第1节

1.1 调度器概述：从 O(1) 到 EEVDF 的演进

Linux 内核调度器是操作系统的核心组件，负责在多个可运行进程之间公平、高效地分配 CPU 时间。其演进历史反映了从“吞吐优先”到“公平与低延迟并重”，再到“面向延迟敏感负载”的设计哲学变迁。本节将梳理三大里程碑调度器及其核心设计思想。

1.1.1 调度器演进时间线

1.1.2 O(1) 调度器：可扩展性的奠基者

O(1) 调度器是 Linux 2.6 早期版本的默认调度器，其名称来源于调度决策的时间复杂度为常数 O(1)，与系统中进程总数无关。它使用两个优先级数组（active 和 expired）来管理 140 个优先级队列（0-99 为实时，100-139 为普通）。

• 核心机制： 每个 CPU 维护两个位图（bitmap），通过 __ffs 指令快速找到最高优先级非空队列。
• 时间片分配： 静态时间片 + 优先级映射表，高优先级进程获得更长的时间片。
• 主要缺陷： 交互式进程识别启发式复杂、时间片分配粒度粗糙、公平性不足。

1.1.3 CFS：公平性的革命

CFS 由 Ingo Molnár 在 2007 年引入，彻底抛弃了固定时间片和优先级数组，转而使用红黑树（Red-Black Tree）按虚拟运行时间（vruntime）排序。vruntime 是进程实际运行时间经过优先级加权的值，CFS 总是选择 vruntime 最小的进程运行。

• 核心公式： vruntime += 实际运行时间 × (NICE_0_LOAD / 进程权重)。
• 调度粒度： 目标延迟（targeted latency）和最小粒度（min_granularity）控制抢占频率。
• 组调度： 引入 task_group 实现 CPU 带宽的层级分配（cgroup cpu.shares）。

1.1.4 EEVDF：延迟感知的新一代调度器

EEVDF 在 Linux 6.6 中作为可选调度器引入，基于 Peter Zijlstra 的补丁集。它保留了 CFS 的红黑树结构，但将排序键从 vruntime 替换为虚拟截止时间（virtual deadline），并引入滞后（lag）追踪机制来保证抢占公平性。

• 核心概念： 每个进程维护一个虚拟截止时间 vd = ve + (slice / weight)，其中 ve 是虚拟开始时间，slice 是时间片。
• 抢占条件： 当运行进程的剩余时间片大于下一个可运行进程的虚拟截止时间时，触发抢占。
• 优势： 提供更严格的延迟边界，减少交互式进程的调度抖动，对延迟敏感负载（如游戏、音视频）更友好。

1.2 调度类与调度策略

Linux 内核使用调度类（Scheduling Class）实现可扩展的调度架构。每个调度类实现一组通用的调度器接口，内核通过 pick_next_task 按优先级顺序遍历调度类，选择最高优先级的可运行进程。

1.2.1 调度类层次结构

1.2.2 调度策略详解

• SCHED_NORMAL (SCHED_OTHER)： 默认策略，由 fair_sched_class 管理，使用 CFS/EEVDF 算法，适用于绝大多数用户进程。
• SCHED_BATCH： 类似 SCHED_NORMAL，但调度器假设进程是 CPU 密集型的，减少抢占次数以提升缓存命中率。
• SCHED_IDLE： 极低优先级，仅在 CPU 空闲时运行，适用于后台低优先级任务。
• SCHED_FIFO： 实时先进先出，优先级范围 1-99，进程一旦运行将持续到主动让出或被更高优先级实时进程抢占。
• SCHED_RR： 实时轮转，类似 SCHED_FIFO 但增加了时间片限制，相同优先级进程轮转执行。
• SCHED_DEADLINE： 使用 EDF (Earliest Deadline First) 算法，进程必须指定运行时间、周期和截止时间，提供硬实时保证。

1.2.3 调度策略与优先级数值

实时策略（SCHED_FIFO、SCHED_RR、SCHED_DEADLINE）的优先级范围为 1-99，数值越大优先级越高。普通策略（SCHED_NORMAL、SCHED_BATCH、SCHED_IDLE）的优先级通过 nice 值（-20 到 19）间接控制，nice 值越小，进程获得的 CPU 时间越多。