在抽象模型中vruntime决定了经过被调节的前后相继顺序,在真实模型中决定被调节的前后相继顺序的参数是由函数entity_key决定的。 
 
static inline s64 entity_key(struct cfs_rq *cfs_rq, struct
sched_entity *se)
{
    return se->vruntime – cfs_rq->min_vruntime;
}
enqueue_task_fair—->enqueue_entity—->__enqueue_entity—->entity_key决定插入就绪队列的地方。

一、概述

平时进程分为三十三个品级,种种阶段对应两个权重值,权重值用多个整数来标示。权重值定义在数组prio_to_weight[40]中;普通进程的权重值最大为88761,最小为15。暗中同意情形下,普通进度的权重值为1024(由NICE_0_LOAD内定)。weight是由进程的静态优先级static_prio决定的,静态优先级越高(static_prio值越小)weight值越大。普通进度的默许nice值为0,即默许静态优先级为120,它的weight值为prio_to_weight[20],即1024。因此NICE_0_LOAD的值就
为1024。

率先简要介绍一下入眼的安排性思路,
CFS思路特别easy。正是根据各样进度的权重分配实施时间(权重怎么来的前边再说)。
进度的实施时间总结公式为:
分配给进度的实施时间 = 调治周期 * 进度权重 / 全体历程权重之和  
(公式1)
调整周期非常好驾驭。就是将全部介乎TASK_RUNNING态进程都调治一次的日子,
差非常的少大同小异也正是O(1)调节算法中试行队列和过期队列切换二遍的年月
(作者对O(1)调治算法看得不是可怜熟,如有错误还望各位大虾建议)。
举个样例。比如仅独有两个进程A, B,权重分别为1和2,
调治周期设为30ms,那么分配给A的CPU时间为
30ms * (1/(1+2)) = 10ms
而B的CPU时间为
 
30ms * (2/(1+2)) = 20ms
那正是说在这里30ms中A将进行10ms。B将进行20ms。
公正无私怎么显示吗?它们的施行时间并分裂阿?
实际公平是体目前别的一个量方面。叫做virtual
runtime(vruntime)。它记录着进度早就实行的岁月,
可是并不是直接记录,而是要基于进程的权重将实践时间放大可能减少二个比例。
我们来看下从实质上实施时间到vruntime的折算公式
vruntime = 实际实践时间 * 1024 / 进度权重。 (公式2)
为了不把大家搞晕。这里小编一贯写1024。实际上它约等于nice为0的历程的权重,代码中是NICE_0_LOAD。
也正是说。全体历程都是nice为0的经过的权重1024看作标准。总括自个儿的vruntime增多快度。
还以上面AB五个经过为例。B的权重是A的2倍,那么B的vruntime增多快度唯有有A的四分之二。

vruntime行走速度:
   
系统鲜明:暗许权重值(1024)对应的进度的vruntime行走时间与事实上运作时刻runtime是1:1的涉嫌。由于vruntime的行动速度和权重值成反比,那么其余进度的vruntime行走速度都通过以下三个参数计算获得:1、该进程的权重值2、私下认可进程的权重值。
    比如权重为3096的进程的vruntime行走速度为:1024/3096 * (wall
clock)。
    “真实石英钟速度”即为runtime(即 wall clock)行走的快慢。

近些日子我们把公式第22中学的实际实施时间用公式1来替换。可以赢得那样叁个结果:
vruntime = (调解周期 * 进程权重 /
整体进程总权重) * 1024 / 进程权重=调治周期 * 1024 / 全部经过总权重
来看哪些样子未有?没有错,就算经过的权重区别,不过它们的vruntime增速应该是如出一辙的(这里所说的增速同样,是从宏观上来看的。从上一篇小说能够看出来。而在上一篇文章中说vruntime的增量分化,是从公式深入分析获得的,算是局地解析,在公式第22中学,假诺实际实施时间都以一样。特别举世瞩目权重小的巩固的多。权首要的抓实的小,笔者个人感觉便是虚构机械钟的留存。转变了观念。才有了那个CFS,事实上依旧依照权重来调控贰个进度在一个调用周期内实施了多长期,可是设想石英钟决定了怎么调整这些进程,那正是观念),与权重无关。
好,既然全部经过的vruntime增速宏观上看应该是同样时候推进的。
这便是说就可以知道用这几个vruntime来采撷实行的历程。何人的vruntime值不大就表明它已经占用cpu的小时十分的短,
遇到了“有失公正”对待,因而下贰个施行进度正是它。

   
进度实施实行时期周期性调整器周期性地运行,其承担更新一些连锁数据,并不辜负责进度之间的切换:
   
timer_tick()—->update_process_times—->schedule_tick()
   
schedule_tick—->task_tick_fair—->entity_tick()—->update_curr()
    update_curr()函数完结相关数据的创新。
        update_curr()—->delta_exec = (unsigned long)(now –
curr->exec_start)
                              |–>__update_curr()
                              |–>curr_exec_start = now;
   
update_curr()函数只承担总括delta_exec以至更新exec_start。别的工作由__update_curr()函数完毕:
        1、更新当前进程的骨子里运维时刻(抽象模型中的runtime)。
        2、更新当前进度的杜撰时间vruntime。
        3、更新cfs_rq->min_vruntime。
          
在眼下进度和下二个快要被调治的经过中甄选vruntime一点都不大的值。然后用该值和cfs_rq->min_vruntime比较,如果比min_vruntime大,则更新cfs_rq为的min_vruntime为所求出的值。

那般不只能公平选取进程,又能保证高优先级进度
赢得很多的奉行时间。
那就是CFS的第一考虑了。

设想下当成立新历程可能经过唤醒时,vruntime在实际模型中的管理格局:
I、新建进程
   
进程的ideal_time长度和weight成正比,vruntime行走速度与weight值成反比。因而当每一个进度在period时间内,都实践了投机相应的ideal_time长期,那么他们的vruntime的增量相等。而nice为0的长河的vruntime行走速度等于runtime行走速度,所以各个进程都运作它本身相应的ideal_runtime时间,其余进度的vruntime增量都等于nice值为0的进程的ideal_runtime。若是起头情况下,它们的具备进度的vruntime值都等于0,那么当一个历程运营完runtime的光阴为ideal_time,那么它的vruntime将为最大,只要任何进度的运营总时间没有直达分别对应的ideal_runtime值,那么它从来排在进程队列的末尾。

