进程调度算法

调度分为非抢占式 (Non-preemptive) 和抢占式 (Preemptive)：

非抢占式：一旦进程拿到 CPU，它就一直占着，直到它自己执行完，或者因为需要等待 I/O（比如读文件）而主动进入阻塞状态。
抢占式：操作系统更强势，如果给你的时间片用完了，或者有更重要的进程来了，系统会强制剥夺你的 CPU 使用权。

为了防止一个进程“霸占”资源导致系统卡死，现代操作系统大多采用抢占式调度，利用时间片（Time Slice）来强制切换，制造“并发”的假象。

那么，最常见的调度算法就是 FCFS (First Come First Serve, 先来先服务)，也就是先到先服务（FIFO）。

问题是，假设有三个进程几乎同时到达，但顺序是 A -> B -> C。

进程 A：是个繁重的计算任务，需要运行 100 秒。
进程 B：是个简单的文本处理，只需要 1 秒。
进程 C：也是个小任务，只需要 1 秒。

这种情况被称为 护航效应 (Convoy Effect)。简单来说就是，一个运行缓慢的任务挡在前面，后面跟着的任务只能憋屈地跟在屁股后面慢慢挪，整个系统的效率（吞吐量）都被拖垮了。

为了解决这个问题，工程师提出了 SJF (最短作业优先) 和它的抢占式版本 SRTN (最短剩余时间优先)。思路很简单：谁运行时间短，谁就插队先走。

问题是：如果系统中源源不断地有新的“短作业”加进来（比如 D, E, F... 都是 1 秒的任务），那个需要 100 秒的长作业 A 会面临什么命运？A 任务会一直抢不到时间片，导致被“饿死”。

操作系统怎么知道运行时间？

实际实现时，通常是根据历史数据来进行预测（指数加权移动平均）。简单说就是：如果这个进程上一次用 CPU 用了很久，我就假设它下一次也要用很久。

但因为预测总有误差，且为了解决“饥饿”问题，产生了一个折中的算法：高响应比优先 (HRRN, Highest Response Ratio Next)。

$$\text{优先权}=\frac{\text{等待时间}+\text{预测服务时间}}{\text{预测服务时间}}$$

等待的越久，优先权越高，操作系统迟早会调度它。

不过，HRRN 还是偏向于理论（因为它需要预知或者费劲去预测服务时间，而且每次切换都要算一遍所有进程的优先级，开销不小）。

现代交互式系统最常用的基石是 时间片轮转 (RR, Round Robin)。

RR 的规则极其简单：大家排队，每人玩 $q$ 毫秒，时间到就滚去队尾重排。

这里最关键的参数就是时间片的大小 ($q$)。我们需要在这个参数上做权衡。请思考以下两个极端情况，这会决定系统的性能：

如果时间片 $q$ 设得非常大（比如无限大），RR 算法实际上就退化变成了 FCFS。
如果时间片 $q$ 设得非常小（比如 0.0001 毫秒），虽然并发感很强，但系统会因为频繁上下文切换原因而导致大部分 CPU 算力被浪费掉。

多级反馈队列 (Multilevel Feedback Queue, MFQ)

现在我们迎来了最终的集大成者——多级反馈队列 (Multilevel Feedback Queue, MFQ)。这是现代操作系统（如 Unix/Linux 的早期版本，以及 Windows NT）调度的基石思路。

它结合了我们之前学过的所有优点：

像 RR 一样支持抢占，响应快。
像 SJF 一样偏爱短作业。
最重要的是：它不需要像 SJF 那样去“预测”未来，而是根据进程的表现来动态调整。

其结构大致为：

有多个队列（比如 Q1, Q2, Q3），优先级 Q1 > Q2 > Q3。
新来的进程默认都进入最高优先级的 Q1。

现在的关键在于降级机制。

假设 Q1 的时间片很短（比如 10ms）。一个进程进入 Q1 开始运行，如果它在 10ms 内没跑完（也就是把时间片用光了），这说明它很可能是一个计算密集型的“长作业”。

为了不让它堵塞后面的快速任务，MFQ 算法会把它移到下一个优先级去

反过来思考，如果一个进程频繁地进行 I/O 操作（比如用户打字，每次只用 CPU 1ms 就主动放弃了），它在时间片用完前就放弃了 CPU，那它大概率会保留在高优先级队列里。

多级反馈队列的精髓：“你用光了时间片，说明你贪婪（CPU 密集），那就降级；你没用完就主动让出，说明你交互多（I/O 密集），那就留你在高优区快进快出。”

CFS (Completely Fair Scheduler)

早期的 Linux (2.4/2.6初期) 确实使用过类似 MFQ 的调度器，但从 Linux Kernel 2.6.23 (2007年) 开始，默认调度器变成了 CFS (Completely Fair Scheduler，完全公平调度器)。

1. 核心理念的转变：从“时间片”到“虚拟时钟”

在之前的 RR (轮转) 或 MFQ (多级反馈) 中，核心单位是物理时间片 (Time Slice)，比如 10ms。CFS 抛弃了固定的时间片概念。它的目标是完全公平。

