进程CFS小结

Question

CFS调度 by chishanmingshen
1.tick中断的调度
tick中断处理函数中,会取得当前cpu的rq,从而得到rq的current进程,
调用scheduler_tick()->task_tick_fair()->entity_tick(cfs_rq, se, queued).
entity_tick()中更新cfs_rq,并判断抢占.
1.1先取得current所在的rq中处理对应的se.
1.2更新current所属的cfs_rq
update_curr(cfs_rq)
{
    /*算出current在上次tick中运行的时间:delta_exec,
    记录标准的运行时间,所以加上delta_exec.*/
    curr->sum_exec_runtime += delta_exec;
    /*根据进程的nice对delta_exec进行修正.
    如果是优先级0,则其load为NICE_0_LOAD,其delta不变.
    其它则根据优先级比例处理:delta*=NICE_0_LOAD/se的load,即优先级高的进程虚拟时间变得慢.
    同理,在过了相同的标准时间后,高优先级的会位于rb_tree的更左边.*/
    delta_exec_weighted = calc_delta_fair(delta_exec, curr);
    /*curr->vruntime:进程的虚拟执行时间.在rb_tree中根据此值进行排列*/
    curr->vruntime += delta_exec_weighted;
    /*更新cfs_rq->min_vruntime,即将系统的虚拟时间推进.*/
    update_min_vruntime(cfs_rq);
}
1.3判断抢占情况(如果该rq上有大于1的可运行进程或者没有设置WAKEUP抢占)
    if (cfs_rq->nr_running > 1 || !sched_feat(WAKEUP_PREEMPT))
        check_preempt_tick(cfs_rq, curr);
在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:计算该进程在本轮的理想运行时间,
    即4ms*nr_running的总时间按se_load/cfs_rq->load的比例计算得出(在calc_delta_weight()中).*/
    ideal_runtime = sched_slice(cfs_rq, curr);
   
    /*进程本轮实际执行的时间.*/
    delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
    /*如果进程新增占用时间超过了ideal_runtime,则需要被抢占.
    那么在tick中断返回用户空间的时候,就会调用schedule()来完成调度过程.*/
    if (delta_exec > ideal_runtime)
        resched_task(rq_of(cfs_rq)->curr);
    /*清除cfs_rq的2个优先调度进程*/
    clear_buddies(cfs_rq, curr);
}
可见:
每个进程有一个se,se的load就表示进程nice在一轮总时间中对应的权重.
cfs_rq->load表示该cfs_rq的总负载,当有进程入列时,此值增加.
一个进程的se在本轮分得的虚拟时间 = (根据进程个数算出的总时间片)* se->load.weight/cfs_rq->load.
系统load越高,进程分得的虚拟时间越小,故系统负载越低,进程允许执行的时间片越长.
进程的nice越小,分得的虚拟时间越高,故高优先级的进程执行的时间要长.
可以知道cfs的原理就是各个进程在逐个推进,但造成的效果就是有权重的公平.
更新cfs_rq的min_vruntime,记录树中节点的一个值,注意:此值表示节点标识的时间已经到了,以此做基点,此值单调递增:
cfs_rq->min_vruntime =
max_vruntime(cfs_rq->min_vruntime, min_vruntime(curr->vruntime, leftmost->vruntime))
=================================
2.当前进程在主动释放cpu或被抢占时
此时当前进程会调用schedule()函数,先put_prev_task_fair(),接着pick_next_task_fair().
即线将旧的切换出,再将新的切换进去.

2.1put_prev_task_fair()->put_prev_entity()将当前进程放回树中.
static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
{
    /*还在rq中,比如被抢占*/
    if (prev->on_rq)
        update_curr(cfs_rq);
    /*如果进程还在cfs_rq中,需要将进程重新加入树中,接着调度.
    在进程主动调用schedule()的时候,会调用deactivate_task()将task移出队列,因为是真的不想调度了.*/   
    if (prev->on_rq) {        
        __enqueue_entity(cfs_rq, prev);
    }
    /*将cfs_rq->curr置空,因为没有current了.*/
    cfs_rq->curr = NULL;
}
__enqueue_entity()将一个新se加入到rb_tree中
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    /*key为se->vruntime - cfs_rq->min_vruntime,可见min_vruntime是一个基点.*/
    s64 key = entity_key(cfs_rq, se);
    将key跟树中节点的key做比较,放到适当的位置,同时设置leftmost字段.
    一定要保证cfs_rq->rb_leftmost始终指向最左节点.
    将se插入到rb_tree中.
}
2.2 pick_next_task()选择下一个被调度的进程.
static struct task_struct *pick_next_task_fair(struct rq *rq)
{
    /*如果cfs_rq中已经没有要调度的进程了,则不选.*/
    if (unlikely(!cfs_rq->nr_running))
        return NULL;

