从有资格的任务中挑选最早截止时间
Linux 公平调度将 EEVDF 的资格条件与虚拟截止时间结合,用增强红黑树搜索候选任务。
相关概念
工程问题#
调度器要兼顾按权重分配 CPU 和响应延迟;单纯选最早截止时间可能选择已经超前获得服务的任务。
实际实现#
任务按虚拟截止时间排序,子树维护最小 vruntime。pick_eevdf 利用该摘要跳过没有合格实体的子树,并与当前任务比较。
处理流程#
- 累计任务的虚拟运行时间
- 判断实体是否具有运行资格
- 搜索最早截止的合格实体
- 结合当前运行实体选择下一任务
源码片段#
固定版本 · 原文摘录kernel/sched/fair.cv6.12 · L945–L964
945 if (left && vruntime_eligible(cfs_rq,946 __node_2_se(left)->min_vruntime)) {947 node = left;948 continue;949 }950951 se = __node_2_se(node);952953 /*954 * The left subtree either is empty or has no eligible955 * entity, so check the current node since it is the one956 * with earliest deadline that might be eligible.957 */958 if (entity_eligible(cfs_rq, se)) {959 best = se;960 break;961 }962963 node = node->rb_right;964 }pick_eevdf
按虚拟截止时间排序的树优先搜索左侧;子树 min_vruntime 摘要判断左子树是否含合格实体,否则检查当前节点,再向右搜索。它展示资格剪枝,不能理解为简单选择最小 vruntime。
截取搜索循环内部的连续原文;循环初始化、快速路径和最终与当前运行实体的比较位于片段之外。
收益与取舍#
工程分析带来的收益
- 把公平性约束与延迟目标分开表达
- 子树摘要减少无效搜索
付出的代价
- 工程分析:额外统计量提高维护复杂度
- 实际效果受权重、时间片与运行队列状态影响
可比较的选择
简单最小截止时间堆能快速取最小值,但不能直接跳过所有不合格任务。
版本与适用范围#
对应 Linux v6.12 fair 调度类;不代表实时调度类,且不能套用旧版 CFS 仅选最小 vruntime 的解释。
参考来源#
源码、官方文档与原始论文相关实现与比较#
4 个相关案例hrtimer 通过 timerqueue 的红黑树维护到期顺序,并缓存最早到期节点。
附源码片段 · 调度与资源分配
nginx 事件定时器以到期时间为键放入红黑树,事件循环读取最小键确定等待上限。
附源码片段 · 调度与资源分配
limit_req 把漏桶计算、红黑树查状态与队列回收组合起来,按配置的 key 管理请求速率。
附源码片段 · 通信与流量
Linux v6.5 的 CFS 将可运行实体按 vruntime 放入红黑树,用加权运行时间作为公平性的基准。
附源码片段 · 调度与资源分配