CFS中的虚拟运行时间vruntime

时间:2021-09-17 08:15:36

一直对CFS(Completely Fair Scheduling,完全公平调度)中的虚拟运行时间(vruntime)不太理解,最近在看cgroup中的cpu子系统算是搞清楚了它是怎么回事。

先 简单说一下CFS调度算法的思想:理想状态下每个进程都能获得相同的时间片,并且同时运行在CPU上,但实际上一个CPU同一时刻运行的进程只能有一个。 也就是说,当一个进程占用CPU时,其他进程就必须等待。CFS为了实现公平,必须惩罚当前正在运行的进程,以使那些正在等待的进程下次被调度。

具体实现时,CFS通过每个进程的虚拟运行时间(vruntime)来衡量哪个进程最值得被调度。CFS中的就绪队列是一棵以vruntime为键值的红黑树,虚拟时间越小的进程越靠近整个红黑树的最左端。因此,调度器每次选择位于红黑树最左端的那个进程,该进程的vruntime最小。

虚拟运行时间是通过进程的实际运行时间和进程的权重(weight)计算出来的。在CFS调度器中,将进程优先级这个概念弱化,而是强调进程的权重。一个进程的权重越大,则说明这个进程更需要运行,因此它的虚拟运行时间就越小,这样被调度的机会就越大。

那么,在用户态进程的优先级nice值与CFS调度器中的权重又有什么关系?在内核中通过prio_to_weight数组进行nice值和权重的转换。

static const int prio_to_weight[40] = {
 /* -20 */     88761,    71755,     56483,     46273,    36291,
 /* -15 */     29154,    23254,     18705,     14949,    11916,
 /* -10 */      9548,     7620,      6100,      4904,     3906,
 /*  -5 */     3121,      2501,      1991,     1586,      1277,
 /*   0 */     1024,       820,       655,       526,       423,
 /*   5 */      335,       272,       215,       172,       137,
 /*  10 */      110,        87,        70,        56,        45,
 /*  15 */       36,        29,        23,        18,        15,
};
 

而在内核中,进程的虚拟运行时间是自进程诞生以来进行累加的,每个时钟周期内一个进程的虚拟运行时间是通过下面的方法计算的:

一次调度间隔的虚拟运行时间=实际运行时间*(NICE_0_LOAD/权重)

其中,NICE_0_LOAD是nice为0时的权重。也就是说,nice值为0的进程实际运行时间和虚拟运行时间相同。通过这个公式可以看到,权重越大的进程获得的虚拟运行时间越小,那么它将被调度器所调度的机会就越大


转http://edsionte.com/techblog/archives/4331