CPU 调度 入门

Linux 每核一条运行队列，因为全局队列意味着每次决策都要抢全局锁。所以问题从来不是「800 个线程里谁跑」，而是「这个核队列上谁拿到」。这里每个核里坐着在跑的那个任务，其余都在等；加可运行线程：

注意核并没有变忙 —— 8 个线程时它们已经饱和。长起来的是每条队列的深度，而深度就是延迟： 256 个可运行线程时，你两次上台之间另外 31 个都要跑。负载不让 CPU 变慢，它把你的任务推得更远。

底下唯一的旋钮是时间片。短时间片买到短等待，付切换开销; 长的让有效工作流得顺，代价是所有人都等。拖第一个边界：

看两条 bar 往相反方向走，注意没有哪个是错的。在4 ms(它不是谁发布的常数，而是 §03 的模型给 32 核机器、8 个可运行线程算出来的)下核的 1.1%花在切换上，最坏等待是 28 ms；拉到0.25 ms，等待塌到 1.75 ms，开销涨到 15%。

那个开销不是切换指令。切换本身是左边那条细缝；剩下的全是重填被上一个任务放凉的 cache。拖工作集：

切换大约 1.2 µs —— 这是 lmbench 的 lat_ctx 在 3 GHz x86 核上、两个零足迹进程之间量到的数， 3 GHz 上约 3,600 个周期，存寄存器、换 mm、跑一遍调度器。重填 256 KB 要 43.7 µs，是它的 36 倍，因为一个核在双路 Ice Lake 上顺序读 DRAM 大约持续拿 6 GB/s(Intel Memory Latency Checker,--bandwidth_matrix)，一条 64 字节 line 每 10.6 ns 才落一条。这已经是 Linux 肯发的最短时间片的 6%；到2 MB就是 350 µs，半个周期。

固定时间片是 Unix 调度了二十年的做法，它坏在你能感觉到的地方。把一个按键处理器排在一队计算任务后面，每个 10 ms，一直加到它越过100 ms 预算:

10 个计算任务时按键正好等 100 ms, 再往后机器就不像在听你说话了。轮转修不了：它没办法知道此刻那个处理器比第 9 个批处理值钱。

每个可运行任务带一个计数器 vruntime，跑的时候往前走，速率除以它的权重。规则是：可运行任务里 vruntime 最小的跑。下面 3 个同等任务从同一起点出发 —— 最小的那个被挑中，越过另外两个:

注意规则里没有一处说「轮流」，可你拿到的就是轮流：9 次决策后每个任务正好拿 6 ms, 6 ms 周期里的 2 ms时间片。这就是不变式 —— 任意两个可运行 vruntime 的差不超过一个时间片。

nice 就是那个权重。Linux 内置 40 项，每档约乘 1.25,vruntime 以 1024 / 权重 倍于墙钟前进。把第二个任务从公平的一半拖开：

一档 nice 挪动约 10% 的机器：nice 1 的任务拿 44%, 对面nice 0 拿 56%，而 −20 到 +19 的全跨度是 5,917 倍。因为权重除的是速率而不是卡住队列，没有谁会停下：

看 被改过 nice 的那个在 +19 时 —— 它仍然拿 0.73% 的 CPU, 另外两个各拿 50%；拖到 −20 它拿 98%，另外两个还剩 1.1%。nice 是比例不是否决，它饿不死任何东西，这正是它可以交给用户的原因。

「vruntime 最小」每个 tick 都要答一次，所以不能是扫描。CFS 把可运行集合放在按 vruntime 排键的红黑树里，答案永远是最左的节点。把队列变长：

255 个可运行任务时，那趟走是 8 层，对着平铺列表要读的 255 —— 而 Linux 连走都不用走，最左指针是缓存的。「挑」是 O(1), 只有跑完时间片的重新插入是 O(log n)，成本住在写路径上。

这就带出规则自己答不了的问题。睡了一秒的任务醒来时 vruntime 陈旧了一秒，于是遥遥领先地成为最左。拖它睡了多久, 再把落位钳制关掉：

钳制关掉时，一个睡了 200 ms 的任务被欠着 200 ms 不被打断的 CPU —— 一次阻塞读就能独占核，任何程序都能靠睡觉薅它。place_entity() 把醒来的 vruntime 往前拽到min_vruntime − sched_latency/2，不管走开多久，补偿都封顶在 3 ms。

