调度算法与实时性

环境：Windows 11 x64（build 26200）、GCC 13.1.0（MinGW-w64，D:/Qt/Tools/mingw1310_64/bin/gcc.exe），-std=gnu11 -O2 -static，6 物理核 / 12 逻辑处理器。调度是这台机器上最受同期负载干扰的测量——测的时候另有 3 个 agent 在编译，所以探针里那句”背景 6 个满载线程共 308807132 次迭代（说明测的时候机器确实很忙）“是刻意留的自证。凡绝对时间都给区间或两次独立运行，优先看比值、顺序和优先级数字本身。本机无 Linux/WSL：CFS 的权重与 vruntime、nice、chrt/SCHED_FIFO、cgroup 的 CPU 配额全部未在本机实测，只按算法语义讲。

一、“优先级”在 Windows 上是两个数相乘出来的

SetThreadPriority 收的是相对值（-15…+15），最终跑的绝对优先级由进程类决定。7 个线程各设一档、同时满载跑，然后从 NtQuerySystemInformation 读它们的动态/基准优先级（6 个进程类各跑一遍，这里贴完整结果）：

进程类	类值	进程基优先级	IDLE(-15)	LOWEST(-2)	BELOW(-1)	NORMAL(0)	ABOVE(+1)	HIGHEST(+2)	TIME_CRITICAL(+15)
IDLE	0x40	4	1	2	3	4	5	6	15
BELOW_NORMAL	0x4000	6	1	4	5	6	7	8	15
NORMAL	0x20	8	1	6	7	8	9	10	15
ABOVE_NORMAL	0x8000	10	1	8	9	10	11	12	15
HIGH	0x80	13	1	11	12	13	14	15	15
REALTIME	0x80	13	1	11	12	13	14	15	15

原样输出（NORMAL 类那段）：

进程类=NORMAL                 (0x20)  进程基优先级=8  主线程 动态=8 基准=8
    LOWEST(-2)               睡着时 动态=6 基准=6
    HIGHEST(+2)              睡着时 动态=10 基准=10
    TIME_CRITICAL(+15)       睡着时 动态=15 基准=15

读这张表要注意四件事：

内核可用的绝对优先级只有 1–15，第 0 级是零页线程。TIME_CRITICAL(+15) 在任何进程类下都是 15——它已经顶到天花板，“再高一档”在 Windows 上不存在。
IDLE(-15) 在任何类下都是 1（除了 IDLE 类自己也是 1）：“低于正常的档”会被夹到 1，不是”基优先级 - 15”。
NORMAL 类的 HIGHEST = 10，而 HIGH 类的 LOWEST = 11——换进程类比调线程档更狠，一个 HIGH 类里”最低优先级”的线程仍然压得住 NORMAL 类里”最高优先级”的线程。
最后一行的 REALTIME 类值是 0x80，和 HIGH 一模一样（REALTIME_PRIORITY_CLASS 的宏是 0x100）。这不是笔误，是第七节的主题。

二、抢占有多严格：把两个线程塞进同一颗逻辑处理器

先确认”优先级只在抢同一颗核时才起作用”（两颗核的对照）：

  分开各占一颗核：LOWEST 15912944 vs HIGHEST 15880031 次，比值 1.002 → 不抢同一颗核时优先级不起作用

再挤同一颗（掩码 0x4，单颗逻辑处理器），固定 400ms 窗口数迭代：

低优先级那一方	它拿到的迭代份额	原始计数
LOWEST(-2)	0.25%	54945 / 21497537
BELOW_NORMAL(-1)	0.01%	1387 / 21603028
NORMAL(+0)	23.17%	6293335 / 20871636
ABOVE_NORMAL(+1)	7.05%	1571956 / 20725677
HIGHEST(+2)（对手也是 HIGHEST）	48.57%	17995261 / 19057224