再补偿一下放权力重的来源于,权重跟进程nice值之间有各种相应的涉及,能够通过全局数组prio_to_weight来转换,
nice值越大,权重越低

    对于新历程,task_fork_fair()->place_entity(cfs_rq, se,
1),其intial参数为1。新历程的vruntime值被安装为min_vruntime+sched_vslice(cfs_rq,
se),
sched_vslice()函数可总结出nice值为0的长河的ideal_runtime。其功能是将新投入的历程的标志为“它在period长日子内早就运行它对应的ideal_time长期”,那么新投入进度在答辩上(全数进程都进行它对应的ideal_runtime时间,未有发生睡眠、进程终止等特种情形)唯有拭目以俟period之后技艺被调节。
    sched_vslice(cfs_rq,
se)—->calc_delta_fair(sched_slice(cfs_rq, se), se),
sched_slice()计算新建进程的ideal_runtime,calc_delta_fair()将ideal_runtime转换成vruntime。

以下来深入分析代码。网络早就有丰富多cfs的小说。因而作者计划换四个方法来写,接纳多少个点来开展情景分析,
含有进度创设时。进度被唤起,主动调整(schedule),石英钟中断。

II、睡眠进程被提醒
   
将经过的vruntime值设置为cfs_rq->min_vruntime值,然后再扩充一下互补:将vruntime减去与sysctl_sched_latencyd相关的叁个数值。进度步入梦眠状态时cfs_rq->min_vruntime就不独有或等于该过程的vruntime值,它在睡觉进度中vruntime值是不改造的,不过cfs_rq->min_vruntime的值却是单调扩充的,进程醒来后补偿的量由sysctl_sched_latency给出,不管进程面对的偏向一方待遇大依然小,一律只补充这么多。

介绍代码此前先介绍一下CFS相关的布局
率先个是调节实体sched_entity,它表示三个调治单位。在组调治关闭的时候能够把她等同为进度。
每个task_struct中都有四个sched_entity,进度的vruntime和权重都保存在这里个结构中。
那正是说任何的sched_entity怎么协会在联合吗?红黑树。全体的sched_entity以vruntime为key
(实际上是以vruntime-min_vruntime为单位,难道是防备溢出?反正结果是同样的)插入到红黑树中,
相同一时间候缓存树的最左側节点。也等于vruntime最小的节点,这样能够急忙选中vruntime最小的历程。
只顾仅唯有等待CPU的就绪态进程在这里棵树上,睡眠进程和正在实施的历程都不在树上。
自己从ibm developer works上偷过来一张图来呈现一下它们的关联:
汗。图片上传功用被关门了。先盗链三个回复。别怪小编没品哈。。。

实际模型总括:
   
a)进程在就绪队列中用键值key来排序,它并未有保留在别的变量中,而是在须求时由函数entity_key()总括得出。它等于
        key = task->vruntime – cfs_rq->min_vruntime
   
b)各类进度有两样的严重性(优先品级),越主要的进程权重值weight(task.se.load.weight)越大。
   
c)每种进程vruntime行走的速度和weight值成反比。权重值为1024(NICE_0_LOAD)的经过vruntime行走速度和runtime同样。
   
d)种种进程每回得到CPU使用权最多推行与该进度对应的ideal_runtime长时间。该时长和weight值成正比,它从未用变量来保存,而是需求运用sched_slice()函数总括得出。
   
e)ideal_runtime计算的规范是period,它也未有用变量来保存,而是由__sched_period()计算得出。

 

 

www.512.net 1

经过的先行等第决定了其权重值,task_struct中与事先级相关数据成员:
   
a)static_prio,指普通进度的静态优先级(实时进度没用该参数),值越小则优先级越高。静态优先级是经过运维时分配的前期级。它可以用nice()恐怕sched_setscheduler()系统调用更动,不然在运行时期一向维持一定。

 

      
注意:关于a),注意本文的最后加多的注释。

 

   
b)rt_priority,表示实时进度的优先级(普通进度没用该参数),它的值介于[0~99]之间。rt_priority的值越大其优先级越高。
   
c)normal_prio,由于static_prio和rt_priority与事先级的关联性不平等,因而用normal_prio统一下“单位”,统一成:normal_prio值越小则进度优先级越高。因而,normal_prio也足以知晓为:统一了单位的“静态”优先级。
   
d)prio,在系统中使用prio推断进程优先级,prio是经过的动态优先级,其表示经过的有效优先级。对于实时进程来讲,有效优先级prio就也正是它的normal_prio。普通进程能够这段日子进步优先级,通过更换prio实现,动态优先级的巩固不影响进度的静态优先级。父进度的动态优先级不会遗传给子进度,子进度的动态优先级prio初叶化为父进度的静态优先级。

 

注:

方今開始分情景分析CFS。

出于在好几意况下须求权且提升进程的优先级,因而不但供给静态优先级和常常优先级,还索要动态优先级prio;

 

参照《深远Linux内核架构》p70-76、
p_288-290;

二、制造进程 

        
linux内核的优先级承袭左券(pip)

先是个场景选为进度成立时CFS相关变量的初步化。
作者们领略。Linux创造进度使用fork大概clone可能vfork等连串调用,终于都会到do_fork。

         进度优先级改变局面难点的化解  

借使未有设置CLONE_STOPPED,则会跻身wake_up_new_task函数,大家看看这些函数的要害部分

        为了在Linux中应用Priority
Inheritance
Protocol公约来化解先行级反转难题,Linux中引进实时互斥量rt_mutex,在task_struc结构体中也引进了pi_waiters链表,须要静心的流水生产线为:

[cpp] view
plaincopy

         rt_mutex_slowlock() —->
