忘记密码   免费注册 查看新帖 | 论坛精华区

ChinaUnix.net

  平台 论坛 博客 认证专区 大话IT HPC论坛 徽章 文库 沙龙 自测 下载 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
12下一页
最近访问板块 发新帖
查看: 3520 | 回复: 10

读 深入Linux内核架构 2.6.3 节的问题 [复制链接]

论坛徽章:
0
发表于 2011-05-05 14:48 |显示全部楼层
关于下面这段话:
由于内核已经承诺在当前的延迟周期内使所有活动进程都至少运行一次,队列的min_vruntime用作基准虚拟时间,通过减去sysctl_sched_latency,则可以确保新唤醒的进程只有在当前延迟周期结束后才能运行。

但如果睡眠进程已经累积了比较大的不公平值(即se_vruntime值比较大),则内核必须考虑这一点。如果se->vruntime比先前计算的差值更大,则将其作为进程的vruntime,这会导致该进程在红黑树中处于比较靠左的位置,回想一下可知具有较大vruntime值的进程可以更早调度执行

上面红色的这段话,让我有点糊涂了,不是vruntime 越小的先被调度么

这个如何理解
请教
谢谢

论坛徽章:
20
丑牛
日期:2014-08-15 14:32:002017金鸡报晓
日期:2017-02-08 10:39:42黑曼巴
日期:2016-11-15 15:48:38CU十四周年纪念徽章
日期:2016-11-09 13:19:1015-16赛季CBA联赛之同曦
日期:2016-04-08 18:00:03平安夜徽章
日期:2015-12-26 00:06:30程序设计版块每日发帖之星
日期:2015-12-03 06:20:002015七夕节徽章
日期:2015-08-21 11:06:17IT运维版块每日发帖之星
日期:2015-08-09 06:20:002015亚冠之吉达阿赫利
日期:2015-07-03 08:39:422015亚冠之西悉尼流浪者
日期:2015-05-15 10:16:372015年亚洲杯之阿曼
日期:2015-04-09 16:23:11
发表于 2011-05-05 15:16 |显示全部楼层
本帖最后由 amarant 于 2011-05-05 15:17 编辑

我也是这么想的,看了下英文版的
However, if the sleeper has accumulated a large unfairness as indicated by a large se_vruntime value, the kernel must honor this. If se->vruntime is larger than the previously computed difference, it is kept as the vruntime of the process, which leads to a leftward placement on the red-black tree — recall that large vruntime values are good to schedule early!

也是这么说的。然后我去看了下源码,下面贴出插入的函数:
  1. /*
  2. * Enqueue an entity into the rb-tree:
  3. */
  4. static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
  5. {
  6.         struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
  7.         struct rb_node *parent = NULL;
  8.         struct sched_entity *entry;
  9.         s64 key = entity_key(cfs_rq, se);
  10.         int leftmost = 1;

  11.         /*
  12.          * Find the right place in the rbtree:
  13.          */
  14.         while (*link) {
  15.                 parent = *link;
  16.                 entry = rb_entry(parent, struct sched_entity, run_node);
  17.                 /*
  18.                  * We dont care about collisions. Nodes with
  19.                  * the same key stay together.
  20.                  */                if (key < entity_key(cfs_rq, entry)) {
  21.                         link = &parent->rb_left;
  22.                 } else {
  23.                         link = &parent->rb_right;
  24.                         leftmost = 0;
  25.                 }
  26.         }

  27.         /*
  28.          * Maintain a cache of leftmost tree entries (it is frequently
  29.          * used):
  30.          */
  31.         if (leftmost)
  32.                 cfs_rq->rb_leftmost = &se->run_node;

  33.         rb_link_node(&se->run_node, parent, link);
  34.         rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
  35. }

复制代码
完全是最小key值最先调度,所以我认为这里写错了。

论坛徽章:
0
发表于 2011-05-05 15:26 |显示全部楼层
本帖最后由 liu090 于 2011-05-05 15:28 编辑
  1. 1.kernel/sched_fair.c   
  2. 2.static void  
  3. 3.place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)  
  4. 4.{  
  5. 5.        u64 vruntime;  
  6. 6.
  7. 7.        vruntime = cfs_rq->min_vruntime;   
  8. 8.
  9. 9.        if (initial)   
  10. 10.                vruntime += sched_vslice_add(cfs_rq, se);   
  11. 11.
  12. 12.        if (!initial) {   
  13. 13.                vruntime -= sysctl_sched_latency;   
  14. 14.                vruntime = max_vruntime(se->vruntime, vruntime);   
  15. 15.        }   
  16. 16.
  17. 17.        se->vruntimevruntime = vruntime;  
  18. 18.}
复制代码
但如果睡眠进程已经累积了比较大的不公平值(即se_vruntime值比较大),则内核必须考虑这一点。如果se->vruntime比先前计算的差值更大,则将其作为进程的vruntime,这会导致该进程在红黑树中处于比较靠左的位置,回想一下可知具有较大vruntime值的进程可以更早调度执行。

