Linux scheduler sync

sched discussion

[PATCH v9 1/2] sched/cache: Reduce the overhead of task_cache_work by only scan the visisted cpus

其它重要分析 success2026/08/18 22:427 封邮件3 个 patch
0/7 已展开

LLM 分析

调度器 cache 子系统：visited_cpus 降低 task_cache_work() 扫描开销

系列概况

  • 标题: [PATCH v9 0/2] Cache aware scheduling: Reduce the overhead of task_cache_work
  • 作者: Luo Gengkun luogengkun2@huawei.com
  • 版本: v9（cover letter 列出 v9→v8→v7→v6→v5→v4 历史）
  • 规模: 2 patches（1 主补丁 + 1 标注 DO NOT APPLY 的调试补丁）
  • 修改文件:
    • 主补丁：include/linux/mm_types.h、include/linux/sched.h、kernel/sched/fair.c
    • 调试补丁：include/trace/events/sched.h、kernel/sched/fair.c、kernel/sched/features.h
  • 代码统计: 主补丁 +47/-57；调试补丁 +91/-5
  • Message-ID: 20260731024417.1106503-1-luogengkun2@huawei.com（cover）、-2-（1/2）、-3-（2/2）
  • 完整性: 完整，含 cover letter、两 patch，以及与 Chen Yu C 的两轮 review 回复

补丁目的

cache-aware scheduling 已经合入主线。task_cache_work() 在每个 mm 上周期扫描所有 CPU 来挑选本进程最适合的 LLC（Last-Level Cache）。在多 NUMA 系统里这个扫描开销非常大，例如 Redis 多实例场景里 task_cache_work() 能占到 0.81% cycles。

补丁为每个 mm 维护一个 visited_cpus cpumask，只扫描最近真正访问过的 CPU，把一次扫描的 CPU 数从 384 降到 16 左右，使 p99 延迟下降约 25%。

旧流程的问题

旧流程调用 get_scan_cpumasks()，按 NUMA 偏好节点 / 任务首选 LLC / 当前运行节点三个维度生成候选 cpumask，结果常常覆盖大部分或全部 CPU：

  • 大量从未运行过该 mm 的 CPU 被一并扫描。
  • 很久之前访问过的 CPU 仍在候选列表里，运行时贡献早已过时。
  • 在跨节点 LLC 拓扑或大 NR_CPUS 配置下，单次扫描 CPU 数可达数百，开销随 CPU 数线性放大。

新流程

account_mm_sched(rq, p, delta_exec)
  -> pcpu_sched->epoch_last_visit = rq->cpu_epoch
  -> cpumask_set_cpu(cpu_of(rq), visited_cpus)

task_cache_work()
  -> elect a single scanner per epoch
  -> cpus = cpu_online_mask AND visited_cpus
  -> for_each_cpu_and(i, sd_llc_span, cpus)
       fraction_mm_sched(i, mm)
         if (rq.cpu_epoch - pcpu_sched.epoch_last_visit > llc_epoch_affinity_timeout)
           cpumask_clear_cpu(i, visited_cpus); return 0

要点：

  • 只记录"最近 llc_epoch_affinity_timeout 内访问过"的 CPU。
  • 超时的位由 fraction_mm_sched() 在扫描时主动清除。
  • get_scan_cpumasks() 被删除，扫描范围由 visited_cpus 单独决定。

Patch 概览

  • PATCH 1/2 主补丁：新增 visited_cpus cpumask 与 epoch_last_visit，改写 fraction_mm_sched() 与 task_cache_work()，删除 get_scan_cpumasks()。
  • PATCH 2/2 调试补丁（DO NOT APPLY）：新增 sched_cache_scan trace event、SC_VISIT / SC_NODE 两个 sched feature（默认关），用于复现并测量扫描成本。

关键实现

/* include/linux/mm_types.h mm_alloc_sched_noprof */
if (!zalloc_cpumask_var(&mm->sc_stat.visited_cpus, GFP_KERNEL)) {
    free_percpu(pcpu_sched);
    return -ENOMEM;
}