什么叫完全公平？假设 CPU 是一个完美的、可无限分割的资源。如果有 2 个进程，CFS 希望它们能在任意时间段内，各占 50% 的 CPU 能力。如果有 $N$ 个进程，每个占 $1/N$。

但现实中 CPU 不能同时跑 $N$ 个任务（单核），所以 CFS 引入了一个全新的计量单位：vruntime (虚拟运行时间)。

2. vruntime：刻画“贫富差距”

这是 CFS 的灵魂：

$$ vruntime += \text{实际运行时间} \times \frac{\text{NICE_0_LOAD}}{\text{权重}} $$

简单解释：

vruntime 就像每个进程的“消费账单”。
权重 (Weight)：由 nice 值决定。nice 值越小（优先级越高），权重越大。

核心机制： CFS 永远选择 vruntime 最小（账单最少、最穷）的那个进程来运行。

普通进程：运行 1ms，vruntime 增加 1ms。
高优进程（VIP）：运行 1ms，因为权重分母大，vruntime 可能只增加 0.1ms。
- 结果：因为它的 vruntime 涨得慢，所以它能赖在 CPU 上更久，或者被调度器选中得更频繁。它得跑很久，vruntime 才能追上普通进程。

3. 数据结构：红黑树 (Red-Black Tree)

以前的调度器（如 Linux O(1) 调度器）用数组/队列。CFS 选择了红黑树。

Key：进程的 vruntime。
最左侧叶子节点：永远是整棵树里 vruntime 最小的那个节点。

调度过程变成了：

取任务：直接拿树最左边的节点（$O(1)$ 复杂度，因为有缓存指针）。
运行：进程跑一会，vruntime 变大了。
放回：把它重新插回到红黑树的正确位置（$O(\log N)$ 复杂度）。
循环：再次取最左边的节点。

为什么要进行切换

场景提示：假设我们用传统的时间片轮转（RR），时间片设为 10ms。现在有一个视频播放器（交互密集，需要极快响应但每次只跑一点点）和一个视频转码器（计算密集，死命跑）。

在 RR 算法下，视频播放器醒来想干活，可能发现转码器刚拿到 10ms 的时间片正在狂奔，播放器只能干等 10ms，导致画面卡顿。

在 CFS 算法下，视频播放器因为经常睡觉（阻塞），它的 vruntime 会非常小（远远落后于转码器）。一旦它醒来（变为就绪态），红黑树会把它放在哪里？这意味着什么？

首先：vruntime 越小，不仅仅越容易被调度，还越能在一次调度时占用更长的运行时间片？

答案是：不完全是，这取决于你的 vruntime 为什么小。

我们需要区分两个概念：“谁先跑” 和 “跑多久”。

谁先跑（调度时机）：完全由 vruntime 决定。谁小谁先上，这是绝对的。
跑多久（时间片长度）：主要由 权重 (Weight/Priority) 决定，而不是当前的 vruntime 数值。

让我们分别考虑两种情况：

情况 A：高权重进程

假设当前运行的是高优先级的进程（Nice 值很低，权重很大）。

根据公式：$vruntime += \text{实际运行时间} \times \frac{\text{常数}}{\text{巨大权重}}$
因为分母很大，进程的 vruntime 涨得非常慢。
结果：为了让进程的 vruntime 追上别的进程（比如从 10 追到 20），进程需要在物理世界里运行很长的时间（比如 20ms）。

情况 B：我是睡醒的普通人（I/O 密集型）

假设当前运行的是普通进程（权重正常），但刚才睡了很久（比如在等网络请求）。

虽然进程也许很久没跑了，但 CFS 不会让进程依然保留原始的、极小的 vruntime（否则进程会霸占 CPU 几秒钟来追赶别人，这会卡死系统）。
修正机制：当进程醒来时，CFS 会把进程的 vruntime 调整为当前红黑树里最小的那个值（min_vruntime）稍微再减去一点点。
结果：
1. 谁先跑？ 进程比 min_vruntime 还小一点，所以进程立刻插队，抢占 CPU（响应极快）。
2. 跑多久？ 因为进程是普通权重，进程的 vruntime 涨得正常快。进程跑一个标准时间片后，vruntime 就追上甚至超过别人了，然后进程就被踢下去了。
结论：在这里，vruntime 小只保证了响应速度（立刻执行），并没有给进程额外的运行时长。

总结

CFS 的逻辑是这样的：

权重 (Weight) 决定了你理应分到的物理运行时间。
vruntime 决定了大家调度顺序。

所以回到问题本身：

如果 vruntime 小是因为权重高 $\rightarrow$ 进程确实能跑更久。
如果 vruntime 小是因为刚睡醒 $\rightarrow$ 进程只是能插队先跑，但跑的时间还是标准的。

这个机制完美解决了视频播放器（情况 B）的需求：它不需要一次跑很久，但它需要一醒来立刻就能跑，这样画面才不会卡。

OS-进程调度