Linux进程管理之CFS调度器分析

本文主要是介绍Linux进程管理之CFS调度器分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

转载出处:http://ericxiao.cublog.cn/
------------------------------------------
一:前言
CFS调度在2.6.23版本的kernel中被加入.引用Ingo Molnar的一句话:80%的设计可以用一句话来概括:CFS中一个”理想的多任务处理器”.也从该版本开始,linux的调度部份采用模块化设计.我们在接下来的分析中,分为几个重要的状态进行分析.本文的代码分析基于2.6.28的kernel.分析代码基本位于linux-2.6.28- rc7/kernel/sched.c和linux-2.6.28-rc7/kernel/sched_fair.c位置.
二:CFS分析
在上面说过,linux调度代码采用了模块化设计,什么叫模块化?简而言之,就是以后如果要更改调度器,不需要更改调度执行部份的代码,只需要填充对应几个函数即可.下面分为几个状态进行分析.
2.1: tick中断
在tick中断处理函数中,会调用scheduler_tick()函数.该函数代码如下:
void scheduler_tick(void)
{
/*取得当前CPU*/
int cpu = smp_processor_id();
/*取得当前CPU对应的runqueue*/
    struct rq *rq = cpu_rq(cpu);
/*当前运行的进程*/
    struct task_struct *curr = rq->curr;

    sched_clock_tick();

    spin_lock(&rq->lock);
    /*更新rq的当前时间戳.即使rq->clock变为当前时间戳*/
    update_rq_clock(rq);
    /*更新rq的负载*/
    update_cpu_load(rq);
    /*调用调度模块的task_tick函数*/
    curr->sched_class->task_tick(rq, curr, 0);
    spin_unlock(&rq->lock);

#ifdef CONFIG_SMP
    rq->idle_at_tick = idle_cpu(cpu);
    trigger_load_balance(rq, cpu);
#endif
}
我们从上面的代码中可以看到,经过一部份共同处理之后,流程会转入调度模块的task_tick()函数.
对应CFS,它的sched_class结构如下:
static const struct sched_class fair_sched_class = {
    .next           = &idle_sched_class,
    .enqueue_task       = enqueue_task_fair,
    .dequeue_task       = dequeue_task_fair,
    .yield_task     = yield_task_fair,

    .check_preempt_curr = check_preempt_wakeup,

    .pick_next_task     = pick_next_task_fair,
    .put_prev_task      = put_prev_task_fair,

#ifdef CONFIG_SMP
    .select_task_rq     = select_task_rq_fair,

    .load_balance       = load_balance_fair,
    .move_one_task      = move_one_task_fair,
#endif

    .set_curr_task          = set_curr_task_fair,
    .task_tick      = task_tick_fair,
    .task_new       = task_new_fair,

    .prio_changed       = prio_changed_fair,
    .switched_to        = switched_to_fair,

#ifdef CONFIG_FAIR_GROUP_SCHED
    .moved_group        = moved_group_fair,
#endif
};
即对应task_tick的处理函数为task_tick_fair().代码如下:

static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
{
    struct cfs_rq *cfs_rq;
    struct sched_entity *se = &curr->se;

    /*在没有配置CONFIG_FAIR_GROUP_SCHED时,for_eachsched_entity(se)为
*for (; se; se = NULL)
*/
    for_each_sched_entity(se) {
        /*se所对应的cfs_rq*/
        cfs_rq = cfs_rq_of(se);
        entity_tick(cfs_rq, se, queued);
    }
}
需要说明的是,在本文中不会对组调度代码做分析,在后续的章节再来分析这个部份.
在这个函数中,我们涉及到了两个陌生的数据结构,一个是struct sched_entity,我们可以将其理解为调度实体,表示每个可以调度的对象(一般指task).另外一个是struct cfs_rq.对于rq我们很熟悉了.在这里可以理解CFS的rq.
Entity_tick()代码如下:
static void
entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
{
    /*
     * Update run-time statistics of the 'current'.
     */
     /*更新cfs_rq与当前进程的有关信息*/
    update_curr(cfs_rq);

#ifdef CONFIG_SCHED_HRTICK
    /*
     * queued ticks are scheduled to match the slice, so don't bother
     * validating it and just reschedule.
     */
    if (queued) {
        resched_task(rq_of(cfs_rq)->curr);
        return;
    }
    /*
     * don't let the period tick interfere with the hrtick preemption
     */
    if (!sched_feat(DOUBLE_TICK) &&
            hrtimer_active(&rq_of(cfs_rq)->hrtick_timer))
        return;
#endif

    /*检查是否要切换出当前进程*/
    if (cfs_rq->nr_running > 1 || !sched_feat(WAKEUP_PREEMPT))
        check_preempt_tick(cfs_rq, curr);
}
首先,调用update_curr()来更新cfs_rq和当前运行进程的信息,然后再调用check_preempt_tick()来判断是否需要抢占当前进程.