__rt_mutex_slowlock() —->

  1. /* 
  2.  * wake_up_new_task – wake up a newly created task for the first time. 
  3.  * 
  4.  * This function will do some initial scheduler statistics housekeeping 
  5.  * that must be done for every newly created context, then puts the task 
  6.  * on the runqueue and wakes it. 
  7.  */  
  8. void wake_up_new_task(struct task_struct *p, unsigned long clone_flags)  
  9. {  
  10.     …..  
  11.     if (!p->sched_class->task_new || !current->se.on_rq) {  
  12.         activate_task(rq, p, 0);  
  13.     } else {  
  14.         /* 
  15.          * Let the scheduling class do new task startup 
  16.          * management (if any): 
  17.          */  
  18.         p->sched_class->task_new(rq, p);  
  19.         inc_nr_running(rq);  
  20.     }  
  21.     check_preempt_curr(rq, p, 0);  
  22.     …..  
  23. }  

                
task_blocks_on_rt_mutex() —-> 
__rt_mutex_adjust_prio()

 上面十三分if语句作者不明白怎么着景况下会为真。笔者測试了一晃。在地点八个支行各加多少个计数器,
估计为实在情况唯有有2次(小编不用依据的推測是idle进度和init进度),而估摸为假的景况有近万次。
就此大家一味看之下的道岔,假诺哪位前辈知道真相的话还望告诉自个儿一声,特别感激。

                                                                  
|–> rt_mutex_adjust_prio_chain()

再以下正是检測是否能够产生抢占,假使新进程能够抢占当前经过则开展进程切换。

         
__rt_mutex_adjust_prio调解了近日抱有锁的经过的动态优先级(承继自等待队列中全部进度的万丈优先级),rt_mutex_adjust_prio_chain()即使被调节的动态优先级的经过也在伺机有个别财富,那么也要链式地调动相应进度的动态优先级。

咱俩三个贰个函数来看
p->sched_class->task_new相应的函数是task_new_fair:

关于Priority
Inversion能够参照《Operating System Concepts》9_ed p217-218
                                                                                                                      

[cpp] view
plaincopy

  1. /* 
  2.  * Share the fairness runtime between parent and child, thus the 
  3.  * total amount of pressure for CPU stays equal – new tasks 
  4.  * get a chance to run but frequent forkers are not allowed to 
  5.  * monopolize the CPU. Note: the parent runqueue is locked, 
  6.  * the child is not running yet. 
  7.  */  
  8. static void task_new_fair(struct rq *rq, struct task_struct *p)  
  9. {  
  10.     struct cfs_rq *cfs_rq = task_cfs_rq(p);  
  11.     struct sched_entity *se = &p->se, *curr = cfs_rq->curr;  
  12.     int this_cpu = smp_processor_id();  
  13.     sched_info_queued(p);  
  14.     update_curr(cfs_rq);  
  15.     place_entity(cfs_rq, se, 1);  
  16.     /* ‘curr’ will be NULL if the child belongs to a different group */  
  17.     if (sysctl_sched_child_runs_first && this_cpu == task_cpu(p) &&  
  18.             curr && curr->vruntime < se->vruntime) {  
  19.         /* 
  20.          * Upon rescheduling, sched_class::put_prev_task() will place 
  21.          * ‘current’ within the tree based on its new key value. 
  22.          */  
  23.         swap(curr->vruntime, se->vruntime);  
  24.         resched_task(rq->curr);  
  25.     }  
  26.     enqueue_task_fair(rq, p, 0);  
  27. }  

 这里有四个至关心重视要的函数,update_curr,place_entity。

当中update_curr在这里地能够忽略。它是翻新进度的一些任何时候间变化的音讯。大家松开前面再看,
place_entity是立异新进程的vruntime值。以便把他插入红黑树。
新进度的vruntime分明今后有二个估摸,满足上面多少个尺码时,沟通父亲和儿子进度的vruntime:
1.sysctl设置了子进度优先推行
2.fork出的子进度与父进度在同叁个cpu上
3.父进度不为空(那一个准绳为啥会产生暂不鲜明,难道是fork第贰个进程的时候?)
4.父进度的vruntime小于子进度的vruntime
多少个规格都还比較好掌握,说下第多个,由于CFS总是挑肥拣瘦vruntime最小的长河试行,
于是必得保障子进程vruntime比父进度小,我未有直接把子进度的vruntime设置为相当小的值,
而是採用交流的法子,能够幸免通过fork新历程来大批量占为己有cpu时间,立刻还要讲到。

最后,调用enqueue_task_fair将新历程插入CFS红黑树中

以下大家看下place_entity是怎么总计新进度的vruntime的。

[cpp] view
plaincopy

  1. static void  
  2. place_entity(struct cfs_rq *cfs_rq, struct sched_entity *www.512.net,se, int initial)  
  3. {  
  4.     u64 vruntime = cfs_rq->min_vruntime;  
  5.     /* 
  6.      * The ‘current’ period is already promised to the current tasks, 
  7.      * however the extra weight of the new task will slow them down a 
  8.      * little, place the new task so that it fits in the slot that 
  9.      * stays open at the end. 
  10.      */  
  11.     if (initial && sched_feat(START_DEBIT))  
  12.         vruntime += sched_vslice(cfs_rq, se);  
  13.     if (!initial) {  
  14.         //先不看这里,  
  15.     }  
  16.     se->vruntime = vruntime;  
  17. }  

 
那边是总括进度的发端vruntime。

它以cfs队列的min_vruntime为法规,再增加进度在三回调解周期中所增加的vruntime。
此处并非计算进程应该进行的时刻。而是先把进度的已经推行时间设为贰个十分大的值。
可是该进度明显还尚未实施过呀,为啥要这么做呢?
就算新进度都能获得最小的vruntime(min_vruntime),那么新进程会率先个被调节施行。
诸如此比程序猿就能够因此持续的fork新历程来让投机的次序平素占有CPU。那鲜明是不创造的,
那跟曾经选用时间片的基石中父亲和儿子进度要平均父进度的时间片是叁个道理。

再解释下min_vruntime,这是各种cfs队列一个的变量,它平日小于等于一体就绪态进程
的微小vruntime。也是有分化。举例对睡眠进程展开时间补偿会导致vruntime小于min_vruntime。

至于sched_vslice总结细节一时半刻不细看,概略上说就是把概述中付出的五个公式结合起来举例以下:
sched_vslice = (调节周期 * 进度权重 / 全体历程总权重) * NICE_0_LOAD
/ 进度权重
也正是算出进程应分配的实际cpu时间,再把它转化为vruntime。
把这一个vruntime加在进度上之后,就一定于感觉新进度在这里一轮调治中一度实践过了。