CFS 从一个承诺出发：每个可运行任务都在 sched_latency(默认 6 ms)之内拿到 CPU。除以可运行任务数就是各自的时间片。下面周期和时间片共用一条轴：

注意 8 那里发生了什么。8 以下承诺还成立，时间片缩短来守住它；8 以上时间片会掉到0.75 ms 的最小粒度之下，于是 CFS 改为把周期拉长。 32 个可运行任务时那个「6 ms 目标」是 24 ms,64 个时是 48 ms。

更糟的是，这两个常数都不是那个常数。它们在启动时都要乘1 + ilog2(ncpus)，所以你内核真正跑的目标延迟取决于它开机时数到几个核。拖核数：

一台 32 核机器开机时是36 ms 目标延迟加4.5 ms 粒度 —— 上一段数字的 6 倍，而 32 个可运行任务时的周期是 144 ms，不是 24。拿 6 ms 跟人争之前，先读 /sys/kernel/debug/sched/latency_ns。

当别人更该拿到核时，时间片会提前结束。唤醒时 CFS 比两个 vruntime, 只有差距超过唤醒粒度才抢占。把唤醒者拖近、再拖远：

1 ms 以内，唤醒者不值一次切换 —— 花 44.9 µs 换不到一毫秒 —— 所以内核让在跑的跑完，下一次时钟中断再收拾。那就是经典的「我的线程按时醒了，但 4 ms 后才跑」，再怎么调 nice 也挪不动。

因为这个检查发生在时钟中断上，时钟中断就是上面一切的真实分辨率。这里一个 0.75 ms 时间片在两次中断之间结束，超出末尾多占的那段叫超时。改 CONFIG_HZ，再切抢占模型：

常见的 CONFIG_HZ=250 下 tick 是 4 ms, 所以一个 0.75 ms 的时间片能跑满 4 ms —— 预算的 5 倍多 —— 才被发现，而那段超时就是你的 p99。PREEMPT_FULL 把它压到 0，用吞吐来付；PREEMPT_VOLUNTARY 是服务器默认，因为大多数服务器更想要吞吐。

CFS 的弱点不是公平，而是靠近延迟的每个旋钮都是启发式。 §02 的睡眠补偿是一个， §03 的唤醒粒度是另一个，都是当年调过一次的常数。

那个量是 lag：此刻这个任务本应得到的服务量，减去它实际拿到的。lag ≥ 0 的任务是合格的；跑到前面去的不合格，根本不会被挑中。这里 T2 一上来就多拿了 4 ms —— 往前拖服务量，看它一点点挣回来：

注意合格性是一道门不是惩罚。T2 没被罚，也没失去那 4 ms, 只是在另外两个追上来之前不能被挑中 —— 那发生在总服务量 8 ms 处，三个 lag 全为 0。不变式是整个可运行集合的 lag 之和恒为 0。

第二个词是虚拟 deadline: 每个任务报一个请求大小 r, 拿到的 deadline 是 ve + r/权重。合格的里面，deadline 最早的赢。拖那个请求：

更小的请求意味着更早的 deadline，主动少要一点时间买到的是更多次上台，代价是切换。 0.75 ms 默认值给 4 个任务 2.25 ms 上界、每秒 1,333 次切换；要 0.1 ms 则上界 0.3 ms、每秒 10,000 次 —— 一次 44.9 µs，吃掉 45% 的核。

关键在于任务自己选，而份额和延迟从此分开了。这里同样 3 个任务在两个调度器下跑，T2 要 0.75 ms，另外两个拿 3 ms。两条带子都已经跑完 —— 往回拖，看任意一条怎么填出来：

两个调度器给 T2 的都正好是 33% —— EEVDF 并没有更大方。变的是形状：5 次上台而不是 3 次，最长空档 3.0 ms 而不是 4.0 ms。在 CFS 下 T2 无从开口，对延迟敏感的线程只能假装自己优先级高。

Linux 在公平类周围又放了 5 个类，严格排序：栈里位置最高、且有可运行任务的那个类赢，nice 插不上话。把一个任务在栈上上下走，越过它压得住的那些类:

注意这是先后，不是加权：一个可运行的 SCHED_FIFO 任务抢占它下面的 4 个类，并占着核直到自己阻塞。nice 挪的是比例，类挪的是绝对否决权。

SCHED_DEADLINE 走得更远，它是调度器唯一会说不的地方。你报(runtime, deadline, period)，内核把利用率加起来对着带宽上限比。把新任务要的量调高：

