你开心就好
调度(16)-EEVDF论文
编辑
2026-03-10
记录知识
0
请注意，本文编写于 60 天前，最后修改于 60 天前，其中某些信息可能已经过时。

目录

EEVDF的提出
服务滞后
EEVDF Algorithm
示例
公平性分析
总结
参考

这篇论文是 EEVDF 算法的理论基石，Linux 6.6+ 内核的 EEVDF 实现基本就是基于它来的。 本文根据论文描述的内容进行介绍

EEVDF的提出

现代操作系统的调度器类型分为两类

  • 比例份额
  • 实时调度

很明显，这种归类下，可以得出如下结论

  1. 步幅调度，CFS调度这类，属于比例份额，它要做到的事公平的让程序分配到应有的份额
  2. FIFO，EDF这类，属于实时调度，这类调度器基于事件驱动模型，例如EDF通过截止事件来决定任务的优先级
In this paper we propose a new scheduler (called Earliest Eligible Virtual Deadline First (EEVDF)which, while retaining all the advantages of the proportional share schedulers, provides strong timeliness guarantees for the service time received by a client. In this way, our algorithm provides a unied approach for scheduling continuous media, interactive and batch applications.

而EEVDF要解决的问题是保留了比例份额的优势的前提上，融合实时调度通过截止时间来保证及时性。这样的情况下，调度器在多媒体和交互式以及批处理三类型的任务上都能够统一的使用一种调度策略满足其需求

服务滞后

我们按照比例份额来计算一个任务的应有份额，那么其计算应该如下

image.png

很好理解，就是自身权重占总权重的比值

但实际调度的过程中，我们不可能简单的任务一个任务的应该开始运行时间和实际开始运行时间一致，那么我们把这两个值相减，提供一个新的概念叫做lag。

image.png

这里Si就是理论认为的运行时间，而si是实际获得的运行时间，将Si-si就是我们称作的lag。

在上一文中我们介绍了一个linux很好的通俗化含义，就是欠条。那么这个lag就很好理解了。

我调度器按照比例分给你任务，但是等你真的运行的时候，肯定存在滞后，那么这个滞后时间是你欠我的，我要找你要回来。

EEVDF Algorithm

虚拟时间的定义

image.png

直观的看

  • 当竞争激烈（总权重很大）时，虚拟时间走得慢。
  • 当竞争减少（总权重变小）时，虚拟时间走得快。

如果虚拟时间的概念引入了，那么我们计算Si-si就可以简单的认为是两个时间点的虚拟时间相减乘以权重

image.png

现在为了计算虚拟时间，再关联两个新的时间

  • Ve： virtual eligible time，合格时间，所谓合格，就是应获得的时间等于其在发出请求前已获得的服务时间。我们称作合格，那么合格时间就是，不合格时间到合格时间的这个差值。如果lag是负数，那么它已经不合格了，我们等到它再次合格的时间，就是Ve
  • Vd： virtual deadline， 截止时间，这个不用解释了

我们看Ve的计算

image.png

就是 T0的虚拟数据V + 实际运行实际si / 权重

这里我们看si的值，如果si已经开始运行了，那么Ve是合格的，这是没问题的
如果si是负数，那么Ve是不合格的，我们得让Vt继续推进，使得Ve合格

再看Vd的计算

image.png

就是 合格时间Ve + 申请的runtime / 权重

示例

image.png

这里假设有两个client，他们的权重都是2，对于的r分别是r1=2，r2=1，时间的粒度是1。那么分析如下

  • t=0： 只有client1，Ve1=0，Vd1=Ve+r1/w1=0+2/2=1
  • t=1： V1=1/2=0.5
  • t=1： Ve2=V1=0.5，Vd2=Ve2+1/2=1，此时我们看到Vd1和Vd2都是1，下一次其实可以任意挑选client1和client2
  • t=2： client2的Ve2=Vd1=1，Vd2=Ve2+1/2=1.5，此时Ve2是1，但是V1是0.5，优先级降低，让client1运行
  • t=3： client1完成，Ve1=Vd1=1，Vd1=Ve1+2/2=2，由于client 2 的dl比client1要早，1.5<2，所以运行clietn2

以此类推

公平性分析

在实际场景中，公平性在EEVDF是通过lag来衡量vt的计算，如下

image.png

假设三个client在t0没有lag，此时client3在t时刻离开，那么计算lag的方法为

lagi(t)=Si(t0,t)−si(t0,t)=∫t0t1fi(τ)dτ−si(t0,t)=wit−t0w1+w2+w3−si(t0,t)−−(1)lag_i(t) = S_i(t_0,t) - s_i(t_0, t) \\ = \int_{t_0}^{t_1}f_i(\tau)d\tau - s_i(t_0, t) \\ = w_i \frac{t - t_0}{w_1 + w_2 + w_3} - s_i(t_0, t) -- (1)

eevdf设计没有所谓的resource idle，则在t0时间中，client1和client2获得的时间为

t−t0−s3(t0,t)t - t_0 - s_3(t_0, t)

那么对于client1和client2，其计算为

Si(t0,t+)=(t−t0−s3(t0,t))wiw1+w2−−(2)S_i(t_0, t^+) = (t - t_0 - s_3(t_0, t)) \frac{w_i}{w_1 + w_2} -- (2)

根据前面的公式代入

lag3(t)=w3t−t0w1+w2+w3−s3(t0,t)s3(t0,t)=w3t−t0w1+w2+w3−lag3(t)−−(3)lag_3(t) = w_3 \frac{t - t_0}{w_1 + w_2 + w_3} - s_3(t_0, t) \\ s_3(t_0, t) = w_3 \frac{t - t_0}{w_1 + w_2 + w_3} - lag_3(t) -- (3)

再将3代入2

Si(t0,t+)=(t−t0−(w3t−t0w1+w2+w3−lag3(t)))wiw1+w2=(t−t0+−w3t+w3t0w1+w2+w3)∗wiw1+w2+wilag3(t)w1+w2=(w1+w2t−w1t0−w2t0w1+w2+w3)∗wiw1+w2+wilag3(t)w1+w2=((w1+w2)(t−t0)w1+w2+w3)∗wiw1+w2+wilag3(t)w1+w2=((t−t0)w1+w2+w3)∗wi+wilag3(t)w1+w2=wi(V(t)−V(t0))+wilag3(t)w1+w2S_i(t_0, t^+) = (t - t_0 - ( w_3 \frac{t - t_0}{w_1 + w_2 + w_3} - lag_3(t))) \frac{w_i}{w_1 + w_2} \\ = (t - t_0 + \frac{-w_3t + w_3 t_0}{w_1 + w_2 + w_3}) * \frac{w_i}{w_1 + w_2} + w_i\frac{lag_3(t)}{w1 + w2} \\ = (\frac{w_1 + w_2t - w_1t_0 - w_2t_0}{w_1 + w_2 + w_3}) * \frac{w_i}{w_1 + w_2} + w_i\frac{lag_3(t)}{w1 + w2} \\ = (\frac{(w_1 + w_2)(t - t_0)}{w_1 + w_2 + w_3}) * \frac{w_i}{w_1 + w_2} + w_i\frac{lag_3(t)}{w1 + w2} \\ = (\frac{(t - t_0)}{w_1 + w_2 + w_3}) * w_i + w_i\frac{lag_3(t)}{w1 + w2} \\ = w_i(V(t) - V(t_0)) + w_i\frac{lag_3(t)}{w1 + w2}

我们可以看到client3离开时，client1和2分摊了client3的lag

所以当一个client离开，那么其Vt的计算为

V(t)=V(t)+lagj(t)∑i∈A(t+)wi−−(4)V(t) = V(t) + \frac{lag_j(t)}{\sum_{i\in{A(t^+)}}w_i} -- (4)

同理，当一个client加入，其Vt计算为

V(t)=V(t)−lagj(t)∑i∈A(t+)wi−−(5)V(t) = V(t) - \frac{lag_j(t)}{\sum_{i\in{A(t^+)}}w_i} -- (5)

那么reweight的时候，其Vt计算为

V(t)=V(t)+lagj(t)∑i∈A(t+)wi−wj+lagj(t)∑i∈A(t+)wi+wj′−−(6)V(t) = V(t) + \frac{lag_j(t)}{\sum_{i\in{A(t^+)}}w_i - w_j} + \frac{lag_j(t)}{\sum_{i\in{A(t^+)}}w_i + w_j^{'}} -- (6)

所以我们可以认为EEVDF是work-conserving最优的

总结

本论文是eevdf的开篇基石，里面详细论证了EEVDF的优势，了解这个论文的熟悉linux eevdf来说至关重要。为了理解这个论文，我重新啃了一些里面的公式，计算过程在上文中。

参考

https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=805acf7726282721504c8f00575d91ebfd750564