一文读懂Linux任务间调度原理和整个执行过程

　　一。前言
　　在前文中，我们分析了内核中进程和线程的统一结构体taskstruct，并分析进程、线程的创建和派生的过程。在本文中，我们会对任务间调度进行详细剖析，了解其原理和整个执行过程。由此，进程、线程部分的大体框架就算是介绍完了。本节主要分为三个部分：Linux内核中常见的调度策略，调度的基本结构体以及调度发生的整个流程。下面将详细展开说明。二。调度策略
　　Linux作为一个多任务操作系统，将每个CPU的时间划分为很短的时间片，再通过调度器轮流分配给各个任务使用，因此造成多任务同时运行的错觉。为了维护CPU时间，Linux通过事先定义的节拍率（内核中表示为HZ），触发时间中断，并使用全局变量Jiffies记录了开机以来的节拍数。每发生一次时间中断，Jiffies的值就加1。节拍率HZ是内核的可配选项，可以设置为100、250、1000等。不同的系统可能设置不同的数值，可以通过查询bootconfig内核选项来查看它的配置值。
　　Linux的调度策略主要分为实时任务和普通任务。实时任务需求尽快返回结果，而普通任务则没有较高的要求。在前文中我们提到了taskstruct中调度策略相应的变量为policy，调度优先级有prio，staticprio，normalprio，rtpriority几个。优先级其实就是一个数值，对于实时进程来说，优先级的范围是099；对于普通进程，优先级的范围是100139。数值越小，优先级越高。2。1实时调度策略
　　实时调度策略主要包括以下几种SCHEDFIFO：先来先出型策略，顾名思义相同优先级的情况下先到先得SCHEDRR：轮询策略，注重公平性，相同优先级的任务会使用相同的时间片轮流执行SCHEDDEADLINE：根据任务结束时间来进行调度，即将结束的拥有较高的优先级2。2普通调度策略
　　普通调度策略主要包括以下几种：SCHEDNORMAL：普通任务SCHEDBATCH：后台任务，优先级较低SCHEDIDLE：空闲时间才会跑的任务CFS：完全公平调度策略，较为特殊的一种策略。CFS会为每一个任务安排一个虚拟运行时间vruntime。如果一个任务在运行，随着一个个CPU时钟tick的到来，任务的vruntime将不断增大，而没有得到执行的任务的vruntime不变。由此，当调度的时候，vruntime较小的就拥有较高的优先级。vruntime的实际计算方式和权重相关，由此保证了优先级高的按比例拥有更多的执行时间，从而达到完全公平。三。调度相关的架构体
　　首先，我们需要一个结构体去执行调度策略，即schedclass。该类有几种实现方式stopschedclass优先级最高的任务会使用这种策略，会中断所有其他线程，且不会被其他任务打断；dlschedclass就对应上面的deadline调度策略；rtschedclass就对应RR算法或者FIFO算法的调度策略，具体调度策略由进程的taskstructpolicy指定；fairschedclass就是普通进程的调度策略；idleschedclass就是空闲进程的调度策略。其次，我们需要一个调度结构体来集合调度信息，用于调度，即schedentity，主要有structschedentityse：普通任务调度实体structschedrtentityrt：实时调度实体structscheddlentitydl：DEADLINE调度实体
　　普通任务调度实体源码如下，这里面包含了vruntime和权重loadweight，以及对于运行时间的统计。structschedentity｛Forloadbalancing：structloadweightload；unsignedlongrunnableweight；structrbnoderunnode；structlistheadgroupnode；unsignedintonrq；u64execstart；u64sumexecruntime；u64vruntime；u64prevsumexecruntime；u64nrmigrations；structschedstatisticsstatistics；ifdefCONFIGFAIRGROUPSCHEDintdepth；structschedentityparent；rqonwhichthisentityis（tobe）queued：structcfsrqcfsrq；rqownedbythisentitygroup：structcfsrqmyq；endififdefCONFIGSMPPerentityloadaveragetracking。Putintoseparatecachelinesoitdoesnotcollidewithreadmostlyvaluesabove。structschedavgavg；endif｝；
　　在调度时，多个任务调度实体会首先区分是实时任务还是普通任务，然后通过以时间为顺序的红黑树结构组合起来，vruntime最小的在树的左侧，vruntime最多的在树的右侧。以CFS策略为例，则会选择红黑树最左边的叶子节点作为下一个将获得CPU的任务。而这颗红黑树，我们称之为运行时队列（runqueue），即structrq。Thisisthemain，perCPUrunqueuedatastructure。Lockingrule：thoseplacesthatwanttolockmultiplerunqueues（suchastheloadbalancingorthethreadmigrationcode），lockacquireoperationsmustbeorderedbyascendingrunqueue。structrq｛runqueuelock：rawspinlocktlock；nrrunningandcpuloadshouldbeinthesamecachelinebecauseremoteCPUsuseboththesefieldswhendoingloadcalculation。unsignedintnrrunning；。。。。。。defineCPULOADIDXMAX5unsignedlongcpuload〔CPULOADIDXMAX〕；。。。。。。captureloadfromalltasksonthisCPU：structloadweightload；unsignedlongnrloadupdates；u64nrswitches；structcfsrqcfs；structrtrqrt；structdlrqdl；。。。。。。ThisispartofaglobalcounterwhereonlythetotalsumoverallCPUsmatters。AtaskcanincreasethiscounterononeCPUandifitgotmigratedafterwardsitmaydecreaseitonanotherCPU。Alwaysupdatedundertherunqueuelock：unsignedlongnruninterruptible；structtaskstructcurr；structtaskstructidle；structtaskstructstop；unsignedlongnextbalance；structmmstructprevmm；unsignedintclockupdateflags；u64clock；Ensurethatallclocksareinthesamecachelineu64clocktaskcachelinealigned；u64clockpelt；unsignedlonglostidletime；atomictnriowait；。。。。。。calcloadrelatedfieldsunsignedlongcalcloadupdate；longcalcloadactive；。。。。。。｝；
　　其中包含结构体cfsrq，其定义如下，主要是CFS调度相关的结构体，主要有权值相关变量、vruntime相关变量以及红黑树指针，其中结构体rbrootcached即为红黑树的节点CFSrelatedfieldsinarunqueuestructcfsrq｛structloadweightload；unsignedlongrunnableweight；unsignedintnrrunning；unsignedinthnrrunning；u64execclock；u64minvruntime；ifndefCONFIG64BITu64minvruntimecopy；endifstructrbrootcachedtaskstimeline；currpointstocurrentlyrunningentityonthiscfsrq。ItissettoNULLotherwise（i。ewhennonearecurrentlyrunning）。structschedentitycurr；structschedentitynext；structschedentitylast；structschedentityskip；。。。。。。｝；
　　对结构体dlrq有类似的定义，运行队列由红黑树结构体构成，并按照deadline策略进行管理Deadlineclassrelatedfieldsinarunqueuestructdlrq｛runqueueisanrbtree，orderedbydeadlinestructrbrootcachedroot；unsignedlongdlnrrunning；ifdefCONFIGSMPDeadlinevaluesofthecurrentlyexecutingandtheearliestreadytaskonthisrq。Cachingthesefacilitatesthedecisionwhetherornotareadybutnotrunningtaskshouldmigratesomewhereelse。struct｛u64curr；u64next；｝earliestdl；unsignedlongdlnrmigratory；intoverloaded；Tasksonthisrqthatcanbepushedaway。Theyarekeptinanrbtree，orderedbytasksdeadlines，withcachingoftheleftmost（earliestdeadline）element。structrbrootcachedpushabledltasksroot；elsestructdlbwdlbw；endifActiveutilizationforthisrunqueue：increasedwhenataskwakesup（becomesTASKRUNNING）anddecreasedwhenataskblocksu64runningbw；Utilizationofthetasksassignedtothisrunqueue（includingthetasksthatareinrunqueueandthetasksthatexecutedonthisCPUandblocked）。Increasedwhenataskmovestothisrunqueue，anddecreasedwhenthetaskmovesaway（migrates，changesschedulingpolicy，orterminates）。Thisisneededtocomputetheinactiveutilizationfortherunqueue（inactiveutilizationthisbwrunningbw）。u64thisbw；u64extrabw；InverseofthefractionofCPUutilizationthatcanbereclaimedbytheGRUBalgorithm。u64bwratio；｝；
　　对于实施队列相应的rtrq则有所不同，并没有用红黑树实现。RealTimeclassesrelatedfieldinarunqueue：structrtrq｛structrtprioarrayactive；unsignedintrtnrrunning；unsignedintrrnrrunning；ifdefinedCONFIGSMPdefinedCONFIGRTGROUPSCHEDstruct｛intcurr；highestqueuedrttaskprioifdefCONFIGSMPintnext；nexthighestendif｝highestprio；endififdefCONFIGSMPunsignedlongrtnrmigratory；unsignedlongrtnrtotal；intoverloaded；structplistheadpushabletasks；endifCONFIGSMPintrtqueued；intrtthrottled；u64rttime；u64rtruntime；Nestsinsidetherqlock：rawspinlocktrtruntimelock；ifdefCONFIGRTGROUPSCHEDunsignedlongrtnrboosted；structrqrq；structtaskgrouptg；endif｝；
　　下面再看看调度类schedclass，该类以函数指针的形式定义了诸多队列操作，如enqueuetask向就绪队列中添加一个任务，当某个任务进入可运行状态时，调用这个函数；dequeuetask将一个任务从就绪队列中删除；yieldtask将主动放弃CPU；yieldtotask主动放弃CPU并执行指定的taskstruct；checkpreemptcurr检查当前任务是否可被强占；picknexttask选择接下来要运行的任务；putprevtask用另一个进程代替当前运行的任务；setcurrtask用于修改调度策略；tasktick每次周期性时钟到的时候，这个函数被调用，可能触发调度。taskdead：进程结束时调用switchedfrom、switchedto：进程改变调度器时使用priochanged：改变进程优先级structschedclass｛conststructschedclassnext；void（enqueuetask）（structrqrq，structtaskstructp，intflags）；void（dequeuetask）（structrqrq，structtaskstructp，intflags）；void（yieldtask）（structrqrq）；bool（yieldtotask）（structrqrq，structtaskstructp，boolpreempt）；void（checkpreemptcurr）（structrqrq，structtaskstructp，intflags）；Itistheresponsibilityofthepicknexttask（）methodthatwillreturnthenexttasktocallputprevtask（）ontheprevtaskorsomethingequivalent。MayreturnRETRYTASKwhenitfindsahigherprioclasshasrunnabletasks。structtaskstruct（picknexttask）（structrqrq，structtaskstructprev，structrqflagsrf）；void（putprevtask）（structrqrq，structtaskstructp）；。。。。。。void（setcurrtask）（structrqrq）；void（tasktick）（structrqrq，structtaskstructp，intqueued）；void（taskfork）（structtaskstructp）；void（taskdead）（structtaskstructp）；Theswitchedfrom（）callisallowedtodroprqlock，thereforewecannotassumetheswitchedfromswitchedtopairisserliazedbyrqlock。Theyarehoweverserializedbyppilock。void（switchedfrom）（structrqthisrq，structtaskstructtask）；void（switchedto）（structrqthisrq，structtaskstructtask）；void（priochanged）（structrqthisrq，structtaskstructtask，intoldprio）；unsignedint（getrrinterval）（structrqrq，structtaskstructtask）；void（updatecurr）（structrqrq）；defineTASKSETGROUP0defineTASKMOVEGROUP1。。。。。。｝；
　　调度类分为下面几种：externconststructschedclassstopschedclass；externconststructschedclassdlschedclass；externconststructschedclassrtschedclass；externconststructschedclassfairschedclass；externconststructschedclassidleschedclass；
　　队列操作中函数指针指向不同策略队列的实际执行函数函数，在linuxkernelsched目录下，fair。c、idle。c、rt。c等文件对不同类型的策略实现了不同的函数，如fair。c中定义了Alltheschedulingclassmethods：conststructschedclassfairschedclass｛。nextidleschedclass，。enqueuetaskenqueuetaskfair，。dequeuetaskdequeuetaskfair，。yieldtaskyieldtaskfair，。yieldtotaskyieldtotaskfair，。checkpreemptcurrcheckpreemptwakeup，。picknexttaskpicknexttaskfair，。putprevtaskputprevtaskfair，。。。。。。。setcurrtasksetcurrtaskfair，。taskticktasktickfair，。taskforktaskforkfair，。priochangedpriochangedfair，。switchedfromswitchedfromfair，。switchedtoswitchedtofair，。getrrintervalgetrrintervalfair，。updatecurrupdatecurrfair，。。。。。。｝；
　　以选择下一个任务为例，CFS对应的是picknexttaskfair，而rtrq对应的则是picknexttaskrt，等等。
　　由此，我们来总结一下：每个CPU都有一个structrq结构体，里面会有着cfsrq，rtrq等一系列队列每个队列由一个红黑树组织，红黑树里每一个节点为一个任务实体schedentity每一个任务实体schedentity对应于一个任务taskstruct在taskstruct中对应的schedclass会根据不同策略申明不同的对应处理函数，处理实际的调度工作四。调度流程
　　有了上述的基本策略和基本调度结构体，我们可以形成大致的骨架，下面就是需要核心的调度流程将其拼凑成一个整体，实现调度系统。调度分为两种，主动调度和抢占式调度。主动调度即任务执行一定时间以后主动让出CPU，通过调度策略选择合适的下一个任务执行。抢占式调度即任务执行中收到了其他任务的中断，由此停止执行并切换至下一个任务。4。1主动调度
　　说到调用，逃不过核心函数schedule（）。其中schedsubmitwork（）函数完成当前任务的收尾工作，以避免出现如死锁或者IO中断等情况。之后首先禁止抢占式调度的发生，然后调用schedule（）函数完成调度，之后重新打开抢占式调度，如果需要重新调度则会一直重复该过程，否则结束函数。asmlinkagevisiblevoidschedschedule（void）｛structtaskstructtskcurrent；schedsubmitwork（tsk）；do｛preemptdisable（）；schedule（false）；schedpreemptenablenoresched（）；｝while（needresched（））；｝EXPORTSYMBOL（schedule）；
　　而schedule（）函数则是实际的核心调度函数，该函数主要操作包括选取下一进程和进行上下文切换，而上下文切换又包括用户态空间切换和内核态的切换。具体的解释可以参照英文源码注释以及中文对各个步骤的注释。schedule（）isthemainschedulerfunction。Themainmeansofdrivingtheschedulerandthusenteringthisfunctionare：1。Explicitblocking：mutex，semaphore，waitqueue，etc。2。TIFNEEDRESCHEDflagischeckedoninterruptanduserspacereturnpaths。Forexample，seearchx86entry64。S。Todrivepreemptionbetweentasks，theschedulersetstheflagintimerinterrupthandlerschedulertick（）。3。Wakeupsdontreallycauseentryintoschedule（）。Theyaddatasktotherunqueueandthatsit。Now，ifthenewtaskaddedtotherunqueuepreemptsthecurrenttask，thenthewakeupsetsTIFNEEDRESCHEDandschedule（）getscalledonthenearestpossibleoccasion：Ifthekernelispreemptible（CONFIGPREEMPTy）：insyscallorexceptioncontext，atthenextoutmostpreemptenable（）。（thismightbeassoonasthewakeup（）sspinunlock（）！）inIRQcontext，returnfrominterrupthandlertopreemptiblecontextIfthekernelisnotpreemptible（CONFIGPREEMPTisnotset）thenatthenext：condresched（）callexplicitschedule（）callreturnfromsyscallorexceptiontouserspacereturnfrominterrupthandlertouserspaceWARNING：mustbecalledwithpreemptiondisabled！staticvoidschednotraceschedule（boolpreempt）｛structtaskstructprev，next；unsignedlongswitchcount；structrqflagsrf；structrqrq；intcpu；从当前的CPU中取出任务队列rq，prev赋值为当前任务cpusmpprocessorid（）；rqcpurq（cpu）；prevrqcurr；检测当前任务是否可以调度scheduledebug（prev）；if（schedfeat（HRTICK））hrtickclear（rq）；禁止中断，RCU抢占关闭，队列加锁，SMP加锁localirqdisable（）；rcunotecontextswitch（preempt）；Makesurethatsignalpendingstate（）signalpending（）belowcantbereorderedwithsetcurrentstate（TASKINTERRUPTIBLE）donebythecallertoavoidtheracewithsignalwakeup（）。Themembarriersystemcallrequiresafullmemorybarrieraftercomingfromuserspace，beforestoringtorqcurr。rqlock（rq，rf）；smpmbafterspinlock（）；PromoteREQtoACTrqclockupdateflags1；updaterqclock（rq）；switchcountprevnivcsw；if（！preemptprevstate）｛不可中断的任务则继续执行if（signalpendingstate（prevstate，prev））｛prevstateTASKRUNNING；｝else｛当前任务从队列rq中出队，onrq设置为0，如果存在IO未完成则延时完成deactivatetask（rq，prev，DEQUEUESLEEPDEQUEUENOCLOCK）；prevonrq0；if（previniowait）｛atomicinc（rqnriowait）；delayacctblkiostart（）；｝唤醒睡眠进程Ifaworkerwenttosleep，notifyandaskworkqueuewhetheritwantstowakeupatasktomaintainconcurrency。if（prevflagsPFWQWORKER）｛structtaskstructtowakeup；towakeupwqworkersleeping（prev）；if（towakeup）trytowakeuplocal（towakeup，rf）；｝｝switchcountprevnvcsw；｝调用picknexttask获取下一个任务，赋值给nextnextpicknexttask（rq，prev，rf）；cleartskneedresched（prev）；clearpreemptneedresched（）；如果产生了任务切换，则需要切换上下文if（likely（prev！next））｛rqnrswitches；rqcurrnext；Themembarriersystemcallrequireseacharchitecturetohaveafullmemorybarrierafterupdatingrqcurr，beforereturningtouserspace。Herearetheschemesprovidingthatbarrieronthevariousarchitectures：mm？switchmm（）：mmdrop（）forx86，s390，sparc，PowerPC。switchmm（）relyonmembarrierarchswitchmm（）onPowerPC。finishlockswitch（）forweaklyorderedarchitectureswherespinunlockisafullbarrier，switchto（）forarm64（weaklyordered，spinunlockisaRELEASEbarrier），switchcount；traceschedswitch（preempt，prev，next）；Alsounlockstherq：rqcontextswitch（rq，prev，next，rf）；｝else｛清除标记位，重开中断rqclockupdateflags（RQCFACTSKIPRQCFREQSKIP）；rqunlockirq（rq，rf）；｝队列自平衡：红黑树平衡操作balancecallback（rq）；｝
　　其中核心函数是获取下一个任务的picknexttask（）以及上下文切换的contextswitch（），下面详细展开剖析。首先看看picknexttask（），该函数会根据调度策略分类，调用该类对应的调度函数选择下一个任务实体。根据前文分析我们知道，最终是在不同的红黑树上选择最左节点作为下一个任务实体并返回。Pickupthehighestpriotask：staticinlinestructtaskstructpicknexttask（structrqrq，structtaskstructprev，structrqflagsrf）｛conststructschedclassclass；structtaskstructp；这里做了一个优化：如果是普通调度策略则直接调用fairschedclass中的picknexttaskOptimization：weknowthatifalltasksareinthefairclasswecancallthatfunctiondirectly，butonlyiftheprevtaskwasntofahigherschedulingclass，becauseotherwisethoseloosetheopportunitytopullinmoreworkfromotherCPUs。if（likely（（prevschedclassidleschedclassprevschedclassfairschedclass）rqnrrunningrqcfs。hnrrunning））｛pfairschedclass。picknexttask（rq，prev，rf）；if（unlikely（pRETRYTASK））gotoagain；Assumesfairschedclassnextidleschedclassif（unlikely（！p））pidleschedclass。picknexttask（rq，prev，rf）；returnp；｝again：依次调用类中的选择函数，如果正确选择到下一个任务则返回foreachclass（class）｛pclasspicknexttask（rq，prev，rf）；if（p）｛if（unlikely（pRETRYTASK））gotoagain；returnp；｝｝Theidleclassshouldalwayshavearunnabletask：BUG（）；｝
　　下面来看看上下文切换。上下文切换主要干两件事情，一是切换任务空间，也即虚拟内存；二是切换寄存器和CPU上下文。关于任务空间的切换放在内存部分的文章中详细介绍，这里先按下不表，通过任务空间切换实际完成了用户态的上下文切换工作。下面我们重点看一下内核态切换，即寄存器和CPU上下文的切换。contextswitchswitchtothenewMMandthenewthreadsregisterstate。staticalwaysinlinestructrqcontextswitch（structrqrq，structtaskstructprev，structtaskstructnext，structrqflagsrf）｛structmmstructmm，oldmm；preparetaskswitch（rq，prev，next）；mmnextmm；oldmmprevactivemm；Forparavirt，thisiscoupledwithanexitinswitchtotocombinethepagetablereloadandtheswitchbackendintoonehypercall。archstartcontextswitch（prev）；IfmmisnonNULL，wepassthroughswitchmm（）。IfmmisNULL，wewillpassthroughmmdrop（）infinishtaskswitch（）。Bothofthesecontainthefullmemorybarrierrequiredbymembarrierafterstoringtorqcurr，beforereturningtouserspace。if（！mm）｛nextactivemmoldmm；mmgrab（oldmm）；enterlazytlb（oldmm，next）；｝elseswitchmmirqsoff（oldmm，mm，next）；if（！prevmm）｛prevactivemmNULL；rqprevmmoldmm；｝rqclockupdateflags（RQCFACTSKIPRQCFREQSKIP）；preparelockswitch（rq，next，rf）；Herewejustswitchtheregisterstateandthestack。switchto（prev，next，prev）；barrier语句是一个编译器指令，用于保证switchto和finishtaskswitch的执行顺序不会因为编译阶段优化而改变barrier（）；returnfinishtaskswitch（prev）；｝
　　switchto（）就是寄存器和栈的切换，它调用到了switchtoasm。这是一段汇编代码，主要用于栈的切换，其中32位使用esp作为栈顶指针，64位使用rsp，其他部分代码一致。通过该段汇编代码我们完成了栈顶指针的切换，并调用switchto完成最终TSS的切换。注意switchto中其实是有三个变量，分别是prev，next，last，而实际在使用时，我们会对last也赋值为prev。这里的设计意图需要结合一个例子来说明。假设有ABC三个任务，从A调度到B，B到C，最后C回到A，我们假设仅保存prev和next，则流程如下A保存内核栈和寄存器，切换至B，此时prevA，nextB，该状态会保存在栈里，等下次调用A的时候再恢复。然后调用B的finishtaskswitch（）继续执行下去，返回B的队列rq，B保存内核栈和寄存器，切换至CC保存内核栈和寄存器，切换至A。A从barrier（）开始运行，而A从步骤1中保存的prevA，nextB则完美的避开了C，丢失了C的信息。因此last指针的重要性就出现了。在执行完switchtoasm后，A的内核栈和寄存器重新覆盖了prev和next，但是我们通过返回值提供了C的内存地址，保存在last中，在finishtaskswitch中完成清理工作。defineswitchto（prev，next，last）do｛prepareswitchto（next）；（（last）switchtoasm（（prev），（next）））；｝while（0）eax：prevtaskedx：nexttaskENTRY（switchtoasm）。。。。。。switchstackmovlesp，TASKthreadsp（eax）movlTASKthreadsp（edx），esp。。。。。。jmpswitchtoEND（switchtoasm）
　　最终调用switchto（）函数。该函数中涉及到一个结构体TSS（TaskStateSegment），该结构体存放了所有的寄存器。另外还有一个特殊的寄存器TR（TaskRegister）会指向TSS，我们通过更改TR的值，会触发硬件保存CPU所有寄存器在当前TSS，并从新的TSS读取寄存器的值加载入CPU，从而完成一次硬中断带来的上下文切换工作。系统初始化的时候，会调用cpuinit（）给每一个CPU关联一个TSS，然后将TR指向这个TSS，然后在操作系统的运行过程中，TR就不切换了，永远指向这个TSS。当修改TR的值得时候，则为任务调度。switchto（x，y）shouldswitchtasksfromxtoy。Wefsavefwaitsothatanexceptiongoesoffattherighttime（asacallfromthefsaveorfwaitineffect）ratherthantothewrongprocess。LazyFPsavingnolongermakesanysensewithmodernCPUs，andthissimplifiesalotofthings（SMPandUPbecomethesame）。NOTE！Weusedtousethex86hardwarecontextswitching。Thereasonfornotusingitanymorebecomesapparentwhenyoutrytorecovergracefullyfromsavedstatethatisnolongervalid（stalesegmentregistervaluesinparticular）。Withthehardwaretaskswitch，thereisnowaytofixupbadstateinareasonablemanner。ThefactthatInteldocumentsthehardwaretaskswitchingtobeslowisafairlyredherringthiscodeisnotnoticeablyfaster。However，thereissomeroomforimprovementhere，sotheperformanceissuesmayeventuallybeavalidpoint。Moreimportant，however，isthefactthatthisallowsusmuchmoreflexibility。Thereturnvalue（inax）willbetheprevtaskafterthetaskswitch，andshowsupinretfromforkinentry。S，forexample。visiblenotracefuncgraphstructtaskstructswitchto（structtaskstructprevp，structtaskstructnextp）｛structthreadstructprevprevpthread，nextnextpthread；structfpuprevfpuprevfpu；structfpunextfpunextfpu；intcpusmpprocessorid（）；neverputaprintkinswitchto。。。printk（）callswakeup（）indirectlyswitchfpuprepare（prevfpu，cpu）；Saveawaygs。Noneedtosavefs，asitwassavedonthestackonentry。Noneedtosaveesandds，asthosearealwayskernelsegmentswhileinsidethekernel。DoingthisbeforesettingthenewTLSdescriptorsavoidsthesituationwherewetemporarilyhavenonreloadablesegmentsinfsandgs。ThiscouldbeanissueiftheNMIhandlereverusedfsorgs（itdoesnottoday），orifthekernelisrunninginsideofahypervisorlayer。lazysavegs（prevgs）；LoadtheperthreadThreadLocalStoragedescriptor。loadTLS（next，cpu）；RestoreIOPLifneeded。Innormaluse，theflagsrestoreintheswitchassemblywillhandlethis。ButifthekernelisrunningvirtualizedatanonzeroCPL，thepopfwillnotrestoreflags，soitmustbedoneinaseparatestep。if（getkernelrpl（）unlikely（previopl！nextiopl））setioplmask（nextiopl）；switchtoextra（prevp，nextp）；Leavelazymode，flushinganyhypercallsmadehere。ThismustbedonebeforerestoringTLSsegmentssotheGDTandLDTareproperlyupdated，andmustbedonebeforefpurestore（），sotheTSbitisuptodate。archendcontextswitch（nextp）；Reloadesp0andcpucurrenttopofstack。Thischangescurrentthreadinfo（）。RefreshtheSYSENTERconfigurationincaseprevornextisvm86。updatetaskstack（nextp）；refreshsysentercs（next）；thiscpuwrite（cpucurrenttopofstack，（unsignedlong）taskstackpage（nextp）THREADSIZE）；Restoregsifneeded（whichiscommon）if（prevgsnextgs）lazyloadgs（nextgs）；switchfpufinish（nextfpu，cpu）；thiscpuwrite（currenttask，nextp）；LoadtheIntelcacheallocationPQRMSR。resctrlschedin（）；returnprevp；｝
　　更多Linux内核视频教程文本资料免费领取后台私信【内核大礼包】自行获取。
　　在完成了switchto（）的内核态切换后，还有一个重要的函数finishtaskswitch（）负责善后清理工作。在前面介绍switchto三个参数的时候我们已经说明了使用last的重要性。而这里为何让prev和last均赋值为prev，是因为prev在后面没有需要用到，所以节省了一个指针空间来存储last。finishtaskswitchcleanupafterataskswitchprev：thethreadwejustswitchedawayfrom。finishtaskswitchmustbecalledafterthecontextswitch，pairedwithapreparetaskswitchcallbeforethecontextswitch。finishtaskswitchwillreconcilelockingsetupbypreparetaskswitch，anddoanyotherarchitecturespecificcleanupactions。Notethatwemayhavedelayeddroppinganmmincontextswitch（）。Ifso，wefinishthathereoutsideoftherunqueuelock。（Doingitwiththelockheldcancausedeadlocks；seeschedule（）fordetails。）Thecontextswitchhaveflippedthestackfromunderusandrestoredthelocalvariableswhichweresavedwhenthistaskcalledschedule（）inthepast。prevcurrentisstillcorrectbutweneedtorecalculatethisrqbecauseprevmayhavemovedtoanotherCPU。staticstructrqfinishtaskswitch（structtaskstructprev）releases（rqlock）｛structrqrqthisrq（）；structmmstructmmrqprevmm；longprevstate；Theprevioustaskwillhaveleftuswithapreemptcountof2becauseitleftusafter：schedule（）preemptdisable（）；1schedule（）rawspinlockirq（rqlock）2Also，seeFORKPREEMPTCOUNT。if（WARNONCE（preemptcount（）！2PREEMPTDISABLEOFFSET，corruptedpreemptcount：sd0xx，currentcomm，currentpid，preemptcount（）））preemptcountset（FORKPREEMPTCOUNT）；rqprevmmNULL；Ataskstructhasonereferencefortheuseascurrent。Ifataskdies，thenitsetsTASKDEADintskstateandcallsscheduleonelasttime。Theschedulecallwillneverreturn，andthescheduledtaskmustdropthatreference。Wemustobserveprevstatebeforeclearingprevoncpu（infinishtask），otherwiseaconcurrentwakeupcangetprevrunningonanotherCPUandwecouldravewithitsRUNNINGDEADtransition，resultinginadoubledrop。prevstateprevstate；vtimetaskswitch（prev）；perfeventtaskschedin（prev，current）；finishtask（prev）；finishlockswitch（rq）；finisharchpostlockswitch（）；kcovfinishswitch（current）；fireschedinpreemptnotifiers（current）；Whenswitchingthroughakernelthread，theloopinmembarrier｛private，global｝expedited（）mayhaveobservedthatkernelthreadandnotissuedanIPI。Itisthereforepossibletoschedulebetweenuserkerneluserthreadswithoutpassingthoughswitchmm（）。Membarrierrequiresabarrierafterstoringtorqcurr，beforereturningtouserspace，soprovidethemhere：afullmemorybarrierfor｛PRIVATE，GLOBAL｝EXPEDITED，implicitlyprovidedbymmdrop（），asynccoreforSYNCCORE。if（mm）｛membarriermmsynccorebeforeusermode（mm）；mmdrop（mm）；｝if（unlikely（prevstateTASKDEAD））｛if（prevschedclasstaskdead）prevschedclasstaskdead（prev）；Removefunctionreturnprobeinstancesassociatedwiththistaskandputthembackonthefreelist。kprobeflushtask（prev）；Taskisdonewithitsstack。puttaskstack（prev）；puttaskstruct（prev）；｝ticknohztaskswitch（）；returnrq；｝
　　至此，我们完成了内核态的切换工作，也完成了整个主动调度的过程。4。2抢占式调度
　　抢占式调度通常发生在两种情况下。一种是某任务执行时间过长，另一种是当某任务被唤醒的时候。首先看看任务执行时间过长的情况。4。2。1任务运行时间检测
　　该情况需要衡量一个任务的执行时间长短，执行时间过长则发起抢占。在计算机里面有一个时钟，会过一段时间触发一次时钟中断，通知操作系统时间又过去一个时钟周期，通过这种方式可以查看是否是需要抢占的时间点。
　　时钟中断处理函数会调用schedulertick（）。该函数首先取出当前CPU，并由此获取对应的运行队列rq和当前任务curr。接着调用该任务的调度类schedclass对应的tasktick（）函数进行时间事件处理。Thisfunctiongetscalledbythetimercode，withHZfrequency。Wecallitwithinterruptsdisabled。voidschedulertick（void）｛intcpusmpprocessorid（）；structrqrqcpurq（cpu）；structtaskstructcurrrqcurr；structrqflagsrf；schedclocktick（）；rqlock（rq，rf）；updaterqclock（rq）；currschedclasstasktick（rq，curr，0）；cpuloadupdateactive（rq）；calcgloballoadtick（rq）；psitasktick（rq）；rqunlock（rq，rf）；perfeventtasktick（）；。。。。。。｝
　　以普通任务队列为例，对应的调度类为fairschedclass，对应的时钟处理函数为tasktickfair（），该函数会获取当前的调度实体和运行队列，并调用entitytick（）函数更新时间。schedulertickhittingataskofourschedulingclass。NOTE：Thisfunctioncanbecalledremotelybythetickoffloadthatgoesalongfulldynticks。Thereforenolocalassumptioncanbemadeandeverythingmustbeaccessedthroughtherqandcurrpassedinparameters。staticvoidtasktickfair（structrqrq，structtaskstructcurr，intqueued）｛structcfsrqcfsrq；structschedentitysecurrse；foreachschedentity（se）｛cfsrqcfsrqof（se）；entitytick（cfsrq，se，queued）；｝if（staticbranchunlikely（schednumabalancing））taskticknuma（rq，curr）；updatemisfitstatus（curr，rq）；updateoverutilizedstatus（taskrq（curr））；｝
　　在entitytick（）中，首先会调用updatecurr（）更新当前任务的vruntime，然后调用checkpreempttick（）检测现在是否可以发起抢占。staticvoidentitytick（structcfsrqcfsrq，structschedentitycurr，intqueued）｛Updateruntimestatisticsofthecurrent。updatecurr（cfsrq）；Ensurethatrunnableaverageisperiodicallyupdated。updateloadavg（cfsrq，curr，UPDATETG）；updatecfsgroup（curr）；。。。。。。if（cfsrqnrrunning1）checkpreempttick（cfsrq，curr）；｝
　　checkpreempttick（）先是调用schedslice（）函数计算出一个调度周期中该任务运行的实际时间idealruntime。sumexecruntime指任务总共执行的实际时间，prevsumexecruntime指上次该进程被调度时已经占用的实际时间，所以sumexecruntimeprevsumexecruntime就是这次调度占用实际时间。如果这个时间大于idealruntime，则应该被抢占了。除了这个条件之外，还会通过pickfirstentity取出红黑树中最小的进程。如果当前进程的vruntime大于红黑树中最小的进程的vruntime，且差值大于idealruntime，也应该被抢占了。Preemptthecurrenttaskwithanewlywokentaskifneeded：staticvoidcheckpreempttick（structcfsrqcfsrq，structschedentitycurr）｛unsignedlongidealruntime，deltaexec；structschedentityse；s64delta；idealruntimeschedslice（cfsrq，curr）；deltaexeccurrsumexecruntimecurrprevsumexecruntime；if（deltaexecidealruntime）｛reschedcurr（rqof（cfsrq））；Thecurrenttaskranlongenough，ensureitdoesntgetreelectedduetobuddyfavours。clearbuddies（cfsrq，curr）；return；｝Ensurethatataskthatmissedwakeuppreemptionbyanarrowmargindoesnthavetowaitforafullslice。Thisalsomitigatesbuddyinducedlatenciesunderload。if（deltaexecsysctlschedmingranularity）return；sepickfirstentity（cfsrq）；deltacurrvruntimesevruntime；if（delta0）return；if（deltaidealruntime）reschedcurr（rqof（cfsrq））；｝
　　如果确认需要被抢占，则会调用reschedcurr（）函数，该函数会调用settskneedresched（）标记该任务为TIFNEEDRESCHED，即该任务应该被抢占。reschedcurrmarkrqscurrenttasktobereschedulednow。OnUPthismeansthesettingoftheneedreschedflag，onSMPitmightalsoinvolveacrossCPUcalltotriggerthescheduleronthetargetCPU。voidreschedcurr（structrqrq）｛structtaskstructcurrrqcurr；intcpu；。。。。。。。cpucpuof（rq）；if（cpusmpprocessorid（））｛settskneedresched（curr）；setpreemptneedresched（）；return；｝if（setnrandnotpolling（curr））smpsendreschedule（cpu）；elsetraceschedwakeidlewithoutipi（cpu）；｝4。2。2任务唤醒情况
　　某些任务会因为中断而唤醒，如当IO到来的时候，IO进程往往会被唤醒。在这种时候，如果被唤醒的任务优先级高于CPU上的当前任务，就会触发抢占。trytowakeup（）调用ttwuqueue（）将这个唤醒的任务添加到队列当中。ttwuqueue（）再调用ttwudoactivate（）激活这个任务。ttwudoactivate（）调用ttwudowakeup（）。这里面调用了checkpreemptcurr（）检查是否应该发生抢占。如果应该发生抢占，也不是直接踢走当前进程，而是将当前进程标记为应该被抢占。staticvoidttwudowakeup（structrqrq，structtaskstructp，intwakeflags，structrqflagsrf）｛checkpreemptcurr（rq，p，wakeflags）；pstateTASKRUNNING；traceschedwakeup（p）；4。2。3抢占的发生
　　由前面的分析，我们知道了不论是是当前任务执行时间过长还是新任务唤醒，我们均会对现在的任务标记位TIFNEEDRESCUED，下面分析实际抢占的发生。真正的抢占还需要一个特定的时机让正在运行中的进程有机会调用一下schedule（）函数，发起真正的调度。
　　实际上会调用schedule（）函数共有以下几个时机
　　从系统调用返回用户态：以64位为例，系统调用的链路为dosyscall64syscallreturnslowpathprepareexittousermodeexittousermodeloop。在exittousermodeloop中，会检测是否为TIFNEEDRESCHED，如果是则调用schedule（）staticvoidexittousermodeloop（structptregsregs，u32cachedflags）｛while（true）｛Wehaveworktodo。localirqenable（）；if（cachedflagsTIFNEEDRESCHED）schedule（）；。。。。。。｝
　　内核态启动：内核态的执行中，被抢占的时机一般发生在preemptenable（）中。在内核态的执行中，有的操作是不能被中断的，所以在进行这些操作之前，总是先调用preemptdisable（）关闭抢占，当再次打开的时候，就是一次内核态代码被抢占的机会。preemptenable（）会调用preemptcountdecandtest（），判断preemptcount和TIFNEEDRESCHED是否可以被抢占。如果可以，就调用preemptschedulepreemptschedulecommonschedule进行调度。definepreemptenable（）do｛if（unlikely（preemptcountdecandtest（）））preemptschedule（）；｝while（0）definepreemptcountdecandtest（）（｛preemptcountsub（1）；shouldresched（0）；｝）staticalwaysinlineboolshouldresched（intpreemptoffset）｛returnunlikely（preemptcount（）preemptoffsettifneedresched（））；｝definetifneedresched（）testthreadflag（TIFNEEDRESCHED）staticvoidschednotracepreemptschedulecommon（void）｛do｛。。。。。。schedule（true）；。。。。。。｝while（needresched（））从中断返回内核态用户态：中断处理调用的是doIRQ函数，中断完毕后分为两种情况，一个是返回用户态，一个是返回内核态。返回用户态会调用prepareexittousermode（），最终调用exittousermodeloop（）返回内核态会调用preemptscheduleirq（），最终调用schedule（）commoninterrupt：ASMCLACaddq0x80，（rsp）interruptdoIRQretfromintr：popqrsptestb3，CS（rsp）jzretintkernelInterruptcamefromuserspaceGLOBAL（retintuser）movrsp，rdicallprepareexittousermodeTRACEIRQSIRETQSWAPGSjmprestoreregsandiretReturningtokernelspaceretintkernel：ifdefCONFIGPREEMPTbt9，EFLAGS（rsp）jnc1f0：cmpl0，PERCPUVAR（preemptcount）jnz1fcallpreemptscheduleirqjmp0basmlinkagevisiblevoidschedpreemptscheduleirq（void）｛。。。。。。do｛preemptdisable（）；localirqenable（）；schedule（true）；localirqdisable（）；schedpreemptenablenoresched（）；｝while（needresched（））；。。。。。。｝五。总结
　　本文分析了任务调度的策略、结构体以及整个调度流程，其中关于内存上下文切换的部分尚未详细叙述，留待内存部分展开剖析。源码资料
　　1、调度相关结构体及函数实现
　　2、schedule核心函数