Software Systems Atlas

中文

English

中文

English

主题

10.2 Linux 调度类、CFS 与 EEVDF ​

地心调度台上的纸面题只有一条 ready queue，真实控制台却同时接着普通服务、批处理任务和有 deadline 的控制线程。机器还有多个 core，任务可能属于不同 cgroup，散热和能耗策略也会改变可用算力。把所有 task 塞进一棵“万能红黑树”解释，已经不够了。

10.1 调度指标与经典算法建立评价尺度。这一课转向 Linux：它同时维护不同 scheduling class，还要处理 SMP、cgroup 与 energy policy。这里只保留跨版本稳定的概念；源码字段和选择规则以运行内核为准。

先确认 task 属于哪一个调度类 ​

Linux scheduler core 通过 scheduling class 组织不同策略。普通 workload、real-time 与 deadline task 不在同一套选择规则里。

常见 user-visible policy 包括：

Policy用途轮廓主要参数
SCHED_OTHER / SCHED_NORMAL普通分时 tasknice/weight、fair scheduling state
SCHED_BATCHCPU-heavy batch降低交互抢占倾向
SCHED_IDLE极低权重后台工作比 nice 19 更弱的普通类策略
SCHED_FIFOfixed-priority real-timeRT priority，无 RR quantum
SCHED_RRfixed-priority real-timeRT priority + round-robin quantum
SCHED_DEADLINEreservation/deadlineruntime、deadline、period

class precedence 与内部 stop/idle class 还有实现细节。普通用户也未必有权限设置 RT/deadline policy；RLIMIT_RTPRIO、capability、cgroup 和 security policy 都会参与。

一个 runnable SCHED_FIFO task 可以长期压住普通 task。RT policy 不是“更快”按钮：程序若死循环、持锁或 page fault，可能让整机失去响应。部署前需要 CPU reservation、watchdog、lock protocol 和 failure recovery。

用 API 读取当前 policy ​

下面的 Linux/POSIX 程序只读取自身 policy、priority 与 nice，不修改系统状态：

c
#define _GNU_SOURCE
#include <errno.h>
#include <sched.h>
#include <stdio.h>
#include <sys/resource.h>

static const char *policy_name(int policy) {
    switch (policy) {
        case SCHED_OTHER: return "SCHED_OTHER";
        case SCHED_BATCH: return "SCHED_BATCH";
        case SCHED_IDLE: return "SCHED_IDLE";
        case SCHED_FIFO: return "SCHED_FIFO";
        case SCHED_RR: return "SCHED_RR";
#ifdef SCHED_DEADLINE
        case SCHED_DEADLINE: return "SCHED_DEADLINE";
#endif
        default: return "unknown";
    }
}

int main(void) {
    int policy = sched_getscheduler(0);
    if (policy < 0) {
        perror("sched_getscheduler");
        return 1;
    }

    struct sched_param parameters;
    if (sched_getparam(0, &parameters) != 0) {
        perror("sched_getparam");
        return 1;
    }

    errno = 0;
    int nice_value = getpriority(PRIO_PROCESS, 0);
    if (nice_value == -1 && errno != 0) {
        perror("getpriority");
        return 1;
    }

    printf("policy=%s rt_priority=%d nice=%d\n",
           policy_name(policy), parameters.sched_priority, nice_value);
    return 0;
}

sched_priority 对普通 fair policy 通常为 0；nice 属于另一套权重接口。不要把二者加在一起当成统一 priority number。

还可用只读命令观察：

bash
chrt -p "$$"
ps -o pid,cls,rtprio,ni,pri,psr,stat,comm -p "$$"
sed -n '1,40p' /proc/self/sched

最后一条的 /proc/self 指向 sed 自己，不是 parent shell。若要看 shell，请把 $$ 展开进 /proc/$$/sched。

CFS 的历史模型：追赶理想公平 CPU ​

Completely Fair Scheduler 在 Linux 2.6.23 合入。它用“理想多任务 CPU”建立普通 task 的 weighted fairness 模型：若 n 个同权 runnable task 可以真的同时运行，每个应得到 1/n CPU。

