CFS 公平调度Completely fair scheduler
以按权重换算的虚拟运行时间衡量实体已获得的 CPU 服务。
- 核心约束
- 持续更新运行时间，并将等待运行实体按虚拟运行时间组织。
- 适用问题
- 理解普通任务的权重公平性以及历史 Linux 调度实现。
- 边界与取舍
- 实际选择还有当前实体、唤醒与组调度规则；Linux 后续版本的 EEVDF 需独立分析。
常见操作#
n 为运行队列中的调度实体数；这里专指 Linux 6.5 的经典 CFS。
| 操作 | 时间复杂度 | 条件与说明 |
|---|---|---|
| 更新运行时间账本 | 固定宽度的运行时间和权重算术，不含层级调度组累计。 | |
| 实体入队 / 出队 | 按 vruntime 维护红黑树。 | |
| 读取缓存的最左候选 | rb_root_cached 保存最左节点；完整 pick_next_entity 还会考虑当前实体和 buddy 提示。 |
时间与空间#
- 时间复杂度
- 树更新 ，缓存最左读取
- 辅助空间
- 队列状态
只描述该历史版本的公平调度核心；不能用于说明 Linux 6.12 EEVDF 的截止时间选择。
工程中的应用#
1 个案例 · 附源码Linux v6.5 的 CFS 将可运行实体按 vruntime 放入红黑树，用加权运行时间作为公平性的基准。
附源码片段 · 调度与资源分配