四行数据完全不单调：差 1 档（ABOVE_NORMAL）7.05%、差 2 档（NORMAL）23.17%、差 3 档 0.01%、差 4 档 0.25%。剩下的那点份额不是”优先级比例”，而是动态提升和量子边界撞出来的边角时间，别拿这几行拟合曲线。整体结论仍然清楚：只要低的那一方被差出 3 档以上，它拿到的 CPU 就在 0.x% 量级；同档对打才像样地各拿一半（48.57%）。

响应时间：先量错了，重做一遍

上一版的实验把两个线程各自的”起跑→跑完”当作被压的时间，结果是这样的：

  大=HIGHEST(+2) 小=LOWEST(-2)  第1次: 大线程 185.8 ms(CPU 需求 190.3) 小线程 25.5 ms  小线程动态优先级=7
      小线程被压掉的时间 = 0.3 ms（它自己只需 25.2 ms）；若等于 215.5 ms 就是完全被大线程压住

看起来”小线程一点没被压”。这个结论是错的：线程自己打的计时是从它第一次上核开始的，等锁/等 CPU 的那段时间根本没进统计。重做的探针改成”从共同起点 t0 算三个时刻：首次上核、跑完用了多久、完成于何时”，并且打印每个线程实际拿到的亲和掩码和所落在的核：

QPC 频率=10000000  逻辑处理器=12  进程可用掩码=0xfff
单独跑（独占掩码 0x4 那颗核）：小线程 8000000 次 = 29.4 ms，大线程 60000000 次 = 194.8 ms
判据：小线程若完成于约 224.2 ms（=29.4+194.8）⇒ 被完全压住；若完成于约 209.5 ms ⇒ 两者平分这颗核

  [1] 大=HIGHEST(+2)  小=LOWEST(-2) 第1次  墙钟 216.1 ms
     大线程 prio=+2: 首次上核 +   0.1 ms  自己跑了   189.3 ms  完成于   189.4 ms  动态优先级=10 落在核 2 掩码=0x4
     小线程 prio=-2: 首次上核 + 189.5 ms  自己跑了    26.6 ms  完成于   216.1 ms  动态优先级=7 落在核 2 掩码=0x4   绑核 err=0/0
  [2] 大=NORMAL(0)    小=NORMAL(0)  第1次  墙钟 218.2 ms
     大线程 prio=+0: 首次上核 +   0.1 ms  自己跑了   218.0 ms  完成于   218.1 ms  动态优先级=8 落在核 2 掩码=0x4
     小线程 prio=+0: 首次上核 +   0.1 ms  自己跑了    29.1 ms  完成于    29.2 ms  动态优先级=8 落在核 2 掩码=0x4
  [3] 大=LOWEST(-2)   小=HIGHEST(+2) 第1次  墙钟 219.4 ms
     大线程 prio=-2: 首次上核 +  25.4 ms  自己跑了   193.9 ms  完成于   219.3 ms  动态优先级=6 落在核 2 掩码=0x4
     小线程 prio=+2: 首次上核 +   0.1 ms  自己跑了    25.1 ms  完成于    25.2 ms  动态优先级=10 落在核 2 掩码=0x4

每种配置都跑了 2 次，这里贴第 1 次；第 2 次分别是 [1] 小线程首次上核 +192.2 ms（完成于 218.2）、[2] 小线程完成于 27.4 ms、[3] 大线程首次上核 +27.3 ms。四次恢复成对复现：

[1] 小线程 首次上核 +189.5 / +192.2 ms——它一次都没能插进来，一直等大线程跑完才开始；响应时间从独处的 29.4 ms 变成 216.1 / 218.2 ms（7.3 倍），正好等于”大 189 + 小 27”。
[2] 同优先级：两个都在 +0.1 ms 上核，小线程 29.2 ms 完成、大线程 218.1 ms 完成（它需要 194.8，被分走约 23 ms）。这就是轮转（RR）：同档平分，短任务照样很快完成。
[3] 反过来（大=LOWEST、小=HIGHEST）：小线程 +0.1 上核、25.2 ms 完成；大线程的首次上核变成 +25.4 / +27.3 ms——虽然探针是先 ResumeThread(大) 再 ResumeThread(小)，高优先级的后到者当场把它抢了下来。抢占是立刻的，不是等量子。

