调度器

kernel/src/sched/ · 全局运行队列、三调度类、唤醒抢占判定、tick 与上下文切换 —— 各项设计均给出机制、数据结构、实测数据与已知代价 · 依据:docs/architecture/design-divergences.md(D-1/D-11/D-14)、docs/development/perf-gate-baseline.md

§1设计定位:单一全局运行队列

Rux 调度子系统的核心结构是由全部 CPU 共享的单颗全局运行队列(Global Run Queue, GRQ)(设计分歧 D-1):不存在 per-CPU 运行队列,不存在负载均衡器,不存在任务偷取。空闲 CPU 经 IPI 唤醒后按需从全局队列取任务 —— 就绪集在结构上即均衡,负载不均衡及其引发的一整类公平性缺陷在该设计下不可表达。

该取舍面向桌面、移动与嵌入式级核数:当前平台以 MAX_CPUS=8 构建(kernel/src/config.rs),目标工作负载为数十至数百任务的图形会话与服务网格,而非数百核服务器。在此规模下,per-CPU 队列加负载均衡所引入的三类额外复杂度 —— 迁移决策、均衡器启发式、均衡不完备导致的公平性缺陷 —— 均为纯成本;GRQ 的两项已知代价(高核数下的争用上限、缓存局部性损失)已登记于分歧条目,并显式记录重审触发条件:当测量表明持锁进入争用受限形态时重新评估。

相对于 per-CPU 设计的关键差异是可取证性:调度序具有唯一事实源,唤醒/拣选/搁浅的全部观测仪器(§8)仅需推理单一结构。OpenHarmony 战役期间的调度缺陷族(丢失唤醒、幻影抢占计数、陈旧拣选声明)均在该单一结构上定位 —— 这属于设计目标而非偶然。

该设计属于有意的历史重采纳,而非发明。单一全局派发队列是前 SMP 经典 UNIX 的原生形态(Bach,《The Design of the UNIX Operating System》,1986)。Rux 在小核数场景重新采纳该形态,并以现代观测手段将其成本约束在实测基准范围内:用户裁定(2026-10-28)在 4 核、持锁时间呈体积耦合而非争用受限的实测条件下,per-CPU 队列化属于过度工程;维持 GRQ,后续工作限于持锁段瘦身,不变更队列模型。

成本约束的实测依据

  • 持锁时长(测量校正后):生产临界区 ≈60 ns;最小括号实测 75–80 ns。切换路径各分段(锁等待 70–84/记账 110–122/出队 58–64/拾取 89–98/所有权 68–77 ns)同为探针类读数,含仪器重量,量级对比仍有效;其中"锁等待"段是 KVM 对跨 vCPU locked 指令的税 —— 虚拟化层用管理程序模拟缓存一致性,跨 vCPU 的原子指令比裸金属贵数倍;Linux 的 per-rq 锁在同一测试平台上同样交这份税,所以它不代表 GRQ 本身慢,而是这套虚拟化测试平台的固定成本。真正属于 GRQ 的锁内工作里,树操作已降到 ~20–30 ns/次且锁内零分配,其余是 D-1 全局队列自身的记账(类链走查、所有权发布、切片算术、min_vruntime rebase、计数更新)—— 整段再压到 10 ns 级需要改动 D-1 本身,已裁定不动。
    门禁指标另计:门禁基准范围跟踪的是调用点 IF=0 段均值(spin_lock_irqsave 关中断→恢复,含锁获取等待与临界区工作):2786 ns(样本数 630 万,累计 17.6 s;KVM q35 smp2/4G,780 s 窗口,宿主负载 6.4–11.3),允许范围 2786 ns。同一次启动内调度量增长约 2× 而该项保持持平 → 该成本是执行体积的函数,而非锁缓存线争用的函数。
  • Amdahl 裁定:该持锁不是并发瓶颈(2026-11-17,用户定向分析):S(N) = 1/(s+(1−s)/N)。以真实临界区(生产 ≈60 ns,最小括号 75–80 ns)× 每次启动 630 万次取锁计,串行占比 s = 0.024–0.032% —— 8 核并行效率 ≈99.8%,Amdahl 天花板 ≈3100–4200 核;按最保守口径(调用点 IF=0 段均值 2786 ns,含锁等待)计 s = 1.13% —— 8 核效率 92.7%,天花板 ≈89 核。两个界都远高于 MAX_CPUS=8,GRQ 持锁对并发的影响微乎其微(经验佐证:4k 直接 I/O 在 numjobs 4→8 近线性扩展)。此后的持锁瘦身是切换延迟工作(每次 schedule 的路径长度),不是并发工作。
  • churn 由配置常量界定:cfs_min_granularity_ns = 0.7 ms(唤醒抢占粒度取同值)加 100 Hz tick —— 新入队任务在约 0.7 ms 的最小服务时间内不会被去调度,10 ms tick 界定重入队速率上限,唤醒风暴不具备扰动队列拓扑的通道。
  • 持锁成本已分解至段级:唤醒持锁 = 运行队列记账 / 摘除-插回 / pick / 统计四段,由 wakewatch 与 WW 普查仪器逐段计量(§8)。
  • 架构调研记录(docs/architecture/os-kernel-survey.md):Barrelfish 式复制态消息内核与 flat combining 两方案均以"携带实测数据否决"的形式登记 —— 其动机问题(高核数缓存一致性流量)在本场景不存在。

