Linux 调度器：从可运行任务到 CPU 时间分配

一个请求的数据已经准备好，处理线程也被唤醒了，却迟迟没有响应。此时需要沿调度器的几个判断继续追踪：⁠在哪运行、能分多少 CPU、这一刻轮到谁⁠。

本文以普通公平调度为主。Linux 从 6.6 开始引入 EEVDF；数值模型用于理解算法，实现细节以本机 Linux 7.2 为对照。

1. 运行队列回答“谁现在有机会运行”

Linux 主要按 CPU 维护运行队列。当前任务和等待执行的任务都可能是 TASK_RUNNING，但睡在 I/O 或条件等待中的任务不会因为优先级高就继续消耗 CPU。唤醒路径更新任务状态、选择合适的 CPU 并入队；如果新任务值得抢占当前任务，会触发重新调度请求。

重新调度请求不是任意指令点上的强制跳转。内核要在相应可调度位置检查请求；中断、抢占关闭、锁约束和内核抢占模型都会影响交接时机。调度器即使运行了一次，也可能仍选中当前任务，因此“执行 schedule”与“发生一次 prev != next 的上下文切换”也不能画等号。

每 CPU 队列减少了全局争用，但不代表调度完全是本地操作。唤醒远端任务、拉取负载、迁移任务需要协调多个 CPU 和队列锁。CPU 亲和性、cpuset、生效中的调度策略先限定候选范围；负载均衡只能在允许的范围内改善分配，不能为了看起来均匀就绕过隔离设置。

2. 公平的计量：把实际时间换算成虚拟服务

先看一个只有 A、B 的理想模型：两者持续可运行，权重为 2:1，共享一颗 CPU 的 9 ms 时间。按权重分配，A 得到 6 ms，B 得到 3 ms。

两者实际时间不同，但除以各自权重后，都前进了 3 个虚拟单位。⁠权重大者的虚拟时钟走得慢，需要运行更久才能追上相同的进度。

常用表达为：

$$\Delta v_i=\Delta t_i\frac{w_0}{w_i}$$

其中 $w_0$ 是基准权重。

例如 nice 0 的基础权重为 1024，nice 5 为 335。若只有它们在同一公平调度层级、同一 CPU 上持续竞争，前者的理想份额约为 1024 / (1024 + 335) = 75.35%。

这个比例随竞争集合变化：对方阻塞后，前者可以使用更多空闲时间；加入新任务或 cgroup 层级后，需要重新计算份额。nice 表达相对权重，不是固定 CPU 百分比。

下面把权重画成宽度、实际时间画成面积。调节分配和权重，高度便显示谁得到了更多归一化服务。

经典 CFS 用 vruntime 接近“谁获得的归一化服务最少”，优先让落后者补上。这样能解释长期份额，却还不充分表达一个短请求应该多快获得响应。EEVDF 在此基础上将是否有资格运行与合格请求的先后次序分开。

3. EEVDF：资格门槛与虚拟截止期的分工

第一步：用 lag 判断是否有资格

在一个固定可运行集合的简化模型中，令任务虚拟运行时间为 vᵢ，权重为 wᵢ，系统虚拟时间 V 为其加权平均。任务服务差额可写成：

$$V=\frac{{\sum }_i{w}_i{v}_i}{{\sum }_i{w}_i},{\mathrm{lag}}_i=w_i(V-v_i)$$

零 lag 也具有资格。正 lag 表示相对公平基准少得到了一些服务，有资格参与选择；负 lag 表示已经超前，暂时不该仅凭短请求继续抢占别人。

第二步：在合格请求中比较期限

若当前请求希望获得实际运行量 rᵢ，其虚拟截止期可用下式理解：

$$d_i=v_{i,\mathrm{start}}+r_i\frac{w_0}{w_i}$$

上式描述一项新请求建立期限时的关系，此时 vᵢ 是该请求的起始虚拟位置。请求执行期间 vruntime 继续增长，已经确定的 deadline 不应随它不断向后平移；新的请求才重新确定期限。下面的快照选择各任务在请求起点的状态，以便直接比较。

在合格实体中，优先选择虚拟截止期较早者。这里的 deadline 是虚拟服务坐标⁠，不是墙钟时刻，也不是 SCHED_DEADLINE 的实时完成保证。

推演：为什么最后选 B

考虑三项等权任务，基准权重归一化为 1：

此时 V = (98 + 99 + 103) / 3 = 100。如果只取最小 vruntime，会选 A；如果只取最小 deadline，会选 C；EEVDF 在这个快照选择 B。C 的短请求不能抵消它已多得服务的事实，而 B 比 A 更早到期的合格请求获得优先响应。这就是两个判断必须分开的原因。

改变 C 的服务位置会影响资格；改变 B 的请求量会影响期限，但不改变已经得到的服务。每次调参都是新的请求快照。

可以直接运行这个小模型检查结果；它不模拟 Linux 的唤醒、层级和迁移逻辑：

from fractions import Fraction as F

tasks = {
    "A": {"w": F(1), "v": F(98), "r": F(10)},
    "B": {"w": F(1), "v": F(99), "r": F(5)},
    "C": {"w": F(1), "v": F(103), "r": F(1, 4)},
}
V = sum(t["w"] * t["v"] for t in tasks.values()) / sum(
    t["w"] for t in tasks.values()
)
eligible = {}
for name, t in tasks.items():
    lag = t["w"] * (V - t["v"])
    deadline = t["v"] + t["r"] / t["w"]
    print(name, "lag=", lag, "deadline=", deadline)
    if lag >= 0:
        eligible[name] = deadline
assert V == 100
assert min(eligible, key=eligible.get) == "B"

从教学模型到内核实现