三、FCFS / SJF / RR：同一批数字能算出平均完成时间

拿第二节那对任务（小 29.4 ms、大 194.8 ms，同一颗核）算：

调度方式	谁先跑	小任务完成	大任务完成	平均完成时间	本机上对应什么
FCFS（先来先服务，大先到）	大 → 小	224.2	194.8	209.5 ms	`[1]` 的实测形状（216.1 / 189.4，平均 202.8）
FCFS（小先到）	小 → 大	29.4	224.2	126.8	`[3]` 的实测形状（25.2 / 219.3，平均 122.3）
SJF/SRTF（最短作业优先）	小 → 大	29.4	224.2	126.8	Windows 不提供，除非你自己控制提交顺序
RR（同档轮转）	交替	29.2	218.1	123.7 ms	`[2]` 实测

同一批任务，把”低优先级排在后面”和”同优先级轮转”两种策略对比，平均完成时间 202.8 ms vs 123.7 ms——严格优先级让整体变差 64%。 这正是教科书里”优先级调度牺牲平均周转换取响应保证”的具体价格。反过来说：如果你不是要保延迟，而是想吞吐好看，别让一个长任务占着一个高优先级档。

Windows 的执行体调度器不是 CFS：它是”15 级固定优先级 + 每档一个时间片 + 多级反馈动态提升”，没有虚拟运行时间、没有权重。Linux CFS 的思路（把 CPU 时间按权重折算成 vruntime，永远选最小的那个红黑树节点，nice 调的是权重不是优先级）以及它的实测（perf sched、/sys/fs/cgroup/cpu.weight）本节未在本机实测，因为本机只有 Windows。

四、多级反馈：内核在你看不见的地方改优先级

同一个探针读”动态优先级 vs 基准优先级”（class 5 快照里的 Priority 与 BasePriority）：

  满载忙等线程       : 动态=8 基准=8 切换=242 用户时间=875 ms  迭代=48707322
  每 2ms 醒一次的线程: 动态=8 基准=8 切换=66 用户时间=0 ms  醒了 61 次
  主线程（刚做完查询）: 动态=8 基准=8
  400ms 后再读        : 忙等=动态8/基准8  睡眠型=动态8/基准8

这台机器上这一轮两者都没被提升（都是 8/8），但《进程、线程与上下文切换》那一节的快照里，等互斥体/等事件/等临界区/等条件变量的 4 个线程动态=9、基准=8，而忙等线程始终 8/8。两组放一起的结论：

提升是给”会等待的线程”的：从等待里醒来时被加一档（+1，实测 9），让它尽快跑完并释放资源；纯 CPU 线程拿不到任何提升。
提升有上限（在本机的观测里是 +1，而且被夹在 15 以下），所以”多级反馈”能防止低优先级线程饿死，但不能突破优先级顺序——第二节 [1] 里那个小线程动态优先级 7（基准 6，被提升 1），仍然抢不动动态 10 的大线程。
想看清提升的全过程需要内核级 tracing（ETW NTKERNEL 的 SetPriority 事件；Linux 侧是 perf sched priority），本机探针只能采样，没覆盖到提升的峰值时刻——这一条我没测准，只能给出”存在 +1 提升”这一档证据。

五、优先级反转：互斥体 vs 信号量，以及本机没看到的继承

三线程经典构造（低优先级线程持锁干活、中优先级线程满载抢核、高优先级线程等锁），同一颗核：