update_curr()代码如下:
static void update_curr(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->curr;
    /*rq_of()用来将cfs_rq转换成它所在的rq*/
    u64 now = rq_of(cfs_rq)->clock;
    unsigned long delta_exec;

    if (unlikely(!curr))
        return;

    /*
     * Get the amount of time the current task was running
     * since the last time we changed load (this cannot
     * overflow on 32 bits):
     */
     /*自从上次tick中断以来,当前进程运行的时间*/
    delta_exec = (unsigned long)(now - curr->exec_start);

    __update_curr(cfs_rq, curr, delta_exec);
    /*更新当前进程的执行时间戳*/
    curr->exec_start = now;

    if (entity_is_task(curr)) {
        struct task_struct *curtask = task_of(curr);

        cpuacct_charge(curtask, delta_exec);
        account_group_exec_runtime(curtask, delta_exec);
    }
}
curr->exec_start表示上次tick中断时设置的时间戳,而rq->clock表示本次tick发生时的时间戳.二者相减,即为该进程自从上次tick以后的执行时间.从上面的代码中可以看到,流程转入到 __update_curr().代码如下:
static inline void
__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
          unsigned long delta_exec)
{
    unsigned long delta_exec_weighted;

    /*schedstat_xxx函数都是在CONFIG_SCHEDSTATS条件下才有用,它用来统计进程执行的
     *相关信息
     */
    schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));

    /*curr->sum_exec_runtime:总共的执行时间*/
    curr->sum_exec_runtime += delta_exec;
    schedstat_add(cfs_rq, exec_clock, delta_exec);
    /*根据进程的nice中对delta_exec进行修正.nice越高.计算出来的delta_exec_weighted会越小*/
    delta_exec_weighted = calc_delta_fair(delta_exec, curr);
    /*curr->vruntime:进程的执行时间.在rb_tree中根据此值进行排列*/
    curr->vruntime += delta_exec_weighted;
    /*更新cfs_rq->min_vruntime,它近似等于rb_tree中最左侧节点的vruntime.
*实际情况是要比它稍微大一点.
*/
    update_min_vruntime(cfs_rq);
}
在这里涉及到了se->vruntime,简单的讲,它就是进程的执行时间,在调度的时候,它先选择执行时间短的进程进行调度.在后面我们会看到,所有的se都是存在rb_tree中的.键值为se->vruntime.也就是说,se->vruntime越高,就越靠近rb_tree的右边,而vruntime小的se都会位于左边.所以,在调度的时候,只需要取 rb_tree中最左的叶子结点即可.

我们先来看一下calc_delta_fair(),代码如下:
static inline unsigned long
calc_delta_fair(unsigned long delta, struct sched_entity *se)
{
    /*NICE_0_LOAD: 优先级0 的weight*/
    /* 如果不是优先级0,就要调用calc_delta_mine计算delta的weight值*/
    if (unlikely(se->load.weight != NICE_0_LOAD))
        delta = calc_delta_mine(delta, NICE_0_LOAD, &se->load);

    return delta;
}
该函数很简单,NICE_O_LOAD表示为优先级0的weight值,这样处理是因为,进程默认的优先级为0.所以在大部份情况,这个if都不会满足.
在这里不打算详细分析calc_delta_mine (delta_exec,weight,lw),它的执行过程约为delta *= weight / lw.
从这个函数中可以看到,如果进程的优先级为0,那么就是返回delta.如果不为0,就会调用calc_delta_mine()对delta值进行修正.对上面对calc_delta_mine()的说明来看,有如下关系:
Delta = delta* NICE_0_LOAD/ se->load
Se->load值是怎么来的呢? 可以跟踪sys_nice(),就可以发现se->load其它就是表示nice对应的load值,nice越低,值越大.
据此,就可以得到一个结论.在执行相同时间的条件下(delta相同),高优先的进程计算出来的delta值会比低优先级的进程计算出来的低.应此,高优先的进程就会位于rb_tree的左边,在下次调度的时候就会优先调度.

另外,在这里就不详细跟踪update_min_vruntime()了,在上面的注释中,有对cfs_rq->min_vruntime的描述.在后面遇到它的时候再来分析它的作用.

