Linux CFS 调度器与实时调度机制深度剖析：从 vruntime 到 SCHED_DEADLINE

一、调度器演进历史：从O(n)到CFS

操作系统调度器的发展史是一段不断追求“公平性”与“效率”平衡的历程。Linux内核调度器经历了多次重大架构重构：

第一代：O(n)调度器

早期Linux 0.11到2.4时期，调度器采用简单的轮询算法。每次选择下一个运行进程时，需要遍历所有就绪进程，计算它们的 counter（动态优先级）。当进程数目增多时，O(n)的时间复杂度会成为系统瓶颈。

第二代：O(1)调度器

Linux 2.5/2.6初期引入了O(1)调度器，由Ingo Molnar设计。它的核心特点是维护140个优先级队列（0-99对应实时进程，100-139对应普通进程），使用 bitmap 标记有效队列，可以在常数时间内找到最高优先级的就绪进程。

但这种方案存在明显缺陷：预测“交互式”进程的处理过于粗粝，以“睡眠时间”作为判断依据，导致服务器场景中的响应延迟不稳定。

第三代：CFS完全公平调度器

Linux 2.6.23以后，Con Kolivas提出的CFS（Completely Fair Scheduler，完全公平调度器）接替O(1)成为默认的普通进程调度器。CFS的核心概念是摇摆的：它不维护因定的时间片，而是记录每个进程的虚拟运行时间，委托最“不公平”（虚拟运行时间最小）的进程来运行。

二、CFS核心架构

CFS的架构关键包括以下几个方面：

1. 虚拟运行时间(vruntime)

vruntime是CFS的核心指标，用于表示一个进程理应获得的CPU时间。它的计算在内核中通过 update_curr() 实现：

vruntime = (实际运行时间) × (NICE_0_LOAD / se.weight)

其中 NICE_0_LOAD 是基准权重(1024)，se.weight 是当前进程的权重。优先级越高的进程，其权重越大，虚拟时间推进越慢，从而理应有更多的CPU时间。

2. 红黑树数据结构

CFS使用了一个红黑树（red-black tree）析来维护所有就绪进程的vruntime。每个CPU有一个 cfs_rq 队列，内核中全局的 fair_sched_class 负责管理学院些队列。

通过红黑树，CFS可以高效地实现以下操作：

- 插入：O(log n)，将新就绪进程插入树中

- 选择：O(1)，读取树最左侧节点（最小vruntime）的进程

- 删除：O(log n)，移出停止运行的节点

这比传统队列的O(n)遍历效率高得多。

3. 分级调度模型

内核采用了“调度类（sched class）”的架构来实现多等级优先应用。调度类从高到低：

- stop_sched_class：最高优先级，用于CPU停止等最紧急任务

- dl_sched_class：SCHED_DEADLINE，基于Deadline的时间片调度

- rt_sched_class：SCHED_FIFO/SCHED_RR，真实时间调度

- fair_sched_class：SCHED_NORMAL/SCHED_BATCH/SCHED_IDLE，CFS处理

- idle_sched_class：空闲任务，仅当全部为空时运行

调度时，从高优先级类开始遍历，直到找到就绪进程。这保证了实时任务对普通进程的绝对优先权。

三、实时调度类详解

Linux支持三种实时调度策略，通过 sched_setscheduler() 设置：

SCHED_FIFO — 先入先出

一个SCHED_FIFO进程运行时，会占据CPU直到：(1)该进程主动让步CPU；(2)有更高优先级的实时进程就绪；(3)该进程被中断。它没有时间片限制，是一种无时间片的最简单算法。

SCHED_RR — 旋转片

SCHED_RR在SCHED_FIFO基础上增加了时间片机制。同优先级的进程共享一个时间配额，默认计划为100ms（sched_rr_timeslice）。时间片轮转后，该进程被推到同优先级队列末尾，等待下一轮时间片。

SCHED_DEADLINE — 截止时间优先（Linux 3.14 ）

这是最先进的实时调度类，基于Earliest Deadline First（EDF）算法。每个任务定义三个参数：

- runtime (μs)：每周期内最大运行时间

- deadline (μs)：任务必须在此时间内完成

- period (μs)：周期长度，通常 equal to deadline

它利用 Bandwidth 机制，确保所有实时任务的：

q = runtime / period