§2数据结构与锁协议

GlobalRunQueue {
    lock:      RawSpinlock,
    dl_rq:     DlRunQueue,      // BTreeMap<(deadline, task_id)>   EDF
    rt_rq:     RtRunQueue,      // 位图 [AtomicU64;2] + 按优先级链表
    cfs_rq:    CfsRunQueue,     // BTreeMap<vruntime> (tasks_timeline)
    nr_running: AtomicUsize,
    idle_cpus:  AtomicU32,      // 位图
}

per-CPU 状态仅保留 current / idle / stop 三个槽位指针。pick_next_task 的调度类顺序:stop(最高,per-CPU)→ DL → RT(本 CPU 处于 RT 带宽节流时跳过)→ CFS → idle;各调度类的 pick 均通过 PID-0 门与 DEAD-pick 门(中毒条目丢弃并计数)。

  • idle_cpus 位图:mark_idle 以 fetch_or 置位;claim_idle_cpu 在查找的同时原子清位 —— 并发唤醒不可能选中同一空闲 CPU;扫描起点绕 LAST_IDLE_HINT 轮转,使唤醒在空闲 CPU 集合上均匀分布。
  • 锁协议:lock_irqsave = 保存中断态 + 关中断 + 抢占计数 + 自旋等待;嵌套变体 lock_irqsave_nested 消费由类型化锁键(D-11)铸造的 NestProof —— 未登记的嵌套序不通过编译。GRQ 与 futex 桶锁的嵌套关系为编译期事实:在桶锁持锁下嵌套获取 GRQ 是 futex 唤醒的常规路径,反向嵌套等价于全机死锁。
  • 计数纪律:nr_running 的全部递减经由 checked-sub(fetch_update)—— 无符号回绕是历史上"未排除临界区"事故家族的特征签名,该路径已不可表达。
  • 结构性限制如实登记:CFS tasks_timeline 的 dequeue() 仍为全树线性扫描(每次 O(n)),leftmost 缓存已登记未实现;pick 对被拒条目的抬出-插回每候选支付 2 次树遍历(有界 ≤32,位于正确性关键路径,不作投机优化)。

