Linux进程管理之CFS调度策略

　　CFS原理
　　CFS（CompletelyFairScheduler），也即是完全公平调度器。
　　CFS的产生就是为了在真实的硬件上模拟理想的多任务处理器，使每个进程都能够公平的获得CPU。
　　CFS调度器没有时间片的概念，CFS的理念就是让每个进程拥有相同的使用CPU的时间。比如有n个可运行的进程，那么每个进程将能获取的处理时间为1n。
　　在CFS调度器中引用权重来代表进程的优先级。各个进程按照权重的比例来分配使用CPU的时间。比如2个进程A和B，A的权重为100，B的权重为200，那么A获得的CPU的时间为100（100200）33，B进程获得的CPU的时间为200（100200）67。
　　在引入权重之后，在一个调度周期中分配给进程的运行时间计算公式如下：
　　实际运行时间调度周期进程权重所有进程权重之和
　　可以看到，权重越大，分到的运行时间越多。
　　调度周期：在某个时间长度可以保证运行队列中的每个进程至少运行一次，我们把这个时间长度称为调度周期。也称为调度延迟，因为一个进程等待被调度的延迟时间是一个调度周期。
　　调度最小粒度：为了防止进程切换太频繁，进程被调度后应该至少运行一小段时间，我们把这个时间长度称为调度最小粒度。
　　调度周期的默认值是20毫秒，调度最小粒度的默认值是4毫秒，如下所示，两者的单位都是纳秒。默认调度周期20msunsignedintsysctlschedlatency20000000ULL；默认调度最小粒度4msunsignedintsysctlschedmingranularity4000000ULL；默认一个调度周期内的进程数：sysctlschedlatencysysctlschedmingranularitystaticunsignedintschednrlatency5；
　　如果运行队列中的进程数量太多，导致把调度周期sysctlschedlatency平分给进程时的时间片小于调度最小粒度，那么调度周期取调度最小粒度进程数量。
　　CFS调度器中使用nice值（取值范围为〔2019〕）作为进程获取处理器运行比的权重：nice值越高（优先级越低）的进程获得的CPU使用的权重越低。
　　在用户态进程的优先级nice值与CFS调度器中的权重又有什么关系？
　　在内核中通过priotoweight数组进行nice值和权重的转换。staticconstintpriotoweight〔40〕｛2088761，71755，56483，46273，36291，1529154，23254，18705，14949，11916，109548，7620，6100，4904，3906，53121，2501，1991，1586，1277，01024，820，655，526，423，5335，272，215，172，137，10110，87，70，56，45，1536，29，23，18，15，｝；
　　从nice和权重的对应值可知，nice值为0的权重为1024（默认权重），nice值为1的权重为820，nice值为15的权重值为36，nice值为19的权重值为15。
　　例如：假设调度周期为12ms，2个相同nice的进程其权重也相同，那么2个进程各自的运行时间为6ms。
　　假设进程A和B的nice值分别为0、1，那么权重也就分别为1024、820。因此，
　　A实际运行时间为121024（1024820）6。66ms，
　　B实际运行时间为12820（1024820）5。34ms。
　　从结果来看，2个进程运行时间时不一样的。由于A的权重高，优先级大，会出现A一直被调度，而B最后被调度，这就失去了公平性，所以CFS的存在就是为了解决这种不公平性。
　　因此为了让每个进程完全公平调度，因此就引入了一个vruntime（虚拟运行时间，virtualruntime）的概念，每个调度实体都有一个vruntime，该vruntime根据调度实体的调度而不停的累加，CFS根据vruntime的大小来选择调度实体。
　　调度实体的结构如下：structschedentity｛structloadweightload；调度实体的负载权重值structrbnoderunnode；用于添加到CFS运行队列的红黑树中的节点unsignedintonrq；用于表示是否在运行队列中u64execstart；当前调度实体的开始运行时间u64sumexecruntime；调度实体执行的总时间虚拟运行时间，在时间中断或者任务状态发生改变时会更新其会不停的增长，增长速度与load权重成反比，load越高，增长速度越慢，就越可能处于红黑树最左边被调度每次时钟中断都会修改其值。注意其值为单调递增，在每个调度器的时钟中断时当前进程的虚拟运行时间都会累加。单纯的说就是进程们都在比谁的vruntime最小，最小的将被调度u64vruntime；虚拟运行时间，这个时间用于在CFS运行队列中排队u64prevsumexecruntime；上一个调度实体运行的总时间。。。ifdefCONFIGFAIRGROUPSCHEDstructschedentityparent；指向调度实体的父对象rqonwhichthisentityis（tobe）queued：structcfsrqcfsrq；指向调度实体归属的CFS队列，也就是需要入列的CFS队列rqownedbythisentitygroup：structcfsrqmyq；指向归属于当前调度实体的CFS队列endif｝；
　　虚拟时间和实际时间的关系如下：
　　虚拟运行时间实际运行时间（NICE0LOAD进程权重）
　　其中，NICE0LOAD是nice为0时的权重（默认），也即是1024。也就是说，nice值为0的进程实际运行时间和虚拟运行时间相同。
　　虚拟运行时间一方面跟进程运行时间有关，另一方面跟进程优先级有关。
　　进程权重越大，运行同样的实际时间，vruntime增长的越慢。
　　一个进程在一个调度周期内的虚拟运行时间大小为：
　　vruntime进程在一个调度周期内的实际运行时间1024进程权重
　　（调度周期进程权重所有进程总权重）1024进程权重
　　调度周期1024所有进程总权重
　　可以看到，一个进程在一个调度周期内的vruntime值大小是不和该进程自己的权重相关的，所以所有进程的vruntime值大小都是一样的。
　　接着上述的例子，通过虚拟运行时间公式可得：
　　A虚拟运行时间为6。66（10241024）6。66ms，
　　B虚拟运行时间为5。34（1024820）6。66ms，
　　在一个调度周期过程中，各个调度实体的vruntime都是累加的过程，保证了在一个调度周期结束后，每个调度实体的vruntime值大小都是一样的。
　　由于权重越高，应该优先的得到运行，因此CFS采用虚拟运行时间越小，越先调度。
　　当权重越高的进程随着调度的次数多，其vruntime的累加也就越多。当其vruntime的累加大于其他低优先级进程的vruntime时，低优先级的进程得以调度。这就保证了每个进程都可以调度而不会出现高优先级的一直得到调度，而优先级低的进程得不到调度而产生饥饿。
　　一言以蔽之：在CFS中，不管权重高低，根据vruntime大小比较，大家都轮着使用CPU。
　　当然，根据一个调度周期中分配给进程的实际运行时间计算公式可知，在一个调度周期内，虽然大家都轮着使用CPU，但是实际运行时间的多少和权重也是有关的，权重越高，总的实际运行的时间也就越多。在一个调度周期结束后，各个调度实体的vruntime最终还是相等的。
　　那么在CFS中vruntime是怎么使用的呢？
　　CFS中的就绪队列是一棵以vruntime为键值的红黑树，虚拟时间越小的进程越靠近整个红黑树的最左端。因此，调度器每次选择位于红黑树最左端的那个进程，该进程的vruntime最小，也就最应该优先调度。
　　实际获取最左叶子节点时并不会遍历树，而是vruntime最小的节点已经缓存在了rbleftmost字段中了，因此CFS很快可以获取vruntime最小的节点。
　　其中红黑树的结构如下：
　　CFS调度时机
　　与CFS相关的有如下几个过程：创建新进程：创建新进程时，需要设置新进程的vruntime值以及将新进程加入红黑树中。并判断是否需要抢占当前进程。进程的调度：进程调度时，需要把当前进程加入红黑树中，还要从红黑树中挑选出下一个要运行的进程。进程唤醒：唤醒进程时，需要调整睡眠进程的vruntime值，并且将睡眠进程加入红黑树中。并判断是否需要抢占当前进程。时钟周期中断：在时钟中断周期函数中，需要更新当前运行进程的vruntime值，并判断是否需要抢占当前进程。
　　创建新进程
　　创建新进程的系统调用fork，vfork，clone。这三个系统调用最终都是调用dofork（）函数。在dofork（）函数中，主要就是设置新进程的vruntime值，将新进程加入到红黑树中，判断新进程是否可以抢占当前进程。
　　doforkwakeupnewtasktasknewfair设置新进程的vruntime值，并将其加入就绪队列中checkpreemptcurr检查新进程是否可以抢占当前进程
　　tasknewfair实现如下：staticvoidtasknewfair（structrqrq，structtaskstructp）｛structcfsrqcfsrqtaskcfsrq（p）；structschedentitysepse，currcfsrqcurr；intthiscpusmpprocessorid（）；schedinfoqueued（p）；updatecurr（cfsrq）；更新当前进程的vruntime值placeentity（cfsrq，se，1）；设置新进程的vruntime值，1表示是新进程currwillbeNULLifthechildbelongstoadifferentgroupsysctlschedchildrunsfirst值表示是否设置了让子进程先运行if（sysctlschedchildrunsfirstthiscputaskcpu（p）currcurrvruntimesevruntime）｛Uponrescheduling，schedclass：：putprevtask（）willplacecurrentwithinthetreebasedonitsnewkeyvalue。swap（currvruntime，sevruntime）；当子进程的vruntime值大于父进程的vruntime时，交换两个进程的vruntime值｝enqueuetaskfair（rq，p，0）；将新任务加入到就绪队列中设置TIFNEEDRESCHED标志值，该标记标志进程是否需要重新调度，如果设置了，就会发生调度reschedtask（rqcurr）；｝
　　该函数给新进程设置一个新的vruntime，然后加入到就绪队列中，等待调度。
　　checkpreemptcurr在CFS中对应的为checkpreemptwakeup函数，其实现如下：staticvoidcheckpreemptwakeup（structrqrq，structtaskstructp）｛structtaskstructcurrrqcurr；structcfsrqcfsrqtaskcfsrq（curr）；structschedentitysecurrse，psepse；unsignedlonggran；。。。gran为进程调度粒度gransysctlschedwakeupgranularity；10msif（unlikely（seload。weight！NICE0LOAD））grancalcdeltafair（gran，seload）；计算调度粒度调度粒度的设置，是为了防止这么一个情况：新进程的vruntime值只比当前进程的vruntime小一点点，如果此时发生重新调度，则新进程只运行一点点时间后，其vruntime值就会大于前面被抢占的进程的vruntime值，这样又会发生抢占，所以这样的情况下，系统会发生频繁的切换。故，只有当新进程的vruntime值比当前进程的vruntime值小于调度粒度之外，才发生抢占。所以，当前进程的虚拟运行时间sevruntime比下一个进程psevruntime大于一个调度粒度，说明当前进程应该被抢占，应该切换出去让别vruntime小的进程进行运行，因此给当前进程设置是一个重新调度标记TIFNEEDRESCHED，当某个时机根据该标记进行调用schedule（），这时会重新选择一个进程进行切换if（psevruntimegransevruntime）reschedtask（curr）；｝
　　该功能就是根据调度粒度，判断是否需要设置被抢占标记，若需要，这调用
　　reschedtask把当前进程设置成被抢占标记TIFNEEDRESCHED，该标记说明当前进程运行的时间够多的了，应该切换出去，让出CPU让让别的进程运行。staticvoidreschedtask（structtaskstructp）｛intcpu；assertspinlocked（taskrq（p）lock）；if（unlikely（testtskthreadflag（p，TIFNEEDRESCHED）））return；设置被被抢占标记settskthreadflag（p，TIFNEEDRESCHED）；cputaskcpu（p）；if（cpusmpprocessorid（））return；NEEDRESCHEDmustbevisiblebeforewetestpollingsmpmb（）；if（！tskispolling（p））smpsendreschedule（cpu）；｝
　　设置完TIFNEEDRESCHED不代表当前进程立马就切换出去了，而是等待一定时机，然后会根据TIFNEEDRESCHED标记调用schedule（）进行调度切换。
　　进程的调度
　　进程调度的主要入口点是schedule函数，它正是内核其他部分用于调用进程调度器的入口：选择哪个进程可以运行，何时投入运行。
　　schedule通常要和一个具体的调度类相关联，也即是，它会找到最高优先级的调度类，然后从就绪队列中选择下一个该运行的进程。
　　当调用schedule（）进行任务切换的时候，调度器调用picknexttask函数选择下一个将要执行的任务，这是相对默认nice值进程的进程而言的。asmlinkagevoidschedschedule（void）｛prev表示调度之前的进程，next表示调度之后的进程structtaskstructprev，next；longswitchcount；structrqrq；intcpu；needresched：preemptdisable（）；关闭内核抢占cpusmpprocessorid（）；获取所在的cpurqcpurq（cpu）；获取cpu对应的运行队列rcuqsctrinc（cpu）；prevrqcurr；让prev成为当前进程switchcountprevnivcsw；释放全局内核锁，并开thiscpu的中断releasekernellock（prev）；needreschednonpreemptible：updaterqclock（rq）；更新运行队列的时钟值。。。if（unlikely（！rqnrrunning））idlebalance（cpu，rq）；对应到CFS，则为putprevtaskfairprevschedclassputprevtask（rq，prev）；通知调度器类当前运行进程要被另一个进程取代picknexttask以优先级从高到底依次检查每个调度类，从最高优先级的调度类中选择最高优先级的进程作为下一个应执行进程（若其余都睡眠，则只有当前进程可运行，就跳过下面了）nextpicknexttask（rq，prev）；选择需要进行切换的task。。。｝
　　在选择下一个进程前，先调用putprevtask（对应到CFS为putprevtaskfair），计算下当前进程的运行时间，根据当前运行时间计算出虚拟运行时间，并累加到vruntime，然后把当前进程根据vruntime重新加入到就绪队列红黑树中，等待下一次被调度。
　　putprevtaskfair
　　putpreventity
　　updatecurr
　　updatecurr更新当前调度实体的实际运行时间和虚拟运行时间
　　enqueueentity把当前调度实体重新加入到就绪队列红黑树中等待下一次调度cfsrq：可运行队列对象。curr：当前进程调度实体。deltaexec：实际运行的时间。updatecurr（）函数主要完成以下几个工作：更新进程调度实体的总实际运行时间。根据进程调度实体的权重值，计算其使用的虚拟运行时间。把计算虚拟运行时间的结果添加到进程调度实体的vruntime字段。staticinlinevoidupdatecurr（structcfsrqcfsrq，structschedentitycurr，unsignedlongdeltaexec）｛unsignedlongdeltaexecweighted；u64vruntime；schedstatset（currexecmax，max（（u64）deltaexec，currexecmax））；增加当前进程总实际运行的时间currsumexecruntimedeltaexec；更新cfsrq的实际执行时间cfsrqexecclockschedstatadd（cfsrq，execclock，deltaexec）；根据实际运行时间计算虚拟运行时间并累加到当前进程的虚拟运行时间deltaexecweighteddeltaexec；根据实际运行时间计算其使用的虚拟运行时间if（unlikely（currload。weight！NICE0LOAD））｛deltaexecweightedcalcdeltafair（deltaexecweighted，currload）；｝currvruntimedeltaexecweighted；更新进程的虚拟运行时间maintaincfsrqminvruntimetobeamonotonicincreasingvaluetrackingtheleftmostvruntimeinthetree。if（firstfair（cfsrq））｛vruntimeminvruntime（currvruntime，picknextentity（cfsrq）vruntime）；｝elsevruntimecurrvruntime；minvruntime记录CFS运行队列上vruntime最小值，但是实际上minvruntime只能单调递增，所以，如果当前进程vruntime比minvruntime小，是不会更新minvruntime的。那么minvruntime的作用的是什么呢？试想一下如果一个进程睡眠了很长时间，则它的vruntime非常小，一旦它被唤醒，将持续占用CPU，很容易引发进程饥饿。CFS调度器会根据minvruntime设置一个合适的vruntime值给被唤醒的进程，既要保证它能优先被调度，又要保证其他进程也能得到合理调度。cfsrqminvruntimemaxvruntime（cfsrqminvruntime，vruntime）；｝
　　该函数的功能如下：更新进程调度实体的总实际运行时间。根据进程调度实体的权重值，计算其虚拟运行时间。把计算虚拟运行时间的结果添加到进程调度实体的vruntime字段。
　　将调度实体加入红黑树中staticvoidenqueueentity（structcfsrqcfsrq，structschedentityse）｛structrbnodelinkcfsrqtaskstimeline。rbnode；红黑树根节点structrbnodeparentNULL；structschedentityentry；s64keyentitykey（cfsrq，se）；当前进程调度实体的虚拟运行时间intleftmost1；Findtherightplaceintherbtree：while（link）｛把当前调度实体插入到运行队列的红黑树中parentlink；entryrbentry（parent，structschedentity，runnode）；Wedontcareaboutcollisions。Nodeswiththesamekeystaytogether。if（keyentitykey（cfsrq，entry））｛比较虚拟运行时间linkparentrbleft；｝else｛linkparentrbright；leftmost0；｝｝Maintainacacheofleftmosttreeentries（itisfrequentlyused）：if（leftmost）缓存最左叶子节点cfsrqrbleftmostserunnode；rblinknode（serunnode，parent，link）；把节点插入到红黑树中rbinsertcolor（serunnode，cfsrqtaskstimeline）；｝
　　enqueueentity（）函数的主要工作如下：获取运行队列红黑树的根节点。获取当前进程调度实体的虚拟运行时间。把当前进程调度实体添加到红黑树中。缓存红黑树最左端节点。对红黑树进行平衡操作。
　　获取下一个合适的调度实体staticinlinestructtaskstructpicknexttask（structrqrq，structtaskstructprev）｛conststructschedclassclass；structtaskstructp；Optimization：weknowthatifalltasksareinthefairclasswecancallthatfunctiondirectly：选择时并不是想象中的直接按照调度器的优先级对所有调度器类进行遍历，而是假设下一个运行的进程属于cfs调度器类，毕竟，系统中绝大多数的进程都是由cfs调度器进行管理，这样做可以从整体上提高执行效率。if（likely（rqnrrunningrqcfs。nrrunning））｛pfairschedclass。picknexttask（rq）；if（likely（p））returnp；｝classschedclasshighest；defineschedclasshighest（rtschedclass）for（；；）｛pclasspicknexttask（rq）；if（p）returnp；WillneverbeNULLastheidleclassalwaysreturnsanonNULLp：classclassnext；｝｝
　　在picknexttask中会遍历所有的调度类，然后从就绪队列中选取一个最合适的调度实体进行调度。
　　对于完全公平调度算法（CFS），会调用fairschedclass。picknexttask（）函数，从fairschedclass中可知，也即是调用picknexttaskfair。staticconststructschedclassfairschedclass｛。nextidleschedclass，。enqueuetaskenqueuetaskfair，。dequeuetaskdequeuetaskfair，。yieldtaskyieldtaskfair，。checkpreemptcurrcheckpreemptwakeup，。picknexttaskpicknexttaskfair，。putprevtaskputprevtaskfair，ifdefCONFIGSMP。loadbalanceloadbalancefair，。moveonetaskmoveonetaskfair，endif。setcurrtasksetcurrtaskfair，。taskticktasktickfair，。tasknewtasknewfair，｝；
　　picknexttaskfair调用过程如下：picknexttaskfairpicknextentitypicknextentity从就绪队列中选取一个最合适的调度实体（虚拟时间最小的调度实体）setnextentity把选中的进程从红黑树中移除，并更新红黑树
　　从schedule调用可知，其在选择下一个运行任务前，先计算当前进程（待切换出去的进程）的时间运行时间，然后根据实际运行时间计算虚拟运行时间，在根据虚拟运行时间把当前进程加入到就绪队列中的红黑树中等待下一次调度。
　　其次，从就绪队列的红黑树中选择虚拟运行时间最小的任务作为即将运行的任务。
　　进程唤醒
　　进程的默认唤醒函数是trytowakeup（），该函数主要是调整睡眠进程的vruntime值，以及把睡眠进程加入红黑树中，并判断是否可以发生抢占。
　　调用关系如下：
　　trytowakeupactivatetaskenqueuetaskcheckpreemptcurr
　　时钟周期中断
　　周期性调度器是基于schedulertick函数实现。系统都是以tick（节拍）来执行各种调度与统计，节拍可以通过CONFIGHZ宏来控制。内核会以1HZms为周期来执行周期性调度，这也是CFS实现的关键。CFS调度类会根据这个节拍来对所有进程进行记账。每个CPU都会拥有自己的周期性调度器。周期性调度器可以把当前进程设置为needresched状态，等待合适的时机当前的进程就会被重新调度。
　　时钟周期中断函数的调用过程：
　　tickperiodicupdateprocesstimesschedulerticktasktickfairentitytickupdatecurrcheckpreempttick
　　在CFS中，schedulertick会调用具体实现tasktickfair，在tasktickfair中会从当前进程开始获取每个调度实体，对每个调度实体进行调用entitytick，在entitytick中更新调度实体的实际运行时间和虚拟运行时间，同时检查是否需要重新调度。staticvoidcheckpreempttick（structcfsrqcfsrq，structschedentitycurr）｛unsignedlongidealruntime，deltaexec；idealruntime为一个调度周期内理想的运行时间，也即是为调度周期进程权重所有进程权重之和idealruntimeschedslice（cfsrq，curr）；sumexecruntime指进程总共执行的实际时间；prevsumexecruntime指上次该进程被调度时已经占用的实际时间。deltaexeccurrsumexecruntimecurrprevsumexecruntime；deltaexec这次调度占用实际时间，如果大于idealruntime，则应该被抢占了if（deltaexecidealruntime）reschedtask（rqof（cfsrq）curr）；｝
　　若当前进程运行的时间超过时间限制，则把当前进程设置为被抢占重新调度标记TIFNEEDRESCHED，待一定时机后会根据TIFNEEDRESCHED标记调用schedule（）进行调度切换。关于一定的时机，后续文章进行分析。