到这里为止,我们已经分析完了update_curr()部份.返回到entity_tick()函数中,来分析下一个函数,即check_preempt_tick().代码如下:
static void
check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    unsigned long ideal_runtime, delta_exec;

    /*ideal_runtime: 应当要运行的时间*/
    ideal_runtime = sched_slice(cfs_rq, curr);

    /*delta_exec: 进程运行的时间*/
    /*sum_exec_runtime: 进程执行的总时间*/
    /*prev_sum_exec_runtime:进程在切换进CPU时的sum_exec_runtime值*/
    delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
    /*如果进程占用CPU时间超过了ideal_runtime.应该要调度进程了*/
    if (delta_exec > ideal_runtime)
        resched_task(rq_of(cfs_rq)->curr);
}
对照代码中的注释,很好理解.delta_exec是在当前环境下进程允许执行的时间片大小,如果进程执行时间片超过了此值,就会调用resched_task()设置该进程的抢占位置,那么在tick中断返回用户空间的时候,就会调用schedule()来完成调度过程.
这个函数的难点是,ideal_runtime的计算由来,该值是由sched_slice()计算而来,代码如下:
static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    unsigned long nr_running = cfs_rq->nr_running;

    if (unlikely(!se->on_rq))
        nr_running++;

    return calc_delta_weight(__sched_period(nr_running), se);
}
Nr_running是cfs_rq中运行进程数目.__sched_peiod()用来计算nr_running个进程调度一次的时间周期.它的代码如下:
static u64 __sched_period(unsigned long nr_running)
{
    u64 period = sysctl_sched_latency;
    unsigned long nr_latency = sched_nr_latency;

    if (unlikely(nr_running > nr_latency)) {
        period = sysctl_sched_min_granularity;
        period *= nr_running;
    }

    return period;
}
从代码可看出,在nr_running小于nr_latency(5)的情况,它的值为sysctl_sched_latency(20ms).否则为nr_running* sysctl_sched_min_granularity(4ms).

返回到sched_slice()中,__sched_period()已经算出了nr_running个进程总的执行时间,那么当前进程又允许占用多长时间呢?
就这由calc_delta_weight()来计算了.代码如下:
static inline unsigned long
calc_delta_weight(unsigned long delta, struct sched_entity *se)
{
    for_each_sched_entity(se) {
        /*根据cpu负载和nice计算所占的delta比重*/
        delta = calc_delta_mine(delta,
                se->load.weight, &cfs_rq_of(se)->load);
    }

    return delta;
}
结合上面的分析: se->load表示进程nice对应的weight,cfs_rq->load表示该cfs_rq的负载,进程入列时,此值增加,进程出列时,此值减小.
再根据上面对calc_delta_mine()的描述,有如下关系:
Delta = delta* se->load.weight / cfs_rq->load
也就是说,系统负载越高,delta越小,nice越小,delta越高.
因此,就允许优先级的进程执行的时间片要长.系统负载越低,进程允许执行的时间片越长.
到这里,tick中断的处理就分析完了.

2.2: schedule()的执行过程
当进程需要被抢占或者是进程主运让出处理器,则会调用schedule()函数.为了减小篇幅,在这里就不分析schedule()函数代码.只列出在该函数中调用模块的主要函数.如下示:
Schedule()---->
sched_class->put_prev_task(rq,prev)---->
sched_class->pick_next_task()