§3CFS 调度类(fair.rs)

  • vruntime = delta_exec × NICE_0_LOAD / weight,实现为移位乘法 delta × NICE_0_LOAD × inv_weight >> 32(inv_weight = 2³²/weight);NICE_0_LOAD = 1024;SCHED_IDLE 策略实现为 fair 类内权重 3(非独立调度类)。
  • 粒度常量:SCHED_MIN_GRANULARITY_NS = 0.7 ms(同时作为唤醒抢占粒度 —— 被唤醒者须领先正在运行的任务 0.7 ms 以上方触发抢占);SCHED_LATENCY_NS = 6 ms 延迟窗;tick 100 Hz。调度时间片 = min(粒度×nr_running, 6 ms) × 本任务权重 / 总权重,下限为最小粒度。
  • 放置与睡眠信用:min_vruntime 为单调下界;唤醒/首次入队的放置基点取 avg_vruntime(与 Linux 6.6 fair.c 同构的映射);睡眠任务入队时获得 min_vruntime − 6 ms 的信用下界(睡眠时长在 vruntime 中获得等值补偿,不被清零);lag 钳制至 max(2×时间片, tick) 的 fair 域内。
  • pick 遍历与条目抬出:leftmost 遍历拒绝本 CPU 当前不可运行的条目 —— 拒绝原因五类(所有权 / on_cpu / pick 声明被其他 CPU 持有 / 亲和性 / cgroup 节流 / healed 复位)—— 每个被拒条目临时移入 32 槽 stash,pick 完成后逆序插回。min_vruntime 在全部插回之后、于完整 timeline 上更新:条目抬出会使最左端点右移,先更新将永久抹除新任务与唤醒者的睡眠信用(该顺序经实测回归后修正)。
  • entity_tick 守卫:单 CPU 密集任务不再于每个 tick 被摘除/重插/重新拣选(对齐 Linux entity_tick 的 nr_running>1 条件)。

§4RT 与 DL 调度类

  • RT(rt.rs):SCHED_FIFO/RR;100 个用户优先级编码于 [AtomicU64; 2] 位图(bit 0 = 用户优先级 99,反转编码,最低置位即最高优先),每优先级一条 ListHead 队列;RR 时间片 10 tick = 100 ms;计数递减同走 checked-sub。
  • DL(deadline.rs):EDF + CBS;BTreeMap 以 (deadline, task_id) 为键;默认周期 1 s / 运行预算 100 ms,带宽单位 1<<20。CBS 曾被完全击穿(每次入队均触发预算补充)—— 修复为真节流语义:预算耗尽的任务离开运行队列(INTERRUPTIBLE),由内核定时器于下一 deadline 处重填预算,每周期恰好补充一次。安全性论证:锁序 GRQ→TIMERS 为单向,因定时器 softirq 的 wake_up_process 派发仅发生在 TIMERS 释放之后(R12-3)。
  • stop / idle:stop 类占位(per-CPU 槽,用于热插拔与主动均衡,当前恒空);idle 任务永不入队 —— 任何唤醒立即抢占 idle 并触发重调度。

§5唤醒路径与抢占判定(D-14)

唤醒派发为三级判定梯(kernel/src/process/task.rs):

  1. 优先选取唤醒目标亲和范围内的空闲 CPU(对齐 Linux select_task_sibling + 远端入队形态):认领一颗空闲 CPU 并发送 resched IPI。
  2. 无空闲 CPU、非 sync 唤醒:通过实测等待抢占判定(D-14)—— 仅当被唤醒者的实测等待时长(sched_clock − 最近拣选时间戳)≥ 延迟窗(6 ms)时,才对忙 CPU 置位 need_resched;窗内刚运行过的任务交由时间片届期/交接机制处理。
  3. sync 唤醒且无空闲 CPU:stacking —— 维持 wake_affine 的等价性质:持有全局队列时,同步唤醒绝不通知其他忙 CPU,唤醒者将接收者叠置于自身 CPU。

不采用 vruntime 信用比较作为判定条件的原因:Linux 实现以"被唤醒者 vruntime 是否领先正在运行的任务"决定抢占。Rux 的睡眠信用下界与唤醒放置调整会使乒乓唤醒对端持续落后数毫秒 vruntime(实测:重排钳制引起 +~10 ms 的 vruntime 跳变)—— Linux 实现的判定条件在本设计的放置策略下于每次唤醒均成立,退化为逐记录的抢占-切换往返。实测等待判定仅在等待者真实等待达阈值时才中断正在运行的任务。

