2. Linux 内核调度器演进：从 O(n) 到实时调度类

Linux 内核调度器经历了从简单到复杂、从通用到实时的演进过程。理解这一演进脉络，是掌握嵌入式实时调度配置的基础。本章将依次剖析 O(n)、O(1)、CFS 以及实时调度类 (RT) 的设计思想与核心差异。

2.1 O(n) 调度器：早期 Linux 的朴素实现

Linux 2.4 内核及更早版本使用 O(n) 调度器。其核心数据结构是一个全局运行队列，所有可运行进程都挂载在这个队列上。

• 调度算法：基于时间片轮转 + 优先级。每次调度时，调度器遍历整个运行队列，计算每个进程的“好度 (goodness)”，选择值最高的进程执行。
• 时间复杂度：O(n)，n 为系统中可运行进程的数量。进程数越多，调度开销越大。
• 对称多处理 (SMP) 支持：弱。全局运行队列需要一把大内核锁，导致多核扩展性差。
• 实时性：无硬实时保证。优先级范围窄 (0-139)，且缺乏抢占点控制。

2.2 O(1) 调度器：可扩展性的革命

Linux 2.6.0 引入 O(1) 调度器，由 Ingo Molnár 设计。它彻底解决了 O(n) 的扩展性问题，成为当时服务器和桌面内核的基石。

• 核心数据结构：每个 CPU 维护独立的运行队列，包含两个优先级数组——活跃数组 (active) 和过期数组 (expired)。
• 算法：基于优先级位图 (bitmap) 和 140 级优先级队列。调度时通过位图指令快速找到最高优先级非空队列，时间复杂度降为 O(1)。
• 时间片计算：根据优先级动态计算，高优先级进程获得更长的时间片。
• SMP 亲和性：每个 CPU 独立调度，负载均衡通过定期拉取 (pull) 实现。

2.3 CFS 调度器：公平与交互的平衡

Linux 2.6.23 合并了 CFS (Completely Fair Scheduler)，由 Con Kolivas 的楼梯调度器启发，Ingo Molnár 实现。CFS 抛弃了固定时间片和优先级数组，采用基于虚拟运行时间 (vruntime) 的红黑树模型。

• 核心思想：模拟“理想多任务处理器”，让每个进程获得 CPU 时间的 1/n。
• 数据结构：红黑树 (rbtree)，键值为 vruntime。最左侧节点（vruntime 最小）是下一个被调度的进程。
• 虚拟运行时间：vruntime += 实际运行时间 × (nice_0_weight / 当前进程权重)。权重由 nice 值决定。
• 调度延迟：通过 sysctl_sched_latency 和 sysctl_sched_min_granularity 控制，保证每个进程在延迟周期内至少运行一次。
• 组调度：支持将进程分组，在组间按权重分配 CPU，组内再按 CFS 调度。

2.4 实时调度类 (RT) 的引入

随着嵌入式实时需求的增长，Linux 2.6 内核开始引入独立的实时调度类。实时调度类与 CFS 等公平调度类共存于内核的调度类框架中，通过 struct sched_class 接口实现多态调度。

• 调度类层次：stop_sched_class → dl_sched_class → rt_sched_class → fair_sched_class → idle_sched_class。优先级从高到低。
• RT 调度策略：
  • SCHED_FIFO：先进先出，无时间片，除非被更高优先级抢占或主动睡眠，否则一直运行。
  • SCHED_RR：时间片轮转，相同优先级进程按时间片轮流执行。
• 优先级范围：1 (最高) ~ 99 (最低)，0 保留给 idle 进程。
• RT 运行队列：每 CPU 维护 100 个优先级链表 (prio_array)，位图加速查找。
• 实时组调度：通过 RT 带宽控制 (RT throttling) 防止实时进程耗尽 CPU，保证非实时进程有运行机会。

2.5 调度器演进对嵌入式实时的影响

从 O(n) 到 CFS + RT 调度类的演进，为嵌入式 Linux 实时系统带来了以下关键能力：

1. 确定性调度：RT 调度类提供固定优先级抢占，调度延迟可预测。
2. 调度类隔离：实时进程与普通进程通过不同调度类管理，互不干扰。
3. 带宽控制：RT 带宽限制防止实时任务饿死系统，CFS 组调度实现资源隔离。
4. 可配置性：通过 chrt 命令、sched_setscheduler() 系统调用、内核 Kconfig 选项灵活配置。