好了。到这边又能够回来wake_up_new_task(希望你还没晕,能想起回去:-)),
看看check_preempt_curr(rq, p,
0);这么些函数就直接调用了check_preempt_wakeup

[cpp] view
plaincopy

  1. /* 
  2.  * Preempt the current task with a newly woken task if needed: 
  3.  */小编略去了一部分不太主要的代码  
  4. static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int sync)  
  5. {  
  6.     struct task_struct *curr = rq->curr;  
  7.     struct sched_entity *se = &curr->se, *pse = &p->se; //se是当下历程。pse是新历程  
  8.     /* 
  9.      * Only set the backward buddy when the current task is still on the 
  10.      * rq. This can happen when a wakeup gets interleaved with schedule on 
  11.      * the ->pre_schedule() or idle_balance() point, either of which can 
  12.      * drop the rq lock. 
  13.      * 
  14.      * Also, during early boot the idle thread is in the fair class, for 
  15.      * obvious reasons its a bad idea to schedule back to the idle thread. 
  16.      */  
  17.     if (sched_feat(LAST_BUDDY) && likely(se->on_rq && curr != rq->idle))  
  18.         set_last_buddy(se);  
  19.     set_next_buddy(pse);  
  20.     while (se) {  
  21.         if (wakeup_preempt_entity(se, pse) == 1) {  
  22.             resched_task(curr);  
  23.             break;  
  24.         }  
  25.         se = parent_entity(se);  
  26.         pse = parent_entity(pse);  
  27.     }  
  28. }  

 
第一对于last和next四个字段给予证实。
例如那多少个字段不为NULL,那么last指向如今被调整出去的长河,next指向被调解上cpu的进度。
举例A正在实践,被B抢占。那么last指向A。next指向B。

那五个指针有怎么着用吧?
当CFS在调治点选取下一个推行进度时,会事先关照那多少个经过。大家前边拜会到,这里仅仅要牢记。

<
那三个指针仅仅使用二回。就是在地方那个函数退出后,重返顾客空间时会触发schedule,
在那选用下四个调整进程时会优先选项next,次优先选项last。选取完后。就能清空那八个指针。
那样设计的由来是,在上头的函数中检測结果是力所能致抢占并不意味已经抢占,而一味是安装了调整标记,
在结尾触发schedule时抢占进度B并不一定是好不轻松被调解的历程(为啥?由于大家估计是还是不是能抢占
的基于是私吞进度B比进行进度A的vruntime小,但红黑树中可能有比抢占进度B的vruntime更加小的进程C,
那般在调治时就能入选vruntime最小的C,实际不是侵占进度B)。不过我们自然期望优先调整B,
鉴于大家正是为了进行B才设置了调解标识,所以这里用一个next指针指向B,以便给他个后门走,
要是B实在不争气,vruntime太大。就照旧继续施行被侵夺进度A比較合理,由此last指向被侵占进程。
那是一个比next小一些的后门,假如next捷径战败,就让被侵吞进度A也走一遍后门,
若是被私吞进度A也不争气。vruntime也太大,仅仅好从红黑树中挑三个vruntime最小的了。
不管它们活动是还是不是成功,一旦选出下五个历程,就立时清空这七个指针,无法老开着那个后门吧。
须求在意的是,schedule中清空那七个指针仅仅在2.6.29及然后的木本才有。在此之前的水源未有那句话。

然后调用wakeup_preempt_entity检測是不是满意抢占条件。假如满足(重临值为1)
则对当前进度设置TIF_NEED_RESCHED标记。在剥离系统调用时会触发schedule函数实行进程切换,
以此函数前面再说。

大家看看wakeup_preempt_entity(se,
pse)。到底怎么测度前面一个是或不是足以抢占前面多个

[cpp] view
plaincopy

  1. /* 
  2.  * Should ‘se’ preempt ‘curr’. 
  3.  * 
  4.  *             |s1 
  5.  *        |s2 
  6.  *   |s3 
  7.  *         g 
  8.  *      |<—>|c 
  9.  * 
  10.  *  w(c, s1) = -1 
  11.  *  w(c, s2) =  0 
  12.  *  w(c, s3) =  1 
  13.  * 
  14.  */  
  15. static int  
  16. wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)  
  17. {  
  18.     s64 gran, vdiff = curr->vruntime – se->vruntime;  
  19.     if (vdiff <= 0)  
  20.         return -1;  
  21.     gran = wakeup_gran(curr);  
  22.     if (vdiff > gran)  
  23.         return 1;  
  24.     return 0;  
  25. }  

以此函数重临-1象征新历程vruntime大于当前历程,当然无法抢占。
重临0表示尽管新进度vruntime比当下历程小。但是未有小到调解粒度,平常也不能够抢占
归来1象征新历程vruntime比近日进程小的超过了调节粒度,能够抢占。
调治粒度是何等概念呢?这些也丰裕好领悟,仅仅是必得对日前的定义作出一些调动,
前方说每趟都轻易选用vruntime最小的经过调整,事实上也不完全部都是那般。
设若进程A和B的vruntime特别类似。那么A先实践了一个tick。vruntime比B大了,
B又进行三个tick,vruntime又比A大了。又切换到A。那样就能够在AB间频仍切换。对质量影响非常大。
之所以假使当前进度的岁月没实用完,就一味有当有进程的vruntime比近期经过小超过调解粒度时。
技能进行进度切换。

函数方面凝视中特别图便是以此意思,大家看下:
横坐标表示vruntime。s1 s2
s3各自代表新进程,c表示如今进程,g表示调治粒度。
s3料定能抢占c。而s1不也许抢占c。
s2固然vruntime比c小。不过在调节粒度之内,是或不是能抢占要看意况,像后天如此的景色就不可能抢占。

到那边,创造进度时的调治相关代码就介绍完了。

 

 

 

三、唤醒进程
我们再看看唤醒进度时的CFS动作。看下函数try_to_wake_up。非常短的函数,仅仅留几行代码

