引言
在 Linux 内核的演进历程中，调度器始终是最核心的组件之一。2.6.23 内核引入的完全公平调度器（Completely Fair Scheduler, CFS）彻底改变了 Linux 进程调器的设计哲学——它不再基于传统的时间片分配，而是引入了一个 elegant 的概念：虚拟运行时间（vruntime）。本文将深入剖析 CFS 的内部机制，从数据结构到算法实现，从调度策略到性能调优，带你全面理解这个支撑现代 Linux 系统的调度核心。
一、CFS 的设计哲学
CFS 的核心思想极其简洁：让所有可运行的进程公平地分享 CPU 时间。为了做到这一点，CFS 为每个进程维护一个虚拟运行时间 vruntime——进程在虚拟时钟下的"已运行时间"。当需要进行调度决策时，CFS 总是选择 vruntime 最小的进程来运行。
这种设计有几个关键特征：
- 无时间片：CFS 不使用传统意义上的时间片，而是通过 vruntime 的增长速率来控制每个进程获得的 CPU 份额
- 理想多任务处理器模型：CFS 设想一个"完美多任务处理器"，能同时以相同速度运行所有任务，每个任务的虚拟时间等于实际时间。真实系统中任务数有限，vruntime 就是对这个理想模型的逼近
- 权重机制：不同 nice 值的进程具有不同权重，权重越高的进程 vruntime 增长越慢，从而获得更多的实际 CPU 时间
二、核心数据结构
2.1 调度实体 sched_entity
每个进程的调度信息保存在 task_struct->se（struct sched_entity）中。关键字段包括：
struct sched_entity {
struct load_weight load; // 权重（由 nice 值决定）
struct rb_node run_node; // 红黑树节点
unsigned int on_rq; // 是否在运行队列中
u64 exec_start; // 本次调度的开始时间
u64 sum_exec_runtime; // 累计实际运行时间
u64 vruntime; // 虚拟运行时间（核心字段）
u64 prev_sum_exec_runtime; // 上一次调度时的 sum_exec_runtime
// ...
};vruntime 是 CFS 的核心度量。vruntime 的增长速率与进程权重成反比：权重越高，vruntime 增长越慢，因此更频繁地被选中执行。
2.2 运行队列 cfs_rq
每个 CPU 的 CFS 运行队列由 struct cfs_rq 表示：
struct cfs_rq {
struct load_weight load; // 运行队列总权重
unsigned int nr_running; // 可运行任务数
u64 min_vruntime; // 队列中最小的 vruntime（单调递增）
struct rb_root tasks_timeline; // 红黑树根节点（按 vruntime 排序）
struct rb_node *rb_leftmost; // 最左侧节点（缓存，即 vruntime 最小的节点）
// ...
};值得注意的两个设计：
rb_leftmost缓存了最左侧节点，使获取最小 vruntime 的进程变为 O(1) 操作min_vruntime是单调递增的基准值，新加入进程的 vruntime 至少为min_vruntime，防止新进程过度抢占
三、CFS 红黑树调度机制
3.1 入队操作
当进程变为可运行状态时，调用 enqueue_entity() 将调度实体插入红黑树：
static void enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
// 如果是新唤醒的任务，调整 vruntime 基准
if (flags & ENQUEUE_WAKEUP)
place_entity(cfs_rq, se, 0);
// 更新运行队列统计
cfs_rq->load.weight += se->load.weight;
cfs_rq->nr_running++;
se->on_rq = 1;
// 插入红黑树
enqueue(cfs_rq, se);
}3.2 place_entity：新进程的 vruntime 放置策略
对于新唤醒的进程（ENQUEUE_WAKEUP），place_entity() 决定了它的初始 vruntime：
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(cfs_rq, se); // 放在后面一点
else // 刚唤醒的进程
vruntime -= sysctl_sched_latency; // 给予优待
// 保证不小于 min_vruntime
se->vruntime = max_vruntime(se->vruntime, vruntime);
}对于刚唤醒的进程，CFS 会将 vruntime 设置为 min_vruntime - sched_latency，这使得它能在下次调度时被优先选中——这体现了 CFS 的"公平"：你刚醒来，欠了你的 CPU 时间。但不能无限累积，所以限制了最多减去一个 sched_latency。
3.3 出队操作
当进程阻塞或停止时，从红黑树中移除：
static void dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
update_curr(cfs_rq); // 先更新当前任务的 vruntime
// 从红黑树中删除
rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
// 更新左右节点缓存
if (cfs_rq->rb_leftmost == &se->run_node)
cfs_rq->rb_leftmost = rb_first(&cfs_rq->tasks_timeline);
cfs_rq->nr_running--;
se->on_rq = 0;
}3.4 选择下一个进程 pick_next_task_fair
static struct task_struct *pick_next_task_fair(struct rq *rq)
{
struct cfs_rq *cfs_rq = &rq->cfs;
struct sched_entity *se;
if (!cfs_rq->nr_running)
return NULL;
// O(1) 获取最左侧节点（vruntime 最小）
se = pick_next_entity(cfs_rq);
set_next_task(rq, se->task);
return task_of(se);
}
static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
{
struct sched_entity *left = __pick_first_entity(cfs_rq);
// left == cfs_rq->rb_leftmost->se
return left;
}四、vruntime 的计算与权重转换
4.1 vruntime 的更新公式
每次时钟 tick 或需要时调用 update_curr()：
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;
curr->sum_exec_runtime += delta_exec;
// 关键：虚拟运行时间增长
curr->vruntime += calc_delta_fair(delta_exec);
// 更新队列的 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;
}
// __calc_delta: delta *= (weight_of_nice_0 / weight_of_se)
// 即：权重越低，vruntime 增长越快4.2 nice 值到权重的映射
内核中有一个静态表 sched_prio_to_weight[40]，将 [-20, 19] 的 nice 值映射为权重：
static const int sched_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,
};相邻 nice 级的权重比约为 10%（4/5），即 nice=0 的任务获得的 CPU 时间大约是 nice=5 的 1.25 倍。
五、调度粒度与抢占
5.1 sched_latency 与 min_granularity
sched_latency 是 CFS 的一个关键参数——在理想多任务处理器上，每个进程应该至少运行一次的时间（默认 6ms）。min_granularity 是保证每个被选中的进程至少运行的最小时间（默认 0.75ms）。默认关系为：
min_granularity = sched_latency / 当 nr_running 较大时
实际时间片 = max(min_granularity, sched_latency / nr_running)5.2 检查是否抢占当前进程
在 check_preempt_tick() 中判断当前进程是否该让出 CPU：
static void check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
unsigned long ideal_runtime, delta_exec;
struct sched_entity *se;
s64 delta;
// 理想运行时间 = sched_latency / nr_running
ideal_runtime = sched_slice(cfs_rq, curr);
delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
// 如果实际运行时间超过了理想值，需要被抢占
if (delta_exec > ideal_runtime) {
resched_curr(rq_of(cfs_rq));
return;
}
// 或者：vruntime 已不是最小
if (ideal_runtime < sysctl_sched_min_granularity)
ideal_runtime = sysctl_sched_min_grularity;
se = __pick_first_entity(cfs_rq);
delta = curr->vruntime - se->vruntime;
if (delta > 0 || delta > ideal_runtime)
resched_curr(rq_of(cfs_rq));
}六、组调度（CGroup Scheduling）
CFS 的组调度机制使得虚拟运行时间的公平性可以应用到进程组级别。每个 cgroup 拥有自己的 cfs_rq，组内的任务先在组内竞争，然后每个组作为一个整体在 CPU 上竞争。
/sys/fs/cgroup/cpu/
├── cpu.cfs_quota_us # 周期内的 CPU 配额（以微秒计）
├── cpu.cfs_period_us # 配额刷新周期（默认 100ms）
└── cpu.shares # 组的权重份额典型的 CPU 带宽限制：设定 cfs_quota_us = 50000，cfs_period_us = 100000，表示该 cgroup 最多使用 0.5 个 CPU 核。当组的 timer 检测到配额用尽时，该组将被节流（throttled），直到下一个周期。
七、NUMA 感知调度
现代多核/多插槽系统中，NUMA（非一致性内存访问）拓扑对调度性能有重大影响。CFS 的 NUMA 平衡机制主要包括：
- 任务放置：新 fork 的进程被尽量放在与父进程相同的 NUMA 节点上
- 页面迁移：内核定期扫描进程的内存页面，发现跨节点访问频繁时，将页面迁移到访问者所在节点
- 自动 NUMA 平衡：
sysctl_numa_balancing控制自动平衡是否开启
// 查看并配置
/sys/kernel/numa_balancing // 启用/禁用自动 NUMA 平衡
/proc/sys/kernel/numa_balancing_scan_delay_ms // 扫描间隔八、多核与负载均衡
在多核系统中，每个 CPU 维护自己的 CFS 红黑树。负载均衡的核心挑战是：如何在各 CPU 间分配任务，既要利用多核并行性，又要考虑缓存亲和性。
| 策略 | 说明 |
|---|---|
| IDLE BALANCE | 当 CPU 空闲时（没有可运行任务），主动从繁忙 CPU 拉取任务 |
| PERIODIC BALANCE | 通过 scheduler_tick 定期检查各 CPU 负载并平衡 |
| NEWIDLE BALANCE | 唤醒新进程时选择最空闲的 CPU（考虑任务唤醒亲和性） |
| WAKE_AFFINITY | 尽量将新唤醒进程放在之前运行过的 CPU 上（复用缓存） |
九、实时调度与 CFS 的协作
Linux 内核的调度类是有优先级顺序的：
- stop_sched_class（优先级最高，用于 CPU hotplug 等）
- dl_sched_class（Deadline 调度器，EDF 算法）
- rt_sched_class（实时调度器，SCHED_FIFO / SCHED_RR）
- fair_sched_class（CFS，SCHED_NORMAL / SCHED_BATCH / SCHED_IDLE）
- idle_sched_class（空闲调度，仅在没有任务时运行）
在调度路径中，pick_next_task() 依次检查这些调度类。如果一个实时进程变为可运行状态，CFS 进程会被立即抢占。这保证了硬实时应用的确定性。
十、CFS 调优实践
10.1 关键内核参数
/proc/sys/kernel/sched_latency_ns # 调度周期（默认 6000000 = 6ms）
/proc/sys/kernel/sched_min_granularity_ns # 最小调度粒度（默认 750000 = 0.75ms）
/proc/sys/kernel/sched_wakeup_granularity_ns # 唤醒抢占粒度（默认 1000000 = 1ms）10.2 计算时间片的经验公式
- 如果进程数 N ≤
sched_latency / min_granularity，每个进程分配sched_latency / N毫秒 - 如果 N >
sched_latency / min_granularity，每个进程至少运行min_granularity - 对于 I/O 密集型进程（频繁唤醒），由于 place_entity 的优待机制，vruntime 会被压低，从而获得更多的调度机会
10.3 cgroup 控制
# 限制某个服务最多使用 0.2 个 CPU
mkdir /sys/fs/cgroup/cpu/limited_service
echo 20000 > /sys/fs/cgroup/cpu/limited_service/cpu.cfs_quota_us
echo 100000 > /sys/fs/cgroup/cpu/limited_service/cpu.cfs_period_us
# 分配 CPU 权重
echo 512 > /sys/fs/cgroup/cpu/webapp/cpu.shares # 相对权重十一、CFS 的性能特征与局限
CFS 以其简洁和优雅而著称，但在某些著名场景中也暴露了局限性：
- CFS 漏洞（2016）：Meltdown/Spectre 缓解后，
vruntime计算的整数溢出被利用，可导致本地提权——已在后续内核中修复 - NUMA-incoherence：在多插槽系统中，不当的组调度配置可能导致所有任务集中在同一 NUMA 节点
- 交互性 vs 吞吐：对于代码编译、科学计算等 CPU 密集型任务，
SCHED_BATCH通过略微减小唤醒优待来换取更高的吞吐量
总结
CFS 的核心之美在于它的简单：没有时间片计数器，没有复杂的优先级队列，仅仅是一个按 vruntime 排序的红黑树加上优雅的虚拟时间模型。从 2.6.23 至今，CFS 经历了持续的优化——NUMA 平衡、组调度、deadline 调度类的协同、EAS 能耗感知调度等——但其核心设计哲学始终保持不变：通过维护一个公平的虚拟运行时间，让每个任务都能在合理的时间内得到自己应得的那一份 CPU。
对于系统管理员和开发者而言，深入理解 CFS 不仅有助于性能调优，更能培养对 Linux 系统设计哲学的直觉——在许多复杂的问题面前，Linux 内核社区总是倾向于找到那个最简洁优雅的解决方案。
发表评论 取消回复