Linux内核进程调度深度实战：CFS算法原理与NUMA优化

一、调度器架构演进

Linux调度器经历了几次重大变革：O(n)调度器（2.4）遍历所有可运行进程，时间复杂度O(n)；O(1)调度器（2.6.0 - 2.6.22）引入活动队列和过期数组，常数时间完成调度决策但交互识别算法复杂；CFS调度器（2.6.23至今）采用红黑树管理可运行进程，以虚拟运行时间vruntime为排序键值，实现O(log n)调度复杂度。

二、CFS核心原理

2.1 虚拟运行时间

CFS追踪每个进程的虚拟运行时间——根据优先级加权后的已运行时间。公式：vtime = (实际运行时间 * NICE_0_LOAD) / 进程权重。优先级越高权重越大，vruntime增长越慢，获得更多CPU时间。

2.2 红黑树数据结构

CFS使用红黑树组织可运行进程，最左节点即vruntime最小进程。调度取出为O(1)，插入O(log n)。

2.3 调度参数

sched_latency_ns（默认6ms）目标调度延迟；min_granularity_ns（默认0.75ms）最小抢占粒度。时间片 = sched_latency_ns / 进程数，不低于min_granularity_ns。

三、进程优先级与权重

nice值-20到+19映射为权重数组sched_prio_to_weight[40]。nice 0权重为基准1024，相邻级差约1.25倍。降低1级nice值，CPU时间增加约25%。

四、实时调度策略

SCHED_FIFO：高优先级实时进程持续运行直到主动放弃，无时间片概念。

SCHED_RR：同优先级按时间片轮转（默认100ms），更公平。

实时优先级1-99（数字越大越高），另有RT Throttling防饥饿：sched_rt_period_us和sched_rt_runtime_us控制实时进程最多占用95%CPU。

五、多核与NUMA调度

调度域(MC/DIE/NUMA)反映物理拓扑，优先同NUMA节点内均衡。CPU亲和性通过taskset绑定核心提升缓存命中率。CGroup cpu子系统(shares/cfs_period/cfs_quota)实现容器级配额控制。

六、性能调优实践

桌面场景降低抢占频率；数据库场景NUMA绑定+CPU隔离+NO_HZ_FULL；实时场景SCHED_FIFO+核心隔离+延迟监控。

七、总结

CFS以完全公平为设计哲学，统一vruntime度量+红黑树管理。理解CFS对系统调优、延迟敏感应用和容器资源管理有重要实践价值。