    /*选择出下一个要调度的进程,并设置该新进程的相关信息*/
    se = pick_next_entity(cfs_rq);/*2.2.1*/
    set_next_entity(cfs_rq, se);/*2.2.2*/
    清除cfs->last和cfs->next指针为空,防止误用.
    return p;
}
2.2.1 pick_next_entity()从rb_tree中选下个进程
static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
{
    /*选rb_tree中最左节点即可,因为它的虚拟时间最小,需要追赶cfs_rq->min_vruntime了.*/
    struct sched_entity *se = __pick_next_entity(cfs_rq);

    /*因为cfs_rq->next有可能不在RB_tree中,
    因此,要判断从rb_tree中取出的结点是否能满足调度的条件*/
   
    /*cfs_rq->next和cfs_last要优先考虑.*/
    if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, se) < 1)
        return cfs_rq->next;
    if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, se) < 1)
        return cfs_rq->last;

    return se;
}
wakeup_preempt_entity()就是判断抢占,如果diff小于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,则为了避免频繁切换,不一定抢占.*/
    /*1.如果超过了它的调度粒度,则抢占*/
    gran = wakeup_gran(curr);
    if (vdiff > gran)
        return 1;
    /*2.如果小于当前进程的调度粒度,则不可抢占*/
    return 0;
}
2.2.2 将新se从rb_tree中出列,因为运行的se要脱离rb_tree.
static void
set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    /* 'current' is not kept within the tree. */
    if (se->on_rq) {
        __dequeue_entity(cfs_rq, se);
    }
    cfs_rq->curr = se;
    /*更新se->prev_sum_exec_runtime,其在tick中会得到持续更新.
    其在cpu上运行的时间由sum_exec_runtime和prev_sum_exec_runtime的差值得出.*/
    se->prev_sum_exec_runtime = se->sum_exec_runtime;
}
当前运行的se是要移出rb_tree,但仍在cfs_rq中.
==============================================

3.新建进程的调度
do_fork()->wake_up_new_task(p, clone_flags)
wake_up_new_task()中
    3.1 调用task_fork_fair()对新进程的vruntime做调整   
    3.2 activate_task(rq, p, 0)将新进程加入到rb_tree中,并增加该cfs_rq的负载.   
    3.3 check_preempt_curr(rq, p, 0)检查新进程是否可以抢占当前进程.如果是则设置抢占标志.
3.1 新建进程的se的vruntime处理后加入到cfs_rq中.
static void task_fork_fair(struct task_struct *p)
{
    update_curr(cfs_rq);
    /*继承父的虚拟时间*/
    if (curr)
se->vruntime = curr->vruntime;
    /*3.1.1 对se(即新进程)的的vruntime进行调整,
    区分是新建还是唤醒,设置新se的虚拟时间:
    1.如果新建,则以cfs_rq->min_vruntime为一个基础加上一段补偿时间(即sched_vslice(cfs_rq, se)),让它晚些时候执行
    2.如果是唤醒,则如果睡眠时间过长则需要特殊处理(即将cfs_rq->min_vruntime适当减一个差值做为进程的vruntime值).
    不管怎样,都不能让自己的虚拟时间变小.*/
    place_entity(cfs_rq, se, 1);

    /*看是否配置了sysctl_sched_child_runs_first,该值可以指定子进程先运行,另外有个entity_before的判断
    1.没有START_DEBIT时,父子进程的虚拟时间相同,此值为假
    2.有START_DEBIT时,子子进程大于父的,此值为真*/
    if (sysctl_sched_child_runs_first && curr && entity_before(curr, se)) {
        新运行子进程
    }
    /*对新进程奖励一下*/
    se->vruntime -= cfs_rq->min_vruntime;
}
3.2 activate_task()
3.3 新建进程是否能抢占当前
check_preempt_curr(struct rq *rq, struct task_struct *p, int sync)->check_preemt_wakeup():
static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int sync)
{
    se是当前进程,pse是唤醒进程.

    记住2个优先调度的进程:
    cfs_rq->last, 指向当前,即要切换出去的进程;
    cfs_rq->next, 指向新的,即要唤醒的进程

    如果已经设置了抢占标志,返回.
    如果唤醒的进程是属于SCHED_BATCH的,返回.因为batch不能抢占普通cfs进程.
    如果不允许在唤醒时抢占,返回.
   
    wakeup_preempt_entity(se, pse)判断唤醒进程能否抢占当前进程,如果能,就goto preempt.
preempt:
    resched_task(curr);
}
=============================================
4 唤醒
try_to_wake_up(sync):
如果sync等于1,则表示唤醒的进程不能够抢占当前CPU上运行的进程.
ttwu_activate()->activate_task(),以1为参数调用enqueue_task(),
最后调place_entity()带唤醒标志更新vruntime,最后调enqueue_entity()入队列.
接着调check_preempt_curr(rq, p, sync)->check_preemt_wakeup()来判断抢占,设置p为运行.

Answer 1

本帖最后由 chishanmingshen 于 2011-06-19 11:09 编辑

进程CFS小结(补充) bychishanmingshen