场景	高优先级线程等了多久	持锁线程的动态优先级（采样）	持锁线程迭代数
互斥体，无中等线程干扰	121.8 ms	最小 6 / 中位 7 / 最大 7	3168805
互斥体 + 中等线程满载	624.5 ms	最小 6 / 中位 6 / 最大 7	324
信号量 + 中等线程满载	600.5 ms	最小 6 / 中位 6 / 最大 7	85196

另一次独立运行（同一构造，持锁线程自己每轮读一次 ThreadBasicInformation 采样 64 次）：

  互斥体(无竞争): 高优先级等 181.5 ms；持锁线程(基准6)自己读到 6 次动态优先级 最小=6 最大=6 均值=6.0
  互斥体+中等线程(10): 高优先级等 805.8 ms；持锁线程(基准6)自己读到 0 次动态优先级 最小=99 最大=-99 均值=0.0
  信号量+中等线程(10): 高优先级等 808.4 ms；持锁线程(基准6)自己读到 0 次动态优先级 最小=99 最大=-99 均值=0.0

三个诚实的读数：

反转的代价是 5 倍量级：无干扰 121.8/181.5 ms，插进一个中等优先级满载线程后变 624.5–808.4 ms。持锁的低线程迭代数从 3168805 掉到 324——它几乎完全被中优先级线程压住，锁一直不放。
互斥体和信号量几乎一样慢（624.5 vs 600.5）。微软文档说内核互斥体支持优先级继承，但本机测不到它的效果：持锁线程（基准 6）的动态优先级在两种情况下都停在 6–7，从没被抬到等待方的高优先级（10）。第二行那三次 最小=99 最大=-99 是采样函数根本没跑成功（一次都没读到值），所以那两行的优先级列不能用——只有第一行”6 次采样，最小=最大=6”是有效证据。我不把”Windows 没有优先级继承”当结论写，只能说：在这台机器、这个构造里，我没观察到继承发生。
真正的解法仍然是构造上不制造反转：持锁期间不依赖任何可能被抢的 CPU 时间（把临界区缩到几微秒），或者按《并发》专栏里的做法用有界自旋 + 明确的锁顺序。

六、调度延迟：`Sleep(5)` 给你 15.67 毫秒

操作	实测
`Sleep(5)` × 40（普通进程类）	最小 12.47 / 中位 15.67 / p90 16.13 / 最大 18.01 ms
`Sleep(5)` × 40（设成”实时类”之后）	最小 14.68 / 中位 15.62 / p90 16.03 / 最大 16.40 ms
`WaitableTimer` 设 1ms 周期，30 次	共 456.6 ms → 平均 15.22 ms/次

要 5ms 给 15.6ms，WaitableTimer 要 1ms 给 15.2ms——和《操作系统在做什么》第三节里 KUSER_SHARED_DATA+0x320 每 15.57 ms 进 1 完全一致：这是系统定时器分辨率（约 15.625 ms），唤醒时间会被圆整到节拍的下一格。“实时类那一行”没变好，原因见下一节（它其实只是 HIGH 类）。想让 15ms 的下界塌下来要 timeBeginPeriod(1)，那是全系统设置，实测效果在《线程与进程模型》一节里量过（Sleep(1) 从 13.72ms 变 1.88ms）。

七、“实时类”在本机是设不上的，而且有明确原因

探针逐档设置并回读，同时问内核要这个进程的基优先级：

  设成 NORMAL(0x20)       返回=1 lasterr=0  GetPriorityClass=0x20  内核里的进程基优先级=8  主线程 动态=8 基准=8
  设成 HIGH(0x80)         返回=1 lasterr=0  GetPriorityClass=0x80  内核里的进程基优先级=13  主线程 动态=13 基准=13
  设成 REALTIME(0x100)    返回=1 lasterr=0  GetPriorityClass=0x80  内核里的进程基优先级=13  主线程 动态=13 基准=13
  设成 字面量 0x100    返回=1 lasterr=0  GetPriorityClass=0x80  内核里的进程基优先级=13  主线程 动态=13 基准=13
  设成 ABOVE_NORMAL(0x8000) 返回=1 lasterr=0  GetPriorityClass=0x8000  内核里的进程基优先级=10  主线程 动态=10 基准=10