D-14 效果(同一测试平台对比)前后
74 字节 unix 流单记录的唤醒—抢占—切换往返开销~275 µs~2.5 µs
p5b unix DGRAM send/recv318.6 / 318.3 µs23.1 / 40.9 µs(−93%/−87%)
p5c unix 流 write 系列276.5–277.6 µs24.9–26.8 µs(−90%)
p5 IPC 族整体10–18×
p5a 管道往返(交接路径不经唤醒判定,按设计不变)19.673 µs18.306 µs(−6.9%)

已知代价(已记录在案):亚 6 ms 乒乓接收者的唤醒延迟由时间片届期界定,而非即时抢占;exec_start 以最近拣选时间戳近似真实等待,存在轻微高估;任务正在运行时的 futex 唤醒→运行延迟被 tick 量化至 ~10 ms(p2f 整轮测试:hog 场景 9.99/10.0 ms,该行为已知量化类的哨兵行)。

IPI 成本与轮询空闲

  • resched IPI 发送端单独 935–1139 ns(cctx 探针);IPI + halt 退出每次交接约 2–5 µs 的 KVM exit 开销。
  • 轮询空闲窗 120 µs:落入纯自旋空闲窗内的唤醒跳过 resched IPI(窗口由 30 µs 提升 —— 第二轮整轮测试实测 815/1915 次唤醒的 IPI 落于窗外,均值 995 ns;每次省略的 IPI 约节省 1 µs 交接开销)。与 resched_cpu 以 Dekker SeqCst 栅栏配对,丢失唤醒安全性具备形式化论证。
  • MARK_IDLE 与 WFI 之间重查 need_resched(R20-2):否则在 mark_idle 前一刻入队的任务将空转等待一个完整 tick 周期(10 ms)。

§6tick、内核抢占与 NOHZ

  • tick:per-CPU 定时器 100 Hz。scheduler_tick() 执行:softlockup 触摸、schedstat 记账、幻影位孤儿扫描、allocwatch、1 Hz CLAIM-SWEEP(持 GRQ 对整条 CFS timeline 执行陈旧拣选声明治愈)、PREEMPT-LEAK 逐任务抢占计数泄漏窗探测。
  • 内核抢占默认关闭(经由显式 schedule() 调用点自愿让出);kpreempt=1/0 引导参数可武装 irq-exit 抢占钩子;A/B 对 hog 场景读数持平 —— 维持默认关闭。
  • can_stop_tick 决策树(对齐 Linux core.c 顺序):存在 DL 任务则需要 tick;RR 任务数 >1 需要;纯 FIFO 不需要;CFS 任务数 >1(GRQ 计数加回各 CPU 非空闲 current)需要。
  • NOHZ(自适应 tick):按 Linux tick-sched.c 逐函数映射实现(check_tick_dependency / tick_nohz_stop·restart_sched_tick / tick_nohz_irq_exit / nohz_full= 参数);tick_dep 位集含 POSIX_TIMER/PERF/SCHED/RCU 等;per-rq→GRQ 的结构性映射已登记(0→1 kick 保留为入队边沿的 resched IPI)。x86_64 已接线(LAPIC one-shot),其余架构待跟进。nohz_full=1 实测(nozh 合并记录):对抗负载下 lmbench lat_syscall,null 通过 11/12(main tip 0/10),p1_null 中位 0.050 vs 0.060 µs(−17%),两条调度事件普查基准精确保持。
  • 依赖门控:负载变化时的 tick 依赖重算由 NOHZ_FULL_RUNNING 门控 —— 无门控时 can-stop 判定中对 per-CPU current 的扫描将落入每次 GRQ 持锁的入队路径(p2_ctxsw 1.242→2.149 µs,+73%,门控后消除)。

§7上下文切换(x86_64 三项优化)

