读 深入Linux内核架构 2.6.3 节的问题

Question

关于下面这段话：
由于内核已经承诺在当前的延迟周期内使所有活动进程都至少运行一次，队列的min_vruntime用作基准虚拟时间，通过减去sysctl_sched_latency，则可以确保新唤醒的进程只有在当前延迟周期结束后才能运行。

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

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

这个如何理解
请教
谢谢

Answer 1

本帖最后由 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;
12.         /*
13.          * Find the right place in the rbtree:
14.          */
15.         while (*link) {
16.                 parent = *link;
17.                 entry = rb_entry(parent, struct sched_entity, run_node);
18.                 /*
19.                  * We dont care about collisions. Nodes with
20.                  * the same key stay together.
21.                  */                if (key < entity_key(cfs_rq, entry)) {
22.                         link = &parent->rb_left;
23.                 } else {
24.                         link = &parent->rb_right;
25.                         leftmost = 0;
26.                 }
27.         }
29.         /*
30.          * Maintain a cache of leftmost tree entries (it is frequently
31.          * used):
32.          */
33.         if (leftmost)
34.                 cfs_rq->rb_leftmost = &se->run_node;
36.         rb_link_node(&se->run_node, parent, link);
37.         rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
38. }

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

Answer 2

本帖最后由 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  的解释,如何理解呢？
取大的值不是更慢被调度了？

Answer 3

如果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;
}

Answer 4

本帖最后由 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，进行 奖励
不知道可否这样理解

Answer 5

回复 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;
5.         if (cfs_rq->curr)
6.                 vruntime = cfs_rq->curr->vruntime;
8.         if (cfs_rq->rb_leftmost) {
9.                 struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
10.                                                    struct sched_entity,
11.                                                    run_node);
13.                 if (!cfs_rq->curr)
14.                         vruntime = se->vruntime;
15.                 else
16.                         vruntime = min_vruntime(vruntime, se->vruntime);
17.         }
19.         cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
20. }

复制代码

Answer 6

最近看书看到这里，很难理解，为什么减去了sysctl_sched_latency之后会使得进程在当前延迟周期结束后才会被调用呢？既然vruntime减小的话应该被提前调用才对啊。。。。那句“vruntime越大越早被调度”更费解。。。

Answer 7

所以俗话说的好：尽信书则不如无书。所以：
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);
这样使新加入进程放在红黑树的最右侧，从而产生的权重对当前周期内进程的调度不会有影响(下周期生效)。

Answer 8

是作者写错了。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);
}

Answer 9

是作者写错了。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);
}