Linux CFS 虚拟时间更新

参考文献:《linux kernel development》P43 下载见

P43讲到关于linux的CFS的调度依据vruntime的时候,想对起做一些深入的了解,加深记忆。

我就暂且从书上所提到的Update_curr函数开始,前面的某些函数调用过程,待清楚之后再做分享。

首先做摘要:

nice和prio的关系如下:

#define NICE_TO_PRIO(nice) (MAX_RT_PRIO+nice+20)

#define PRIO_TO_NICE(prio) (prio-MAX_RT_PRIO-20)

其中,MAX_RT_PRIO=100,nice的值在-20到19之前,那么优先级就在100 -139之间。

prio和weight之间的转换关系参见prio_to_weight。

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)) 

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

2.         return delta; //nice=/!=NICE_0_LOAD

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

tmp = (u64)delta_exec * weight; 

1.    if (unlikely(tmp > WMULT_CONST)) 

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

3.                WMULT_SHIFT/2); 

4.        else 

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

从这些代码可以看出上述结论!

继续摘抄。。。

在每次更新完vruntime之后,将会进行一次检查,要不要设置调度位TIF_NEED_SCHED。

通过以上分析,我们基本上已经分析了不开组调度的情况下,进程一般的调度的原理。

附加

我们再举一个极端的情况假设有两个用户A,B,注意这里使用户。A用户有1个进程a且a.weight=1;B用户也有1个进程b且b.weight=1000,根据上面的公平理论,我们可以发现B用户可能会一直霸占cpu,在用户更多的情况下,肯能会更糟。为了解决这种问题,CFS引入了组调度,即调度的对象不仅仅限于调度实体,而是可以以用户为调度单位,即A和B位调度单位的话,A B各占50%的CPU。而且只要一个组里的进程被调度,其他的进程也会跟着被调度,但是占用的CPU却至于用户有关。

在文件sched.c中可以找到关于NICE_TO_PRIO和PRIO_TO_NICE以及prio_to_weight的定义。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.heiqu.com/d8bf6eede95221c7a1e496658d03cd4a.html