本篇位置 承接第 5 篇那个死结。这一篇是在没有先知的情况下逼近 SJF
运行环境 容器里的 Linux，Python 3。演示限定在一个核上：docker run --rm --cpuset-cpus=0 ...

一、死结和破法

第 5 篇的结论有点让人泄气：

  • 平均周转最优的策略是 SJF/STCF。
  • 它要求知道每个作业要跑多久。
  • 你不可能知道。

MLFQ（Multi-Level Feedback Queue，多级反馈队列）的破法是把问题换掉：

你确实不知道一个作业将要跑多久。 但你完全知道它刚才跑了多久。

那就用过去预测未来。

这个思路 1962 年就出现在 Corbató 的 CTSS 系统里，后来拿了图灵奖。它今天还活在 Windows、macOS、Solaris 里，也活过 Linux——2007 年之前的 O(1) 调度器就是一个 MLFQ，后来被下一篇的 CFS 换掉了。

⚠️ 顺带澄清一个常见的误记：Linux 现在的实时调度类（SCHED_FIFO、SCHED_RR）不是 MLFQ。 它确实有很多层优先级，但那些优先级是你设死的，不会因为进程的行为升降——而"优先级由行为决定"恰恰是 MLFQ 的定义性特征。有分层不等于有反馈。

打个比方

接着上一篇那个超市。

经理不可能拦住每位顾客问"你车里有多少件"——没人会老实说，问也来不及。但他可以在旁边看。

看什么呢？很简单：上次这个人结账花了多久。 常来买瓶水的，五秒就走；推整车的，十分钟。看几次就够了。于是经理干脆开一条快速通道，把"每次都很快就走"的人放进去。

⭐ 他从没问过任何人是谁，也没问过任何人打算买什么。他只是看着大家的行为，然后据此排队。 这就是 MLFQ 的全部思想。

二、规则一二：分层，高层优先

MLFQ 摆好几个队列，每个队列一个优先级：

Q3 (最高)  →  [ 进程A ]  [ 进程B ]        ← 时间片最短
Q2         →  [ 进程C ]
Q1         →  
Q0 (最低)  →  [ 进程D ]  [ 进程E ]        ← 时间片最长

规则 1： 如果 A 的优先级 > B，跑 A。 规则 2： 如果 A 和 B 优先级相同，它们之间轮转（RR）。

到这里还什么都没解决——优先级从哪来？

三、规则三四：优先级由行为决定

规则 3： 一个作业刚进系统时，放在最高优先级。

先假设你是短作业。猜错了代价也不大（马上就降下去），猜对了就赚到——第 5 篇说过，短作业先跑对平均周转的收益最大。

规则 4（初版）：

  • 用完了整个时间片 → 降一级。
  • 时间片没用完就主动让出（比如去等 I/O）→ 留在原地。

这条规则是整个 MLFQ 的心脏。读一遍它在说什么：

你用完整个时间片，说明你在闷头算，你是个长作业 → 往下走。 你没用完就走了，说明你在等什么，你是个交互型作业 → 留着。

⭐ 于是你的优先级完全由你自己的行为决定，调度器一句话都没问过你。 一个 CPU 密集的作业会自动沉到最底层；一个交互式作业会自动浮在最上层。

四、这个版本会被三件事打垮

初版 MLFQ 有三个漏洞。它们都不是理论上的假想，都是真实系统上摔出来的。

漏洞一：饥饿

如果系统里长期有很多交互型作业占着高优先级，沉到底层的长作业永远轮不上。它会一直饿着。

漏洞二：故意骗它

规则 4 的判据是"有没有用完时间片"。那我在时间片快用完的时候故意睡 1 毫秒呢？

我就永远算作"主动让出"，永远留在最高优先级，同时占着 99% 的 CPU。

⚠️ 这不是纸上谈兵。任何"根据行为给好处"的机制，都会被"表演出那种行为"攻击。你会在这门课里反复看到这个模式——第 30 篇的侧信道是它最极端的形态。

漏洞三：程序会变

一个程序前半段读文件（交互型），后半段闷头算（计算型），或者反过来。行为变了，但它已经被钉在某一层了。

五、规则五和规则四的修订

规则 5（定期提升）： 每隔一段时间 S，把所有作业一律拉回最高优先级。

一条规则同时补了漏洞一和漏洞三：饿着的长作业周期性地被捞上来；行为变了的程序有机会重新被评估。

S 取多少？这是 OSTEP 里说的"巫毒常量"——太大了饥饿依然存在，太小了交互型作业的优势被冲淡。没有理论最优值，得测。 这门课里凡是这种地方我都会直说。

规则 4（修订版）： 不看"有没有用完一个时间片"，改成记账：在某一层累计用满了配额就降级，不管你是分几次用的。

这一条堵死了漏洞二。你睡 1 毫秒也好，睡 100 次也好，你用掉的 CPU 时间是一样的，账记在那儿。

⭐ 从"看单次行为"改成"看累计消耗"，这个修法值得记住：判据要选那个攻击者没法便宜地伪造的量。 时间片用没用完，可以靠一个 sleep 伪造；累计消耗了多少 CPU，伪造不了——除非他真的少用 CPU，那正是你想要的结果。

五条规则合在一起

1. 优先级高的先跑
2. 优先级相同的轮转
3. 新来的放最高层
4. 在某层累计用满配额 → 降一级（不管分几次用的）
5. 每隔 S 时间，全部拉回最高层

六、跑一遍看看：真实系统真的这么干

Linux 的普通进程用的是 CFS 而不是教科书 MLFQ（下一篇讲），但**“用行为区分交互型和计算型"这个效果是一样的**。我们把它逼出来。

场景：一个核，20 个纯计算进程死命抢。再放一个进程进去，分别用两种行为，看它们受到的待遇：

