Linux内核CFS完全公平调度器：从vruntime到负载均衡的深度实现分析
一、CFS的设计哲学与核心数据结构
CFS（Completely Fair Scheduler）自Linux 2.6.23起替代O(1)调度器，成为默认的进程调度器。其核心设计目标可概括为：在任意观测窗口内，将CPU时间公平地分配给所有可运行进程。
实现这一目标的核心机制是vruntime（虚拟运行时间）。传统调度器按实际运行时间分配，导致高优先级进程可能长时间独占CPU；CFS用vruntime归一化真实的运行时间，保证各进程在虚拟时间维度上同步推进。
vruntime的计算公式为：
vruntime += delta_exec × (NICE_0_LOAD / se.load.weight)
其中delta_exec是本调度周期内的实际运行时间，weight是进程权重，由Nice值映射而来。Nice值越高（优先级越低），weight越小，vruntime增长越快，获得调度机会越少。
CFS使用红黑树（rbtree）组织所有可运行的调度实体（sched_entity）。红黑树以vruntime为键值，最左节点是vruntime最小的进程，每次调度时直接选取最左节点，时间复杂度O(logN)。内核使用缓存最左节点（cached leftmost）优化，实际选择操作为O(1)。
/*
* CFS调度实体核心数据结构
* 摘录自: kernel/sched/sched.h (简化示意)
*/
struct sched_entity {
struct load_weight load; /* 负载权重 */
struct rb_node run_node; /* 红黑树节点 */
unsigned int on_rq; /* 是否在就绪队列上 */
u64 exec_start; /* 本周期开始执行的时间戳 */
u64 sum_exec_runtime; /* 累计实际运行时间 */
u64 vruntime; /* 虚拟运行时间，红黑树键值 */
u64 prev_sum_exec_runtime; /* 前次统计快照 */
struct sched_entity *parent; /* 组调度时指向父实体 */
struct cfs_rq *cfs_rq; /* 所属CFS运行队列 */
struct cfs_rq *my_q; /* 组调度时的子运行队列 */
};
/*
* CFS就绪队列
*/
struct cfs_rq {
struct load_weight load; /* 队列总负载权重 */
unsigned int nr_running; /* 可运行进程数 */
u64 min_vruntime; /* 队列最小vruntime基准 */
struct rb_root_cached tasks_timeline; /* 红黑树根（含最左缓存） */
struct sched_entity *curr; /* 当前正在执行的实体 */
struct sched_entity *next; /* 预调度实体 */
struct sched_entity *last; /* 上次执行的实体 */
u64 exec_clock; /* 累积执行时钟 */
};
/* 红黑树：最左节点快速获取 */
struct rb_root_cached {
struct rb_root rb_root;
struct rb_node *rb_leftmost; /* 缓存最左节点 */
};
二、调度核心流程：从pick_next到context_switch
CFS调度决策的核心流程包含以下步骤：
第一步：更新当前进程vruntime。 在每个调度点（时钟中断、系统调用、唤醒等），函数update_curr()被调用，计算当前进程在本周期的实际运行时间，按权重折算后累加到vruntime。
第二步：选择下一个进程。 pick_next_task_fair()调用红黑树操作获取最左节点。如果最左节点对应的实体与当前执行实体不同，触发上下文切换。
第三步：放置被抢占进程。 如果当前进程时间片用完（或更高优先级进程就绪），将其重新插入红黑树，vruntime作为排序键。
第四步：上下文切换。 context_switch()完成地址空间切换（切换mm_struct）、寄存器状态保存与恢复。
调度周期（sched_period）的计算公式：当可运行进程数小于等于8时，周期固定为6ms（默认）；超过8个时，周期等比例增长，保证每个进程获得的最小时间粒度不低于0.75ms。
/*
* CFS调度核心逻辑（教学简化版）
* 演示 update_curr + pick_next 的关键路径
*/
#include <stdio.h>
#include <stdint.h>
/* Nice值到权重的映射表（内核源码 prio_to_weight 简化） */
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,
};
#define NICE_0_LOAD 1024
#define NSEC_PER_MSEC 1000000ULL
#define DEFAULT_MIN_GRANULARITY (750000ULL) /* 0.75ms */
#define DEFAULT_SCHED_PERIOD (6000000ULL) /* 6ms */
typedef struct {
uint64_t vruntime;
uint64_t sum_exec_runtime;
uint64_t exec_start;
int weight;
int nice;
char name[32];
} MockSchedEntity;
typedef struct {
MockSchedEntity entities[16];
int nr_running;
uint64_t min_vruntime;
} MockCFSRQ;
static int nice_to_weight(int nice) {
int idx = nice + 20;
if (idx < 0) idx = 0;
if (idx > 39) idx = 39;
return sched_prio_to_weight[idx];
}
/*
* 更新进程的vruntime
* 调用时机：每个调度tick、进程被唤醒、进程被抢占
*/
static void update_curr(MockCFSRQ *cfs_rq, MockSchedEntity *curr,
uint64_t now) {
uint64_t delta_exec;
if (!curr || curr->exec_start == 0) return;
/* 计算本周期实际运行时间 */
delta_exec = now – curr->exec_start;
curr->exec_start = now;
curr->sum_exec_runtime += delta_exec;
/* 核心公式：vruntime = 实际时间 × (NICE_0_LOAD/weight) */
uint64_t delta_vruntime = delta_exec;
if (curr->weight != NICE_0_LOAD) {
delta_vruntime = delta_exec * NICE_0_LOAD / curr->weight;
}
curr->vruntime += delta_vruntime;
/* 更新队列最小vruntime */
if (curr->vruntime < cfs_rq->min_vruntime)
cfs_rq->min_vruntime = curr->vruntime;
}
/*
* 计算目标调度延迟（一个完整调度周期）
* nr_running ≤ 8: 固定6ms
* nr_running > 8: 每个进程至少0.75ms × nr_running
*/
static uint64_t calc_sched_period(int nr_running) {
uint64_t period = DEFAULT_SCHED_PERIOD;
uint64_t min_granularity = DEFAULT_MIN_GRANULARITY;
if (nr_running > 8) {
period = nr_running * min_granularity;
}
return period;
}
/*
* 计算进程时间片
*/
static uint64_t calc_time_slice(MockCFSRQ *cfs_rq,
MockSchedEntity *se) {
uint64_t period = calc_sched_period(cfs_rq->nr_running);
uint64_t slice = period * se->weight / NICE_0_LOAD;
uint64_t min_granularity = DEFAULT_MIN_GRANULARITY;
return slice < min_granularity ? min_granularity : slice;
}
/*
* 选择下一个要运行的进程（演示最左节点选取逻辑）
*/
static int pick_next_entity(MockCFSRQ *cfs_rq) {
if (cfs_rq->nr_running == 0) return -1;
int idx = 0;
uint64_t min_vruntime = UINT64_MAX;
/* 简化：线性扫描找最小vruntime（内核用红黑树O(logN)） */
for (int i = 0; i < cfs_rq->nr_running; i++) {
if (cfs_rq->entities[i].vruntime < min_vruntime) {
min_vruntime = cfs_rq->entities[i].vruntime;
idx = i;
}
}
return idx;
}
/*
* 演示：运行调度模拟
*/
static void simulate_cfs_schedule(void) {
MockCFSRQ cfs_rq = {.nr_running = 0, .min_vruntime = 0};
uint64_t now = 0;
/* 创建三个不同Nice值的进程 */
MockSchedEntity tasks[] = {
{.vruntime = 0, .nice = 0, .name = "Task-A (nice=0)"},
{.vruntime = 0, .nice = 5, .name = "Task-B (nice=5)"},
{.vruntime = 0, .nice = -5, .name = "Task-C (nice=-5)"},
};
for (int i = 0; i < 3; i++) {
tasks[i].weight = nice_to_weight(tasks[i].nice);
cfs_rq.entities[cfs_rq.nr_running++] = tasks[i];
}
printf("CFS调度模拟：3个进程 × 10个周期\\n");
printf("%-20s %-8s %-10s %-15s\\n",
"进程", "Nice", "Weight", "累计vruntime");
printf("———————————————–\\n");
/* 模拟10个调度周期 */
for (int cycle = 0; cycle < 30; cycle++) {
int picked = pick_next_entity(&cfs_rq);
MockSchedEntity *curr = &cfs_rq.entities[picked];
/* 模拟运行1ms */
uint64_t run_time = NSEC_PER_MSEC;
curr->exec_start = now;
now += run_time;
update_curr(&cfs_rq, curr, now);
if (cycle % 10 == 9) {
printf("— 周期 %d 结束 —\\n", cycle / 10 + 1);
for (int i = 0; i < cfs_rq.nr_running; i++) {
printf("%-20s %-8d %-10d %-15llu\\n",
cfs_rq.entities[i].name,
cfs_rq.entities[i].nice,
cfs_rq.entities[i].weight,
(unsigned long long)cfs_rq.entities[i].vruntime);
}
printf("\\n");
}
}
}
三、负载均衡机制
负载均衡是CFS在多核系统上的关键功能。内核周期性检查各CPU运行队列的负载情况，必要时迁移进程以实现均衡。
负载跟踪使用PELT（Per-Entity Load Tracking），基于几何级数衰减累积每个调度实体的历史负载：
L = L0 + L1×y + L2×y² + L3×y³ + …
其中y≈0.9785，半衰期为32个周期（每个周期1ms）。
负载均衡触发路径：scheduler_tick() → trigger_load_balance() → 软中断SCHED_SOFTIRQ → run_rebalance_domains() → load_balance()。
stateDiagram-v2
[*] –> READY: 进程创建
READY –> RUNNING: pick_next_task<br/>选取最左节点
RUNNING –> READY: 时间片耗尽<br/>或被抢占
RUNNING –> SLEEPING: 等待IO/事件
SLEEPING –> READY: 事件到达/wake_up
RUNNING –> ZOMBIE: 进程退出
state RUNNING {
[*] –> update_curr: 调度tick到达
update_curr –> check_preempt: vruntime更新
check_preempt –> reschedule: 需要抢占
check_preempt –> continue: 继续执行
reschedule –> [*]: 设置TIF_NEED_RESCHED
}
note right of READY
vruntime归一化后
插入红黑树
end note
note left of SLEEPING
vruntime补偿机制：
唤醒时vruntime -= min_vruntime
end note
四、Nice值的真实影响
Nice值从-20到+19，映射到权重[88761, 15]（参见上文的权重表）。两个进程的CPU时间分配比等于权重比。
具体举例：Nice=0（weight=1024）的进程与Nice=5（weight=335）的进程竞争时，CPU时间分配比约为1024:335，即约75%:25%。换句话说，Nice值每变化约1.25，CPU份额变化约10%。
vruntime补偿机制保证了休眠进程被唤醒后不会因长时间休眠而拥有极低的vruntime（从而不公平地长时间占用CPU）：唤醒时将进程的vruntime设置为max(se->vruntime, cfs_rq->min_vruntime – sched_latency/2)。
这个设计防止了"休眠囤积"效应——一个休眠很久的进程醒来后，有机会获得调度，但不会被赋予远超公平份额的执行时间。
五、总结
- CFS核心机制是vruntime归一化：实际运行时间乘以(NICE_0_LOAD/weight)，将不同优先级进程统一到虚拟时间维度进行公平比较
- 红黑树以vruntime为键值组织可运行进程，最左节点总是下一个被调度的进程，配合最左节点缓存实现O(1)选取
- 调度周期默认6ms（nr_running≤8），超8个时按进程数等比例增长，保证每个进程最小粒度0.75ms
- 负载均衡使用PELT几何衰减累积负载，半衰期32ms（y≈0.9785），通过软中断触发进程在CPU间的迁移
- Nice值的CPU分配比等于权重比，Nice差5对应权重比约3:1，休眠唤醒时的vruntime补偿防止"囤积效应"
