Home [论文阅读] Earliest Eligible Virtual Deadline First (EEVDF)
Post
Cancel

[论文阅读] Earliest Eligible Virtual Deadline First (EEVDF)

Linux内核已经合入了EEVDF调度器(这该怎么翻译啊?)用于替代任职多年的CFS调度器。我对调度这种宏观且复杂的算法一直感到敬畏,还是先了解一下基本思路吧。

论文全名及链接:Earliest Eligible Virtual Deadline First : A Flexible and Accurate Mechanism for Proportional Share Resource Allocation

TL;DR

一句话总结就是:调度资源只会分配给 具有合格的(eligible)最早虚拟截止时间 调度请求 的任务。

引出问题

这部分和EEVDF基本无关,但这是作者认为调度需要解决的本质问题。

首先定义:

  • \(w_i\):关联到任务\(i\)的权重。
  • \(A(t)\):在时间点\(t\)时,处于活跃状态(正在竞争调度资源)的任务集合。

那么可以描述\(f_i(t)\),表示时间点\(t\)时任务\(i\)的份额:

\[\begin{equation} f_i(t) = \frac{w_i}{\sum_{j \in A(t)}w_j} \tag{1} \end{equation}\]

理想状态下,任务\(i\)在\([t_0, t_1]\)时间段内的应得服务时间为:

\[\begin{equation} S_i(t_0, t_1) = \int_{t_0}^{t_1}f_i(\tau)d\tau \tag{2} \end{equation}\]

但是一个真实的调度器是实际处于离散状态,设\(t_{0}^{i}\)为任务\(i\)变为活跃状态的时间点,\([t_{0}^{i}, t]\)内的实际服务时间为\(s_i(t_{0}^{i}, t)\)。实际环境下由于调度开销等因素,与理想环境相比存在服务时间差距\(lag\)。设时间点\(t\)时任务\(i\)服务时间差距为:

\[\begin{equation} lag_i(t) = S_i(t_{0}^{i}, t) - s_i(t_{0}^{i}, t) \tag{3} \end{equation}\]

这里的核心问题就是怎么去处理lag。

一些概念

EEVDF是一种比例份额调度算法。而比例份额调度的特色在于每个任务都有权重的概念。不同的权重占比影响一个任务能获得调度资源的份额:比如存在2个任务,一个权重为1,另一个权重为3,那就分别能获得25%和75%的调度资源。

关于调度资源:在本论文中认为,如果一个任务想要获取调度资源,则需发出调度请求。

关于虚拟时间:可简单理解为经权重调整过的现实时间。这种概念在CFS调度器中也有应用,因为完全公平调度追求的是所有任务的虚拟运行时间相同,当一个任务权重更高(low nice),其虚拟时间流逝速度相比普通任务更慢,因此能在公平的意义下获取更多的实际运行时间。EEVDF的用法基本一样,它统一了所有不同权重的任务的时间统计单位,同时可以轻易转换为现实时间:比如一个运行队列中只有2个任务,一个任务权重为2,另一个权重为3,那么系统的虚拟时间增速就是\(\frac{1}{w_1+w_2} = \frac{1}{2 + 3} = 0.2\)每秒,一个虚拟时间单位对应于5个现实时间单位。

关于截止时间:正如实时调度里的概念,就是最晚获得所有请求资源的时间点。作者用周期性调度举例,已知调度周期\(T\),最大服务时间\(r\),就是要求每个周期内都能拥有\(r\)的服务时间长度,因此资源份额有\(f = \frac{r}{T}\)。反过来,已知请求创建的时间点\(t\),其请求长度为\(r\),其截止时间则是\(t + \frac{r}{f}\)。

关于合格时间:这是EEVDF中独有的概念。在新的调度请求发出前,理论应得服务时间长度等同于现实已有服务时间长度,那么此时的时间点则是合格时间。这个定义使得在后续公式计算中关联上理论应得和实际已得的数值。

EEVDF描述

在EEVDF算法中,通过结合公式\((1)\)和\((2)\),得到活跃任务\(i\)在时间段\([t_1, t_2]\)应得服务时间:

\[\begin{equation} S_i(t_0, t_1) = w_i\int_{t_1}^{t_2}\frac{1}{\sum_{j \in A(\tau)}w_j}d\tau \tag{4} \end{equation}\]

并且定义时间点\(t\)对应的虚拟时间\(V(t)\):

\[\begin{equation} V(t) = \int_{0}^{t}\frac{1}{\sum_{j \in A(\tau)}w_j}d\tau \tag{5} \end{equation}\]

