EEVDFEarliest eligible virtual deadline first
从具备资格的实体中选择虚拟截止时间最早者。
- 核心约束
- 资格与截止时间是不同的选择条件。
- 适用问题
- 公平调度与延迟控制。
- 边界与取舍
- 不能简化为选最小 vruntime 或普通最小 deadline。
常见操作#
n 为一个调度队列中的调度实体数；针对 Linux 6.12 fair.c 的增强红黑树实现。
| 操作 | 时间复杂度 | 条件与说明 |
|---|---|---|
| 实体入队 / 出队 | 按虚拟截止时间组织树，并维护 eligibility 剪枝所需的子树信息。 | |
| 选择最早 eligible 截止时间 | 增强字段允许沿树高剪枝；当前实体与缓存候选另有短路路径。 |
时间与空间#
- 时间复杂度
- 树更新与一般选择
- 辅助空间
- 队列状态
这是单个运行队列的结构成本，不包含任务切换、层级调度组遍历和跨 CPU 负载均衡。EEVDF 的公平 / 延迟目标不等同于实时截止期保证。
工程中的应用#
1 个案例 · 附源码Linux 公平调度将 EEVDF 的资格条件与虚拟截止时间结合，用增强红黑树搜索候选任务。
附源码片段 · 调度与资源分配
基础原理参考资料
Linux 6.12 · EEVDF schedulerlag、eligibility 与虚拟截止时间的选择语义。
Linux 6.12 · fair.cpick_eevdf 和 __enqueue_entity 的实际树遍历。