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补偿防止"囤积效应"