[cpp] view
plaincopy

  1. /*** 
  2.  * try_to_wake_up – wake up a thread 
  3.  * @p: the to-be-woken-up thread 
  4.  * @state: the mask of task states that can be woken 
  5.  * @sync: do a synchronous wakeup? 
  6.  * 
  7.  * Put it on the run-queue if it’s not already there. The “current” 
  8.  * thread is always on the run-queue (except when the actual 
  9.  * re-schedule is in progress), and as such you’re allowed to do 
  10.  * the simpler “current->state = TASK_RUNNING” to mark yourself 
  11.  * runnable without the overhead of this. 
  12.  * 
  13.  * returns failure only if the task is already active. 
  14.  */  
  15. static int try_to_wake_up(struct task_struct *p, unsigned int state, int sync)  
  16. {  
  17.     int cpu, orig_cpu, this_cpu, success = 0;  
  18.     unsigned long flags;  
  19.     struct rq *rq;  
  20.     rq = task_rq_lock(p, &flags);  
  21.     if (p->se.on_rq)  
  22.         goto out_running;  
  23.     update_rq_clock(rq);  
  24.     activate_task(rq, p, 1);  
  25.     success = 1;  
  26. out_running:  
  27.     check_preempt_curr(rq, p, sync);  
  28.     p->state = TASK_RUNNING;  
  29. out:  
  30.     current->se.last_wakeup = current->se.sum_exec_runtime;  
  31.     task_rq_unlock(rq, &flags);  
  32.     return success;  
  33. }  

 
update_rq_clock正是翻新cfs_rq的机械钟,保持与系统时间同步。
重点是activate_task,它将经过增添红黑树而且对vruntime做一些调动。
然后用check_preempt_curr检查是不是构成私吞条件。若是能够抢占则设置TIF_NEED_RESCHED标识。

由于check_preempt_curr讲过了,大家唯有顺着以下的次第走壹遍
   activate_task
–>enqueue_task
–>enqueue_task_fair
–>enqueue_entity
–>place_entity

[cpp] view
plaincopy

  1. static void activate_task(struct rq *rq, struct task_struct *p, int wakeup)  
  2. {  
  3.     if (task_contributes_to_load(p))  
  4.         rq->nr_uninterruptible–;  
  5.     enqueue_task(rq, p, wakeup);  
  6.     inc_nr_running(rq); //实行队列上的稳当职分多了一个  
  7. }  
  8. static void enqueue_task(struct rq *rq, struct task_struct *p, int wakeup)  
  9. {  
  10.     sched_info_queued(p);  
  11.     p->sched_class->enqueue_task(rq, p, wakeup);  
  12.     p->se.on_rq = 1;  //被唤醒的职分会将on_rq设为1  
  13. }  
  14. /* 
  15.  * The enqueue_task method is called before nr_running is 
  16.  * increased. Here we update the fair scheduling stats and 
  17.  * then put the task into the rbtree: 
  18.  */  
  19. static void enqueue_task_fair(struct rq *rq, struct task_struct *p, int wakeup)  
  20. {  
  21.     struct cfs_rq *cfs_rq;  
  22.     struct sched_entity *se = &p->se;  
  23.     for_each_sched_entity(se) {  
  24.         if (se->on_rq)  
  25.             break;  
  26.         cfs_rq = cfs_rq_of(se);  
  27.         enqueue_entity(cfs_rq, se, wakeup);  
  28.         wakeup = 1;  
  29.     }  
  30.     hrtick_update(rq);  
  31. }  
  32. static void  
  33. enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int wakeup)  
  34. {  
  35.     /* 
  36.      * Update run-time statistics of the ‘current’. 
  37.      */  
  38.     update_curr(cfs_rq);  
  39.     account_entity_enqueue(cfs_rq, se);  
  40.     if (wakeup) {  
  41.         place_entity(cfs_rq, se, 0);  
  42.         enqueue_sleeper(cfs_rq, se);  
  43.     }  
  44.     update_stats_enqueue(cfs_rq, se);  
  45.     check_spread(cfs_rq, se);  
  46.     if (se != cfs_rq->curr)  
  47.         __enqueue_entity(cfs_rq, se);  //把进程扩大CFS红黑树  
  48. }  

 
那边还需求再看贰遍place_entity,前边就算看过三次,不过第八个參数不均等。
当參数3为0的时候走的是还会有一条门路,我们看下

[cpp] view
plaincopy

  1. static void  
  2. place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)  
  3. {  
  4.     u64 vruntime = cfs_rq->min_vruntime;  
  5.     /* 
  6.      * The ‘current’ period is already promised to the current tasks, 
  7.      * however the extra weight of the new task will slow them down a 
  8.      * little, place the new task so that it fits in the slot that 
  9.      * stays open at the end. 
  10.      */  
  11.     if (initial && sched_feat(START_DEBIT))  
  12.         vruntime += sched_vslice(cfs_rq, se);  
  13.     if (!initial) {  
  14.         /* sleeps upto a single latency don’t count. */  
  15.         if (sched_feat(NEW_FAIR_SLEEPERS)) {  
  16.             unsigned long thresh = sysctl_sched_latency;  
  17.             /* 
  18.              * convert the sleeper threshold into virtual time 
  19.              */  
  20.             if (sched_feat(NORMALIZED_SLEEPER))  
  21.                 thresh = calc_delta_fair(thresh, se);  
  22.             vruntime -= thresh;  
  23.         }  
  24.         /* ensure we never gain time by being placed backwards. */  
  25.         vruntime = max_vruntime(se->vruntime, vruntime);  
  26.     }  
  27.     se->vruntime = vruntime;  
  28. }  

 