对应到CFS中,put_prev_task()函数为put_prev_task_fair(),该操作就是将进程放回队列.代码如下示:
static void put_prev_task_fair(struct rq *rq, struct task_struct *prev)
{
    struct sched_entity *se = &prev->se;
    struct cfs_rq *cfs_rq;

    for_each_sched_entity(se) {
        cfs_rq = cfs_rq_of(se);
        put_prev_entity(cfs_rq, se);
    }
}
流程转入到put_prev_entity()中,它的代码如下:
static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
{
    /*
     * If still on the runqueue then deactivate_task()
     * was not called and update_curr() has to be done:
     */
     /*如果prev在runqueue中.更新它的相关信息*/
    if (prev->on_rq)
        update_curr(cfs_rq);

    /*DEBUG用*/
    check_spread(cfs_rq, prev);
    if (prev->on_rq) {
        /*更新prev的wait_start*/
        update_stats_wait_start(cfs_rq, prev);
        /* Put 'current' back into the tree. */
        /*将prev放回rb_tree*/
        __enqueue_entity(cfs_rq, prev);
    }
    /*将cfs_rq->curr置空.因为它已经放入了rb_tree中*/
    cfs_rq->curr = NULL;
}
在这里需要注意的是,只是进程在cfs_rq中,也就是prev->on_rq为1的时候,才需要将进程入列,这是因为在进程主动调用schedule()的时候,会调用deactivate_task()将task移出队列.
上面函数中的update_curr()在前面已经分析过了,我们重点来分析一下__enqueue_entity().代码如下:
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    /*cfs_rq的rb_tree*/
    struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
    struct rb_node *parent = NULL;
    struct sched_entity *entry;
    /*排序的key. 为se->vruntime - cfs_rq->min_vruntime*/
    s64 key = entity_key(cfs_rq, se);
    int leftmost = 1;

    /*
     * Find the right place in the rbtree:
     */
     /*将se 以key为键值存放到rb_tree中*/
    while (*link) {
        parent = *link;
        entry = rb_entry(parent, struct sched_entity, run_node);
        /*
         * We dont care about collisions. Nodes with
         * the same key stay together.
         */
         /*如果key要小于当前节点,往左移*/
        if (key < entity_key(cfs_rq, entry)) {
            link = &parent->rb_left;
        }
        /*否则往右移.se已经往右移动了,不可能位于最左边了,因此将leftmost置0*/
        else {
            link = &parent->rb_right;
            leftmost = 0;
        }
    }

    /*
     * Maintain a cache of leftmost tree entries (it is frequently
     * used):
     */
     /*如果新加入的结点位于最左端,更新cfs_rq->rb_leftmost
     *cfs_rq->rb_leftmost起优先作用,这样调度器在找最小key值结点的时候就不用
     *遍历整个rb_tree了.只需直接取cfs_rq->rb_leftmost就可以了
     */
    if (leftmost)
        cfs_rq->rb_leftmost = &se->run_node;

    /*插入红黑树.设置结点颜色*/
    rb_link_node(&se->run_node, parent, link);
    rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
}
这段代码就是将se存入rb_tree,结合上面的注释,应该不难理解这段代码,因此在这里就不详细分析了.
在上面的代码中,我们可以看到,rb_tree的key为se->vruntime- cfs_rq->min_vruntime.这里se->vruntime本身就表示进程的执行”时间”,为什么不直接采用 se->vruntime做为key呢? 莫非是为了防止s64数据溢出么?

到这里,CFS的put_prev_task()操作就完成了.接下来分析schedule()的另外一个操作,即pick_next_task()操作,该操作是用来选择下一个被调度的进程.代码如下:

static struct task_struct *pick_next_task_fair(struct rq *rq)
{
    struct task_struct *p;
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct sched_entity *se;

    /*如果cfs_rq中已经没有要调度的进程了*/
    if (unlikely(!cfs_rq->nr_running))
        return NULL;

    do {
        /*选择出下一个要调度的进程*/
        se = pick_next_entity(cfs_rq);
        /*设置选择了的进程的相关信息*/
        set_next_entity(cfs_rq, se);
        cfs_rq = group_cfs_rq(se);
    } while (cfs_rq);

    p = task_of(se);
    hrtick_start_fair(rq, p);

    return p;
}
在没有配置组调度选项(CONFIG_FAIR_GROUP_SCHED)的情况下.group_cfs_rq()返回NULL.因此,上函数中的循环只会循环一次.
该函数中有两个重要的子函数,一个是pick_next_entity().另一个是set_next_entity().先来分析pick_next_entity().代码如下:
static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
{
    /*选择RB_TREE中最左端的结点*/
    struct sched_entity *se = __pick_next_entity(cfs_rq);

    /*因为cfs_rq->next有可能不在RB_tree中,因此,要判断从rb_tree中取出的结点是否能
    *满足调度的条件
    */

    /*判断是否会被cfs_rq->next抢占*/
    if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, se) < 1)
        return cfs_rq->next;
    /*判断是否会被cfs_rq->last抢占*/
    if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, se) < 1)
        return cfs_rq->last;

    return se;
}
在这里出现了cfs_rq->next和cfs_rq->last,它们指的又是什么?为什么这里要优先调度它们两个呢?在稍后的分析中遇到它们的时候再来分析.