经典 CFS 为每个 scheduling entity 维护 virtual runtime。实际运行时间按 nice weight 归一化：

text
delta_vruntime ≈ delta_exec × NICE_0_LOAD / weight

高 weight task 的 vruntime 增长较慢，长期得到更大 CPU share。run queue 中的 entity 按 vruntime 排序，经典选择逻辑偏向最小 vruntime；min_vruntime 为新唤醒/迁入 entity 提供基准，防止无限累积 sleeper bonus。

红黑树是这一历史实现的重要结构，但“取左端最小 vruntime”不应继续充当所有现代 Linux 的完整 pick-next 契约。官方 CFS documentation 已明确写出 CFS 正在给 EEVDF 让位。

CFS 也不是“没有 slice”。官方文档所说的“没有传统固定 timeslice”是指它不采用旧 scheduler 那种按 HZ/nice 固定量子的模型；fair class 仍需决定 entity 一次运行多久，并有 base slice/granularity 等机制控制 preemption 与 cache thrashing。

nice 是相对权重，不是 deadline ​

普通 task 的 nice 范围通常是 -20 到 19，数值更低代表更高 weight。相邻 nice level 按近似乘法权重变化，使相对 share 不依赖绝对起点。

两项限制经常被漏掉：

  • nice 决定的是竞争同一 fair hierarchy 时的 CPU share 倾向，不保证某次请求在多少毫秒内响应；
  • autogroup、cgroup task group、CPU quota 与多核 load balancing 会改变两个 process 的实际 share。

普通用户通常可把自己的 task nice 调大（更“礼让”），调小需要相应权限或 limit。nice(1)、renice 与 setpriority 的权限和容器行为应在目标环境验证。

EEVDF：调度台先判断谁有资格，再比较 virtual deadline ​

控制台不能把“欠了多少公平服务”和“接下来选谁”混成一个数字。EEVDF 先用 lag 判断 entity 是否 eligible，再在可选者中比较 virtual deadline。这里的 deadline 属于调度模型，不是业务承诺的完成时间。

Linux 从 6.6 开始把 fair scheduling 选择逐步转向 Earliest Eligible Virtual Deadline First。EEVDF 仍使用 virtual time 与 weight 衡量公平份额，但不只选最小 vruntime。

按官方 EEVDF documentation 的概念：

  1. 计算 entity 的 lag，表示它相对公平份额是“被欠 CPU”还是“已经超额”；
  2. lag 非负的 entity 才 eligible；
  3. 在 eligible 集合中，选择 virtual deadline 最早者；
  4. requested slice 会影响 virtual deadline，使 latency-sensitive task 可以请求较短 slice。

正 lag 表示应补回 CPU，负 lag 表示已超过应得份额。公式与字段会随实现演进，应用不应依赖 /proc 中内部数值保持格式稳定。

EEVDF 还要处理 sleeping task 的 lag。若 task 一 sleep 就立即清掉负 lag，它可以反复短睡来骗取响应优势；当前设计使用 deferred dequeue/lag decay 等机制，让公平债务随 virtual time 处理。这个部分仍是实现演进区域，教程只保留动机与官方文档入口。

virtual deadline 不是业务 deadline ​

EEVDF 的 virtual deadline 用于 fair-class 内部选择，不能替代产品 SLA 或 SCHED_DEADLINE 的 reservation 参数。

SCHED_DEADLINE task 描述 runtime、deadline、period，kernel 做 admission/control bandwidth 以限制总预留。即使 admission 成功，应用仍要避免不可控 page fault、锁依赖、device delay 与超过 runtime budget。

业务 request deadline 又在更上层。一个 web request 可能跨多 thread、network hop 与 database；给 worker 改 nice 不能自动传播 end-to-end deadline。

real-time class 与 priority inversion ​

