CFS：以加权虚拟运行时间组织公平调度
Linux v6.5 的 CFS 将可运行实体按 vruntime 放入红黑树，用加权运行时间作为公平性的基准。
工程问题#
普通任务对 CPU 的需求、nice 权重和唤醒节奏不同，调度器需要持续记账，避免仅按任务到达顺序决定运行机会。
实际实现#
update_curr 将实际执行时间经 calc_delta_fair 按权重换算后累加到 vruntime。等待运行的实体进入带最左节点缓存的红黑树；pick_next_entity 以较小 vruntime 为基准，再处理当前实体以及 next / last / skip buddy 等规则。
处理流程#
- 统计当前实体实际获得的 CPU 时间
- 按权重转换为虚拟运行时间并累加 vruntime
- 在红黑树中组织等待运行实体，以最左候选和当前实体作比较
- 在公平性检查约束下应用 buddy 等选择规则
源码片段#
固定版本 · 原文摘录920 curr->sum_exec_runtime += delta_exec;921 schedstat_add(cfs_rq->exec_clock, delta_exec);922923 curr->vruntime += calc_delta_fair(delta_exec, curr);924 update_min_vruntime(cfs_rq);925926 if (entity_is_task(curr)) {927 struct task_struct *curtask = task_of(curr);928929 trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);930 cgroup_account_cputime(curtask, delta_exec);931 account_group_exec_runtime(curtask, delta_exec);932 }933934 account_cfs_rq_runtime(cfs_rq, delta_exec);实际执行时间计入 sum_exec_runtime；经 calc_delta_fair 转换的时间计入 vruntime，再推进运行队列的 min_vruntime。后续还有任务与组的时间记账。
653struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)654{655 struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline);656657 if (!left)658 return NULL;659660 return __node_2_se(left);661}通过 rb_first_cached 读取红黑树缓存的最左节点，并转换为调度实体。它只是基本候选入口；完整 pick_next_entity 还会比较当前实体并应用 buddy 规则。
两个片段分别展示公平时间记账和树中候选读取。版本刻意固定在 v6.5，避免把 CFS 的最小 vruntime 直觉误用于 v6.12 EEVDF。
收益与取舍#
工程分析带来的收益
- 用统一的虚拟时间尺度表达不同权重实体已获得的服务
- 红黑树维护动态有序集合，缓存最左节点可直接读取基本候选
付出的代价
- 工程分析：入树和出树为 O(log n)，缓存最左候选读取为 O(1)；完整调度成本还受组调度与负载均衡影响
- 最终选择不等于无条件运行树中最左节点：当前实体及 buddy 规则也参与
- 该历史策略不提供硬实时截止时间保证，也不能替代后续 EEVDF 的资格与虚拟截止时间解释
可比较的选择
EEVDF进一步区分资格和虚拟截止时间；本项目另有 Linux v6.12 的实现案例，可对照不同版本。
固定优先级实时调度遵循另一种任务优先级与调度策略，不能直接套用普通公平调度的权重模型。
版本与适用范围#
明确对应 Linux v6.5 的历史 CFS 实现；用于理解调度演进与红黑树应用，不描述当前版本调度器，也不是 Linux 所有调度类别的统一规则。
参考来源#
源码、官方文档与原始论文kernel/sched/fair.c · __enqueue_entity / __pick_first_entity
相关实现与比较#
4 个相关案例Linux 公平调度将 EEVDF 的资格条件与虚拟截止时间结合，用增强红黑树搜索候选任务。
hrtimer 通过 timerqueue 的红黑树维护到期顺序，并缓存最早到期节点。
nginx 事件定时器以到期时间为键放入红黑树，事件循环读取最小键确定等待上限。
limit_req 把漏桶计算、红黑树查状态与队列回收组合起来，按配置的 key 管理请求速率。