Linux内核CFS完全公平调度器从vruntime到负载均衡的深度实现分析一、CFS的设计哲学与核心数据结构CFSCompletely Fair Scheduler自Linux 2.6.23起替代O(1)调度器成为默认的进程调度器。其核心设计目标可概括为在任意观测窗口内将CPU时间公平地分配给所有可运行进程。实现这一目标的核心机制是vruntime虚拟运行时间。传统调度器按实际运行时间分配导致高优先级进程可能长时间独占CPUCFS用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_switchCFS调度决策的核心流程包含以下步骤第一步更新当前进程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 (nice0)}, {.vruntime 0, .nice 5, .name Task-B (nice5)}, {.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运行队列的负载情况必要时迁移进程以实现均衡。负载跟踪使用PELTPer-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_taskbr/选取最左节点 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时间分配比等于权重比。具体举例Nice0weight1024的进程与Nice5weight335的进程竞争时CPU时间分配比约为1024:335即约75%:25%。换句话说Nice值每变化约1.25CPU份额变化约10%。vruntime补偿机制保证了休眠进程被唤醒后不会因长时间休眠而拥有极低的vruntime从而不公平地长时间占用CPU唤醒时将进程的vruntime设置为max(se-vruntime, cfs_rq-min_vruntime - sched_latency/2)。这个设计防止了休眠囤积效应——一个休眠很久的进程醒来后有机会获得调度但不会被赋予远超公平份额的执行时间。五、总结CFS核心机制是vruntime归一化实际运行时间乘以(NICE_0_LOAD/weight)将不同优先级进程统一到虚拟时间维度进行公平比较红黑树以vruntime为键值组织可运行进程最左节点总是下一个被调度的进程配合最左节点缓存实现O(1)选取调度周期默认6msnr_running≤8超8个时按进程数等比例增长保证每个进程最小粒度0.75ms负载均衡使用PELT几何衰减累积负载半衰期32msy≈0.9785通过软中断触发进程在CPU间的迁移Nice值的CPU分配比等于权重比Nice差5对应权重比约3:1休眠唤醒时的vruntime补偿防止囤积效应