完全公平调度CFS探索之时间更新相关内容

CFS允许每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行进程，而不再采用分配给每个进程时间片的做法了，CFS在所有可运行进程总数基础上计算出一个进程应该运行多久，而不是依靠nice值来计算时间片。nice值在CFS中被作为进程获得的处理器运行比的权重：越高的nice值（越低的优先级）进程获得更低的处理器使用权重，这是相对默认nice值进程的进程而言的；相反，更低的nice值（越高的优先级）的进程获得更高的处理器使用权重。

下面我们在没有开组调度的情况下，讨论CFS调度的时间更新的相关内容：

    假设现在系统有A，B，C三个进程，A.weight=1,B.weight=2,C.weight=3.那么我们可以计算出整个公平调度队列的总权重是cfs_rq.weight = 6，很自然的想法就是，公平就是你在重量中占的比重的多少来拍你的重要性，那么，A的重要性就是1/6,同理，B和C的重要性分别是2/6,3/6.很显然C最重要就应改被先调度，而且占用的资源也应该最多，即假设A，B,C运行一遍的总时间假设是6个时间单位的话，A占1个单位，B占2个单位，C占三个单位。这就是CFS的公平策略。在linux内核中采用了如下计算公式：

ideal_time = sum_runtime *se.weight/cfs_rq.weight

注：ideal_time:每个进程应该运行的时间

    sum_runtime:运行队列中所有任务运行完一遍的时间

    se.weight:当前进程的权重

    cfs.weight:整个cfs_rq的总权重

这里se.weight和cfs.weight根据上面讲解我们可以算出，sum_runtime是怎们计算的呢，linux内核中这是个经验值，其经验公式是：

(1) sum_runtime=sysctl_sched_min_granularity *nr_running（if 进程数 > 5）

(2) sum_runtime=sysctl_sched_latency = 20ms           （if 进程数 <=5）

注：sysctl_sched_min_granularity =4ms

 

linux内核代码中是通过一个叫vruntime的变量来实现上面的原理的，即：每一个进程拥有一个vruntime,每次需要调度的时候就选运行队列中拥有最小vruntime的那个进程来运行，vruntime在时钟中断里面被维护，每次时钟中断都要更新当前进程的vruntime,即vruntime以如下公式逐渐增长：

 (1) vruntime =  delta* NICE_0_LOAD/se.weight;(if curr.nice!=NICE_0_LOAD)

 (2)vruntime = delta;                         (ifcurr.nice=NICE_0_LOAD)

 

vruntime更新是在如下地方进行：

Update_curr：delta_exec=(unsignedlong)(now->curr->exec_starrt);

                      __update_curr(cfs_rq,curr,delta_exec);

__update_curr:delta_exec_weighted=calc_delta_fair(delta_exec,curr);

                       Curr->vruntime =delta_exec_weighted;

Calc_delta_fair：    

if (unlikely(se->load.weight != NICE_0_LOAD))  

        delta = calc_delta_mine(delta, NICE_0_LOAD, &se->load);  

         return delta;

 

Calc_delta_mine: /* delta*=weight/lw */ 

tmp = (u64)delta_exec * weight;  

    if (unlikely(tmp > WMULT_CONST))  

            tmp = SRR(SRR(tmp, WMULT_SHIFT/2) * lw->inv_weight,  

                WMULT_SHIFT/2);  

    else  

            tmp = SRR(tmp * lw->inv_weight, WMULT_SHIFT); 

上面介绍的是CFS调度涉及到的时间更新内容。