但是,按他对max_vruntime  的解释,如何理解呢?
取大的值不是更慢被调度了?

论坛徽章:
20
丑牛
日期:2014-08-15 14:32:002017金鸡报晓
日期:2017-02-08 10:39:42黑曼巴
日期:2016-11-15 15:48:38CU十四周年纪念徽章
日期:2016-11-09 13:19:1015-16赛季CBA联赛之同曦
日期:2016-04-08 18:00:03平安夜徽章
日期:2015-12-26 00:06:30程序设计版块每日发帖之星
日期:2015-12-03 06:20:002015七夕节徽章
日期:2015-08-21 11:06:17IT运维版块每日发帖之星
日期:2015-08-09 06:20:002015亚冠之吉达阿赫利
日期:2015-07-03 08:39:422015亚冠之西悉尼流浪者
日期:2015-05-15 10:16:372015年亚洲杯之阿曼
日期:2015-04-09 16:23:11
发表于 2011-05-05 15:57 |显示全部楼层
如果se->vruntime比先前计算的差值更大,则将其作为进程的vruntime,这会导致该进程在红黑树中处于比较靠左的位置
应该是更小吧,我感觉书说错了。


place_entity这个函数主要在下面三个地方调用
   1    756  kernel/sched_fair.c <<enqueue_entity>>
             place_entity(cfs_rq, se, 0);
   2   1931  kernel/sched_fair.c <<task_new_fair>>
             place_entity(cfs_rq, se, 1);
   3   2002  kernel/sched_fair.c <<moved_group_fair>>
             place_entity(cfs_rq, &p->se, 1);

是不是说明这个函数在插入一个entity的时候给定vruntime总是给比较低的优先级的,不然减一下成了负数了就不好了,那么就不能正确判断了。
当然这个是次要的,数据结构可以自己设计。
我认为可能是因为当要插入一个进程的时候,不能比vruntime比cfs->min_vruntime小,不然一插入不就必须要运行了?


u64 min_vruntime;

static inline s64 entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
        return se->vruntime - cfs_rq->min_vruntime;
}

论坛徽章:
0
发表于 2011-05-05 17:11 |显示全部楼层
本帖最后由 liu090 于 2011-05-05 18:51 编辑

非常感谢回复
我看了这个帖子 :
http://blog.csdn.net/dog250/archive/2010/02/10/5302856.aspx
他提到了防止vrun time 倒流

1。 vruntime = max_vruntime(se->vruntime, vruntime); //保证虚拟时钟不会倒流

2。 然后书注释部分中也提到过  :对与短时间休眠有所不同
3。 加上你的意思是 :“max_vruntime,取出大的,会导致该进程在红黑树中处于比较靠右的位置”

那么意思就是sleep 较短的情况的,还是按原来的情况vruntime 来插入rb tree,
其他如果sleep 很长的情况, 醒来后,cfs_rq->min_vruntime - sysctl_sched_latency, 减小vruntime,进行 奖励
不知道可否这样理解

论坛徽章:
20
丑牛
日期:2014-08-15 14:32:002017金鸡报晓
日期:2017-02-08 10:39:42黑曼巴
日期:2016-11-15 15:48:38CU十四周年纪念徽章
日期:2016-11-09 13:19:1015-16赛季CBA联赛之同曦
日期:2016-04-08 18:00:03平安夜徽章
日期:2015-12-26 00:06:30程序设计版块每日发帖之星
日期:2015-12-03 06:20:002015七夕节徽章
日期:2015-08-21 11:06:17IT运维版块每日发帖之星
日期:2015-08-09 06:20:002015亚冠之吉达阿赫利
日期:2015-07-03 08:39:422015亚冠之西悉尼流浪者
日期:2015-05-15 10:16:372015年亚洲杯之阿曼
日期:2015-04-09 16:23:11
发表于 2011-05-05 20:51 |显示全部楼层
回复 5# liu090

我认为,


vruntime = max_vruntime(se->vruntime, vruntime);   

这个vruntime(就是se->vruntime)就应该是 cfs_rq->min_vruntime 和 se->vruntime 的较大值。
因为一个vruntime有着较小值排在红黑树前面,而cfs_rq->min_vruntime是红黑树内最小的vruntime值(该值仅在下面的函数内更新)。
如果一个函数睡眠太久,醒来的时候也应该把它的vruntime提到cfs_rq->min_vruntime.
第一,因为这个vruntime是u64类型的,就是无符号的(这样的好处是可以让vruntime的上限又增大了两倍)。如果不提到这个值相减的结果不是一个负数,而是一个很大的正整数,这样就会导致插入红黑树的比较出错。
第二,如果没有取用这个较大值,而是降低了cfs_rq->vruntime,那么这个vruntime就不是单调递增的了,这样不太好吧。