initial不平等时候两条门路有何两样吧?路线1是新创造职分的时候对其vruntime实行初叶化,将它献身红黑树右端。
而以下那条路是提示睡眠任务时的代码,大家思索二个职分睡眠了那些长日子,它的vruntime就直接不会更新,
那样当它醒来时vruntime会远小于实施队列上的不论什么一个任务,于是它会漫长据有CPU,那显著是不创立的。
之所以那要对唤醒职分的vruntime举行局地调度,我们能够看见。这里是用min_vruntime减去四个thresh,
本条thresh的测算过程正是将sysctl_sched_latency换算成进度的vruntime,而那几个sysctl_sched_latency
就是暗许的调解周期。单核CPU上相似为20ms。之所以要减去一个值是为着对睡眠进程做三个互补,
能让它醒来时能够异常的快的到CPU。
个人感到那么些规划很聪慧,曾经O(1)调整器有三个繁琐的公式(到前天笔者也未能记住),
用来分别交互式进程和CPU密集型进度,详细情形请參考ULK等书。而前几日CFS无须再利用非常复杂的公式了。
独有倘若常睡眠的经过,它被提醒时必定会有特别小的vruntime。能够登时施行,省却了十分的多差别平日情状的管理。
同临时间还要小心那句凝视 ensure we never gain time by being placed
backwards。
自然这里是给由于长日子睡觉而vruntime远远低于min_vruntime的长河补偿的,不过有个别进度仅仅睡眠非常的长时间,
这么在它恢复后vruntime依然出乎min_vruntime,无法让进程经过睡眠获得额外的施行时间。所以最后选用
计量出的补给时间与经过原来vruntime中的极大者。

到这里,place_entity就讲完了。

唯独作者有一个主题素材,为何计算thresh要用整个调治周期换算成vruntime?
个人认为应该用(调解周期 * 进度权重 /
全体进度总权重)再折算成vruntime才制造阿,用任何调整周期
是或不是补充太多了?

 

 

四、进程调解schedule

以下看下主动调解代码schedule。

[cpp] view
plaincopy

  1. /* 
  2.  * schedule() is the main scheduler function. 
  3.  */  
  4. asmlinkage void __sched schedule(void)  
  5. {  
  6.     struct task_struct *prev, *next;  
  7.     unsigned long *switch_count;  
  8.     struct rq *rq;  
  9.     int cpu;  
  10. need_resched:  
  11.     preempt_disable(); //在此其间被侵夺大概现身故障。先禁绝它!  
  12.     cpu = smp_processor_id();  
  13.     rq = cpu_rq(cpu);  
  14.     rcu_qsctr_inc(cpu);  
  15.     prev = rq->curr;  
  16.     switch_count = &prev->nivcsw;  
  17.     release_kernel_lock(prev);  
  18. need_resched_nonpreemptible:  
  19.     spin_lock_irq(&rq->lock);  
  20.     update_rq_clock(rq);  
  21.     clear_tsk_need_resched(prev); //清除供给调治的位  
  22.     //state==0是TASK_RUNNING,不等于0便是筹算睡觉,符合规律状态下应该将它移出实施队列  
  23.     //不过还要检查下是还是不是有功率信号过来。要是有随机信号况且经过处于可间歇睡眠就提醒它  
  24.     //注意对于须求上床的进程。这里调用deactive_task将其移出队列何况on_rq也被清零  
  25.     //这个deactivate_task函数就不看了,非常easy  
  26.     if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {  
  27.         if (unlikely(signal_pending_state(prev->state, prev)))  
  28.             prev->state = TASK_RUNNING;  
  29.         else  
  30.             deactivate_task(rq, prev, 1);  
  31.         switch_count = &prev->nvcsw;  
  32.     }  
  33.     if (unlikely(!rq->nr_running))  
  34.         idle_balance(cpu, rq);  
  35.     //那四个函数都以生死攸关,大家以下剖析  
  36.     prev->sched_class->put_prev_task(rq, prev);  
  37.     next = pick_next_task(rq, prev);  
  38.     if (likely(prev != next)) {  
  39.         sched_info_switch(prev, next);  
  40.         rq->nr_switches++;  
  41.         rq->curr = next;  
  42.         ++*switch_count;  
  43.         //完结进度切换,不讲了,跟CFS不妨  
  44.         context_switch(rq, prev, next); /* unlocks the rq */  
  45.         /* 
  46.          * the context switch might have flipped the stack from under 
  47.          * us, hence refresh the local variables. 
  48.          */  
  49.         cpu = smp_processor_id();  
  50.         rq = cpu_rq(cpu);  
  51.     } else  
  52.         spin_unlock_irq(&rq->lock);  
  53.     if (unlikely(reacquire_kernel_lock(current) < 0))  
  54.         goto need_resched_nonpreemptible;  
  55.     preempt_enable_no_resched();  
  56.     //这里新进度也只怕有TIF_NEED_RESCHED标识,固然新进度也亟须调节则再调节三遍  
  57.     if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))  
  58.         goto need_resched;  
  59. }  

 

首先看put_prev_task,它等于put_prev_task_fair,后面一个基本上正是直接调用put_prev_entity

[cpp] view
plaincopy

  1. static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)  
  2. {  
  3.     /* 
  4.      * If still on the runqueue then deactivate_task() 
  5.      * was not called and update_curr() has to be done: 
  6.      */  
  7.     //记得这里的on_rq吗?在schedule函数中要是进度境况不是TASK_RUNNING,  
  8.     //那么会调用deactivate_task将prev移出施行队列,on_rq清零。由此这里也是独自有当  
  9.     //prev进度依然在实行态的时候才要求更新vruntime等消息。  
  10.     //假使prev进度由于被私吞只怕是因为岁月到了而被调治出去则on_rq仍然为1  
  11.     if (prev->on_rq)  
  12.         update_curr(cfs_rq);  
  13.     check_spread(cfs_rq, prev);  
  14.     //这里也一样,仅只有当prev进度仍在实行情状的时候才须求更新vruntime音讯  
  15.     //实际上正在cpu上推行的进程是不在红黑树中的,仅独有在守候CPU的进度才在红黑树  
  16.     //由此这里将调整出的长河又三回扩大红黑树。

    on_rq并不代表在红黑树中,而是表示在实施情状

      

  17.     if (prev->on_rq) {  

  18.         update_stats_wait_start(cfs_rq, prev);  
  19.         /* Put ‘current’ back into the tree. */  
  20.         //这几个函数也不跟进去了,就是把进度以(vruntime-min_vruntime)为key扩充到红黑树中  
  21.         __enqueue_entity(cfs_rq, prev);  
  22.     }  
  23.     //未有当前进程了。这一个当前过程将要pick_next_task中更新  
  24.     cfs_rq->curr = NULL;  
  25. }  

 