REALTIME（0x100）传进去，SetPriorityClass 返回 TRUE、GetLastError() 是 0，可 GetPriorityClass 回读是 0x80 = HIGH，内核里的基优先级 13 而不是实时类该有的 24。API 成功、参数被静默替换。写代码时 if (!SetPriorityClass(...)) 这种检查完全防不住它——必须回读。

为什么？看进程令牌里有没有那个特权：

令牌里有 5 项 privileges:
   SeShutdownPrivilege                      attrs=0x0
   SeChangeNotifyPrivilege                  attrs=0x3
   SeUndockPrivilege                        attrs=0x0
   SeIncreaseWorkingSetPrivilege            attrs=0x0
   SeTimeZonePrivilege                      attrs=0x0
TokenElevation=0
SeIncreaseBasePriorityPrivilege LUID=0:14
  启用它：返回=0 lasterr=5

令牌里根本没有 SeIncreaseBasePriorityPrivilege（5 项里没有它），显式启用时报 lasterr=5（拒绝访问）。这就是整条链的物理解释：没有该特权 → 内核把 0x100 降为 0x80 → 于是第六节”实时类”那一行的唤醒延迟和普通类一模一样。普通用户身份写不出真实时进程，这不是 API 用错了，是权限模型。要拿到它得提升令牌（管理员 + 该特权在策略里授予）。

顺带解释第一节表里那句括号：（类变了，绝对优先级从 16 起） 是探针自己的注释，错的——本机的绝对优先级上限是 15，实时类才会用到 16–31，而实时类在本机没设上。这种”探针作者（我）写下的解释”和”探针打出的数字”矛盾时，信数字。

小结

Windows 的优先级是相对档 × 进程类查出来的绝对值，可用范围 1–15：NORMAL 类 HIGHEST=10、HIGH 类 LOWEST=11、TIME_CRITICAL 恒 15、IDLE 恒 1。换类比调档狠。
严格抢占在这台机器上量的到两个形状：差 4 档时低优先级只拿 0.25%（ BELOW_NORMAL 差 3 档拿 0.01%）迭代份额；[1] 里短线程 189.5 ms 内一次都没能上核，响应时间从 29.4 ms 变 216.1/218.2 ms。后到的高优先级会当场抢下 CPU（[3]：大线程首次上核被推到 +25.4 ms）。
但优先级不是免费的：同一批任务，严格优先级平均完成 202.8 ms，同档轮转 123.7 ms——差 64%。要吞吐就别让长任务占高优先级档。
多级反馈能看到的是”会等待的线程 +1（9/8）“，忙等线程没有提升，且提升顶不过优先级顺序；完整提升轨迹需要 ETW，本机未覆盖。优先级反转实测 5 倍代价（121.8 → 624.5 ms，持锁线程迭代 3168805 → 324）；本机没测到互斥体的优先级继承生效（持锁线程动态优先级始终是 6–7），信号量与互斥体表现几乎相同（600.5 vs 624.5）。
调度延迟的下界是系统节拍：Sleep(5) 中位 15.67 ms、WaitableTimer 设 1ms 实得 15.22 ms/次，与 KUSER_SHARED_DATA+0x320 的 15.57 ms 步进同源。
实时类设不上：SetPriorityClass(REALTIME) 返回 TRUE、lasterr=0，实际类是 0x80（HIGH）、基优先级 13；根因是令牌里没有 SeIncreaseBasePriorityPrivilege，启用报 5。判据是回读 GetPriorityClass，不是看返回值。
未在本机实测：CFS 权重/vruntime、nice/chrt/SCHED_FIFO/SCHED_DEADLINE、cgroup CPU 配额、perf sched——本机只有 Windows。