再结合公式\((4)\)和\((5)\)得到在虚拟时间意义下的服务时间:

\[\begin{equation} S_i(t_0, t_1) = w_i(V(t_2) - V(t_1)) \tag{6} \end{equation}\]

由于合格时间\(e\)的定义满足\(S_i(t_{0}^{i}, e) = s_i(t_{0}^{i}, t)\),其中\(t\)为请求初始化的时间点(注意存在两种情况\(e1 \le t\)或者\(e2 > t\),第一种情况就是\(t\)时间点立刻确认合格,第二种情况需要等待到\(e2\)时间点才算合格)。再结合使用公式\((6)\)可以描述虚拟合格时间:

\[\begin{equation} V(e) = V(t_{0}^{i}) + \frac{s_i(t_{0}^{i}, t)}{w_i} \tag{7} \end{equation}\]

以及虚拟截止时间,其中\(r\)表示一个新请求的时间长度,即\(S_i(e, d) = r\),再结合公式\((6)\)得到:

\[\begin{equation} V(d) = V(e) + \frac{r}{w_i} \tag{8} \end{equation}\]

直到这一步,作者已经把现实时间的概念给抛弃掉,因为这些时间现在都可用虚拟时间来描述。

后面将用\(ve\)表示虚拟合格时间,\(vd\)表示虚拟截止时间。由于每个请求都有\(ve\)和\(vd\),再次定义:

  • \(r^{(k)}\):由任务\(i\)创建的第\(k\)个请求的长度。
  • \(ve^{(k)}\):上述请求对应的虚拟合格时间。
  • \(vd^{(k)}\):上述请求对应的虚拟截止时间。

如果任务每次都完整使用了它请求到的服务时间,使用公式\((7)\)和\((8)\)可以得到:

\[\begin{equation} ve^{(1)} = V(t_{0}^{i}) \tag{9} \end{equation}\] \[\begin{equation} vd^{(k)} = ve^{(k)} + \frac{r^{(k)}}{w_i} \tag{10} \end{equation}\] \[\begin{equation} ve^{(k+1)} = vd^{(k)} \tag{11} \end{equation}\]

如果任务并没有完整使用服务时间,那么相比上面只需改动公式\((11)\),其中\(u^{(k)}\)表示在第\(k\)个请求中实际用到的服务时间:

\[\begin{equation} ve^{(k+1)} = ve^{(k)} + \frac{u^{(k)}}{w_i} \tag{12} \end{equation}\]

可以看出这种情况下,后续的合格时间会被提前。

示例

example

上面展示了EEVDF的一个示例。两个不同的任务(client),发出的请求长度为\(r_1 = 2, r_2 = 1\)。

假设任务1在\(t_0 = 0\)时参与调度,根据公式\((9)\)和\((10)\),\(ve = 0, vd = ve + \frac{r_1}{w_1} = 1\)。此时由于是只有单个任务且具有合格请求,因此获得调度资源(这里单次分配的资源是time quantum,设为1秒)。

在\(t = 1\)时,任务2参与调度竞争。虚拟时间从现实时间\([0, 1)\)的增长速率是固定的(\(\frac{1}{w_1} = 0.5\)),由公式\((5)\)得到\(V(1) = \int_{0}^{1}\frac{1}{w_1}d\tau = 0.5\),后续任务2加入后的增速改为\(\frac{1}{w_1 + w_2} = 0.25\)。假设此时任务2也有了调度请求,此时共有2个待定请求:一个是来自任务1的虚拟截止时间为1的请求(在等待其它time quantum到来以“填满”请求);另一个是来自任务2的刚创建的请求,同样是虚拟截止时间为1。这种请求任选其一,比如选择任务2的请求,因此第二个time quantum已经填满了任务2的当前请求,任务2现在可以发出一个新的请求,其中虚拟合格时间为1,虚拟截止时间为1.5。

在\(t = 2\)时,唯一合格的请求来自任务1,因此它获得了下一个time quantum。

在\(t = 3\)时,再次有两个合格的请求,但由于任务2的请求拥有比任务1新发出的请求更早的虚拟截止时间(\(vd_2 = 1.5 < vd_1 = 2\)),因此选择前者。

公平性

作者认为一个调度器需要满足以下三种操作:

  • 让任务加入调度竞争。
  • 让任务离开调度竞争。
  • 修改任务的权重。

理想状态不存在lag,而实际额外开销使得这三种操作均会产生lag,这会影响到后续的公平性。

那怎么办?结论是:EEVDF将lag也加入到虚拟时间的更新中来保证公平性。