再回到schedule中看看pick_next_task函数。基本上也正是平素调用pick_next_task_fair

[cpp] view
plaincopy

  1. static struct task_struct *pick_next_task_fair(struct rq *rq)  
  2. {  
  3.     struct task_struct *p;  
  4.     struct cfs_rq *cfs_rq = &rq->cfs;  
  5.     struct sched_entity *se;  
  6.     if (unlikely(!cfs_rq->nr_running))  
  7.         return NULL;  
  8.     do {  
  9.         //那五个函数是重视,选取下一个要运维的任务  
  10.         se = pick_next_entity(cfs_rq);  
  11.         set_next_entity(cfs_rq, se);  
  12.         cfs_rq = group_cfs_rq(se);  
  13.     } while (cfs_rq);  
  14.     p = task_of(se);  
  15.     hrtick_start_fair(rq, p);  
  16.     return p;  
  17. }  

 

器重看下pick_next_entity和set_next_entity

[cpp] view
plaincopy

  1. static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)  
  2. {  
  3.     //__pick_next_entity正是一分区直属机关接选举择红黑树缓存的最左结点,也正是vruntime最小的结点  
  4.     struct sched_entity *se = __pick_next_entity(cfs_rq);  
  5.     //以下的wakeup_preempt_entity已经讲过。忘记的同桌能够到上边看下  
  6.     //这里正是前边所说的事先打点next和last进程,仅唯有当__pick_next_entity选出来的进度  
  7.     //的vruntime比next和last都小当先调节粒度时才轮到它实践,不然正是next或许last  
  8.     if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, se) < 1)  
  9.         return cfs_rq->next;  
  10.     if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, se) < 1)  
  11.         return cfs_rq->last;  
  12.     return se;  
  13. }  
  14. static void  
  15. set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)  
  16. {  
  17.     /* ‘current’ is not kept within the tree. */  
  18.     //这里怎么动静下规范会为假?笔者感到刚唤醒的进程恐怕不在rq上  
  19.     //可是回到地方去看了下,唤醒的历程也由此activate_task将on_rq置1了  
  20.     //新制造的进度on_rq也被置1,这里怎么状态会为假,想不出去  
  21.     //这里本人也測试了一晃。在标准为真假的路线上各设置了一个计数器  
  22.     //当条件为真经过了将近五100000次的时候条件为假独有三回。  
  23.     //所以我们能够感觉差十分的少都会一贯进去if语句块实施  
  24.     if (se->on_rq) {  
  25.         /*此处凝视是还是不是写错了?dequeued写成了enqueued? 
  26.          * Any task has to be enqueued before it get to execute on 
  27.          * a CPU. So account for the time it spent waiting on the 
  28.          * runqueue. 
  29.          */  
  30.         update_stats_wait_end(cfs_rq, se);  
  31.         //就是把结点从红黑树上取下来。

    方今说过,占用CPU的进程不在红黑树上

      

  32.         __dequeue_entity(cfs_rq, se);  

  33.     }  
  34.     update_stats_curr_start(cfs_rq, se);  
  35.     cfs_rq->curr = se;  //OK。在put_prev_entity中清空的curr在那间被更新  
  36.     //将进度推行总时间保存到prev_..中。那样经过本次调整的施行时间能够用以下公式计算:  
  37.     //进度此番施行已据有CPU时间 =  sum_exec_runtime – prev_sum_exec_runtime  
  38.     //这里sum_exec_runtime会在每一次石英钟tick中更新  
  39.     se->prev_sum_exec_runtime = se->sum_exec_runtime;  
  40. }  

 
到此schedule函数也讲罢了。

关于dequeue_task,dequeue_entity和__dequeue_entity三者差异
前两个差不太多。不一致的那部分自己也没看显著。。。首借使它们都会将on_rq清零。
本人感到是当进程要相差TASK_RUNNING状态时调用。这八个函数能够将经过取下奉行队列。

而__dequeue_entity不会将on_rq清零,仅仅是将经过从红黑树上取下,
本人觉着平常用在进度将获得CPU的事态,那时需要将它从红黑树取下,不过还要保留在rq上。

 

 

五、机械钟中断

接下去的情状正是石英钟中断,石英钟中断在time_init_hook中初叶化,中断函数为timer_interrupt
规行矩步举个例子以下门路
   timer_interrupt
–>do_timer_interrupt_hook
–>这里有贰个回调函数,在自己机器上測试调用的是tick_handle_oneshot_broadcast
–>从tick_handle_oneshot_broadcast前边一部分经过怎么走的没搞掌握,不经常光用kgdb追踪一下
–>反正最终是到了tick_handle_periodic
–>tick_periodic
–>update_process_times
–>scheduler_tick 那当中跟CFS相关的基本点就是立异了cfs_rq的时钟
–>通过回调函数调到task_tick_fair,没作什么事,直接步入了entity_tick
–>entity_tick那么些函数看下

[cpp] view
plaincopy

  1. static void  
  2. entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)  
  3. {  
  4.     /* 
  5.      * Update run-time statistics of the ‘current’. 
  6.      */  
  7.     update_curr(cfs_rq);  
  8.     //….非亲非故代码  
  9.     if (cfs_rq->nr_running > 1 || !sched_feat(WAKEUP_PREEMPT))  
  10.         check_preempt_tick(cfs_rq, curr);  
  11. }  

entity_tick函数正是翻新意况音讯,然后检測是不是满意抢占条件。
前面我们一贯忽视update_curr,这里一定要看一下了

