2. Linux内核调度器基础：CFS调度器原理、时间片与优先级、O(1)调度器回顾
在深入实时抢占模型之前，必须理解Linux内核调度器的演进与核心机制。调度器决定了哪个进程获得CPU、运行多久以及如何响应外部事件。本章聚焦于当前主流调度器——完全公平调度器（CFS）的原理，并回顾其前身O(1)调度器，为后续分析PREEMPT_RT的调度延迟优化奠定基础。
2.1 调度器演进概览
Linux调度器经历了三个主要阶段：
| 阶段 | 内核版本 | 核心算法 | 主要问题 |
|---|---|---|---|
| O(1)调度器 | 2.6.0 ~ 2.6.22 | 基于优先级数组、固定时间片 | 交互性差、公平性不足、复杂启发式 |
| CFS调度器 | 2.6.23 ~ 至今 | 红黑树、虚拟运行时间、加权公平队列 | 实时性仍依赖内核抢占模型 |
| 实时调度类 | 始终存在 | SCHED_FIFO / SCHED_RR | 优先级反转、调度延迟抖动 |
2.2 O(1)调度器回顾
O(1)调度器得名于其调度决策的时间复杂度为O(1)——无论系统中有多少进程，选择下一个运行进程的时间都是常数。其核心设计如下：
- 优先级数组（Priority Array）： 维护两个数组——活跃数组（active）和过期数组（expired）。每个数组包含140个优先级队列（0~99为实时，100~139为普通）。
- 位图（Bitmap）： 使用一个140位的位图标记非空队列，通过
__ffs()指令快速找到最高优先级的非空队列。 - 固定时间片（Timeslice）： 每个优先级对应固定的时间片长度，高优先级获得更长的时间片。
- 负载均衡： 每个CPU维护独立的运行队列，通过定期负载均衡迁移进程。
// O(1)调度器核心数据结构示意（简化）
struct prio_array {
unsigned long bitmap[BITMAP_SIZE]; // 140位位图
struct list_head queue[MAX_PRIO]; // 140个队列
int nr_active; // 活跃进程计数
};
struct runqueue {
spinlock_t lock;
struct prio_array *active; // 指向活跃数组
struct prio_array *expired; // 指向过期数组
struct prio_array arrays[2]; // 实际存储
// ... 其他字段
};
2.3 CFS调度器核心原理
CFS（Completely Fair Scheduler）由Ingo Molnár于2007年引入，彻底抛弃了固定时间片和优先级数组，转而采用基于虚拟运行时间（vruntime）的加权公平队列模型。
2.3.1 虚拟运行时间（vruntime）
每个普通进程（SCHED_NORMAL/SCHED_BATCH）都有一个vruntime，表示该进程已经消耗的CPU时间，但经过优先级加权调整。CFS的目标是让所有进程的vruntime尽可能相等。
计算公式：
vruntime += 实际运行时间 × (NICE_0_LOAD / 进程权重)
其中NICE_0_LOAD是nice值为0时的基准权重（1024），进程权重由nice值决定：
| nice值 | 权重 | 相对CPU占比（vs nice=0） |
|---|---|---|
| -20 | 88761 | 86.7倍 |
| -10 | 11051 | 10.8倍 |
| 0 | 1024 | 1.0倍 |
| 10 | 304 | 0.3倍 |
| 19 | 15 | 0.015倍 |
2.3.2 红黑树（Red-Black Tree）
CFS将所有可运行的普通进程组织在一棵红黑树中，以vruntime为键值。红黑树保证：
- 最左侧节点（最小
vruntime）就是下一个被选中的进程。 - 插入和删除操作的时间复杂度为O(log N)。
- 树始终保持平衡，避免极端情况下的性能退化。
- 从红黑树中获取最左侧节点（vruntime最小的进程）。
- 将该进程从红黑树中移除。
- 设置定时器，在进程运行一段时间后触发调度。
- 进程运行结束后，更新其vruntime，重新插入红黑树。
- 如果进程被抢占（更高优先级任务就绪），则更新vruntime后重新入树。
2.3.3 调度延迟与最小粒度
CFS引入了两个关键参数来控制调度频率：
| 参数 | 默认值 | 说明 |
|---|---|---|
sysctl_sched_latency |
6ms（桌面） 20ms（服务器） |
CFS保证所有可运行进程在一个调度周期内至少运行一次的时间窗口。 |
sysctl_sched_min_granularity |
0.75ms（桌面） 4ms（服务器） |
每个进程至少运行的最小时间片，防止频繁上下文切换。 |
当可运行进程数量较少时，每个进程获得的时间片 = 调度延迟 / 进程数；当进程数增多导致时间片小于最小粒度时，CFS会扩大调度延迟，保证每个进程至少运行最小粒度的时间。
2.4 CFS调度器架构图
2.5 CFS与实时任务的关系
CFS仅管理SCHED_NORMAL、SCHED_BATCH和SCHED_IDLE调度类的进程。实时任务（SCHED_FIFO/SCHED_RR）由独立的实时调度类管理，优先级高于CFS的所有进程。但CFS的以下机制直接影响实时系统的延迟：
- 调度延迟参数：
sched_latency和sched_min_granularity决定了CFS进程的时间片大小，过大的时间片会延长实时任务的等待时间。 - 组调度（Group Scheduling）： CFS支持将进程分组，每个组获得公平的CPU份额。实时任务如果与CFS进程共享CPU，组调度可能引入额外的延迟。
- 负载均衡： CFS在多个CPU之间迁移进程时，可能触发运行队列锁的竞争，影响实时任务的调度延迟。
- 实时任务应使用SCHED_FIFO或SCHED_RR调度类，并设置高优先级（通常为1~50）。
- 减少CFS可运行进程的数量，或通过cgroup限制其CPU份额，降低对实时任务的干扰。
- 调整
sched_latency和sched_min_granularity为更小的值，使CFS进程更频繁地被抢占。 - 使用isolcpus内核参数将实时任务隔离到专用CPU核心，完全避免CFS进程的干扰。
2.6 CFS关键数据结构
// CFS运行队列核心结构（简化）
struct cfs_rq {
struct rb_root tasks_timeline; // 红黑树根节点
struct rb_node *rb_leftmost; // 最左侧节点（最小vruntime）
struct sched_entity *curr; // 当前正在运行的调度实体
unsigned long nr_running; // 可运行进程数
u64 min_vruntime; // 队列最小vruntime（用于新进程初始化）
// ... 其他字段
};
// 调度实体（每个进程一个）
struct sched_entity {
struct rb_node run_node; // 红黑树节点
unsigned long on_rq; // 是否在运行队列中
u64 vruntime; // 虚拟运行时间
u64 sum_exec_runtime; // 实际CPU总运行时间
struct sched_entity *parent; // 组调度中的父实体
// ... 其他字段
};
2.7 时间片与优先级在CFS中的体现
CFS没有传统意义上的“时间片”，而是通过权重和调度周期共同决定每个进程获得的CPU时间比例：
| 概念 | O(1)调度器 | CFS调度器 |
|---|---|---|
| 时间片 | 固定值，由优先级决定 | 动态计算，由调度周期和进程数决定 |
| 优先级 | 直接映射到时间片长度 | 通过权重影响vruntime增长速率 |
| 公平性 | 基于优先级的时间片分配 | 基于vruntime的完全公平 |
| 交互式优化 | 复杂启发式判断 | 自动通过睡眠/唤醒时的vruntime补偿 |
在CFS中，高优先级（低nice值）进程的权重更大，因此其vruntime增长更慢，从而在红黑树中更靠左，获得更多的CPU时间。但CFS保证所有进程最终都会得到调度，不会出现O(1)中低优先级进程被饿死的情况。