那到底怎样判断选择出的se与cfs_rq->next和cfs_rq->last的调度优先顺序呢?来跟踪wakeup_preempt_entity()的代码.如下示:
/*
* Should 'se' preempt 'curr'.
*
*             |s1
*        |s2
*   |s3
*         g
*      |<--->|c
*
* w(c, s1) = -1
* w(c, s2) = 0
* w(c, s3) = 1
*
*/
/*如果小于1,则se不可抢占curr*/
static int
wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
{
    s64 gran, vdiff = curr->vruntime - se->vruntime;

    /*如果se->vruntime 大于/等于curr->vruntime.不可抢占*/
    if (vdiff <= 0)
        return -1;

    /*运行到这里,属于se->vruntime小于curr->vruntime的情况*/

    /*如果超过了它的调度粒度.se可以抢占curr*/
    gran = wakeup_gran(curr);
    if (vdiff > gran)
        return 1;
    /*如果小于调度粒度,不可抢占*/
    return 0;
}
这个函数有点不太好理解,注释看得云里雾里.在这里要特别感谢Miao Xie <miaox@cn.fujitsu.com>的指点,引用他的原话吧:
“这个注释的意思如下：
横坐标是vruntime值，向右逐渐增大。c = current.g = c的最小调度颗粒，也就是理论上最短占有CPU的时间. s1与c比较vruntime，发现s1的vruntime比c大或者相等，根据cfs调度器的原理，s1自然不能抢占c，所以返回-1;s2与c比较 vruntime，发现s2的vruntime比c小，但是这个时候必须要考虑最小调度颗粒的问题，避免频繁调度，浪费CPU时间。这个可能比较难理解。打个比方：一个机器触发调度的点很多，也就是说可能在很短时间内很频繁的检查当前进程需不需要被切换，假如 10ns检查一次，而s2与c的vruntime相差很小，每次检查时就发现c的vruntime刚好超过s2的vruntime，如果不考虑最小调度颗粒的问题，s2 就要抢占 c 的CPU。可是10 ns之后 s2的vruntime刚好超过c的 vruntime，于是又进行一次切换。如此，s2和c就在不停的互相切换，浪费CPU时间。这种情况就必须考虑最小调度颗粒，让 wake_up_preempt_entity()返回0.s3与c比较vruntime，发现s3的vruntime比c小，而且幅度超过c的最小调度颗粒，说明c已经运行足够长的时间了，可以进行切换，返回1”
Miao Xie老师的指点说的已经够详细了,在这里就不再做过多的解释了.

回到pick_next_task_fair()中,来看下一个子函数,即set_next_entity().代码如下:
static void
set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    /*如果se已经在运行队列中,将其出列*/
    /* 'current' is not kept within the tree. */
    if (se->on_rq) {
        /*
         * Any task has to be enqueued before it get to execute on
         * a CPU. So account for the time it spent waiting on the
         * runqueue.
         */
         /*选择编译函数*/
        update_stats_wait_end(cfs_rq, se);
        /*将se从rb_tree中移出*/
        __dequeue_entity(cfs_rq, se);
    }
    /*更新se的开始执行时间.即se->exec_start*/
    update_stats_curr_start(cfs_rq, se);
    /*更新cfs_rq->curr,即cfs_rq上当前执行的的进程为se所表示的进程*/
    cfs_rq->curr = se;
#ifdef CONFIG_SCHEDSTATS
    /*
     * Track our maximum slice length, if the CPU's load is at
     * least twice that of our own weight (i.e. dont track it
     * when there are only lesser-weight tasks around):
     */
    if (rq_of(cfs_rq)->load.weight >= 2*se->load.weight) {
        se->slice_max = max(se->slice_max,
            se->sum_exec_runtime - se->prev_sum_exec_runtime);
    }
#endif
    /*更新se->prev_sum_exec_runtime为进程切换进CPU的sum_exec_runtime*/
    se->prev_sum_exec_runtime = se->sum_exec_runtime;
}
现在已经找到要调度的se了,如果该se还处于运行队列中,那么将其移出rb_tree,在这里我们可以看到: 当前运行的se是不在rb_tre,在这里要特别注意的是,虽然se被移出了rb_tree,但se->on_rq仍然为1,表示可调度的.并且更新cfs_rq上当前执行的进程指向,然后,再更新se->prev_sum_exec_runtime.它表示进程被切换上CPU时的进程执行总时间,在每个tick中,就会更新se->sum_exec_runtime,即总的执行时间.因此se->sum- exec_runtime - se->prev_sum_exec_runtime就计算出了,进程运行的时间片,可以参考前面对check_preempt_tick()函数的分析.
到这里为止,schedule()的执行过程已经分析完了.