纯属个人理解,如有不正,请指点,谢谢!

1.o(1)
o(1)中有一个饥饿问题,是由于过期数组导致的.
交互进程长时间地放在活跃数组,自然导致过期数组中进程的饥饿,
而且可能过期数组中就有高优先级的进程呢.
o(1)的好处就是选下一个选得快,但是实在是很不公平.

2.cfs引入权值
在cfs中优先级的概念转为了权值,每个进程都有一个权值,这个是简单的线性计算转换的.
每个进程根据权值拥有一个自己的虚拟时间管理器,权值大的,其虚拟时间走得慢,
这样就间接地实现了不同优先级有不同的cpu占有时间.

使用权值的地方主要是:
1)进程虚拟时间增量=实际时间*(1024/进程权值)
比如tick中断时,本进程要计算该值来更新rb_tree.可见权值小的进程占有时间较短.
2)进程运行时间=系统调度周期*(进程权值/运行队列总的权值)
比如计算进程的理想时间时需要计算该值.
总之,每个进程都在随时调整自己的虚拟运行时间,不管是抢占,唤醒,新建还是tick中.
这样就能随时更新rb_tree,目的就是维护公平.

3.tick中的调度
检查自己的sched_slice()是否已经推进完,如果完了,需要让出cpu.
另外,如果发现自己的虚拟时间比leftmost的虚拟时间大了sched_slice(),也是要让出cpu的.
可见,tick中的检查是从较高的层次,比较的都是自己的sched_slice().
感觉这种检查比较宽松,因为可能自己的sched_slice()被多次打断,但没有得到累加.因为
它累加的仅是自己持续的时间.
而之前的o(1)是计算好时间片,一直检查其是否全部耗尽.

4.唤醒的进程
对于唤醒的进程,要看睡眠了多久,要是睡得不久就照常cfs;
如果睡得太久,即该进程的虚拟时间小于cfs_rq->min_vruntime-thresh,
(这个thresh不同的版本还有有些差异).
总之,就是避免长睡的进程醒后长时间地耗着cpu,当然对睡眠的进程还是给予时间上的奖励的.

5.新进程
对于新进程,比较复杂.
如果设置了DEBIT,则其虚拟时间定为cfs_rq->min_vruntime再加上一个自己的sched_slice()时间.
这个是为了避免新进程一上来就导致选好的leftmost进程失效,所以要推迟新进程加入运行队列导致的竞争.

对于fork新进程,由于写时复制的限制是会要求新进程最好先运行的,
但是这个可能会与cfs调度机制的结果冲突!
在cfs中可以设置是否要子进程先运行,默认是设置子进程运行.

1)没有设置DEBIT:
就是不给新进程做DEBIT,即新进程的虚拟时间初始化为cfs_rq->min_vruntime,
而当前进程的虚拟时间可能大于也可能小于cfs_rq->min_vruntime,故
A.小于:cfs_rq->min_vruntime不变,而新进程的虚拟时间初始化为cfs_rq->min_vruntime,
故当前进程的虚拟时间小于新进程的,继续运行.
如果设置了子先运行,则在entity_before()的判断为真,故子先运行;
如果没有设置,则由cfs接管,当前继续运行,之后就是check_preempt_curr()检查抢占.
B.大于:cfs_rq->min_vruntime更新为当前进程的虚拟时间,
新进程的虚拟时间初始化为cfs_rq->min_vruntime,故父子的虚拟时间相等.
如果设置了子先运行,则在entity_before()的判断为假,由cfs接管,当前优先执行,
之后也是check_preempt_curr()检查抢占;
如果没有设置,则由cfs接管,当前优先执行,之后是check_preempt_curr()检查抢占.

2)设置了DEBIT:
子进程会假设自己已经(DEBIT的意思)运行了cfs_rq->min_vruntime再加上自己的sched_slice().
如果设置了子先运行,则entity_before()为假,故新进程先运行;
如果没有设置,则该cfs管理了,子进程的虚拟时间虽然DEBIT了,父进程的虚拟时间也有比其小的可能,
故也有先执行的可能.
接着,不管配置是否,都检查抢占,即check_preempt_curr(),这是不可少的.

由1)和2)可见:当前进程继续执行的情况还是有的,但很少.
因为至少过这一关:check_preempt_curr(),即当前进程没推进完sched_slice().

另外,有个代码层次的问题值得注意:
task_fork_fair()中最后将新进程的虚拟时间减去cfs_rq->min_vruntime,
在随后的enqueue_task_fair()加入rb_tree时会再加上cfs_rq->min_vruntime.

6.总结
cfs之前的版本是每次tick中断都做虚拟时间的检查,即把当前进程先出队再入队.
现在是基于cfs_rq的min_vruntime为基点的追赶,在追赶的过程中,始终追求一个理想状态,
即此时所有进程的运行时间是按权值成精确的比例关系.而调度期间新加入的进程导致了较高复杂性.