/* kernel/sched/fair.c fraction_mm_sched 重写 */
if ((rq->cpu_epoch - pcpu_sched->epoch_last_visit) > llc_epoch_affinity_timeout) {
    cpumask_clear_cpu(cpu, mm->sc_stat.visited_cpus);
    return 0;
}

/* kernel/sched/fair.c account_mm_sched 新增位记录 */
pcpu_sched->epoch_last_visit = epoch;
if (!cpumask_test_cpu(cpu_of(rq), mm->sc_stat.visited_cpus))
    cpumask_set_cpu(cpu_of(rq), mm->sc_stat.visited_cpus);

/* kernel/sched/fair.c task_cache_work 用 visited_cpus 限定扫描 */
cpumask_and(cpus, cpu_online_mask, mm->sc_stat.visited_cpus);
for_each_cpu_and(i, sched_domain_span(sd), cpus) {
    cur = rcu_dereference_all(cpu_rq(i)->curr);
    if (cur && !(cur->flags & (PF_EXITING | PF_KTHREAD)) && cur->mm == mm)
        nr_running++;
    occ = fraction_mm_sched(i, mm);
    if (occ == 0)
        continue;
    /* ... */
}

注释里明确：扫描 visited_cpus 时无锁，与 account_mm_sched() 并发置位存在 data race，是为避免锁开销的故意权衡；下一轮 epoch 会自然补回。

类比

把 cache-aware 调度比作公司每月给员工重新挑工位：

  • 旧流程：HR 把整栋办公楼的工位全看一遍，多数楼层跟这个员工毫无关系。
  • 新流程：HR 只翻员工最近一周实际坐过的楼层（visited_cpus）；某楼层超过一个月没人坐，就从候选清单上划掉（epoch_last_visit + timeout）。
  • 新出现的楼层会随打卡自动加入清单（account_mm_sched() 中的 set bit），形成一个自动维护的"近期活动楼层表"。

Highlight：风险与注意点

  1. Data race：扫描 visited_cpus 时无锁，可能漏掉扫描瞬间刚被 account_mm_sched() 置位的 CPU。作者认为这类遗漏的运行时贡献在下个 epoch 自会补回。
  2. 单线程进程噪声：Chen Yu C 指出 visited_cpus 位只在 fraction_mm_sched() 内部被清除，而该函数在 invalid_llc_nr() 让单线程进程短路时不会被调用，结果就是单线程进程一直 cpumask_set_cpu 但从不消费。
  3. 跨 NUMA 抖动：若仅靠 visited_cpus 而忽略 NUMA 偏好，挑选 LLC 时可能在不同 epoch 之间跨节点切换。Chen Yu C 建议改用 cpumask_and(cpus, get_scan_cpumasks(...), visited_cpus) 做交集。
  4. 作者回应：Luo Gengkun 认为加 gate 不必要，开销几乎为零，且同路径上有更重的 __update_mm_sched()；若要优化更值得看那里。
  5. 准确性 vs 效率：扫描范围收窄换性能，命中率下降需要靠 trace event 与 Redis/hackbench 长期观察。

版本变化

  • v9 → v8：扫描循环改用本地 for_each_cpu_and(i, sched_domain_span(sd), cpus)，缩小读取 mm->sc_stat.pcpu_sched 的 race window；注释更新为"elect a single scanner per epoch"。
  • v8 → v7：移除 get_scan_cpumasks()，由 visited_cpus 单独提供扫描范围。
  • v7 → v6：新增 race condition 注释。
  • v6 → v5：visited_cpus 改用 cpumask_var_t 动态分配，避免 NR_CPUS 大时每进程内存膨胀；LLC span 与 visited_cpus 直接求交；epoch_timeout 重命名为 epoch_last_visit；__update_mm_sched 移到 timeout 检查之前。
  • v5 → v4：恢复 get_scan_cpumasks() 以兼容 NUMA_BALANCING 约束。

一句话总结

v9 通过为每个 mm 维护"最近访问过的 CPU"位图，让 task_cache_work() 只扫描真实活跃的核心，把多 NUMA 系统中 cache-aware 调度的 p99 延迟降低约 25%，但 Chen Yu C 仍提出单线程进程噪声与跨节点抖动两个后续讨论点。