第67期 | 一百四十个座位，两套点名册

操作系统 · 2026-10-24 · 九羲科技

第六章第二期。上一期我们从 1959 年巴黎讲到时间片，今天钻进 2002 年那个 O(1) 调度器的肚子里，亲手数一遍：它到底是怎么"算公平"的。

一、两套点名册，一次翻转

2002 年 1 月 4 日，Ingo Molnar 给 LKML 的长邮件里¹，把新调度器的核心画得很直白：每个 CPU 一条 runqueue（运行队列），队列里放两套"点名册"——active 和 expired。每套册子 140 页，一页一个优先级：0 到 99 留给实时任务，100 到 139 给普通进程，nice 值 -20 到 +19 就映射在这 40 页里。

点名怎么点？140 页配一张 140 位的位图，哪页有人，哪位就置 1。找最高优先级，就是找位图里第一个 1——页数是死的，查找时间是死的，这就是 O(1) 的"O(1)"²。进程时间片跑完，不重新排整条队，直接搬进 expired 那套册子，顺手重算下一轮的时间片；等 active 这套点空了，两套册子的指针一交换——翻转本身，也是 O(1)。上一代 2.4 调度器每次要点遍全队重算（O(n)），Molnar 在邮件里吐槽的正是这个：进程越多，调度器自己越慢，成了它要调度的对象的瓶颈。

O(1) 调度器的两套点名册：时间片用完换册，active 点空，指针一交换，expired 转正。

反常识的细节藏在奖惩里。O(1) 会记仇，也会报恩：它统计每个进程睡了多久（sleep_avg），睡得多的——等键盘、等网络的交互进程——加分，优先级数字变小，下次更早被点名；抱着 CPU 不撒手的，扣分。加减幅度各 5 档²。更妙的是，高度交互的进程时间片用完，可以不进 expired，直接插回 active 那套册子——只要上次翻转没过去太久。公平在这里不是"人人等一轮"，而是"等人的，不等跑步的"。

二、学会定价的调度器

如果 AI 的操作系统先出现，这套奖惩会被设计成什么样？先看 O(1) 的奖惩是什么：sleep_avg 是"感知"（统计过去的行为），加减分是"比较"，动态优先级是"执行"——这正是维纳 1948 年在《控制论》里写下的反馈回路³：感知—比较—执行。O(1) 的调度器里，早住着半个控制论。

推演一步：AI-native OS 会把这个回路做完整。sleep_avg 是人拍脑袋定的启发式——"睡得多＝交互式＝重要"。这个等式在 2002 年的桌面上成立，在今天的推理服务器上未必。原生的做法：调度器里跑一个小模型，持续估计每个任务的"边际收益"——多给它 10ms，能多产出多少价值？优先级不再是人填的 nice 数字，而是系统自己学出来的定价。CFS 当年用 vruntime 把"公平"翻译成"欠账"，AI OS 会把"公平"翻译成"出价"：对话任务为低时延出高价，批量任务为吞吐出低价，调度器做市成交。

照见平时看不见的一层：O(1) 的奖惩有个从没被问过的前提——"睡得多的一定更重要"。这个前提被默认了二十年，被调参，被反复吐槽，最后 CFS 干脆换了整套定义。AI OS 的第一课也许是：别再默认任何"重要"的定义，让调度器自己从结果里学。

三、三十行，亲手翻一次册子

手边任何一台能跑 Python 的机器，把 O(1) 的核心机制亲手跑一遍——两套册子、优先级数字越小越优先、时间片用完换册、点空就翻转：

ACTIVE, EXPIRED = {}, {}

procs = {'vim': [120, 3], 'gcc': [125, 5], 'bash': [120, 2]}

for name, (prio, ts) in procs.items():

ACTIVE.setdefault(prio, []).append([name, ts])

for tick in range(12):

if not ACTIVE: # 点空了，翻转！

ACTIVE, EXPIRED = EXPIRED, ACTIVE

prio = min(ACTIVE) # 位图的现实版：找最小数字

name, ts = ACTIVE[prio].pop(0)

if not ACTIVE[prio]: del ACTIVE[prio]

print(f'tick{tick}: 跑 {name}（优先级{prio}）')

ts -= 1

(ACTIVE if ts else EXPIRED).setdefault(prio, []).append([name, ts or 3])

跑起来你会看见：优先级 120 的 vim 总比 125 的 gcc 先被点到；gcc 时间片用完被扔进 expired；active 点空的那一 tick，两套册子"啪"地一交换——O(1) 的全部秘密，就在这一次交换里。上一期 top 看的是 CFS 的"欠账"，今天看的是 O(1) 的"翻转"。六十年调度史，两种公平观，都在你眼前跑过一遍。

落到普遍场景：一台跑着本地模型的机器上，推理服务常驻、日常任务来来去去，nice 和 chrt 就是现成的"定价"旋钮——先给时延敏感的任务降 nice（数字变小、优先级变高），再看效果；边缘算力盒上算力更金贵，值得先把各任务的 SLO 列出来，按"出价"配权重，而不是默认一人一半。企业私有智能中心里多个智能体任务抢同一块算力，也是同一个问题：给每个任务定权重，按权重分算力，再给时延敏感的留"抢占"的口子。

· · ·