引言： scheduling的本质与CFS的诞生
在操作系统中，CPU是最稀缺的资源之一。当多个进程竞争CPU时，调度器必须在它们之间做出公平的分配决策。早期的Linux调度器（O(n)调度器、O(1)调度器）虽然在某些场景下表现良好，但都存在一个根本问题：如何定义"公平"？
2007年，Ingo Molnár引入了完全公平调度器（Completely Fair Scheduler, CFS），作为Linux 2.6.23内核的默认调度器。CFS的核心思想不是按时间片轮转，而是基于一个简单的数学理想：如果CPU有无限快的速度，每个进程应该获得相同比例的CPU时间。现实中的CFS通过虚拟运行时间（vruntime）来逼近这一理想模型。
一、核心数据结构：红黑树与调度实体
1.1 sched_entity：调度实体的核心抽象
CFS使用sched_entity来描述一个可调度实体。它不仅是进程的抽象，也是cgroup组调度的基础单元。一个进程可以属于一个调度组，而组内又有自己的sched_entity，形成层级调度。
struct sched_entity {
struct load_weight load; // 权重（与nice值相关）
struct rb_node run_node; // 红黑树节点
u64 vruntime; // 虚拟运行时间（核心字段）
u64 exec_start; // 本次开始执行的时间
u64 sum_exec_runtime; // 总实际运行时间
u64 vruntime_prev; // 切换前的vruntime
u64 prev_sum_exec_runtime; // 上次总运行时间
// ...
};
// 虚拟运行时间的计算（简化版）
// vruntime += (delta_exec * NICE_0_LOAD) / se->load
// 其中delta_exec是实际运行时间，NICE_0_LOAD是nice=0的权重1.2 CFS红黑树：O(log n)的高效调度
CFS将所有可运行进程按vruntime存入红黑树（rbtree）。vruntime最小的进程位于树的最左侧，即为下一个被调度的进程。红黑树的插入、删除和查找操作都是O(log n)，即使在高负载（数万进程）场景下也能保持高效。
struct cfs_rq {
struct load_weight load;
unsigned long nr_running; // 可运行进程数
u64 min_vruntime; // 树中最小vruntime（用于新进程补偿）
struct rb_root tasks_timeline; // 红黑树根节点
struct rb_node *rb_leftmost; // 最左节点缓存（快速选取）
struct sched_entity *curr; // 当前运行的实体
struct sched_entity *next; // 抢占唤醒时优先调度的实体
struct sched_entity *last; // 上次运行的实体（缓存亲和性）
};rb_leftmost指针作为一个缓存，使得选取下一个进程的操作可以达到O(1)。只有当最左进程被取出后，才需要在红黑树中重新查找下一个最左节点。
1.3 load_weight：将nice值映射为CPU权重
Linux内核预定义了一张权重转换表，将-20到19的nice值映射为不同的权重。nice值每降低1（优先级提高），获得约1.25倍的CPU时间比例。
// 内核中的prio_to_weight数组（部分）
static const int prio_to_weight[40] = {
/* -20 */ 88761, 71755, 56483, 46273, 36291,
/* -15 */ 29154, 23254, 18705, 14949, 11916,
/* -10 */ 9548, 7620, 6100, 4904, 3906,
/* -5 */ 3121, 2501, 1991, 1586, 1277,
/* 0 */ 1024, 820, 655, 526, 423,
/* 5 */ 335, 272, 215, 172, 137,
/* 10 */ 110, 87, 70, 56, 45,
/* 15 */ 36, 29, 23, 18, 15,
};
// 计算公式：
// 进程A获得的CPU时间比例 = weight_A / (weight_A + weight_B)
// 两个nice=0的进程：各获得 1024/(1024+1024) = 50%
// nice=0与nice=5的进程：1024/(1024+335) ≈ 75.4% vs 335/(1024+335) ≈ 24.6%二、虚拟运行时间：魔法公式与时间记账
2.1 核心公式解析
CFS最核心的操作是更新虚拟运行时间，该操作在每次时钟_tick和上下文切换时触发：
// 简化的vruntime更新逻辑
static void update_curr(struct cfs_rq *cfs_rq)
{
struct sched_entity *curr = cfs_rq->curr;
u64 now = rq_clock_task(rq_of(cfs_rq));
u64 delta_exec;
delta_exec = now - curr->exec_start; // 计算本次运行的物理时间
curr->exec_start = now; // 重置开始时间
// 关键公式：虚拟运行时间 = 实际运行时间 * (NICE_0_LOAD / 权重)
curr->vruntime += calc_delta_fair(delta_exec, curr);
// 更新cfs_rq->min_vruntime（单调递增）
update_min_vruntime(cfs_rq);
}calc_delta_fair的实现仅有两行：
static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
if (unlikely(se->load.weight != NICE_0_LOAD))
delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
return delta;
}对于nice=0的进程，vruntime等于实际运行时间；对于高权重（低nice）的进程，vruntime增长更慢，从而获得更多的实际CPU时间。
2.2 新进程的vruntime初始化：防止饥饿与过载
新创建的进程如果vruntime从零开始，会饿死所有已有进程。CFS通过以下策略解决：
// 新进程的vruntime初始化为当前cfs_rq->min_vruntime
// 并在place_entity中做进一步调整：
static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
u64 vruntime = cfs_rq->min_vruntime;
if (initial) // 新进程：给予一定的惩罚延迟，避免立即抢占
vruntime += sched_vslice(se, se); // 增加一个调度周期
// 保证vruntime >= min_vruntime（防回退）
se->vruntime = max_vruntime(se->vruntime, vruntime);
}对于从睡眠中唤醒的进程，不增加惩罚，它们可能等待已久，vruntime可能远小于min_vruntime，此时保留其较小的vruntime让它们尽快运行。
三、调度流程：从tick中断到上下文切换
3.1 周期性调度（tick_sched_tick）
每个CPU定时器中断触发时，内核会调用task_tick_fair，检查当前进程是否已用完了其应得的时间片：
static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
{
struct cfs_rq *cfs_rq;
struct sched_entity *se = &curr->se;
// 从叶子到根遍历cfs_rq层级
for_each_sched_entity(se) {
cfs_rq = cfs_rq_of(se);
entity_tick(cfs_rq, se, queued);
}
}
static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *se, int queued)
{
// 1. 更新vruntime
update_curr(cfs_rq);
// 2. 检查是否需要抢占
if (cfs_rq->nr_running > 1)
check_preempt_tick(cfs_rq, se);
}
// 抢占判断：当当前进程运行时间超过了"理想"值时，设置重新调度标志
static void check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
unsigned long ideal_runtime, delta_exec;
struct sched_entity *curr = cfs_rq->curr;
s64 delta = curr->vruntime - se->vruntime;
// 最小粒度检查：防止频繁切换
ideal_runtime = sched_slice(cfs_rq, curr);
delta_exec = delta_exec(curr);
if (delta_exec > ideal_runtime) // 超过理想时间片
resched_curr(rq_of(cfs_rq));
else if (delta_exec < sysctl_sched_min_granularity) // 低于最小粒度（默认0.75ms）
return; // 不切换
if (delta > ideal_runtime) // 远落后于最左进程
resched_curr(rq_of(cfs_rq));
}2.2 唤醒抢占：快速响应延迟敏感任务
当进程从睡眠中唤醒时（I/O完成、信号量释放等），CFS会尝试立即抢占当前进程：
static void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags)
{
struct cfs_rq *cfs_rq = task_cfs_rq(current);
// 检查唤醒进程的vruntime是否显著低于当前进程
if (pick_task_fair(rq, p, cfs_rq) != current)
resched_curr(rq);
}
// wakeup_preempt_entity：判断唤醒进程是否应抢占
static int wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
{
s64 gran, vdiff = curr->vruntime - se->vruntime;
if (vdiff <= 0) return -1; // 当前进程的vruntime更小，不抢占
gran = wakeup_gran(se); // 考虑唤醒粒度
if (vdiff > gran) return 1; // 差距足够大，允许抢占
return 0;
}四、组调度（Group Scheduling）与CPU控制组
4.1 bandwidth控制：cgroup的CPU配额
cgroup v1使用CFS Bandwidth Control来限制一个cgroup的CPU使用。它基于令牌桶（token bucket）算法，核心参数为cfs_period_us和cfs_quota_us：
struct cfs_bandwidth {
ktime_t period; // 周期长度（默认100ms）
u64 quota; // 周期内可用配额
u64 runtime; // 剩余运行时间（负数表示已透支）
raw_spinlock_t lock;
struct hrtimer period_timer; // 周期定时器
};
// cfs_rq对应的带宽控制
struct cfs_rq {
// ...
struct cfs_bandwidth *cfs_b;
int throttled; // 是否被限流
u64 throttled_clock; // 限流时间戳
};
// 周期定时器回调：补充配额
static enum hrtimer_restart sched_cfs_period_timer(struct hrtimer *timer)
{
// 1. 为每个限流的cfs_rq补充配额
// 2. 解除限流（unthrottle）被限制的实体
// 3. 重新设置下次定时
}使用方法示例：
# 限制组最多使用0.5核（50ms/100ms）
echo 100000 > /sys/fs/cgroup/cpu/myapp/cpu.cfs_period_us
echo 50000 > /sys/fs/cgroup/cpu/myapp/cpu.cfs_quota_us
# 限制组最多使用2核
echo 100000 > /sys/fs/cgroup/cpu/myapp/cpu.cfs_period_us
echo 200000 > /sys/fs/cgroup/cpu/myapp/cpu.cfs_quota_us4.2 层级组调度：加权公平分配
CFS支持在调度组之间按权重分配CPU。例如，两个组groupA（shares=1024）和groupB（shares=512），组内进程的CPU时间按2:1分配。每个组内的进程仍然按CFS原则公平分配本组的份额。
五、NUMA感知调度：减少远程内存访问
5.1 NUMA架构带来的挑战
在NUMA（非统一内存访问）系统中，CPU访问本地节点的内存延迟远低于跨节点访问。CFS在NUMA Balancing和调度域层做了大量优化。
struct sched_domain {
struct sched_domain *parent; // 上一层域（NUMA节点级）
struct sched_domain *child; // 下一层域（core级）
struct sched_group *groups; // 调度组（用于负载均衡）
unsigned long min_interval; // 最小均衡间隔
unsigned long max_interval; // 最大均衡间隔
unsigned int imbalance_pct; // 不均衡阈值（默认125）
// NUMA特有
unsigned int numa_faults[MAX_NUMNODES]; // 远程缺页统计
};
// 调度域层级（从低到高）：
// DIE级 → MC级（多核共享L3）→ NUMA节点级 → 全系统级5.2 NUMA Balancing：自动页面迁移
Linux内核4.0+引入了基于采样机制的NUMA自动页迁移：
- 扫描阶段：内核周期性地扫描进程地址空间的一部分，清除页表访问位（Accessed Bit）
- 缺页判断：当下一次访问发生时触发缺页，内核发现该页在远程节点
- 迁移决策：如果访问模式表明进程"归属"于另一个节点，则迁移页面
- 进程迁移：如果进程的内存大部分都在远程节点（超过25%），且远程访问频率高，则迁移进程本身
// NUMA balancing的核心结构：numa_group
struct numa_group {
spinlock_t lock;
atomic_t refcount;
int nr_tasks; // 组内任务数
unsigned int active_nodes; // 活跃节点位图
unsigned long total_faults; // 总缺页数
unsigned long *faults_cpu; // 每CPU故障统计
unsigned long faults[MAX_NUMNODES]; // 各节点故障数
int gid; // 组ID
struct rcu_head rcu;
};
// 页面迁移决策条件（简化）：
// 1. page_nid != current_node (远端页面)
// 2. p->numa_faults[page_nid] > p->numa_faults[current_node] (远端访问更多)
// 3. !pte_young(ptep) (近期未访问，非热页)5.3 AutoNUMA：自动负载均衡
AutoNUMA将进程的线程与最"亲近"的NUMA节点绑定，减少跨节点通信。关键参数：
# 查看 NUMA 平衡状态
cat /proc/sys/kernel/numa_balancing
# 0=关闭，1=开启自动NUMA平衡
# 查看进程NUMA状态
cat /proc/$(pidof myapp)/numa_maps
# 手动绑定
numactl --cpunodebind=0 --membind=0 ./myapp
taskset -c 0-7 ./myapp六、性能调优参数全解析
6.1 调度粒度参数
| 参数 | 默认值 | 说明 |
|---|---|---|
sched_min_granularity_ns | 750000 ns (0.75ms) | 最小调度粒度，防止频繁切换 |
sched_latency_ns | 6000000 ns (6ms) | 目标调度延迟：所有可运行进程至少运行一次的时间 |
sched_wakeup_granularity_ns | 10000000 ns (10ms) | 唤醒抢占粒度，降低唤醒抢占的频率 |
sched_migration_cost_ns | 500000 ns (0.5ms) | 进程迁移成本估计，影响负载均衡决策 |
# 查看调度参数
sysctl -a | grep sched
# 降低FPS游戏/实时应用的延迟
sysctl -w kernel.sched_min_granularity_ns=1000000
sysctl -w kernel.sched_latency_ns=4000000
# 增加HPC/批处理吞吐
sysctl -w kernel.sched_min_granularity_ns=5000000
sysctl -w kernel.sched_latency_ns=200000006.2 NUMA与负载均衡参数
# NUMA平衡开关
sysctl -w kernel.numa_balancing=1
# 负载均衡间隔（毫秒）
# 值越小越积极均衡，开销越大
echo 1000 > /proc/sys/kernel/sched_migration_cost_ns
# 查看当前调度统计
cat /proc/schedstat
grep sched /proc/zoneinfo # 节点级统计6.3 cgroup v2 CPU控制器调优
# cgroup v2的cpu.weight替代了shares
# 权重范围 1-10000
echo "cpu.weight 200" > /sys/fs/cgroup/myapp/cpu.max # 注意：实际格式可能不同
# cpu.max: "$MAX $PERIOD" - 每$PERIOD微秒最多用$MAX微秒
echo "50000 100000" > /sys/fs/cgroup/myapp/cpu.max # 0.5核
echo "max 100000" > /sys/fs/cgroup/myapp/cpu.max # 不限制七、生产实战：调度器问题诊断
7.1 性能诊断工具链
# 1. perf sched：调度器专用分析
perf sched record -a sleep 10
perf sched latency # 查看进程调度延迟
perf sched map # 可视化调度热力图
perf sched script # 导出原始事件
# 2. ftrace调度器跟踪
echo 1 > /sys/kernel/debug/tracing/events/sched/enable
cat /sys/kernel/debug/tracing/trace_pipe | grep "sched_switch"
# 3. bpftrace/bcc：实时调度监控
bpftrace -e 'tracepoint:sched:sched_switch { @[comm] = count(); }'
funclatency 'pick_next_task_fair' # 测量调度器选择延迟
runqlat-bpfcc # 显示运行队列延迟直方图
# 4. 查看进程调度统计
cat /proc/$(pidof myapp)/sched
se.vruntime : 1234567.890 # 当前vruntime
se.sum_exec_runtime : 98765.432 # 总运行时间
nr_switches : 12345 # 上下文切换次数
nr_voluntary_switches : 1111 # 自愿切换（等待I/O）
nr_involuntary_switches: 1max : 1234 # 强制切换（抢占）7.2 典型问题案例
案例一：CPU-bound进程响应延迟飙升
当系统中有大量CPU-bound进程时（如科学计算集群），它们的vruntime增长趋同，CFS会不断在它们之间轮转，导致延迟敏感任务（如Web服务）响应变慢。
解决方案：将关键服务放入高权重cgroup，或使用SCHED_FIFO/SCHED_RR实时调度策略。
案例二：NUMA远程访问导致性能下降50%+
在4路NUMA服务器上，如果MySQL的buffer pool分配在Node 0，而mysqld线程运行在Node 2，则内存访问延迟增加一倍以上。
解决方案：
# NUMA绑核
numactl --cpunodebind=0 --membind=0 mysqld --innodb_buffer_pool_size=128G ...
# 或利用AutoNUMA自动迁移
echo 1 > /proc/sys/kernel/numa_balancing案例三：CFS带宽限流导致突发请求延迟
当cgroup的CPU配额较严格时，突发流量导致cgroup限流（throttle），请求处理延迟急剧上升。
解决方案：使用cfs_burst_us允许短期透支：
echo 200000 > /sys/fs/cgroup/cpu/myapp/cpu.cfs_burst_us
# 允许在周期内最多使用 quota + burst 的时间八、内核演进：CFS的未来方向
8.1 即将合入的特性
- Core Scheduling：解决L1TF/TAA等侧信道攻击，将不信任的进程调度到不同的物理核心SMT超线程上
- sched_ext（Linux 6.12+）：可扩展调度器框架，允许用户空间通过eBPF实现自定义调度策略
- NUMA层级感知的内存回收：结合调度器感知优化页面回收
8.2 eBPF在调度中的应用
新的sched_ext调度器允许通过eBPF程序实现自定义调度逻辑，这对于云原生场景极为重要：Kubernetes的kube-scheduler可以直接通过eBPF在kernel层完成调度决策，避免用户态-内核态切换开销。
总结
CFS调度器是Linux内核中最精巧的子系统之一。其核心设计——基于红黑树的虚拟运行时间排序——既简洁又高效，能够在O(1)选取下一个进程和O(log n)维护数据结构之间取得平衡。从单机到数据中心，从嵌入式到超级计算机，CFS在各种场景下都展现了卓越的性能。
理解CFS不仅是理解Linux调度的关键，更是诊断和优化生产环境中性能问题的基础。建议工程师在日常工作中多用perf sched、bpftrace、以及/proc接口观察调度行为，将理论与实践结合。
发表评论 取消回复