悠悠楠杉
网站页面
Linux内核进程调度探秘（上）：从时间片到完全公平调度
08/06
一、调度器的使命：CPU时间分配的艺术家
在Linux系统的核心，调度器如同一位看不见的指挥家，决定着每个进程何时能获得CPU资源。早期的Linux 2.4内核采用传统的时间片（Timeslice）轮转算法，每个进程被分配固定的时间片段（通常是100ms），通过时钟中断触发调度。但这种方式存在明显缺陷：
- 交互式进程响应延迟：文本编辑器等I/O密集型进程常因时间片耗尽被强制切换
- 静态权重不公：nice值调整的优先级权重线性变化，缺乏动态适应性
- 调度粒度粗糙：固定时间片无法适应现代多核处理器架构
c
// 早期调度器代码片段（Linux 2.4）
if (current->policy == SCHED_RR && !--current->time_slice) {
current->time_slice = task_timeslice(current);
move_last_runqueue(current);
}
二、CFS的革命：虚拟时间代替物理时间
2007年引入的完全公平调度器（Completely Fair Scheduler, CFS）彻底改变了游戏规则。其核心创新在于：
1. 虚拟运行时（vruntime）概念
每个进程维护一个vruntime计数器，记录其应获得的CPU时间。调度器总是选择vruntime最小的进程执行，实现了"虚拟时间"维度上的公平。
python
简化的CFS选择逻辑
def picknexttask():
return rb_tree.min() # 从红黑树中选择vruntime最小的进程
2. 红黑树的高效管理
所有可运行进程按vruntime排序存储在红黑树中：
- 插入操作：O(log n)时间复杂度
- 删除操作：O(1)平均时间复杂度
- 最小节点查询：O(1)时间复杂度
3. 动态时间片计算
时间片不再固定，而是由进程权重决定：
时间片 = (调度周期 * 进程权重) / 所有进程权重之和
其中nice值每差1级，CPU时间权重相差约10%（具体为1.25倍）
三、调度策略的精细调控
Linux通过调度类（sched_class）实现策略多样化：
| 调度类 | 适用场景 | 特点 |
|--------------|-------------------------|-----------------------------|
| STOPSCHED | 内核停止任务 | 最高优先级，用于CPU热迁移等 |
| DLSCHED | 实时限期任务 | 使用Earliest Deadline First |
| RTSCHED | 实时循环/先进先出 | 固定优先级，抢占式 |
| FAIRSCHED | 普通进程（默认） | 本文讨论的CFS实现 |
| IDLE_SCHED | 空闲任务 | 当无其他可运行任务时激活 |
抢占时机的精妙设计：
1. 时钟中断（tick）时检查needresched标志
2. 进程从TASKRUNNING状态退出时
3. 显式调用cond_resched()的代码路径
c
// 典型抢占检查点
static void __sched notrace preempt_schedule_common(void) {
do {
preempt_disable();
__schedule(true); // 关键调度入口
preempt_enable();
} while (need_resched());
}
四、真实世界的权衡艺术
在实际应用中，CFS面临诸多挑战：
1. 新进程的vruntime初始化：直接设为当前最小vruntime会导致老进程饥饿
2. 多核负载均衡：通过scheddomain结构实现跨CPU的任务迁移
3. 唤醒抢占：使用wakeuppreempt_entity()比较vruntime差值决定是否抢占
性能数据：在标准工作负载下，CFS相比O(1)调度器可降低交互式应用的响应延迟达30%（数据来自Phoronix测试）
（接下篇将探讨实时调度、组调度、以及CPU亲和性等高级主题）
