Linux 内核已经合入了 EEVDF 调度器用于替代任职多年的 CFS 调度器。我对调度这种宏观且复杂的算法一直感到敬畏,还是先了解一下基本思路吧。
TL;DR
一句话总结就是:调度资源只会分配给 具有合格的(eligible)最早虚拟截止时间 调度请求 的任务。
引出问题
这部分和 EEVDF 基本无关,但这是作者认为调度需要解决的本质问题。
首先定义:
:关联到任务 的权重。 :在时间点 时,处于活跃状态(正在竞争调度资源)的任务集合。
那么可以描述
理想状态下,任务
但是一个真实的调度器是实际处于离散状态,设
这里的核心问题就是怎么去处理 lag。
一些概念
EEVDF 是一种比例份额调度算法。而比例份额调度的特色在于每个任务都有权重的概念。不同的权重占比影响一个任务能获得调度资源的份额:比如存在 2 个任务,一个权重为 1,另一个权重为 3,那就分别能获得 25% 和 75% 的调度资源。
关于调度资源:在本论文中认为,如果一个任务想要获取调度资源,则需发出调度请求。
关于虚拟时间:可简单理解为经权重调整过的现实时间。这种概念在 CFS 调度器中也有应用,因为完全公平调度追求的是所有任务的虚拟运行时间相同,当一个任务权重更高(low nice),其虚拟时间流逝速度相比普通任务更慢,因此能在公平的意义下获取更多的实际运行时间。EEVDF 的用法基本一样,它统一了所有不同权重的任务的时间统计单位,同时可以轻易转换为现实时间:比如一个运行队列中只有 2 个任务,一个任务权重为 2,另一个权重为 3,那么系统的虚拟时间增速就是
关于截止时间:正如实时调度里的概念,就是最晚获得所有请求资源的时间点。作者用周期性调度举例,已知调度周期
关于合格时间:这是 EEVDF 中独有的概念。在新的调度请求发出前,理论应得服务时间长度等同于现实已有服务时间长度,那么此时的时间点则是合格时间。这个定义使得在后续公式计算中关联上理论应得和实际已得的数值。
EEVDF 描述
在 EEVDF 算法中,通过结合公式
并且定义时间点
再结合公式
由于合格时间
以及虚拟截止时间,其中
直到这一步,作者已经把现实时间的概念给抛弃掉,因为这些时间现在都可用虚拟时间来描述。
后面将用
:由任务 创建的第 个请求的长度。 :上述请求对应的虚拟合格时间。 :上述请求对应的虚拟截止时间。
如果任务每次都完整使用了它请求到的服务时间,使用公式
如果任务并没有完整使用服务时间,那么相比上面只需改动公式
可以看出这种情况下,后续的合格时间会被提前。
示例
上面展示了 EEVDF 的一个示例。两个不同的任务(client),发出的请求长度为
假设任务 1 在
在
在
在
公平性
这部分会说明如何去更新 lag 和虚拟时间。
作者认为一个调度器需要满足以下三种操作:
- 让任务加入调度竞争。
- 让任务离开调度竞争。
- 修改任务的权重。
理想状态不存在 lag,而实际额外开销使得这三种操作均会产生 lag,这会影响到后续的公平性。
那怎么办?结论是:EEVDF 将 lag 也加入到虚拟时间的更新中来保证公平性。
假设存在这种情况:三个任务从
而剩下的两个任务已分配的服务时间可以通过
注意到
接着使用
因此,为了保证剩下任务的公平性,需要根据离开竞争的任务对应的 lag 来更新虚拟时间。同时作者认为
总结
相应的,当一个任务
得出一个结论:通过公式
NOTE: 至于修改权重的操作那就是同时离开并加入:
但是作者指出,如果一个(存在非零 lag 的)任务先离开调度竞争,后续再次加入回调度竞争(rejoin),那此时刻对应的 lag 的补偿(或惩罚)计算就没有简单的办法。
算法实现
前面提到对于 rejoin 这种行为没有好办法去处理公平性,作者给了三种策略:
- 如果任务在
离开, 重加,则 。其它操作按照公式 来计算。 - 类似上面的策略,但不同在于:离开竞争后,不再保留 lag,因此重加后 lag 也是 0。
- 只允许在 lag 为 0 的情况下执行加入、离开、修改操作,因此不需要更新虚拟时间。但是这种策略有它本身的复杂性,具体看论文吧……
论文后续有相关的代码实现以及复杂的公平性证明。个人感觉实现的部分可以直接从 Linux v6.6 入手(看论文就是为了这个!),所以这里就跳过了,感兴趣的读者请翻附录;证明部分应该没人愿意看的吧……我也不看这些的,再次跳了。
所以没有别的了,就这样吧,全文完。