过了 20%，总量越过 95%,sched_setattr() 返回EBUSY —— 这个任务根本起不来，而不是先起来、以后再错过 deadline。这就是保证和优先级的区别：一个保证必须能够拒绝你。

严格先后有一个显而易见的坏法，Linux 为它配了安全带。这里一个永不阻塞的 SCHED_FIFO 死循环占着核，带宽保留量就是你 shell 的全部。把 sched_rt_runtime_us 拖到最大：

默认每 1,000,000 µs 给 950,000 时，每秒还剩 50 ms —— 够一条 200 ms 的 shell 命令用 4 秒跑完，而不是永远跑不完。把保留量推到 0，读数就不再给数字：没有 shell、没有 SSH、没有日志，唯一的恢复手段是电源键。

更隐蔽的那种坏法不需要 bug。这里一个低优先级任务持着锁,一个高优先级的在锁上阻塞, 而一个两边都不要的中优先级任务抢占了持锁者。切换那把锁，再往回拖着看两个版本：

那个高优先级任务用普通锁 11 ms 才完事，用带优先级继承的锁 5 ms —— 它被一个自己压得住的任务挡着，挡了整整「另一个不相干的任务想跑多久」那么久。1997 年火星探路者就是这么挂的。用 PTHREAD_PRIO_INHERIT，并记住它只修 mutex: 自旋锁、以及你没写过的那个库里的锁，照样会反转。

cpu.max 是硬上限，不是权重：一个组每 100 ms 周期拿到一份配额的 CPU 微秒数，花完就冻结，直到下个周期翻页。陷阱在于配额是并行花掉的。加线程，或者拖配额边界：

看一个 200 线程的 JVM 在 32 核机器上碰到一核配额：32 个线程同时跑，配额在3.13 ms里就没了，剩下的 97 ms 被冻住。应用看到一次 97 ms 停顿，没有 CPU 压力、没有 GC pause、日志里什么都没有。

直觉是把周期缩短，好让冻结短一点。把 cpu.cfs_period_us 拖下去，读最坏停顿:

它管用 —— 10 ms 周期把停顿封在 9.7 ms —— 代价是每秒 100 个执行点而不是 10 个。真正的修法在上游：告诉运行时它实际有几个核(GOMAXPROCS、-XX:ActiveProcessorCount)，因为 nproc 报的是宿主机。

第二口咬来自负载均衡器做了它该做的事。把一个任务搬到空闲的核上缩短了等待，代价是一次落在冷 cache 上的切换。搬几个过去，再把工作集调大：

256 KB 工作集时 6 个里搬 3 个，用0.14 ms 的迁移省下1.0 ms 的等待。到 2 MB，同样这一搬要花 1.1 ms 去省 1.0 ms; 6 个全搬一点没省却付了 2.1 ms —— 失衡换了一边。这就是 sched_migration_cost_ns 存在的原因。

最后一口根本不是调度器的，却是通过调度器送到的。双 socket 机器上内存挂在 socket 上，所以被均衡器搬走的线程会跨 link 读而不是就近读。拖那个比例：

Intel 的 Memory Latency Checker 在双路 Ice Lake 上量到本地 85 ns、远端 139 ns—— 1.64 倍，而 top 里什么都看不出来。Linux 按首次触碰分配，这就是为什么「一个启动线程分配大堆、然后被 40 个线程用」永远是出事的形状。

pick_next(rq):              # the whole policy
  V = avg_vruntime(rq)      # the fair-share clock
  ok = [e for e in rq if e.vruntime <= V]
  return min(ok, key=lambda e: e.deadline)

值得记住的落差在第 3 级到最后一级：一次切换是微秒级，一个被限流的 cgroup 周期是 97 ms。落差之上你靠时间片和 nice 调，落差之下你是在跟一份配额讲道理。

32 个可运行任务时，排队那版要 88 ms, 对着空闲核的 2 ms —— 44 倍 —— 而 profiler 看不出来。先读 cpu.stat 的 nr_throttled, 再看 perf sched latency 和 vmstat 1 的 r 列。

review 时的红旗

• 容器里用 nproc 定线程池大小。它报的是宿主机。
• 没有 watchdog 的 SCHED_FIFO。一个循环就能拿走整台机器。
• 实时线程共用的 mutex 没上 PTHREAD_PRIO_INHERIT。第三个任务就够。
• 把 6 ms 当延迟目标引用。它在启动时按核数放大。