CFS调度器选择vruntime最小的任务来进行调度,在更新vruntime的时候一个是要考虑当前时间和上次更新vruntime的时间差,二是要加权计算sched_entity的load。load的值依赖于当前sched_entity的nice值,在内核中这个nice和load的对应关系事先已经被计算好。
-
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 levels are multiplicative, with a gentle 10% change for every
-
* nice level changed. I.e. when a CPU-bound task goes from nice 0 to
-
* nice 1, it will get ~10% less CPU time than another CPU-bound task
-
* that remained on nice 0.
-
*
-
* The "10% effect" is relative and cumulative: from _any_ nice level,
-
* if you go up 1 level, it's -10% CPU usage, if you go down 1 level
-
* it's +10% CPU usage. (to achieve that we use a multiplier of 1.25.
-
* If a task goes up by ~10% and another task goes down by ~10% then
-
the relative distance between them is ~25%.)
大概的意思就是nice值的上升1级(越小执行优先级越高),也就意味着sched_entity的运行时间会减少。规定这个减少的幅度是10%,这个差距导致了两个sched_entityl的oad大概差了1.25倍,例子:两个sched_entity具有相同的nice,也就是各占50%的cpu时间,其中一个nice上升,导致了这个sched_entity
cpu时间比之前少了10%,也就是一个sched_entity是55%,一个是45%,所以这个时候55和45大概差了1.25倍。
这样就有了 prio_to_weight数组。
还有数组,每个元素的值是1>>32/prio_to_weight每个元素的值。
-
/*
-
* Nice levels are multiplicative, with a gentle 10% change for every
-
* nice level changed. I.e. when a CPU-bound task goes from nice 0 to
-
* nice 1, it will get ~10% less CPU time than another CPU-bound task
-
* that remained on nice 0.
-
*
-
* The "10% effect" is relative and cumulative: from _any_ nice level,
-
* if you go up 1 level, it's -10% CPU usage, if you go down 1 level
-
* it's +10% CPU usage. (to achieve that we use a multiplier of 1.25.
-
* If a task goes up by ~10% and another task goes down by ~10% then
-
the relative distance between them is ~25%.)
这个数组的存在的意义很大,因为在更新vruntime的时候,时间差需要加权load,当nice=0表示不需要加权load计算。如果nice!=0那么需要按照当前的load和nice=0的load(nice=0的load=1024)的比例进行等比例缩减或者增加vruntime。
公式如下:
delta vruntime= deltaTime*1024/load (1024是nice=0的时候)
这里delta
vruntime是vruntime的差值。deltaTime就是当前时间和上次计算的load的时间差,load就是当前sched_entity的load值,通过上面的公式可以看出,如果load越大,vruntime越小,cfs会通过红黑树选择出最需要调度的sched_entity,也就是vruntime最小的。
但是内核中会频繁统计这个delta
vruntime,我们知道运算中,除法的运行周期十分长,这样就导致了计算delta
vruntime会很慢。那么这个除法可以用乘法和位移运算来代替。
可以看出公式中,利用到了inv_load数组,这个数组事先缓存好了的值,然后最后结果在右移32位就是结果。
代码中,我想了很久才明白的一行代码:
-
/*
-
* Shift right and round:
-
*/
-
#define SRR(x, y) (((x) + (1UL << ((y) - 1))) >> (y))
注释的意思是,x右移y位,相当于然后结果,四舍五入。
可以知道1UL<<(y-1)相当于1<的一半,对于一个位移操作,相当于除法取整的操作。话语很难表述清楚这个
x+1UL
<< ((y) – 1))
的作用,举例说明一下:
SRR (10,2) 也就是10/4, 1010+0010=1100 >>2=0011=3
SRR (9,2) 就是9/4,1001+0010=1010>>2=0010=2
看了上面的例子也就清楚了,1UL<<(y-1)作用于y-1位(右边第一位是0位),如果为y-1位为1,就是产生了5入的情况,需要1UL<<(y-1)来帮助它进位,不被位移操作抵销掉。如果y-1位为0,那么也就是产生了4舍的情况,1UL<<(y-1)对它来说都是没有任何作用的,因为不会产生进位操作。
所以这个(1UL
<< ((y) – 1))是SRR操作能四舍五入的根本原因。
看下代码:
-
static unsigned long calc_delta_mine(unsigned long delta_exec, unsigned long weight,struct load_weight *lw){
-
u64 tmp;
-
-
if (!lw->inv_weight) { //如果inv_load为0,设置一个最小的inv_load为1,因为weight超过了1>>32,那么按原有逻辑得到的inv_load肯定是0,后面的乘法没有意义了。
-
if (BITS_PER_LONG > 32 && unlikely(lw->weight >= WMULT_CONST))
-
lw->inv_weight = 1;
-
else
-
lw->inv_weight = 1 + (WMULT_CONST-lw->weight/2) / (lw->weight+1);//这个逻辑不太清楚
-
}
-
-
tmp = (u64)delta_exec * weight;
-
/*
-
* Check whether we'd overflow the 64-bit multiplication:
-
*/
-
-
if (unlikely(tmp > WMULT_CONST)) //如果tmp结果大于了32位整数的限制,那么在乘以inv_load会产生overflow,那么处理逻辑可以先位移一半16位,再位移后一半16位
-
tmp = SRR(SRR(tmp, WMULT_SHIFT/2) * lw->inv_weight,WMULT_SHIFT/2);
-
else
-
tmp = SRR(tmp * lw->inv_weight, WMULT_SHIFT);
-
-
return (unsigned long)min(tmp, (u64)(unsigned long)LONG_MAX);
不明白的问题:在sched_entity更新weight的时候(update_load_add,update_load_sub)会把inv_weight置为0,导致在计算delta_vruntime的时候重新计算inv_weight,公式中的
lw->inv_weight = 1 +
(WMULT_CONST-lw->weight/2)/ (lw->weight+1) 是我不理解的,尤其是那个 lw->weight/2,有什么特殊的用意。希望看懂这行代码的同学能指点我一下。
阅读(1699) | 评论(0) | 转发(0) |