Linux CFS调度器：从红黑树到vruntime，手把手带你读懂内核4.18.10源码里的公平艺术

Linux CFS调度器从红黑树到vruntime手把手带你读懂内核4.18.10源码里的公平艺术在计算机科学的世界里调度算法就像一位隐形的指挥家默默协调着CPU资源的分配。而Linux内核中的CFSCompletely Fair Scheduler调度器无疑是这位指挥家手中的一把精密乐器。它不仅仅是一个功能模块更像是一件精心雕琢的艺术品将公平这一抽象概念转化为可执行的代码逻辑。对于中高级开发者来说理解CFS调度器的实现原理就像是学习欣赏一幅复杂的油画——需要从整体构图到细微笔触层层深入。本文将带你走进Linux 4.18.10内核源码以红黑树和vruntime为切入点揭示CFS调度器背后的公平艺术。我们将重点分析update_curr()和pick_next_task_fair()等核心函数看看Linux是如何用精妙的算法实现看似简单的公平理念。1. CFS调度器的艺术基础公平的数学表达公平这个概念在计算机调度中需要被量化。CFS调度器创造性地引入了**虚拟运行时间vruntime**这一核心指标将抽象的公平理念转化为可计算的数值。每个进程的vruntime计算公式如下vruntime (实际运行时间 × NICE_0_LOAD) / 进程权重这个看似简单的公式背后蕴含着深刻的调度哲学。让我们用一个表格来理解不同nice值进程的权重关系nice值权重(weight)相对CPU时间比例-208876110:1010241:119151:10在实际代码中kernel/sched/core.c这个关系通过sched_prio_to_weight数组实现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, };这种设计体现了CFS的核心思想不是简单地分配固定时间片而是通过权重来动态调整每个进程获取CPU的比例从而实现长期视角下的公平。2. 红黑树CFS调度器的平衡艺术如果说vruntime是CFS的理论基础那么红黑树就是实现这一理论的精巧数据结构。在kernel/sched/fair.c中CFS使用红黑树来组织所有可运行进程以vruntime作为键值。这种选择绝非偶然——红黑树的自平衡特性完美契合了调度器对效率和公平的双重追求。红黑树在CFS中的关键操作包括插入操作当进程变为可运行状态时其调度实体被插入红黑树删除操作当进程阻塞或终止时从树中移除对应节点选择操作总是选择最左侧节点vruntime最小的进程让我们看一段实际的代码片段简化版struct sched_entity { struct rb_node run_node; // 红黑树节点 u64 vruntime; // 虚拟运行时间 // ... 其他字段 }; struct cfs_rq { struct rb_root_cached tasks_timeline; // 红黑树根节点 // ... 其他字段 }; static struct sched_entity *__pick_next_entity(struct sched_entity *se) { struct rb_node *next rb_next(se-run_node); if (!next) return NULL; return rb_entry(next, struct sched_entity, run_node); }红黑树的操作复杂度为O(log n)这保证了即使系统中有数千个进程调度器也能高效工作。下表对比了不同调度算法的时间复杂度调度算法插入复杂度选择复杂度删除复杂度O(n)O(1)O(n)O(n)O(1)O(1)O(1)O(1)CFSO(log n)O(1)*O(log n)*注CFS选择最左侧节点实际上是O(1)操作因为内核会缓存最左侧节点3. 动态平衡的艺术update_curr()函数解析update_curr()是CFS调度器中最频繁调用的函数之一它负责更新当前运行进程的vruntime。这个函数就像一位细心的会计持续跟踪每个进程的CPU使用账单。让我们深入分析这个函数的逻辑基于Linux 4.18.10static 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; if (unlikely(!curr)) return; delta_exec now - curr-exec_start; if (unlikely((s64)delta_exec 0)) return; curr-exec_start now; curr-sum_exec_runtime delta_exec; curr-vruntime calc_delta_fair(delta_exec, curr); update_min_vruntime(cfs_rq); // ... 其他统计更新 }这个函数的关键步骤可以分解为获取当前时间戳和当前运行的调度实体计算自上次更新以来的实际执行时间(delta_exec)更新进程的总执行时间和vruntime更新cfs_rq的最小vruntime(min_vruntime)注意min_vruntime是一个非常重要的概念它记录了运行队列中所有进程的最小vruntime用于保证新创建或唤醒的进程不会因为历史vruntime太小而垄断CPU。vruntime的动态调整是CFS实现公平的核心机制。考虑以下场景新进程创建会被赋予当前min_vruntime避免立即抢占CPU进程唤醒会根据睡眠时间适当补偿vruntime多核负载均衡迁移进程时会调整vruntime以保持跨CPU公平4. 调度决策的艺术pick_next_task_fair()剖析当需要选择下一个运行进程时CFS调度器调用pick_next_task_fair()函数。这个函数的决策过程体现了CFS对公平与效率的平衡艺术。让我们看看这个函数的主要逻辑static struct task_struct * pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) { struct cfs_rq *cfs_rq rq-cfs; struct sched_entity *se; struct task_struct *p; // 处理组调度等复杂情况 if (prev) put_prev_task(rq, prev); do { se pick_next_entity(cfs_rq); cfs_rq group_cfs_rq(se); } while (cfs_rq); p task_of(se); return p; }这个看似简单的函数背后隐藏着几个精妙的设计选择最左侧节点优先pick_next_entity()本质上就是选择红黑树最左侧节点组调度支持通过group_cfs_rq()递归处理组调度情况平滑过渡put_prev_task()会处理好前一个进程的状态转换在实际系统中CFS调度器还需要考虑以下特殊情况新创建的进程通过place_entity()函数初始化vruntime唤醒的进程enqueue_task_fair()会适当调整其vruntimeCPU迁移task_move_group_fair()处理跨CPU时的公平性问题下表展示了不同场景下vruntime的处理策略场景vruntime调整策略相关函数新进程创建初始化为cfs_rq-min_vruntime 补偿值task_fork_fair()进程唤醒根据睡眠时间补偿vruntimeenqueue_task_fair()进程迁移根据目标CPU的min_vruntime调整task_move_group_fair()普通运行按实际运行时间和权重更新update_curr()5. 高级特性CFS调度器的扩展艺术除了基本调度功能外CFS还实现了几项高级特性这些特性进一步丰富了它的公平艺术内涵。5.1 负载均衡的艺术在多核系统中CFS通过负载均衡机制确保所有CPU核心都能得到合理利用。负载均衡的主要逻辑在load_balance()函数中实现它会定期检查各CPU负载情况识别过载和空闲的CPU迁移任务以平衡负载关键的负载均衡触发点包括定时器中断(scheduler_tick())进程唤醒(try_to_wake_up())显式的平衡请求(active_load_balance())5.2 带宽控制的艺术CFS带宽控制允许管理员限制特定进程组的CPU使用量。这是通过cfs_bandwidth机制实现的主要涉及配额分配设置时间周期和配额struct cfs_bandwidth { u64 period; u64 quota; // ... };配额消耗跟踪在update_curr()中更新已用时间限制执行当配额用尽时throttle对应的cfs_rq5.3 组调度的艺术CFS的组调度功能允许将CPU时间分配给进程组而非单个进程。这是通过层级化的cfs_rq结构实现的root cfs_rq ├── group A cfs_rq │ ├── task 1 │ └── task 2 └── group B cfs_rq ├── task 3 └── task 4组调度的关键函数包括task_group_path()获取组的完整路径update_cfs_group()更新组的权重分配account_entity_enqueue()处理组内调度实体的入队6. 性能调优在实践中欣赏CFS艺术理解CFS的内部实现后我们可以更好地进行性能调优。以下是一些实用的调优参数和技巧/proc/sys/kernel/sched_调优参数*参数文件默认值说明sched_latency_ns24000000 (24ms)目标调度延迟影响时间片计算sched_min_granularity_ns3000000 (3ms)最小调度粒度防止过度频繁的上下文切换sched_wakeup_granularity_ns4000000 (4ms)唤醒抢占粒度控制新唤醒进程何时可以抢占当前进程sched_migration_cost_ns500000 (0.5ms)任务迁移成本估计影响负载均衡决策实用调试技巧使用/proc/pid/sched查看进程调度信息cat /proc/self/sched通过ftrace跟踪调度事件echo 1 /sys/kernel/debug/tracing/events/sched/enable cat /sys/kernel/debug/tracing/trace_pipe使用perf分析调度行为perf sched record -- sleep 1 perf sched latency常见问题排查表现象可能原因检查点CPU使用不均衡负载均衡失效/proc/schedstat交互式应用响应慢调度延迟设置不当sched_latency_ns某些进程占用过多CPUnice值设置不当或权重计算问题ps -eo pid,nice,pri,cmd频繁的上下文切换调度粒度过小sched_min_granularity_ns