CFS调度器.pdf

1.CFS调度器的虚拟时钟CFS把进程的优先级转化为权重（weight），每个进程的优先级对应一个权重，优先级越高，权重越大。每一个CPU有一个cfs_rq对象，它维护着就绪队列中进程的总权重。普通进程的静态优先级为100~139，进程描述符task_struct中的prio保存着进程的优先级，通过nice可以调整进程的静态优先级（-20~19）。优先级转化相关的数据结构（include/linux/sched.h）:/*实现进程的最大优先级*/#defineMAX_USER_RT_PRIO100#defineMAX_RT_PRIOMAX_USER_RT_PRIO/*最大优先级*/#defineMAX_PRIO(MAX_RT_PRIO+40)/*普通进程的默认优先级*/#defineDEFAULT_PRIO(MAX_RT_PRIO+20)/*nice到静态优先级的转换，-20对应100，19对应139*/#defineNICE_TO_PRIO(nice)(MAX_RT_PRIO+(nice)+20)/*静态优先级到nice的转换，100对应-20，139对应19*/#definePRIO_TO_NICE(prio)((prio)-MAX_RT_PRIO-20)/*静态优先级到权重的转换，nice值-20的权重为88761，*19的权重为15，权重越大，优先级越高*/staticconstintprio_to_weight[40]={/*-20*/88761,71755,56483,46273,36291,/*-15*/29154,23254,18705,14949,11916,/*-10*/9548,7620,6100,4904,3906,/*-5*/3121,2501,1991,1586,1277,/*0*/1024,820,655,526,423,/*5*/335,272,215,172,137,/*10*/110,87,70,56,45,/*15*/36,29,23,18,15,};cfs_rq对象维护着一个虚拟时钟，时钟前进的步伐和总权重成反比，也就是说，权重越大，虚拟时钟前进的步伐越慢。同时每一个进程也有一个虚拟时钟，它记录着进程已经占用CPU的虚拟时间，它前进的步伐和本进程的权重成反比。当一个进程受到了完全公平的调度待遇时，它的虚拟时钟应该和调度对象cfs_rq的虚拟时钟一致，如果某个进程的虚拟时钟快于cfs_rq的虚拟时钟，则在将来的调度过程中需要接受“惩罚”，而对于虚拟时钟比cfs_rq的虚拟时钟慢的，则需要适当的“奖励”。CFS调度的原则就是：总是把CPU分配给虚拟时钟最慢的那个进程。每一个进程有一个load_weight结构，专门用来保存当前进程优先级对应的权重W，以及（2^32）/W的值，其定义如下：structload_weight{unsignedlongweight,unsignedlonginv_weight;};每当通过nice系统调用改变进程的权重weight时，inv_weight也随之改变。每当进程被调度运行时，CFS记录了进程的起始运行时间，每次时钟中断，CFS根据当前系统时间，计算出进程已经运行的实际时间delta_exec，然后调用calc_delta_fair函数，根据进程的load_weight结构计算虚拟时钟的时间。a.进程的运行时间计算公式为:分配给进程的运行时间=调度周期*进程权重/所有进程权重之和(公式1)b.从实际运行时间到vruntime的换算公式vruntime=实际运行时间*1024/进程权重。(公式2)式子中，1024，实际上它等于nice为0的进程的权重，代码中是NICE_0_LOAD。c.把公式2中的实际运行时间用公式1来替换，可以得到这么一个结果：vruntime=(调度周期*进程权重/所有进程总权重)*1024/进程权重=调度周期*1024/所有进程总权重(公式3)从公式3得到，虽然进程的权重不同，但是它们的vruntime增长速度应该是一样的，与权重无关。/*delta_exec是实际运行的时间，weight是基准因子1024，*lw是进程load_weight的结构*/staticunsignedlongcalc_delta_mine(unsignedlongdelta_exec,unsignedlongweight,structload_weight*lw){u64tmp;if(!lw->inv_weight){if(BITS_PER_LONG>32&&unlikely(lw->weight>=WMULT_CONST))lw->inv_weight=1;elselw->inv_weight=1+(WMULT_CONST-lw->weight/2)/