2.3:新进程的调度过程
在创建新进程的时候,在do_fork()中有如下过程:
long do_fork(unsigned long clone_flags,
          unsigned long stack_start,
          struct pt_regs *regs,
          unsigned long stack_size,
          int __user *parent_tidptr,
          int __user *child_tidptr)
{
    ．．．．．．
    ．．．．．．
if (unlikely(clone_flags & CLONE_STOPPED)) {
            /*
             * We'll start up with an immediate SIGSTOP.
             */
            sigaddset(&p->pending.signal, SIGSTOP);
            set_tsk_thread_flag(p, TIF_SIGPENDING);
            __set_task_state(p, TASK_STOPPED);
        } else {
            wake_up_new_task(p, clone_flags);
        }
    ．．．．．．
    ．．．．．．
｝
即在末带CLONE_STOPPED标志创建进程时,就会对新进程调用wake_up_new_task().代码如下:
void wake_up_new_task(struct task_struct *p, unsigned long clone_flags)
{
    unsigned long flags;
    struct rq *rq;

    /*进程所在的rq.并加锁*/
    rq = task_rq_lock(p, &flags);
    /*如果进程不为TASK_RUNNING状态,BUG*/
    BUG_ON(p->state != TASK_RUNNING);
    /*更新rq->clock*/
    update_rq_clock(rq);

    /*计算有效优先级,如果为一般进程,就是其static_prio*/
    p->prio = effective_prio(p);

    /*如果调度器没有task_new操作.或者当前进程已经被移出运行队列了*/
    if (!p->sched_class->task_new || !current->se.on_rq) {
        activate_task(rq, p, 0);
    } else {
        /*
         * Let the scheduling class do new task startup
         * management (if any):
         */
        p->sched_class->task_new(rq, p);
        inc_nr_running(rq);
    }
    trace_sched_wakeup_new(rq, p);
    /*检查其是否可以抢点当前进程.如果是,设置抢占标志*/
    check_preempt_curr(rq, p, 0);
#ifdef CONFIG_SMP
    if (p->sched_class->task_wake_up)
        p->sched_class->task_wake_up(rq, p);
#endif
    /*unlock rq*/
    task_rq_unlock(rq, &flags);
}
这个函数比较简单,如果被新进程所属调度器的task_new()为空或者当前进程已经被移出运行队了,就直接调用activate_task()将新进程放入运行队列.否则调用调度器的task_new()函数.或许有人觉得对 current->se.on_rq判断有点迷糊,current不是正在运行的进程么?怎么会不在运行队列中呢?很简单,有一种情况,SMP中, 一上CPU对另一个CPU上运行进程执行了dequeue_task()的操作.
Activate_task()代码很简单,这里就不详细分析了,我们接下来看一下CFS的task_new操作,它的对应接口为: task_new_fair().代码如下:
static void task_new_fair(struct rq *rq, struct task_struct *p)
{
    struct cfs_rq *cfs_rq = task_cfs_rq(p);
    struct sched_entity *se = &p->se, *curr = cfs_rq->curr;
    int this_cpu = smp_processor_id();

    /*选择编译函数*/
    sched_info_queued(p);
    /*更新cfs_rq的信息*/
    update_curr(cfs_rq);
    /*对se(即新进程)的的vruntime进行调整*/
    place_entity(cfs_rq, se, 1);

    /* 'curr' will be NULL if the child belongs to a different group */
    /*如果sysctl_sched_child_runs_first即强制子进程先于父进程先运行
    *所以,如果子进程的vruntime大于父进程的vruntime的时候,父互两者的vruntime值
    *并设置强制抢占,这样就要以强制使子进程先于父进程而运行*/
    if (sysctl_sched_child_runs_first && this_cpu == task_cpu(p) &&
            curr && curr->vruntime < se->vruntime) {
        /*
         * Upon rescheduling, sched_class::put_prev_task() will place
         * 'current' within the tree based on its new key value.
         */
        swap(curr->vruntime, se->vruntime);
        resched_task(rq->curr);
    }

    enqueue_task_fair(rq, p, 0);
}
我们首先来看一下,怎样对进程的vruntime进行调整.这是在place_entity()中进行的,代码如下:
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.
     */
     /*sched_vslice():将进程的最大运行时间片转换为vruntime.*/
    if (initial && sched_feat(START_DEBIT))
        vruntime += sched_vslice(cfs_rq, se);

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

            /*
             * convert the sleeper threshold into virtual time
             */
            if (sched_feat(NORMALIZED_SLEEPER))
                thresh = calc_delta_fair(thresh, se);

            vruntime -= thresh;
        }

        /* ensure we never gain time by being placed backwards. */
        /*不能小于se->vruntime,即不能使它的vruntime值变得比现在还要小*/
        vruntime = max_vruntime(se->vruntime, vruntime);
    }

    se->vruntime = vruntime;
}
首先,这个函数有一个initial参数,这是为了区别两种不同情况下的vruntime调整,一种情况是新创建进程的情况,也就是我们在上面所分析的情况,它的initial值为1.另外一种情况是唤醒一个进程时的vruntime调整.为了便于后面对唤醒过程的分析,在这里分析这个函数的时候针对这两种情况做一个讲解.
在第一种情况下,新创建的进程都以cfs_rq->min_vruntime都为一个基础,在其后的一段时间后得到调度.这段时间的大小为sched_vslice(),它其实就是将sched_slice()转换为虚拟运行时间.
在第二种情况下,是调整唤醒进程的vruntime值,这种情况比较复杂.
首先,为什么要对唤醒进程的时间进行调整呢?我们来考虑一个这样的问题:
假设进程A睡眠了较长时间,以后被唤醒,如果没有调整其vruntime值,就会使得其vruntime远小于cfs_rq->min_vruntime.这样的后果就是,在其后相当长的一段时间内,进程A都会独占CPU,造成了其它进程不能及时得到响应.
那怎么调整呢?有以下两个情况:
1):如果进程睡眠的时间很短,也就是se->vruntime仍然大于cfs_rq->min_vruntime.这种情况下,不需要对se->vruntime进程调整.
2):如果进程睡眠时间较长,那当然要对睡眠进程的时间做一个补偿,因此,就将cfs_rq->min_vruntime适当减一个差值做为进程的vruntime值,当然,这种情况下,不能使调整之后的值比之前的vruntime还要小.
结合上面的分析,应该很容易理解这个函数了,接下来,返回到task_new_fair(),来分析它的下一个子函数, enqueue_task_fair().它的代码如下:
static void enqueue_task_fair(struct rq *rq, struct task_struct *p, int wakeup)
{
    struct cfs_rq *cfs_rq;
    struct sched_entity *se = &p->se;

    for_each_sched_entity(se) {
        if (se->on_rq)
            break;
        cfs_rq = cfs_rq_of(se);
        enqueue_entity(cfs_rq, se, wakeup);
        wakeup = 1;
    }

    hrtick_update(rq);
}
现在,新进程的vruntime已经调整好了,是到将它加入到运行队列的时候了,enqueue_task_fair()就是完成这样的工作.
注意这个函数的wakeup参数,它来有标识,是不是在唤醒进程的条件下调用enqueue_task_fair().区分这样的情况,是因为在之后还要调整唤醒进程的vruntime值.
我们在这里的情况是创建的一个新进程,因此在task_new_fair()中调用这个函数的wakeup参数为0.
流程接着转入到了enqueue_entity()中,代码如下:
static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int wakeup)
{
    /*
     * Update run-time statistics of the 'current'.
     */
     /*更新当前信息*/
    update_curr(cfs_rq);
    /*计算cfs_rq的负载和运行进程数目并且将se->on_rq置为1,表示该进程
     *已经处于运行队列中了
     */
    account_entity_enqueue(cfs_rq, se);

    /*如果是因为唤醒而入列,调用place_entity()来调整其vruntime值*/
    if (wakeup) {
        place_entity(cfs_rq, se, 0);
        enqueue_sleeper(cfs_rq, se);
    }

    update_stats_enqueue(cfs_rq, se);
    check_spread(cfs_rq, se);
    /*如果se不是当前运行进程,加其入列.(当前运行的进程是没有在
     *rb_tree中的)
     */
    if (se != cfs_rq->curr)
        __enqueue_entity(cfs_rq, se);
}
这个函数中的几个子函数在前面都已经分析过了,结合注释应该很容易看懂这段代码,在这里不再详细分析了.我们来看一下account_entity_enqueue():
static void
account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    /*增加cfs_rq的负载(load)*/
    update_load_add(&cfs_rq->load, se->load.weight);
    /*增加run queue的负载*/
    if (!parent_entity(se))
        inc_cpu_load(rq_of(cfs_rq), se->load.weight);
    /*涉及到CONFIG_FAIR_GROUP_SCHED*/
    if (entity_is_task(se)) {
        add_cfs_task_weight(cfs_rq, se->load.weight);
        list_add(&se->group_node, &cfs_rq->tasks);
    }
    /*递增运行进程数目*/
    cfs_rq->nr_running++;
    /*置se->on_rq为1*/
    se->on_rq = 1;
}
通过这个函数,我们可以看到cfs_rq->load的改变.一般来说,有进程入列,就会增加cfs_rq->load,即负载加大,有进程出列,就会减小cfs_rq->load,即负载变小.
到这里,新进程的调度过程就分析完了.