缩短请求量能影响响应顺序，但不会自动增大任务的长期权重。真实内核还要防止任务通过“运行到超前就短暂睡眠，醒来重新领信用”的方式破坏公平；睡眠时的 lag 保存、衰减和延迟出队记账，都是维护这个约束的手段。延迟出队中的记账实体不等于一个仍在等待事件的任务可以执行用户代码。

真实实现还要解决查找成本。本机 kernel/sched/fair.c 的相关树按 deadline 组织，用子树 vruntime 信息帮助剪枝查找合格实体；pick_eevdf() 还处理当前请求保护。

分层组实体、入队/出队修正和整数精度，让 V 的维护比固定集合平均值复杂。阅读源码时，可以先核对“资格与期限”两个判断，再追踪这些实现细节。EEVDF 文档、CFS 设计

4. 调度策略与调度类：不要混用三种 deadline

普通任务通常使用 SCHED_OTHER，内核也常称 SCHED_NORMAL；公平类内部采用 EEVDF，不存在一个要求应用改成 SCHED_EEVDF 才能启用的通用策略。实时策略和可扩展调度则是另外的选择：

通常 deadline 类先于实时类，实时类先于公平类；内核还有 stop 等内部类，启用 sched_ext 时应结合运行模式阅读类次序，不能把一张三行表当成全部实现。

对照：调度期限与业务超时

以 runtime=2 ms、deadline=10 ms、period=10 ms 为例：任务声明每周期最多需要 2 ms CPU 服务，并要求相应期限。参数需要满足 runtime ≤ deadline ≤ period 等约束，还要通过准入检查。

它不会替应用每隔 10 ms 自动调用函数。应用仍要释放工作、控制执行预算并分析阻塞，才能讨论时限是否可行。

这三种期限分属不同层次，不能相互替代。SCHED_DEADLINE、sched_ext

5. cgroup：权重决定竞争份额，quota 决定可用上限

组权重：先分给组，再分给任务

公平调度可以分层。假设根下有 A、B 两组，权重 2:1，A 中两个等权持续可运行任务，B 中一个；仅考虑一颗 CPU、没有 quota 时，A 先获得约 2/3，再在组内各分 1/2，所以三个任务各约 1/3。若 A 再增加一个任务，A 仍约 2/3，内部各约 2/9；B 中唯一任务仍约 1/3。组隔离让“多创建几个线程”不必直接侵占另一个组的份额。

quota：多核共同消耗一份预算

cpu.weight 描述相对份额，不是预留资源，也不是严格上限。cpu.max 则限制周期内组的总 CPU 时间。例如 50000 100000 是 100 ms 周期最多使用 50 ms CPU 时间。若两线程在两颗 CPU 上同时运行，它们可以约 25 ms 就耗尽合计 50 ms 的预算，然后被节流到后续补充；不能按“每颗 CPU 各允许用 50 ms”理解。

调节并行数，再把墙钟时间拖过周期边界。各条 CPU 运行带都从同一份预算扣除时间。

回到开头的慢请求：即使全机还有空闲 CPU，这个 cgroup 的本周期预算也可能已经耗尽。⁠供给还有剩余，不代表该组仍有使用额度。

检查时，把 cpu.stat 的节流次数/时间、cpu.max 和请求延迟放在同一时间窗口比较。节流增量提供排查线索，具体慢请求仍需结合应用锁、I/O 和上层队列分析。cgroup v2 CPU 控制器

6. 多核放置：均匀不一定最快

两颗 CPU 各运行一项任务，看起来比一颗拥挤、一颗空闲更合理，但迁移有代价。任务刚在 CPU 0 填热缓存，迁到 CPU 1 会损失局部性；若数据主要在另一个 NUMA 节点，内存访问还可能变远。SMT 兄弟线程共享执行资源，也不能机械地当成两颗完全独立的核心。调度器因此在空闲容量、缓存、拓扑与能耗之间权衡。

PELT 等历史信号帮助估计任务近期的运行/可运行行为。利用率、可运行负载和带权负载不是同一个数：一个任务等待 CPU 很久可能体现排队压力，而真正执行比例才直接反映已消耗的算力。短暂采样看到某 CPU 100% 并不能预测迁移一定获益，也不能保证它是全部系统瓶颈。

唤醒放置、周期性均衡和空闲 CPU 拉取工作会在不同情境发生。亲和性与 cpuset 缩小候选集合，异构 CPU 的能力与能耗策略进一步改变选择。因此排查时应先确认任务实际允许使用哪些 CPU，再解释负载是否不均；对被绑在一个 CPU 的任务，增加其他 CPU 数量不会自动消除排队。

7. 可重复的只读观察

下面只查询当前 Python 进程的策略、nice、亲和性及部分调度统计，不修改策略或系统配置。/proc/self/sched 的字段受内核配置影响，不应作为固定列数格式解析。

import os
from pathlib import Path

print("policy:", os.sched_getscheduler(0))
print("nice:", os.getpriority(os.PRIO_PROCESS, 0))
print("allowed CPUs:", sorted(os.sched_getaffinity(0)))
try:
    for line in Path("/proc/self/sched").read_text().splitlines():
        if any(key in line for key in (
            "se.sum_exec_runtime", "nr_switches", "nr_voluntary_switches",
            "nr_involuntary_switches", "se.load.weight", "policy", "prio"
        )):
            print(line)
except OSError as exc:
    print("sched statistics unavailable:", exc)

要把一次延迟拆开，分别观测事件发生、sched_wakeup 和任务真正出现在 sched_switch 的 next 位置的时间。唤醒到运行的间隔反映运行队列等待及相关调度延迟；执行时间又包含应用自己的工作。它们都不等于一次寄存器和地址空间切换的纯成本。下一篇上下文切换沿具体交接说明这些边界。