一孔之见,如有不对,请不吝指教!
  1. static void update_min_vruntime(struct cfs_rq *cfs_rq)
  2. {
  3.         u64 vruntime = cfs_rq->min_vruntime;

  4.         if (cfs_rq->curr)
  5.                 vruntime = cfs_rq->curr->vruntime;

  6.         if (cfs_rq->rb_leftmost) {
  7.                 struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
  8.                                                    struct sched_entity,
  9.                                                    run_node);

  10.                 if (!cfs_rq->curr)
  11.                         vruntime = se->vruntime;
  12.                 else
  13.                         vruntime = min_vruntime(vruntime, se->vruntime);
  14.         }

  15.         cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
  16. }
复制代码

论坛徽章:
0
发表于 2012-01-25 23:27 |显示全部楼层
最近看书看到这里,很难理解,为什么减去了sysctl_sched_latency之后会使得进程在当前延迟周期结束后才会被调用呢?既然vruntime减小的话应该被提前调用才对啊。。。。那句“vruntime越大越早被调度”更费解。。。

论坛徽章:
0
发表于 2012-12-25 12:19 |显示全部楼层
所以俗话说的好:尽信书则不如无书。所以:
1、se->vruntime越大越靠右;
2、睡眠后醒来的进程会有个奖赏,所以减去sysctl_sched_latency,但是最终的vruntime不会低于原值;也就是队列的min_vruntime和se->vrumtime都是保持递增的。
3、使得进程在当前延迟周期结束后才会被调用,这个应该是新建立进程的情况,即参数initial!=0的时候,见place_entity():
if (initial && sched_feat(START_DEBIT))
                vruntime += sched_vslice_add(cfs_rq, se);
这样使新加入进程放在红黑树的最右侧,从而产生的权重对当前周期内进程的调度不会有影响(下周期生效)。

论坛徽章:
0
发表于 2017-07-01 21:16 |显示全部楼层
是作者写错了。3.18.31版本内核代码,针对这一行已经有了注释。。。就是保证sched_entity->vruntime不要倒流,可以奖励,但是不能比之前少。。。

static void
place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
    u64 vruntime = cfs_rq->min_vruntime;

    /*   
     * The 'current' period is already promised to the current tasks,
     * however the extra weight of the new task will slow them down a
     * little, place the new task so that it fits in the slot that
     * stays open at the end.
     */
    if (initial && sched_feat(START_DEBIT))
        vruntime += sched_vslice(cfs_rq, se);

    /* sleeps up to a single latency don't count. */
    if (!initial) {
        unsigned long thresh = sysctl_sched_latency;

        /*   
         * Halve their sleep time's effect, to allow
         * for a gentler effect of sleepers:
         */
        if (sched_feat(GENTLE_FAIR_SLEEPERS))
            thresh >>= 1;

        vruntime -= thresh;
    }

    /* ensure we never gain time by being placed backwards. */
    se->vruntime = max_vruntime(se->vruntime, vruntime);
}

论坛徽章:
0
发表于 2017-07-01 21:18 |显示全部楼层
是作者写错了。3.18.31版本内核代码,针对这一行已经有了注释。。。就是保证sched_entity->vruntime不要倒流,可以奖励,但是不能比之前少。。。

static void
place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
    u64 vruntime = cfs_rq->min_vruntime;

    /*   
     * The 'current' period is already promised to the current tasks,
     * however the extra weight of the new task will slow them down a
     * little, place the new task so that it fits in the slot that
     * stays open at the end.
     */
    if (initial && sched_feat(START_DEBIT))
        vruntime += sched_vslice(cfs_rq, se);

    /* sleeps up to a single latency don't count. */
    if (!initial) {
        unsigned long thresh = sysctl_sched_latency;

        /*   
         * Halve their sleep time's effect, to allow
         * for a gentler effect of sleepers:
         */
        if (sched_feat(GENTLE_FAIR_SLEEPERS))
            thresh >>= 1;

        vruntime -= thresh;
    }

    /* ensure we never gain time by being placed backwards. */
    se->vruntime = max_vruntime(se->vruntime, vruntime);
}

您需要登录后才可以回帖 登录 | 注册

本版积分规则

10张SACC2017门票等你来拿~

在数字化转型时代,云已成为万物智能的数字化大脑。而随着大数据应用、人工智能、移动互联网等技术的飞速发展,“智慧 +” 的概念正在深入到各行各业,提升企业效率,释放商业潜能,创造全新机遇。作为国内顶级技术盛会之一,2017 中国系统架构师大会(SACC2017)将于 10 月 19-21 日在北京新云南皇冠假日酒店震撼来袭。今年,大会以 “云智未来” 为主题,云集国内外顶级专家,围绕云计算、人工智能、大数据、移动互联网、产业应用等热点领域展开技术探讨与交流。本届大会共设置 2 大主会场,18 个技术专场;邀请来自互联网、金融、制造业、电商等多个领域,100 余位技术专家及行业领袖来分享他们的经验;并将吸引 4000 + 人次的系统运维、架构师及 IT 决策人士参会,为他们提供最具价值的交流平台。
----------------------------------------
优惠时间:2017年10月19日前

活动链接>>
  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号 北京市公安局海淀分局网监中心备案编号:11010802020122
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP