📚 课程目录第1章调度器概述

1. 调度器概述：Linux 调度器的发展历史与核心地位

1.1 调度器在操作系统中的地位与作用

进程调度器是操作系统内核中最核心的子系统之一，它负责决定在任意时刻哪个进程应当获得 CPU 的使用权。从宏观视角看，调度器承担着以下关键职责：

资源分配：在多个可运行进程之间公平、高效地分配 CPU 时间片。
系统响应：确保交互式进程（如桌面应用、终端）获得及时响应，避免用户感知到卡顿。
吞吐量优化：在服务器场景下最大化单位时间内完成的任务数量。
功耗与热量控制：在移动或嵌入式设备上，通过调度策略影响 CPU 频率与空闲状态。
多核负载均衡：在 SMP（对称多处理）系统中，将进程均匀分布到各个 CPU 核心上。

  核心矛盾：调度器始终在 公平性（每个进程获得应有的 CPU 份额）与 效率（最小化上下文切换开销、最大化缓存亲和性）之间寻求平衡。不同工作负载（批处理、交互式、实时）对这两者的侧重完全不同。

1.2 Linux 调度器的发展历史

Linux 内核自 1991 年诞生以来，进程调度器经历了三次重大的架构演进：O(n) 调度器、O(1) 调度器和完全公平调度器（CFS）。每一次演进都针对前一代的瓶颈进行了根本性重构。

1.2.1 O(n) 调度器（Linux 2.4 及更早）

最早的 Linux 调度器采用了一种简单但低效的设计：每次调度时，调度器需要遍历所有可运行进程（Runqueue）来计算每个进程的“好度”（Goodness），然后选择好度最高的进程运行。

时间复杂度：O(n)，其中 n 是系统中可运行进程的数量。进程越多，调度开销线性增长。
数据结构：单一全局运行队列，所有 CPU 共享一个队列。
SMP 支持：极差。全局运行队列需要大锁保护，多核扩展性几乎为零。
交互式进程识别：通过进程睡眠时间长短来猜测是否为交互式进程，启发式逻辑复杂且容易误判。

O(n) 调度器的致命缺陷：当系统中运行大量进程（例如数百个）时，调度器本身会消耗大量 CPU 时间，导致系统吞吐量急剧下降。在服务器场景下，这个问题尤为突出。

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

由 Ingo Molnár 在 2003 年引入，O(1) 调度器彻底解决了 O(n) 调度器的扩展性问题。其核心设计思想是：将调度决策的时间复杂度从 O(n) 降低到 O(1)，即无论系统中有多少进程，调度开销都是常数时间。

特性	O(n) 调度器	O(1) 调度器
时间复杂度	O(n)	O(1)
运行队列结构	单一全局队列	每个 CPU 独立运行队列 + 优先级位图
优先级范围	静态优先级（0-139）	静态优先级（0-139）+ 动态优先级调整
交互式进程识别	基于睡眠时间启发式	基于平均睡眠时间（sleep_avg）
SMP 扩展性	差（全局锁）	好（每 CPU 队列 + 负载均衡）
主要问题	高负载下性能崩溃	交互式进程识别复杂，公平性不够精确

O(1) 调度器引入了两个关键数据结构：活跃数组（active array）和过期数组（expired array）。每个优先级对应一个链表，调度器通过位图（bitmap）在 O(1) 时间内找到最高优先级的非空链表。

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

2007 年，Ingo Molnár 再次重写了调度器，引入了 CFS（Completely Fair Scheduler）。CFS 摒弃了 O(1) 调度器中复杂的优先级数组和交互式进程启发式逻辑，采用了一种全新的设计哲学：模拟“理想的多任务处理器”。

CFS 的核心思想是：如果有一个完美的多任务处理器，它应该让每个可运行进程以相同的速度并行执行。CFS 通过 虚拟运行时间（vruntime） 来量化每个进程已经获得的 CPU 时间，并始终选择 vruntime 最小的进程来运行。

维度	O(1) 调度器	CFS 调度器
核心数据结构	优先级数组 + 位图	红黑树（Red-Black Tree）
调度决策依据	静态优先级 + 动态优先级	vruntime（虚拟运行时间）
时间复杂度	O(1)	O(log n)
公平性模型	基于时间片轮转 + 优先级	加权公平队列（WFQ）
交互式进程处理	复杂的 sleep_avg 启发式	自然体现（睡眠进程 vruntime 不变，醒来后自动获得补偿）
调度粒度	固定时间片（如 100ms）	动态时间片（目标延迟 / 进程数）

为什么 CFS 选择 O(log n) 而不是 O(1)？ 虽然 O(1) 在理论时间复杂度上更优，但 CFS 的设计者认为：在实际系统中，可运行进程数量通常不会很大（几十到几百个），O(log n) 的开销完全可以接受。更重要的是，CFS 的红黑树结构带来了更好的公平性和灵活性，这是 O(1) 调度器无法比拟的。

1.3 调度器演进的核心驱动力

回顾 Linux 调度器的三次重大演进，我们可以总结出推动变革的核心驱动力：

扩展性需求：从单核到多核、从几十个进程到数千个进程，调度器必须能够线性扩展。
公平性追求：从粗糙的优先级轮转到精确的加权公平队列，调度器对“公平”的定义越来越数学化。
交互体验优化：桌面和移动场景要求调度器能够快速响应交互式进程，同时不牺牲批处理吞吐量。
实时性支持：工业控制、音视频处理等场景需要确定性调度延迟，催生了 SCHED_FIFO、SCHED_RR 和 SCHED_DEADLINE 等实时调度策略。
功耗管理：现代调度器需要与 CPU 频率调节（cpufreq）和空闲管理（cpuidle）协同工作，在性能与功耗之间取得平衡。

  关键洞察：调度器的演进并非简单的“新替代旧”。O(1) 调度器在实时性场景下仍有优势，CFS 在桌面和通用服务器场景下表现更好。Linux 内核通过 调度类（sched_class） 架构，将不同调度策略组织成可插拔的层次结构，使得内核可以同时支持多种调度器——这正是本课程后续章节要深入剖析的核心架构。

1.4 本章小结

本章我们建立了对 Linux 进程调度器的宏观认知：

调度器是操作系统资源分配的核心，决定了系统的响应速度、吞吐量和公平性。
Linux 调度器经历了 O(n) → O(1) → CFS 三次重大架构演进，每一次都解决了前一代的关键瓶颈。
O(n) 调度器简单但扩展性差；O(1) 调度器通过双数组和位图实现了常数时间调度；CFS 通过红黑树和 vruntime 实现了精确的加权公平调度。
调度器的演进反映了操作系统从单核到多核、从批处理到交互式、从性能优先到性能与功耗平衡的发展趋势。