fairness

假设存在这种情况:三个任务从\(t_0\)开始参与调度竞争,但是\(t\)时间点任务3离开调度竞争。因为在\([t_0, t)\)时间段中,活跃任务的个数以及份额并没有发生改变,所以虚拟时间的增速是\(\frac{1}{w_1 + w_2 + w_3}\)。并且使用公式\((3)\)可以算出:

\[\begin{equation} lag_i(t) = w_i\frac{t - t_0}{w_1 + w_2 + w_3} - s_i(t_0, t), i = 1,2,3 \tag{13} \end{equation}\]

而剩下的两个任务已分配的服务时间可以通过\(t - t_0 - s_3(t_0, t)\)来表示。并使用\(t^+\)表示任务3离开竞争后的那一瞬间,忽略开销的话就是\(t^+ \to t\)。那么\(t^+\)时刻任务1和任务2已接收多少服务时间呢?一个思路就是直接比例划分:

\[\begin{equation} S_i(t_0, t^+) = (t - t_0 - s_3(t_0, t))\frac{w_i}{w_1 + w_2}, i = 1,2 \tag{14} \end{equation}\]

注意到\(lag_3(t) \ne 0\),上面的式子并不等于离开前每个任务所接收服务时间(\((t-t_0)\frac{w_i}{w_1 + w_2 + w_3}\))。这是因为任务3离开后会等比例的丢失或增加服务时间。作者用该式子和\((13)\)将\(s_3(t, t_0)\)替换:

\[\begin{equation} \begin{aligned} S_i(t_0, t^+) &= (t - t_0)\frac{w_i}{w_1 + w_2 + w_3} + w_i\frac{lag_3(t)}{w_1 + w_2} \\ &= w_i(V(t) - V(t_0)) + w_i\frac{lag_3(t)}{w_1 + w_2}, i = 1,2 \end{aligned} \tag{15} \end{equation}\]

接着使用\((6)\)和\((15)\)去掉权重可得到:

\[\begin{equation} V(t^+) = V(t) + \frac{lag_3(t)}{w_1 + w_2} \tag{16} \end{equation}\]

因此,为了保证剩下任务的公平性,需要根据离开竞争的任务对应的lag来更新虚拟时间。作者认为\(s_i(t_0, t) = s_i(t_0, t^+)\),从这里可以算出前2个任务在\(t^+\)的lag:

\[\begin{equation} \begin{aligned} lag_i(t^+) &= w_i(V(t^+) - V(t_0)) - s_i(t_0, t^+) \\ &= lag_i(t) + w_i\frac{lag_3(t)}{w_1 + w_2}, i = 1,2 \end{aligned} \tag{17} \end{equation}\]

因此总结\((16)\)得出,当一个任务\(j\)在时间点\(t\)离开调度竞争时,对应的虚拟时间更新为:

\[\begin{equation} V(t) = V(t) + \frac{lag_j(t)}{\sum_{i \in A(t^+)}w_i} \tag{18} \end{equation}\]

相应的,当一个任务\(j\)在时间点\(t\)加入调度竞争时,对应的虚拟时间更新为:

\[\begin{equation} V(t) = V(t) - \frac{lag_j(t)}{\sum_{i \in A(t^+)}w_i} \tag{19} \end{equation}\]

这里再给出一个结论:通过公式\((18), (19)\)来更新虚拟时间,可以保证所有活跃任务的lag之和为0。

至于修改权重的操作那就是同时离开并加入:

\[\begin{equation} 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 + w'_j} \tag{20} \end{equation}\]

但是作者指出,如果一个(存在非零lag的)任务先离开调度竞争,后续再次加入回调度竞争(rejoin),那此时刻对应的lag的补偿(或惩罚)计算就没有简单的办法。

算法实现

前面提到对于rejoin这种行为没有好办法去处理公平性,作者给了三种策略:

  1. 如果任务在\(t\)离开,\(t'\)重加,则\(lag(t) = lag(t')\)。其它操作按照公式\((18), (19), (20)\)来计算。
  2. 类似上面的策略,但不同在于:离开竞争后,不再保留lag,因此重加后lag也是0。
  3. 只允许在lag为0的情况下执行加入、离开、修改操作,因此不需要更新虚拟时间。但是这种策略有它本身的复杂性,具体看论文吧……

另外,论文后续有复杂的公平性证明,附录还有代码实现,这里不拷贝过来了。

就这样吧,抄公式都抄麻了,全文完。

This post is licensed under CC BY 4.0 by the author.
Contents