Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1320309
  • 博文数量: 175
  • 博客积分: 2743
  • 博客等级: 少校
  • 技术积分: 4024
  • 用 户 组: 普通用户
  • 注册时间: 2010-12-30 01:41
文章分类

全部博文(175)

文章存档

2015年(1)

2013年(53)

2012年(71)

2011年(50)

分类: LINUX

2013-04-22 14:33:22


     CFS调度器选择vruntime最小的任务来进行调度,在更新vruntime的时候一个是要考虑当前时间和上次更新vruntime的时间差,二是要加权计算sched_entityloadload的值依赖于当前sched_entitynice值,在内核中这个niceload的对应关系事先已经被计算好。

           

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



这些值的取值原因自己也没有搞清楚,看了注释大概明白。


  1. /*
  2. * Nice levels are multiplicative, with a gentle 10% change for every
  3. * nice level changed. I.e. when a CPU-bound task goes from nice 0 to
  4. * nice 1, it will get ~10% less CPU time than another CPU-bound task
  5. * that remained on nice 0.
  6. *
  7. * The "10% effect" is relative and cumulative: from _any_ nice level,
  8. * if you go up 1 level, it's -10% CPU usage, if you go down 1 level
  9. * it's +10% CPU usage. (to achieve that we use a multiplier of 1.25.
  10. * If a task goes up by ~10% and another task goes down by ~10% then
  11. the relative distance between them is ~25%.)



     大概的意思就是nice值的上升1级(越小执行优先级越高),也就意味着sched_entity的运行时间会减少。规定这个减少的幅度是10%,这个差距导致了两个sched_entityload大概差了1.25倍,例子:两个sched_entity具有相同的nice,也就是各占50%cpu时间,其中一个nice上升,导致了这个sched_entity cpu时间比之前少了10%,也就是一个sched_entity55%,一个是45%,所以这个时候5545大概差了1.25倍。

这样就有了 prio_to_weight数组。

还有数组,每个元素的值是1>>32/prio_to_weight每个元素的值。

            

  1. /*
  2. * Nice levels are multiplicative, with a gentle 10% change for every
  3. * nice level changed. I.e. when a CPU-bound task goes from nice 0 to
  4. * nice 1, it will get ~10% less CPU time than another CPU-bound task
  5. * that remained on nice 0.
  6. *
  7. * The "10% effect" is relative and cumulative: from _any_ nice level,
  8. * if you go up 1 level, it's -10% CPU usage, if you go down 1 level
  9. * it's +10% CPU usage. (to achieve that we use a multiplier of 1.25.
  10. * If a task goes up by ~10% and another task goes down by ~10% then
  11. the relative distance between them is ~25%.)


      这个数组的存在的意义很大,因为在更新vruntime的时候,时间差需要加权load,当nice=0表示不需要加权load计算。如果nice=0那么需要按照当前的loadnice=0loadnice=0load=1024)的比例进行等比例缩减或者增加vruntime

公式如下:

delta vruntime= deltaTime*1024/load (1024nice=0的时候)


      这里delta vruntimevruntime的差值。deltaTime就是当前时间和上次计算的load的时间差,load就是当前sched_entityload值,通过上面的公式可以看出,如果load越大,vruntime越小,cfs会通过红黑树选择出最需要调度的sched_entity,也就是vruntime最小的。

      但是内核中会频繁统计这个delta vruntime,我们知道运算中,除法的运行周期十分长,这样就导致了计算delta vruntime会很慢。那么这个除法可以用乘法和位移运算来代替。

      可以看出公式中,利用到了inv_load数组,这个数组事先缓存好了的值,然后最后结果在右移32位就是结果。

代码中,我想了很久才明白的一行代码:

      

  1. /*
  2.         * Shift right and round:
  3.         */
  4.         #define SRR(x, y) (((x) + (1UL << ((y) - 1))) >> (y))


     注释的意思是,x右移y位,相当于然后结果,四舍五入。

     可以知道1UL<<(y-1)相当于1<的一半,对于一个位移操作,相当于除法取整的操作。话语很难表述清楚这个x+1UL << ((y) – 1))的作用,举例说明一下:

     SRR (10,2) 也就是10/41010+0010=1100 >>2=0011=3

     SRR (9,2) 就是9/41001+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操作能四舍五入的根本原因。

     看下代码:

 

  1. static unsigned long calc_delta_mine(unsigned long delta_exec, unsigned long weight,struct load_weight *lw){
  2.         u64 tmp;
  3.         
  4.         if (!lw->inv_weight) { //如果inv_load为0,设置一个最小的inv_load为1,因为weight超过了1>>32,那么按原有逻辑得到的inv_load肯定是0,后面的乘法没有意义了。
  5.                 if (BITS_PER_LONG > 32 && unlikely(lw->weight >= WMULT_CONST))
  6.                         lw->inv_weight = 1;
  7.                 else
  8.                         lw->inv_weight = 1 + (WMULT_CONST-lw->weight/2) / (lw->weight+1);//这个逻辑不太清楚
  9.         }

  10.         tmp = (u64)delta_exec * weight;
  11.     /*
  12.     * Check whether we'd overflow the 64-bit multiplication:
  13.     */

  14.         if (unlikely(tmp > WMULT_CONST)) //如果tmp结果大于了32位整数的限制,那么在乘以inv_load会产生overflow,那么处理逻辑可以先位移一半16位,再位移后一半16位
  15.                 tmp = SRR(SRR(tmp, WMULT_SHIFT/2) * lw->inv_weight,WMULT_SHIFT/2);
  16.         else
  17.                 tmp = SRR(tmp * lw->inv_weight, WMULT_SHIFT);

  18.         return (unsigned long)min(tmp, (u64)(unsigned long)LONG_MAX);


     不明白的问题:在sched_entity更新weight的时候(update_load_addupdate_load_sub)会把inv_weight置为0,导致在计算delta_vruntime的时候重新计算inv_weight,公式中的

lw->inv_weight = 1 + (WMULT_CONST-lw->weight/2)/ (lw->weight+1) 是我不理解的,尤其是那个 lw->weight/2,有什么特殊的用意。希望看懂这行代码的同学能指点我一下。


阅读(1700) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~