SCHED_FIFO 同 priority task 通常运行到 block、yield、priority change 或被更高 RT priority 抢占；SCHED_RR 在同 priority 上增加轮转 quantum。两者都优先于普通 fair task。

若 low-priority thread 持有 high-priority thread 所需 mutex，medium-priority runnable thread 可持续抢占 low，形成 unbounded inversion。POSIX mutex attribute 的 PTHREAD_PRIO_INHERIT 可请求 priority inheritance，但实现支持、policy combination 与 nested lock 行为必须检查。

继承只在 owner 已知的 mutex dependency 上帮助，不会修复 semaphore misuse、I/O server priority、page fault 或任意 lock-free dependency。实时分析要计算 blocking bound，而不是只打开一个 attribute。

cgroup 与 quota 改变“公平”的层级 ​

container/service 常先在 group 之间分配 CPU，再在 group 内调度 task。CPU weight 决定相对 share，CPU quota/period 可以给 group 设置 bandwidth 上限；quota 耗尽后，即使机器某处还有 CPU，group 也可能被 throttle 到下一周期。

这会造成看似“scheduler 不公平”的 tail latency。排障时同时检查：

bash
cat /proc/self/cgroup
cat /sys/fs/cgroup/cpu.stat
cat /sys/fs/cgroup/cpu.weight
cat /sys/fs/cgroup/cpu.max

路径和文件适用于 cgroup v2 的常见挂载，容器内权限与 namespace 可能只暴露子树。不要在教程实验里直接修改 host cgroup 配置。

SMP load balance 让公平不再是一棵树 ​

每 CPU run queue 降低 global lock contention，也保留 cache locality；scheduler domain 定期或在 idle/wakeup 时 balance load。task migration 可能改善利用率，却损失 warm cache、TLB locality 与 NUMA placement。

heterogeneous system 还要考虑 CPU capacity 与 energy-aware scheduling。utilization clamp（uclamp）可给频率/placement 提示，但它不是硬 deadline 保证。

因此，从单个 task 的 vruntime 不能独立预测它下一纳秒在哪个 core 运行。CPU affinity、cpuset、IRQ、SMT sibling 与 thermal throttling 都会参与观测结果。

调度排障从 delay 分解开始 ​

一个 request 慢，可能时间花在：

  • runnable 但没获得 CPU：run-queue delay；
  • blocked on mutex/futex；
  • sleep 等 I/O/timer；
  • cgroup throttling；
  • page fault、memory reclaim；
  • CPU migration 后 cache/NUMA penalty；
  • 实际在 CPU 上执行太久。

只看 process %CPU 无法区分。可组合 scheduler tracepoint、perf sched、PSI、cgroup cpu.stat、off-CPU profiler 和 application span。观测工具有开销，字段也依 kernel/version，先在 staging 校准。

yield() 很少是修复方案。它只把当前执行机会交还 scheduler，不能表达“等 queue 非空”或“等 lock 释放”；用 condition variable、eventfd、futex-backed primitive 才能把等待原因交给内核。

动手核对运行内核 ​

  1. 运行读取程序，比较普通 shell、nice -n 10 与 chrt 查询结果，不提升权限。
  2. 在两个 CPU-bound process 间调整 nice，测量长期 CPU share，而不是单次 response。
  3. 给其中一个 process 放进受 quota cgroup，观察 nr_throttled 与 tail latency。
  4. 用官方文档分别写出 classic CFS 与 EEVDF 的 pick-next 条件，禁止混成一句话。
  5. 设计一个 priority-inversion trace，说明 inheritance 能缩短哪段 blocking。
  6. 区分 EEVDF virtual deadline、SCHED_DEADLINE 参数和 HTTP request deadline。

下一步：调度器如何让 mutex waiter 睡下去 ​

调度算法决定 runnable task 的顺序，mutex implementation 决定竞争者继续 spin 还是进入 kernel wait queue。下一章进入锁实现与动态存储，会先把原本混在一起的 lock 与 allocator 拆成两篇。

Built with VitePress | Software Systems Atlas

Copyright 2026 Steven Yang