2. Linux内核调度器演进

Linux 内核调度器经历了多次重大重构，每一次演进都针对特定负载场景下的性能瓶颈。理解这一演进过程，是掌握实时调度与 Deadline 调度设计背景的前提。

2.1 早期调度器：O(n) 调度器（Linux 2.4 及之前）

O(n) 调度器是 Linux 内核最早的通用调度器，其核心设计围绕一个全局运行队列展开。

• 数据结构：所有可运行进程被放入一个全局链表。
• 调度算法：每次选择下一个要运行的进程时，调度器必须遍历整个链表，计算每个进程的“好度”（goodness），选出最大值。
• 时间复杂度：O(n)，其中 n 为系统中可运行进程的数量。

2.2 O(1) 调度器（Linux 2.6.0 - 2.6.22）

为解决 O(n) 调度器的性能问题，Ingo Molnár 在 Linux 2.6 内核中引入了 O(1) 调度器。

• 核心数据结构：每个 CPU 维护两个优先级数组（active 和 expired），每个优先级对应一个 FIFO 队列。
• 算法：通过位图（bitmap）在常数时间内找到最高优先级的非空队列，调度时间复杂度降为 O(1)。
• 时间片：基于优先级静态分配时间片，高优先级进程获得更长的时间片。

2.3 CFS 完全公平调度器（Linux 2.6.23 至今）

CFS 由 Con Kolivas 的“楼梯调度器”启发，由 Ingo Molnár 实现，旨在提供真正的公平调度。

• 核心思想：模拟“理想的多任务处理器”，让每个进程获得 1/n 的 CPU 时间。
• 数据结构：使用红黑树（Red-Black Tree）组织进程，键值为 vruntime（虚拟运行时间）。
• 算法：调度器选择红黑树中最左侧节点（vruntime 最小）的进程运行。每次时钟中断更新当前进程的 vruntime。
• 权重：通过 nice 值映射权重，权重高的进程 vruntime 增长慢，从而获得更多 CPU 时间。

2.4 实时调度类（RT）的引入背景

尽管 CFS 在通用场景下表现出色，但它无法满足硬实时应用的需求。CFS 的公平性目标与实时任务的确定性需求存在根本冲突。

• 实时任务需求：要求可预测的响应时间、确定的调度延迟，以及优先级驱动的抢占行为。
• CFS 的不足：CFS 基于 vruntime 的公平调度策略无法保证高优先级任务的立即执行，因为 vruntime 的累积效应可能导致低优先级任务暂时“饿死”高优先级任务。
• 解决方案：引入独立的 实时调度类（RT），使用 SCHED_FIFO 和 SCHED_RR 策略，优先级范围 0-99（数值越小优先级越高），严格抢占 CFS 任务。

2.5 Deadline 调度类（SCHED_DEADLINE）的引入背景

随着多媒体、工业控制、自动驾驶等领域的快速发展，系统对确定性调度的需求进一步提升。传统的固定优先级调度（如 SCHED_FIFO/RR）存在以下问题：

• 优先级反转：高优先级任务被低优先级任务阻塞，导致不可预测的延迟。
• 缺乏时序保证：固定优先级无法直接表达任务的截止时间（deadline）需求。
• 利用率控制困难：无法精确保证 CPU 利用率不超过 100%，可能导致任务集不可调度。

SCHED_DEADLINE 基于 最早截止时间优先（EDF） 算法，结合 常量带宽服务器（CBS） 机制，为每个任务指定 runtime、deadline 和 period 参数，提供确定性的调度保证。

2.6 演进总结

Linux 内核调度器的演进反映了从“通用性能优化”到“多样化负载确定性保证”的转变：

1. O(n) → O(1)：解决大规模进程下的调度性能瓶颈，引入每 CPU 数据结构提升 SMP 扩展性。
2. O(1) → CFS：摒弃复杂的交互性启发式，采用基于 vruntime 的公平调度模型，提升桌面和服务器负载的响应一致性。
3. CFS → RT + Deadline：在通用公平调度器之上，引入专用调度类以满足实时和时序确定性需求。RT 调度类提供固定优先级抢占，Deadline 调度类提供基于 EDF 的时序保证。