一、调度器演进：为什么需要 CFS？
Linux 调度器的演进是一部不断追求"公平"与"高效"的历史。早期 Linux 2.4 使用 O(n) 遍历所有进程选择最高优先级任务，每次调度决策代价随进程数线性增长。2.6 初期引入 O(1) 调度器，使用 active/expired 双数组实现常数时间选取，但其交互式进程识别算法（sleep_avg 奖惩机制）复杂且容易误判——"I/O 密集型"与"CPU 密集型"的启发式推断在实际负载中经常失效。
2007 年 Ingo Molnár 提交 CFS（Completely Fair Scheduler），彻底抛弃"时间片"概念，改为"谁欠的 CPU 最少就先给谁运行"。CFS 的核心洞察是：调度公平 = 每个进程获得的 CPU 时间与其权重成正比。这一设计使得调度算法从启发式分类回归到简洁的数学模型。
二、CFS 核心数据结构
2.1 sched_entity 与 vruntime
每个进程的调度实体（sched_entity）中最关键的字段是 vruntime（virtual runtime），记录进程在虚拟时钟下的累计运行时间：
// kernel/sched/sched.h
struct sched_entity {
struct load_weight load; // 权重（nice 值转换）
struct rb_node run_node; // 红黑树节点
u64 exec_start; // 本次开始执行时间
u64 sum_exec_runtime; // 总执行时间
u64 vruntime; // 虚拟运行时间
u64 prev_sum_exec_runtime; // 上次总执行时间
...
};
vruntime 的增长公式为：
vruntime += (实际运行时间) * (NICE_0_LOAD / 进程权重)
权重越高的进程（nice 值越小/优先级越高），vruntime 增长越慢，因此在红黑树中位置越靠前，被调度次数越多。nice 值每差 1 级，权重相差约 1.25 倍（10% CPU 差距），这是由 prio_to_weight[] 数组决定的经典比例。
2.2 红黑树：选择 vruntime 最小的进程
CFS 使用红黑树（cfs_rq->tasks_timeline）以 vruntime 为 key 管理所有可运行进程。调度时只需取树的最左节点（__pick_next_entity()），即 vruntime 最小的进程——也就是最"亏欠"CPU的那个：
static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
{
struct rb_node *left = cfs_rq->tasks_timeline.rb_node;
// 实际通过 cached 的 rb_leftmost 直接获取
return rb_entry(cfs_rq->leftmost, struct sched_entity, run_node);
}
插入/删除/查找均为 O(log n)，即使面对数万进程的高效调度也能保持稳定延迟。
2.3 min_vruntime 与防止饥饿
每个运行队列维护 min_vruntime，表示队列中曾经出现过的最小 vruntime。新建进程或唤醒的进程的 vruntime 会被设置为 max(vruntime, min_vruntime)，防止新进程因 vruntime 从零开始而长期霸占 CPU。但过度补偿也会导致等待进程被加入时反而处于劣势，因此内核还会通过 min_vruntime 适度追赶。
三、调度时机与抢占
3.1 触发调度的时机
CFS 在以下场景触发调度决策：
- 主动让出：进程睡眠（
schedule()）、等待 I/O、获取锁失败 - 中断返回：时钟 tick（
scheduler_tick()）检测当前进程的 ideal_runtime 是否耗尽 - 唤醒抢占：唤醒的进程 vruntime 显著小于当前进程时（
check_preempt_wakeup()），立即抢占 - 新建进程：
wake_up_new_task()将新进程插入红黑树并检查抢占
3.2 时钟 tick 与理想调度周期
CFS 不分配固定时间片，而是使用"理想调度周期"（sysctl_sched_latency，默认 6ms）。对于 N 个可运行进程，每个进程的 ideal_runtime = latency / N。当一个进程的实际运行时间超过 ideal_runtime 时，task_tick_fair() 会调用 resched_curr() 设置 TIF_NEED_RESCHED 标志，在下次调度点切换。
为防止进程过多时 ideal_runtime 过短导致频繁切换，内核设置 sysctl_sched_min_granularity（默认 0.75ms）作为最低保证粒度。
四、组调度（cgroups CPU 子系统）
4.1 CFS 组调度
CFS 支持组调度（CONFIG_FAIR_GROUP_SCHED），允许将进程分组（对应 cgroup），每组有独立的 sched_entity，在父级红黑树中参与竞争。两个层级：
- 组间公平：各 cgroup 的 vruntime 反映该组整体CPU欠额
- 组内公平：同一 cgroup 内各进程按 CFS 规则竞争
用户通过 /sys/fs/cgroup/cpu/<group>/cpu.shares 设置组权重（默认 1024）。
4.2 CPU 带宽控制（cpu.cfs_quota_us）
除了按比例分配，CFS 还支持硬上限：通过 cpu.cfs_period_us 和 cpu.cfs_quota_us 组合，限制一个 cgroup 在固定周期内最多使用的 CPU 时间：
/sys/fs/cgroup/cpu/myapp/cpu.cfs_period_us = 100000 # 100ms
/sys/fs/cgroup/cpu/myapp/cpu.cfs_quota_us = 50000 # 50ms = 0.5核
超出配额的进程会在当前周期剩余时间中被节流（throttled），直到下一个周期 replenish。
五、实时调度类
5.1 SCHED_FIFO 与 SCHED_RR
Linux 内核提供两种 POSIX 实时调度策略：
- SCHED_FIFO：先进先出，不使用时间片。高优先级进程会一直运行直到主动放弃（睡眠/让出），同优先级进程不轮转。
- SCHED_RR：轮转（Round-Robin），同优先级进程共享时间片（
sched_rr_timeslice，默认 100ms），用完后放到队列末尾。
实时进程的优先级（1-99，1 最低 99 最高）始终高于普通 CFS 进程。任何可运行的实时进程都会抢占 CFS 进程。
5.2 SCHED_DEADLINE：最早截止时间优先（EDF）
Linux 3.14 引入 SCHED_DEADLINE，基于 EDF（Earliest Deadline First）算法，配合 CBS（Constant Bandwidth Server）保证实时任务的截止时间：
struct sched_attr {
.sched_policy = SCHED_DEADLINE,
.sched_runtime = 10 * 1000 * 1000, // 10ms 每次运行
.sched_deadline = 20 * 1000 * 1000, // 20ms 周期
.sched_period = 20 * 1000 * 1000, // 20ms 截止时间 = 周期
};
sched_setattr(pid, &attr, 0);
三个参数约束条件：runtime ≤ deadline ≤ period。内核通过可调度性测试保证在最坏情况下也不会超限，适合音视频处理、控制回路等硬实时场景。
5.3 实时调度的优先级继承
实时场景中经典问题是优先级反转：高优先级任务因等待低优先级任务持有的锁而被阻塞。Linux 内核通过 rt_mutex 的优先级继承（Priority Inheritance）协议解决：当高优任务阻塞在 rt_mutex 上时，临时提升锁持有者的优先级到等待者级别，确保中间优先级任务无法抢占锁持有者。
六、生产环境调优实践
6.1 chrt 设置实时优先级
# 以 SCHED_FIFO 优先级 50 运行关键音频处理程序
chrt -f 50 ./audio_processor
# 以 SCHED_RR 优先级 80 运行实时控制任务
chrt -r 80 ./control_loop
# 以 SCHED_DEADLINE 运行硬实时任务
sched_setattr --dl_runtime=10000000 --dl_deadline=20000000 --dl_period=20000000 -p 0 ./rt_task
6.2 taskset / cpuset 绑核
# 将进程绑定到 CPU 2-3
taskset -c 2-3 ./db_server
# 使用 cpuset cgroup 隔离核
mkdir /sys/fs/cgroup/cpuset/rt_tasks
echo "2-3" > /sys/fs/cgroup/cpuset/rt_tasks/cpuset.cpus
echo "0" > /sys/fs/cgroup/cpuset/rt_tasks/cpuset.mems
echo $PID > /sys/fs/cgroup/cpuset/rt_tasks/cgroup.procs
6.3 关键 sysctl 参数
# 调度粒度（影响延迟与吞吐的权衡）
kernel.sched_min_granularity_ns = 1000000 # 1ms
kernel.sched_latency_ns = 6000000 # 6ms
kernel.sched_wakeup_granularity_ns = 1500000 # 唤醒抢占容忍度
# RCU 宽限期kip实时性
kernel.sched_rt_period_us = 1000000 # 实时进程 1s 内最多跑 950ms
kernel.sched_rt_runtime_us = 950000 # 保留 5% 给普通进程
6.4 调度延迟诊断
# 跟踪调度延迟（sched_wakeup → sched_switch 的时差）
perf sched record -- sleep 5
perf sched latency
# 实时监控特定进程的 vruntime 与上下文切换
perf trace -e sched:sched_switch -p $PID
# 查看进程调度统计
cat /proc/$PID/sched
se.vruntime : 1234567.89
nr_switches : 1024
nr_voluntary_switches : 800
nr_involuntary_switches : 224
七、调度器层次：stop → dl → rt → fair → idle
内核调度类按优先级排列：
stop_sched_class # 停机调度（CPU 热插拔）
dl_sched_class # SCHED_DEADLINE (EDF + CBS)
rt_sched_class # SCHED_FIFO / SCHED_RR
fair_sched_class # CFS (SCHED_NORMAL / BATCH)
idle_sched_class # IDLE（无任务时的占位）
调度时按此顺序遍历，for_each_class 依次检查是否有可运行任务。实时任务始终被优先考虑，空闲任务仅在无其他任务时运行。
八、NUMA 感知调度
在多路服务器上，NUMA（Non-Uniform Memory Access）拓扑对调度性能至关重要。内核的 NUMA 平衡机制包括：
- NUMA balancing（AutoNUMA）：通过页错误统计热页位置，自动将进程迁移到靠近其内存的 CPU
- Sched NUMA：调度器倾向于在 NUMA 内选择目标 CPU，减少跨节点流量
- numactl：手动绑定进程到指定 NUMA 节点
对于高频交易、HPC 等场景，建议关闭 AutoNUMA（/proc/sys/kernel/numa_balancing）并使用显式 cpuset + numactl 绑定的确定性策略。
九、未来方向：extensible scheduler 与 BPF 调度器
Linux 6.12+ 引入 sched_ext（Scheduler Extension），允许通过 BPF 程序实现自定义调度策略而无需修改内核源码：
// 自定义 BPF 调度器核心逻辑
SEC("struct_ops/bpf_ext_ops")
int BPF_PROG(enqueue, struct task_struct *p, u64 enq_flags)
{
// 自定义入队策略，如基于 LLM 推理延迟的优先级选择
scx_bpf_dispatch(p, SCX_DSQ_GLOBAL, SCX_SLICE_DFL, enq_flags);
return 0;
}
这意味着用户可以像写 eBPF 一样写调度器——不再需要漫长的内核补丁 review 周期。社区已有 scx_rustland、scx_rlfifo 等参考实现，为实时音视频、游戏服务器等场景提供了低门槛的自定义调度能力。
十、总结：选型速查
| 场景 | 推荐策略 | 关键参数 |
|---|---|---|
| Web 服务器 / 数据库 | CFS（默认） | nice 调整 + cpu.shares |
| 低延迟音视频 | SCHED_RR / SCHED_FIFO | chrt + 绑核 + isolcpus |
| 批处理 / CI/CD 构建 | CFS (SCHED_BATCH) | nice +19，吞吐量优先 |
| 控制系统 / 嵌入式 | SCHED_DEADLINE | runtime/deadline/period 精细调谐 |
| 需要自定义策略 | sched_ext (BPF) | scx_rustland / scx_rlfifo |
发表评论 取消回复