Linux Kernel/公平调度器

从有资格的任务中挑选最早截止时间

Linux 公平调度将 EEVDF 的资格条件与虚拟截止时间结合,用增强红黑树搜索候选任务。

v6.12调度与资源分配核验 2026-10-08
相关概念

工程问题#

调度器要兼顾按权重分配 CPU 和响应延迟;单纯选最早截止时间可能选择已经超前获得服务的任务。

实际实现#

任务按虚拟截止时间排序,子树维护最小 vruntime。pick_eevdf 利用该摘要跳过没有合格实体的子树,并与当前任务比较。

处理流程#

  1. 累计任务的虚拟运行时间
  2. 判断实体是否具有运行资格
  3. 搜索最早截止的合格实体
  4. 结合当前运行实体选择下一任务

源码片段#

固定版本 · 原文摘录
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 的解释。

参考来源#

源码、官方文档与原始论文
01
linux · pick_eevdf / __enqueue_entity

kernel/sched/fair.c · pick_eevdf / __enqueue_entity

源码v6.12

相关实现与比较#

4 个相关案例
nginx·事件循环release-1.26.3

nginx 事件定时器以到期时间为键放入红黑树,事件循环读取最小键确定等待上限。

附源码片段 · 调度与资源分配
11 个匹配案例