操作系统 / 系统课时

用 EEVDF 理解公平调度决策

用 EEVDF 理解公平调度决策

普通任务同时可运行时,调度器不能只看“谁等得最久”。EEVDF 会先判断任务是否欠了 CPU 服务,再在有资格的任务里比较虚拟截止期,从而把长期公平、交互响应和权重差异统一到同一套选择规则中。

学习目标

  • 理解 lag、虚拟运行时间和虚拟截止期各自解决什么问题
  • 能按“先看资格、再比截止期”的顺序判断下一个普通任务
  • 解释任务权重为何会同时影响长期 CPU 份额和虚拟时间推进速度

从理想公平到可执行决策

可以先想象一个“理想处理器”:所有可运行任务同时按权重分到 CPU。真实 CPU 一次通常只能运行一个任务,因此调度器需要记录每个任务相对理想状态是“少拿了”还是“多拿了”服务,再决定接下来补给谁。

EEVDF 中,虚拟运行时间可以理解为任务已经消耗 CPU 的加权进度。权重越大,同样运行一段真实时间时,虚拟运行时间推进得越慢,因此高权重任务可以获得更多真实 CPU 时间,而不会在虚拟时间上过快跑到前面。

lag 决定谁有资格竞争

lag 表示任务相对理想公平服务的欠账。用简化表达可以写成 lagi=wi(V−vi)lag_i = w_i(V - v_i):V 是系统的虚拟时间基准,v_i 是任务的虚拟进度,w_i 是权重。

当 lag 为正时,任务相对理想份额拿得偏少,可以视为“系统欠它 CPU”;lag 为负时,它已经拿得偏多。EEVDF 不会因为某个任务的截止期很早就无条件选择它,而是先把没有资格的任务排除,再在 eligible 任务中决策。

EEVDF 按 lag 与虚拟截止期选择普通任务

虚拟截止期决定先运行谁

对已经 eligible 的任务,EEVDF 选择虚拟截止期更早的实体。可把它理解为“这次服务请求应该在虚拟时间轴上的哪个位置完成”。简化地说,截止期由当前虚拟起点加上经过权重缩放的服务请求长度得到。

因此,权重相同的两个任务若都欠服务,较短的服务请求通常会得到更近的虚拟截止期,有利于缩短短任务的等待;而长期看,lag 又会约束某个任务不能无限抢占其他任务的公平份额。响应性和公平性不是两套互不相关的规则,而是在资格与截止期两个阶段共同实现。

用三个任务走一遍选择过程

假设当前有三个可运行任务,下面的数值只用于理解决策顺序:

任务 lag 虚拟截止期 是否 eligible
A +4 12 是
B +2 9 是
C -3 8 否

虽然 C 的虚拟截止期最早,但它的 lag 为负,说明此前已经获得了超过理想份额的服务,因此当前不参与竞争。A 与 B 都 eligible,B 的虚拟截止期 9 更早,所以 B 被选择。

B 运行后,它的虚拟进度会增加,lag 会向较小方向变化;如果它从“欠服务”变成“拿得偏多”,后续就可能暂时失去资格,让其他任务追上。这就是 EEVDF 维持长期公平的关键反馈环。

不要套用固定时间片思维

nice 或其他权重变化不会简单变成“每轮固定给某任务多少毫秒”。权重会影响虚拟时间推进和公平份额,任务是否 eligible 会随实际运行不断变化,虚拟截止期也会随新的服务请求重新计算。

因此,看普通任务的调度选择时,不必尝试背一套固定轮转周期。把每次选择理解成“公平欠账过滤 + 最早虚拟截止期竞争”,就能解释为什么高权重任务长期拿到更多 CPU,同时短请求仍能保持较好的响应性。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用 EEVDF 理解公平调度决策

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通