切换路径经 cctx 分段计数器分解为 FPU 保存 / mm 切换 / FS·GS / 汇编体 / FPU 恢复五段:

  • 惰性 FPU:仅当 prev 任务自切入后实际使用过浮点单元才执行保存(xsaveopt);恢复移入 #NM 缺陷处理器(CR0.TS 置位);内核二进制经反汇编验证不含编译器生成的浮点指令。fpusave 51 ns + fpurest 76 ns/切换。
  • FSGSBASE:CPUID 门控;FS/GS 读写改用 wrfsbase/rdfsbase(该项占每切换 393 ns);无硬件支持时回退 wrmsr;每任务缓存镜像消除切换期 rdmsr。
  • PCID:CPUID 双门控(PCID+INVPCID);每 mm 分配 12-bit PCID,CR3 写携带 tag+NOFLUSH —— 切回先前 mm 时保留 TLB 缓存,不再执行全冲刷(PCID 前 CR3 重载 543 ns,为切换最大单项);INVPCID type 0 单页精确失效 / type 3 全冲刷;ASID 回收前于全部 CPU 同步冲刷。
  • 实测(3 次交错 A/B 取中位):lat_ctx -s64 2 4.97→2.07 µs(−58%)、-s64 8 4.68→1.94 µs(−59%)。lmbench 同机权威行(smp2 KVM,同 guest 同二进制):2.51 vs 12.84–12.97 µs(领先 5.14×;-s64 8:1.92 vs 12.06–12.08,领先 6.29×)。

§8观测仪器与门禁带

调度域观测自成体系,各仪器的用法见调试指南:

  • wakewatch:唤醒→运行延迟取证。1024 槽旁表(以 Task 指针哈希,不触碰任务结构布局),将"应运行未运行"判别为四类:WAKE-STRANDED(唤醒及时但未获拣选,输出受害任务、延迟时长、拣选 CPU)/ TIMER-LATE-FIRE(定时器超期触发)/ WAKE-REFUSED / 进程内丢失;WW5 分档计数 N250/N500/N750;搁浅阈值 1000 ms(因打印位于 IF=0 语境消耗 LIFECYCLE_TIMEOUT 预算而调高)。
  • 调度事件普查(启动期调度事件的计数器):TERM-DESCHED 8±2(DEAD 任务终末去调度循环,打印预算 n<8)、WAKE-REFUSED 32±4(W3 唤醒拒绝普查,预算 32)。两条普查在每次合格静默启动上精确一致(8/32),作为调度域的形状签名纳入性能门。
  • cctx 分段:唤醒侧 WK_N/WK_SEL/WK_ENQ/WK_DISP/IPI_N/IPI_NS;切换侧 CW_FPUSAVE/CW_MM/CW_MSR/CW_ASM/CW_FPUREST;调度侧 SCH_PRE/LOCKWAIT/ACCT/DEQREQ/PICK/PUB —— 任何切换或唤醒回归均可定位至段。
  • 门禁带(调度域):GRQ 平均持锁 2786 ns、调度事件普查 8±2/32±4、p2_ctxsw ±20%、p5 行带;GRQ pick/放置的任何改动须通过 release-strong pbench 启动验证。

§9已知代价与未决项

  • GRQ 争用上限与局部性损失:登记于 D-1;重审触发条件 = IF=0/持锁测量进入争用受限形态(当前实测为体积耦合)。
  • CFS timeline 的 O(n) 线性 dequeue 与 leftmost 缓存缺失:持锁瘦身的下一个已知目标;pick 抬出-插回的 2× 树遍历有界但真实存在。
  • p4 fork 族当前为未决回归(fork_exit 13.2 ms,历史族 9.4–10.0 ms),在门禁表 watch 行如实挂账。
  • 内核抢占默认关闭:吞吐型工作负载下与 Linux 的可选内核抢占默认不同;落后唤醒的 ~10 ms tick 量化与该选择同源 —— 消除量化依赖 NOHZ 全架构接线与 kpreempt 调优。
代码:kernel/src/sched/(sched.rs / fair.rs / rt.rs / deadline.rs / idle.rs / wakewatch.rs)。分歧登记:D-1/D-11/D-14。仪器:cctx(syscost 内)、wakewatch、调度事件普查。门禁带:docs/development/perf-gate-baseline.md 调度域行。