# latency.py
import os, sys, time, statistics

def pct(v, p):
    v = sorted(v); return v[min(len(v)-1, int(len(v)*p))]

def interactive():
    """交互型：睡 20 毫秒，醒来干一丁点活。量「说好 20ms 醒，实际晚了多久」"""
    lat = []
    for _ in range(80):
        t0 = time.time(); time.sleep(0.02)
        lat.append((time.time() - t0 - 0.02) * 1000)
    return lat

def cpu_bound():
    """计算型：一直想跑。量「两次连续运行之间被停了多久」"""
    gaps = []
    t_end = time.time() + 2.0
    prev = time.time()
    while time.time() < t_end:
        now = time.time()
        d = (now - prev) * 1000
        if d > 1.0:                      # 超过 1ms 说明被抢走过
            gaps.append(d)
        prev = now
    return gaps or [0.0]

hogs = []
for _ in range(20):
    pid = os.fork()
    if pid == 0:
        x = 0
        while True: x += 1
    hogs.append(pid)
time.sleep(0.5)

print("场景：1 个核，20 个纯计算进程在死命抢。再放一个进程进去——")
print()
lat = interactive()
print(f"  交互型（睡 20ms 醒一次）  唤醒延迟  中位 {statistics.median(lat):6.2f} ms   p95 {pct(lat,0.95):6.2f} ms   最坏 {max(lat):6.2f} ms")
gaps = cpu_bound()
print(f"  计算型（一直想跑）        被停时长  中位 {statistics.median(gaps):6.2f} ms   p95 {pct(gaps,0.95):6.2f} ms   最坏 {max(gaps):6.2f} ms")
print()
print(f"  如果调度器一视同仁地轮转（21 个人排队，每人 4ms），谁都得等 {20*4} ms 左右。")

for p in hogs:
    os.kill(p, 9); os.waitpid(p, 0)

场景：1 个核，20 个纯计算进程在死命抢。再放一个进程进去——

  交互型（睡 20ms 醒一次）  唤醒延迟  中位   0.05 ms   p95   2.89 ms   最坏  12.87 ms
  计算型（一直想跑）        被停时长  中位  60.00 ms   p95  60.01 ms   最坏  60.01 ms

  如果调度器一视同仁地轮转（21 个人排队，每人 4ms），谁都得等 80 ms 左右。

同一台机器、同一个核、同样的 20 个竞争者。

  • 交互型进程想跑的时候，中位 0.05 毫秒就跑上了。
  • 计算型进程一被停就是 60 毫秒。

⭐ 相差一千二百倍。而调度器从来没有问过这两个进程任何问题。 它们没有声明自己是什么类型，没有设过优先级，代码里没有一行提到调度。区别完全来自它们各自干过什么。

再看最后那行对照：如果调度器一视同仁地轮转，21 个人排队，谁都得等 80 毫秒左右。交互型进程实际等的是 0.05 毫秒——它拿到的待遇比"公平"好了三个数量级。

这就是超市经理开的那条快速通道。买瓶水的人从来没告诉过经理自己只买一瓶。

七、代价与取舍

MLFQ 换来了什么： 在不知道未来的前提下，同时逼近了两个目标——对短作业和交互型作业，周转和响应都接近 SJF；对长作业，靠规则 5 保证不饿死。这是一个非常划算的近似。

它花了什么：

  • 一堆没有理论依据的参数：几层队列、每层时间片多长、S 取多少、每层配额多少。这些都得测出来，换个负载可能就得重调。
  • 优先级反转的风险：一个低优先级进程拿着锁，高优先级进程等这把锁，中优先级进程把低优先级的挤掉——高优先级就被间接堵死了。1997 年火星探路者号在火星上反复重启，就是这个原因。第 21 篇细讲。

它放弃了什么： 它不提供任何份额保证。 你没法说"给这个容器 20% 的 CPU”。MLFQ 只管排序，不管分配比例。这个需求在虚拟机和容器时代变得很硬，正是下一篇 CFS 和 cgroup 要解决的。

八、小结

  • MLFQ 的破法是把问题换掉：预测不了未来，就观察过去。
  • 五条规则：高优先级先跑；同级轮转；新来的进最高层；在某层累计用满配额就降级；每隔 S 全部拉回最高层。
  • 每条规则都是被一个具体失败逼出来的——规则 5 补饥饿和行为漂移，规则 4 的"累计记账"版补故意伪装。
  • ⭐ 判据要选攻击者没法便宜地伪造的量。“时间片用没用完"可以靠 sleep 伪造；“累计用了多少 CPU"伪造不了。
  • 实测：一个核 + 20 个抢 CPU 的进程，交互型唤醒延迟中位 0.05 ms，计算型被停中位 60 ms。一千二百倍的差距，全部来自行为，没有任何声明。
  • 它的软肋是一堆需要经验调的参数，以及完全不提供份额保证——这是下一篇的起点。

思考题

  1. 规则 3 说新作业进最高层。有人想攻击这个：不停地 fork 出新进程，每个都只跑很短一会儿。这能骗到 CPU 吗？累计记账（规则 4 修订版）挡得住吗？
  2. 第六节的实测里，交互型进程的 p95 是 2.89 ms，最坏 12.87 ms。中位数才 0.05 ms。为什么尾部会翘这么高？对一个要求"每 16.7 毫秒必须画一帧"的程序，你该看哪个数字？
  3. 规则 5 的 S 如果设成无穷大（永不提升），系统会怎样？如果设成 1 毫秒呢？
  4. 超市经理开快速通道靠的是"看你上次花了多久”。但超市其实还有个更省事的办法——在通道口贴"十件以下”，让顾客自己选。操作系统里有对应的东西吗？它为什么不能单独用？

延伸