返回到wake_up_new_task(),来接着分析下一个重要子函数check_preempt_curr().代码如下:
static inline void check_preempt_curr(struct rq *rq, struct task_struct *p, int sync)
{
    rq->curr->sched_class->check_preempt_curr(rq, p, sync);
}
在CFS中,该操作会指向check_preemt_wakeup():
static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int sync)
{
    struct task_struct *curr = rq->curr;
    struct sched_entity *se = &curr->se, *pse = &p->se;

    /*如果是实时进程*/
    if (unlikely(rt_prio(p->prio))) {
        struct cfs_rq *cfs_rq = task_cfs_rq(curr);

        update_rq_clock(rq);
        update_curr(cfs_rq);
        resched_task(curr);
        return;
    }

    /*如果不属于CFS调度*/
    if (unlikely(p->sched_class != &fair_sched_class))
        return;

    /*要唤醒的进程和当前运行的进程是同一个*/
    if (unlikely(se == pse))
        return;

    /*
     * Only set the backward buddy when the current task is still on the
     * rq. This can happen when a wakeup gets interleaved with schedule on
     * the ->pre_schedule() or idle_balance() point, either of which can
     * drop the rq lock.
     *
     * Also, during early boot the idle thread is in the fair class, for
     * obvious reasons its a bad idea to schedule back to the idle thread.
     */
     /*设置cfs_rq->last*/
    if (sched_feat(LAST_BUDDY) && likely(se->on_rq && curr != rq->idle))
        set_last_buddy(se);
    /*设置cfs_rq->next*/
    set_next_buddy(pse);

    /*
     * We can come here with TIF_NEED_RESCHED already set from new task
     * wake up path.
     */
     /*如果已经设置了抢占标志,返回*/
    if (test_tsk_need_resched(curr))
        return;

    /*
     * Batch tasks do not preempt (their preemption is driven by
     * the tick):
     */
     /*如果是属于SCHED_BATCH 的进程,返回*/
    if (unlikely(p->policy == SCHED_BATCH))
        return;
    /*如果不允许在唤醒时抢占(该值可以使用sysctl配置),返回*/
    if (!sched_feat(WAKEUP_PREEMPT))
        return;

    /*接下来,主要判断唤醒进程能否抢占当前进程*/
    if (sched_feat(WAKEUP_OVERLAP) && (sync ||
            (se->avg_overlap < sysctl_sched_migration_cost &&
             pse->avg_overlap < sysctl_sched_migration_cost))) {
        resched_task(curr);
        return;
    }

    find_matching_se(&se, &pse);

    while (se) {
        BUG_ON(!pse);

        if (wakeup_preempt_entity(se, pse) == 1) {
            resched_task(curr);
            break;
        }

        se = parent_entity(se);
        pse = parent_entity(pse);
    }
}
需要指出的是,在这里,会调用set_last_buddy()和set_next_buddy()来设置 cfs_rq->last和cfs_rq->next.这也就是我们在schedule()过程分析中遇到的,在这里我们可以看到,cfs_rq->last指向当前运行进程,而cfs_rq->next指向要插入的进程.在schedule()调度的时候,会优先让这两个进程运行.check.同样,这个操作在进程的唤醒也存中,见接下来的分析:

2.4:进程的唤醒
我们以try_to_wake_up()为例来分析进程的唤醒过程,代码片段如下:
static int try_to_wake_up(struct task_struct *p, unsigned int state, int sync)
{
    ．．．．．．
    ．．．．．．
    activate_task(rq, p, 1);
    success = 1;

out_running:
    trace_sched_wakeup(rq, p);
    check_preempt_curr(rq, p, sync);

    p->state = TASK_RUNNING;
    ．．．．．．
    ．．．．．．
｝
在这里需要注意一个参数，即sync, 如果sync等于1,则表示唤醒的进程不能够抢占当前CPU上运行的进程.
Activate_task()的代码很简单,它的核心操作是以1为参数调用enqueue_task().即会调用进程的vruntime值并且入列.在这里就不做过多分析.接下来它也会调用check_preempt_curr().这个函数在之前已经分析过了.

2.5:关于cfs_rq->next和cfs_rq->last
搜索2.6.28的源代码,发现只有在进程dequeue_task()的时候才会调用clear_buddies()将cfs_rq->next和cfs_rq->last的指向清空,即变为NULL.
那假设有这样的情况:
从进程A中唤醒进程B,根据之前的分析,就有cfs_rq->last = A.se ,cfs_rq->next = b.se.那只要以后没有操作去更改cfs_rq->last和cfs_rq->next且A,B没有退出,就会一直保持A,B的优先调度. 而实际上在唤醒操作完成之后,这个优先调度的过程是不需要的.这样或多或少会造成性能上的损失.
而在最新的kernel版本2.6.29中,在每次schedule()之后都增添了一个操作:
static struct task_struct *pick_next_task_fair(struct rq *rq)
{
    ．．．．．．
    ．．．．．．
    do {
        se = pick_next_entity(cfs_rq);
        /*
         * If se was a buddy, clear it so that it will have to earn
         * the favour again.
         */
        __clear_buddies(cfs_rq, se);
        set_next_entity(cfs_rq, se);
        cfs_rq = group_cfs_rq(se);
    } while (cfs_rq);
    ．．．．．．
    ．．．．．．．
｝
如上代码片段如示:在每次选择好下个调度进程之后,就会调用__clear_buddies()将这种指向关系清除.这也就避免了上面的这个问题.

三:小结
总的来说,CFS较之前的O(1)简单了很多,没有那么多经验性的公式,CFS的主要思想就是在于虚拟时间的管理.在本节的分析中,忽略了CFS组调度和SMP上的调度.在后续的章节中再给出这两部份的分析.