[cpp] view
plaincopy

  1. static void update_curr(struct cfs_rq *cfs_rq)  
  2. {  
  3.     struct sched_entity *curr = cfs_rq->curr;  
  4.     u64 now = rq_of(cfs_rq)->clock; //这个clock刚刚在scheduler_tick中更新过  
  5.     unsigned long delta_exec;  
  6.     /* 
  7.      * Get the amount of time the current task was running 
  8.      * since the last time we changed load (this cannot 
  9.      * overflow on 32 bits): 
  10.      */  
  11.     //exec_start记录的是上二回调用update_curr的时日,大家用当下日子减去exec_start  
  12.     //就获得了从上次划算vruntime到前日经过又进行的流年,用那些时辰换算成vruntime  
  13.     //然后加到vruntime上,那全部是在__update_curr中结束的  
  14.     delta_exec = (unsigned long)(now – curr->exec_start);  
  15.     __update_curr(cfs_rq, curr, delta_exec);  
  16.     curr->exec_start = now;   
  17.     if (entity_is_task(curr)) {  
  18.         struct task_struct *curtask = task_of(curr);  
  19.         cpuacct_charge(curtask, delta_exec);  
  20.         account_group_exec_runtime(curtask, delta_exec);  
  21.     }  
  22. }  
  23. /* 
  24.  * Update the current task’s runtime statistics. Skip current tasks that 
  25.  * are not in our scheduling class. 
  26.  */  
  27. static inline void  
  28. __update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,  
  29.           unsigned long delta_exec)  
  30. {  
  31.     unsigned long delta_exec_weighted;  
  32.     //前边说的sum_exec_runtime就是在那间总括的,它约等于进度从创立開始占用CPU的总时间  
  33.     curr->sum_exec_runtime += delta_exec;   
  34.     //以下变量的weighted表示那几个值是从实践时间思量权重因素换算来的vruntime。再写三回那一个公式  
  35.     //vruntime(delta_exec_weighted) = 实际实行时间(delta_exe) * 1024 / 进程权重  
  36.     delta_exec_weighted = calc_delta_fair(delta_exec, curr);  
  37.     //将进度刚刚实行的时日换算成vruntime后立马加到进程的vruntime上。  
  38.     curr->vruntime += delta_exec_weighted;  
  39.     //由于有进度的vruntime变了,因而cfs_rq的min_vruntime恐怕也要扭转,更新它。  
  40.     //这几个函数简单,就不跟进去了,便是先取tmp = min(curr->vruntime,leftmost->vruntime)  
  41.     //然后cfs_rq->min_vruntime = max(tmp, cfs_rq->min_vruntime)  
  42.     update_min_vruntime(cfs_rq);  
  43. }   

OK。更新完CFS状态之后重临entity_tick中,这时须求检測是或不是满足抢占条件。这里也是CFS的要害之中的贰个

[cpp] view
plaincopy

  1. static void  
  2. check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)  
  3. {  
  4.     unsigned long ideal_runtime, delta_exec;  
  5.     //这里sched_slice跟下边讲过的sched_vslice非常象,只是sched_vslice换算成了vruntime,  
  6.     //而这里这些就是实在时间,未有通过换算,重回值的便是此进度在三个调整周期中应当实践的年月  
  7.     ideal_runtime = sched_slice(cfs_rq, curr);  
  8.     //上边提到过那个公式了,总结进度已攻下的CPU时间。假使超越了应有占据的日子(ideal_runtime)  
  9.     //则设置TIF_NEED_RESCHED标识,在剥离石英钟中断的经过中会调用schedule函数进行进度切换  
  10.     delta_exec = curr->sum_exec_runtime – curr->prev_sum_exec_runtime;  
  11.     if (delta_exec > ideal_runtime)  
  12.         resched_task(rq_of(cfs_rq)->curr);  
  13. }  

 

 

 

 

附:贰个小測试

看prio_to_weight数组,差别nice值的历程权重差别相当的大。最大权重是相当小权重的四千倍左右,
是还是不是代表即便同期有五个进度A和B在系统中施行。A的nice为-20,B的为19,那么A分配的实施时间
是B的四千倍啊?没有错。作者做了二个实验,先施行举个例子以下顺序,

[cpp] view
plaincopy

  1. int main()  
  2. {  
  3.     errno = 0;  
  4.     if(fork()) {  
  5.         setpriority(PRIO_PROCESS, 0, -20);  
  6.     } else {  
  7.         setpriority(PRIO_PROCESS, 0, 19);  
  8.     }     
  9.     if(errno) {  
  10.         printf(“failed/n”);  
  11.         exit(EXIT_FAILURE);  
  12.     }     
  13.     printf(“pid:%d/n”, getpid());  
  14.     while(1);  
  15.     return 0;  
  16. }  

 
接下来再插入举例以下模块

[cpp] view
plaincopy

  1. #define T1 (第二个进度的pid)  
  2. #define T2 (第1个经过的pid)  
  3. static int __init sched_test_init(void)  
  4. {  
  5.     struct task_struct *p;   
  6.     for_each_process(p) {  
  7.         if(p->pid == T1 || p->pid == T2)   
  8.             printk(“%d runtime:%llu/n”, p->pid, p->se.sum_exec_runtime);  
  9.     }     
  10.     return -1; //再次回到-1堤防模块真正插入,大家唯有须求打字与印刷出地方的音信就可以见到了。  
  11. }  

 
再dmesg查看结果,笔者測试过两回。二遍设置nice分别为0和6,那么权重之比为
1024 / 272 = 3.7647。结果进行时间之比为 146390068851 / 38892147894 =
3.7640
可以见到见到结果一定左近,
还会有壹次设置nice分别为-20和19,权重之比为88761 / 15 = 5917.伍仟,
结果进行时间之比为187800781308 / 32603290 = 5760.1788。也分外临近。
可以看出,上面包车型地铁权重与施行时间成正比的下结论是白手起家的。
其实,当本身推行二个nice为-20的顺序后,整个系列很卡,差了一点儿成了幻灯片,
也验证nice值的例外带来的间隔很显然。

另外有好几值得说,即使全数种类特别卡,可是对鼠标键盘的响应照旧一点也不慢。
自己打字的时候大概不会有哪些延迟,那也认证。就算CFS未有经过复杂的阅历公式区分
交互式进程。但是它的统一计划思路使他天生地对交互式进度的响应可能比O(1)调节还要好。

(总计:1、在经超过实际践时,其vruntime牢固的充裕,它在红黑树中三回九转向右移动。由于越主要的历程vruntime加多越慢,由此他们向右移动的进程也越慢。那样其被调解的时机要超越次要进度,那恰好是大家必得的。2、假使进度步入眠眠,则其vruntime保持不改变,由于每一个行列min_vruntime同期会增加(由于她们是单调的),那么睡眠进度醒来后,在红黑树中的地点会更靠左。由于其键值变得越来越小了。注意底层使用的是红黑树结构)