Linux进程管理之进程调度与切换

　　进程调度相关内核结构
　　我们知道，进程运行需要各种各样的系统资源，如内存、文件、打印机和最
　　宝贵的CPU等，所以说，调度的实质就是资源的分配。系统通过不同的调度算法（SchedulingAlgorithm）来实现这种资源的分配。通常来说，选择什么样的调度算法取决于资源分配的策略（SchedulingPolicy）。
　　有关调度相关的结构保存在taskstruct中，如下：structtaskstruct｛taskstruct采用了如下3个成员表示进程的优先级，prio、normalprio表示动态优先级staticprio为静态优先级，静态优先级是进程启动时分配的优先级，它可以使用nice和schedsetscheduler系统调用修改，否则在进程运行期间会一直保持恒定intprio，staticprio，normalprio；schedclas表示该进程所属的调度器类2。6。24版本中有3中调度类：实时调度器：rtschedclass完全公平调度器：fairschedclass空闲调度器：idleschedclassconststructschedclassschedclas；调度实体structschedentityse；policy保存了对该进程应用的调度策略。进程的调度策略有6种SCHEDNORMALSCHEDFIFOSCHEDRRSCHEDBATCHSCHEDIDLE普通进程调度策略：SCHEDNORMAL、SCHEDBATCH、SCHEDIDLE，这些都是通过完全公平调度器来处理的实时进程调度策略：SCHEDRR、SCHEDFIFO这些都是通过实时调度器来处理的unsignedintpolicy；除了内核线程（KernelThread），每个进程都拥有自己的地址空间（也叫虚拟空间），用mmstruct来描述。activemm是为内核线程而引入的。因为内核线程没有自己的地址空间，为了让内核线程与普通进程具有统一的上下文切换方式，当内核线程进行上下文切换时，让切换进来的线程的activemm指向刚被调度出去的进程的activemm（如果进程的mm域不为空，则其activemm域与mm域相同）structmmstructmm，activemm；表示实时进程的优先级，最低的优先级为0，最高为99，值越大，优先级越高unsignedintrtpriority；。。。｝；
　　每个进程都拥有自己的地址空间（也叫虚拟空间），用mmstruct来描述。
　　activemm是为内核线程而引入的，因为内核线程没有自己的地址空间，为了让内核线程与普通进程具有统一的上下文切换方式，当内核线程进行上下文切换时，让切换进来的线程的activemm指向刚被调度出去的进程的activemm（如果进程的mm域不为空，则其activemm域与mm域相同）。
　　在linux2。6中schedclass表示该进程所属的调度器类有3种：
　　实时调度器（RT，rtschedclass）：为每个优先级维护一个队列；完全公平调度器（CFS，fairschedclass）：采用完全公平调度算法，引入虚拟运行时间的概念。空闲调度器（idleschedclass）：为每个CPU都会有一个idle线程，当没有其他进程可以调度时，调度运行idle线程。
　　进程的调度策略有5种，用户可以调用调度器里不同的调度策略：
　　SCHEDFIFO：采用了先入先出，不使用时间片的调度算法。若处于可执行状态，就会一直执行，没有更高优先级的情况下，进程只能等待其主动让出cpu；SCHEDRR：时间片轮转，进程用完时间片后加入优先级对应的运行队列的尾部，把CPU让给同一优先级的其他进程；SCHEDNORMAL：使task选择CFS调度器来调度运行；SCHEDBATCH：批量处理，使task选择CFS调度器来调度运行；SCHEDIDLE：使task选择CFS调度器来调度运行
　　在每个CPU中都有一个自身的运行队列rq，每个活动进程只出现在一个运行队列中，在多个CPU上同时运行一个进程是不可能的。
　　运行队列是使用如下结构实现的：structrq｛运行队列中进程的数目unsignedlongnrrunning；进程切换总数u64nrswitches；用于完全公平调度器的就绪队列structcfsrqcfs；用于实时调度器的就绪队列structrtrqrt；记录本cpu尚处于TASKUNINTERRUPTIBLE状态的进程数，和负载信息有关unsignedlongnruninterruptible；curr指向当前运行的进程实例，idle指向空闲进程的实例structtaskstructcurr，idle；上一次调度时的mm结构structmmstructprevmm；。。。｝；
　　每个运行队列中有2个调度队列：CFS调度队列和RT调度队列。
　　tast作为调度实体加入到CPU中的调度队列中。
　　系统中所有的运行队列都在runqueues数组中，该数组的每个元素分别对应于系统中的一个CPU。在单处理器系统中，由于只需要一个就绪队列，因此数组只有一个元素。staticDEFINEPERCPUSHAREDALIGNED（structrq，runqueues）；
　　内核也定义了一下便利的宏，其含义很明显。definecpurq（cpu）（percpu（runqueues，（cpu）））definethisrq（）（getcpuvar（runqueues））definetaskrq（p）cpurq（taskcpu（p））definecpucurr（cpu）（cpurq（cpu）curr）
　　进程调度与切换
　　在分析调度流程之前，我们先来看在什么情况下要执行调度程序，我们把这种情况叫做调度时机。
　　Linux调度时机主要有。进程状态转换的时刻：进程终止、进程睡眠；当前进程的时间片用完时（currentcounter0）；设备驱动程序；进程从中断、异常及系统调用返回到用户态时。
　　时机1，进程要调用sleep（）或exit（）等函数进行状态转换，这些函数会主动调用调度程序进行进程调度。
　　时机2，由于进程的时间片是由时钟中断来更新的，因此，这种情况和时机4是一样的。
　　时机3，当设备驱动程序执行长而重复的任务时，直接调用调度程序。在每次反复循环中，驱动程序都检查needresched的值，如果必要，则调用调度程序schedule（）主动放弃CPU。
　　时机4，如前所述，不管是从中断、异常还是系统调用返回，最终都调用retfromsyscall（），由这个函数进行调度标志的检测，如果必要，则调用调用调度程序。那么，为什么从系统调用返回时要调用调度程序呢？这当然是从效率考虑。从系统调用返回意味着要离开内核态而返回到用户态，而状态的转换要花费一定的时间，因此，在返回到用户态前，系统把在内核态该处理的事全部做完。
　　Linux的调度程序是一个叫Schedule（）的函数，这个函数来决定是否要进行进程的切换，如果要切换的话，切换到哪个进程等。
　　Schedule的实现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进程prev和进程next切换前更新各自的schedinfoschedinfoswitch（prev，next）；if（likely（prev！next））｛rqnrswitches；rqcurrnext；switchcount；完成进程切换（上下文切换）contextswitch（rq，prev，next）；unlockstherq｝elsespinunlockirq（rqlock）；if（unlikely（reacquirekernellock（current）0））｛cpusmpprocessorid（）；rqcpurq（cpu）；gotoneedreschednonpreemptible；｝preemptenablenoresched（）；if（unlikely（testthreadflag（TIFNEEDRESCHED）））gotoneedresched；｝
　　从代码分析来看，Schedule主要完成了2个功能：
　　picknexttask以优先级从高到底依次检查每个调度类，从最高优先级的调度类中选择最高优先级的进程作为下一个应执行进程。contextswitch完成进程的上下文切换。
　　进程上下文切换staticinlinevoidcontextswitch（structrqrq，structtaskstructprev，structtaskstructnext）｛structmmstructmm，oldmm；preparetaskswitch（rq，prev，next）；mmnextmm；获取要执行进程的mm字段oldmmprevactivemm；被切换出去进程的activemm字段mm为空，说明是一个内核线程if（unlikely（！mm））｛内核线程共享上一个运行进程的mmnextactivemmoldmm；借用切换出去进程的mmstruct增加引用计数atomicinc（oldmmmmcount）；惰性TLB，因为内核线程没有虚拟地址空间的用户空间部分，告诉底层体系结构无须切换enterlazytlb（oldmm，next）；｝else进程切换包括进程的执行环境切换和运行空间的切换。运行空间的切换是有switchmm完成的。若是用户进程，则切换运行空间switchmm（oldmm，mm，next）；若上一个运行进程是内核线程if（unlikely（！prevmm））｛prevactivemmNULL；断开内核线程与之前借用的地址空间联系更新运行队列的prevmm成员，为之后归还借用的mmstruct做准备rqprevmmoldmm；｝Herewejustswitchtheregisterstateandthestack。切换进程的执行环境switchto（prev，next，prev）；barrier（）；进程切换之后的处理工作finishtaskswitch（thisrq（），prev）；｝
　　进程上下文切换包括进程的地址空间的切换和执行环境的切换。
　　switchmm完成了进程的地址空间的切换：如果新进程有自己的用户空间，也就是说，如果nextmm与nextactivemm相同，那么，switchmm（）函数就把该进程从内核空间切换到用户空间，也就是加载next的页目录。如果新进程无用户空间（nextmm为空），也就是说，如果它是一个内核线程，那它就要在内核空间运行，因此，需要借用前一个进程（prev）的地址空间，因为所有进程的内核空间都是共享的，因此，这种借用是有效的。switchto完成了执行环境的切换，该宏实现了进程之间的真正切换。进程切换包括进程的执行环境切换和运行空间的切换。运行空间的切换是有switchmm完成的staticinlinevoidswitchmm（structmmstructprev，structmmstructnext，structtaskstructtsk）｛得到当前进程运行的cpuintcpusmpprocessorid（）；若要切换的prev！next，执行切换过程if（likely（prev！next））｛stopflushipisforthepreviousmm清除prev的cpuvmmask，标志prev已经弃用了当前cpucpuclear（cpu，prevcpuvmmask）；ifdefCONFIGSMP在smp系统中，更新cputlbstatepercpu（cputlbstate，cpu）。stateTLBSTATEOK；percpu（cputlbstate，cpu）。activemmnext；endif设置cpuvmmask，表示next占用的当前的cpucpuset（cpu，nextcpuvmmask）；Reloadpagetables加载CR3loadcr3（nextpgd）；loadtheLDT，iftheLDTisdifferent：若ldt不相同，还要加载ldtif（unlikely（prevcontext。ldt！nextcontext。ldt））loadLDTnolock（nextcontext）；｝ifdefCONFIGSMPelse｛percpu（cputlbstate，cpu）。stateTLBSTATEOK；prevnext那当前cpu中的activemm就是prev，也即是nextBUGON（percpu（cputlbstate，cpu）。activemm！next）；在smp系统中，虽然mm时一样的，但需要加载CR3执行cputestandset来判断next是否正运行在此cpu上，这里是判断在切换next是否运行在当前的cpu中，假设cpu为1，一个进程在1上执行时候，被调度出来，再次调度的时候，又发生在cpu1上if（！cputestandset（cpu，nextcpuvmmask））｛WewereinlazytlbmodeandleavemmdisabledtlbflushIPIdelivery。Wemustreloadcr3。loadcr3（nextpgd）；loadLDTnolock（nextcontext）；｝｝endif｝
　　对于switchmm处理，关键的一步就是它将新进程页面目录的起始物理地址装入到寄存器CR3中。CR3寄存器总是指向当前进程的页面目录。defineswitchto（prev，next，last）do｛unsignedlongesi，edi；分别保存了eflags、ebp、esp，flags和ebp他们是被保存在prev进程（其实就是要被切换出去的进程）的内核堆栈中的asmvolatile（pushflSaveflagspushlebp0为prevthread。esp，1为prevthread。eipmovlesp，0saveESP5为nextthread。esp，6为nextthread。eipmovl5，esprestoreESP将标号为1所在的地址，也即是poplebp指令所在的地址保存在prevthread。eip中，作为prev进程下一次被调度运行而切入时的返回地址，因此可以知道，每个进程调离时都要执行movl1f，1，所以这就决定了每个进程在受到调度恢复运行时都会从标号1处也即是poplebp开始执行。但是有一个例外，那就是新创建的进程，新创建的进程并没有在上一次调离时执行上面的指令，所以一来要将其taskstruct中的thread。eip事先设置好，二来所设置的返回地址也未必是这里的标号1所在的地址，这取决于系统空间堆栈的设置。事实上可以下fork（）中可以看到，这个地址在copythread（）中设置为retfromfork，其代码在entry。S中，也就是对于新创建的进程，在调用scheduletail（）后直接转到了retfromsyscall，也即是返回到了用户空间去了movl1f，1saveEIP将nextthread。eip压入栈中，这里的nextthread。eip正是next进程上一次被调离在movl1f，1保存的，也即是指向标号为1的地方，也即是poplebp指令所在的地址pushl6restoreEIP需要注意的是switchto是经过regparm（3）来修饰的，这个是gcc的一个扩展语法。即从eax，ebx，ecx寄存器取函数的参数。这样，switchto函数的参数就是从寄存器中取的。并是不向普通函数那样从堆栈中取的。在switchto之前，将nextthread。eip压栈了，这样从函数返回后，它的下一条运行指令就是nextthread。eip了。对于新创建的进程。我们设置了pthread。eipretfromfork。这样子进程被切换进来之后，就会通过retfromfork返回到用户空间了。对于已经运行的进程，我们这里可以看到，在进程被切换出去的时候，prevthread。eip被设置了标号1的地址，即是从标号1的地址开始运行的。标号1的操作：恢复ebp（poplebp）恢复flags（popf1）这样就恢复了进程的执行环境。从代码可以看到，在进程切换时，只保留了flagsesp和ebp寄存器，显示的用到了eax和edx，那其他寄存器怎么保存的呢？实际上过程切换只是发生在内核态，对于内核态的寄存器来说，它的段寄存器都是一样的，所以不需要保存通过jmp指令转入到函数switchto中，由于上一行pushl6把nextthread。eip，也即是标号为1的地址压到栈中，所以跳入switchto执行完后，执行标记为1的地方，也即是poplebp指令jmpswitchto1：poplebppopfl：m（prevthread。esp），m（prevthread。eip），a（last），S（esi），D（edi）：m（nextthread。esp），m（nextthread。eip），2（prev），d（next））；｝while（0）
　　switchto把寄存器中的值比如esp等存放到进程thread结构中，保存现场一边后续恢复，同时调用switchto完成了堆栈的切换。
　　在进程的taskstruct结构中有个重要的成分thread，它本身是一个数据结构threadstruct，里面记录着进程在切换时的（系统空间）堆栈指针，取指令地址（也就是返回地址）等关键性的信息。
　　switchto处理的主要逻辑是TSS，其核心就是loadesp0将TSS中的内核空间（0级）堆栈指针换成nextesp0。这是因为cpu在穿越中断门或者陷阱门时要根据新的运行级别从TSS中取得进程在系统空间的堆栈指针，其次，段寄存器fs和gs的内容也做了相应的切换。同时cpu中为debug而设计的一些寄存器以及说明进程IO操作权限的位图。structtaskstructfastcallswitchto（structtaskstructprevp，structtaskstructnextp）｛structthreadstructprevprevpthread，nextnextpthread；intcpusmpprocessorid（）；structtssstructtsspercpu（inittss，cpu）；。。。将TSS中的内核级（0级）堆栈指针换成nextesp0，这就是next进程在内核栈的指针loadesp0（tss，next）；为prev保存gssavesegment（gs，prevgs）；从next的tlsarray缓存中加载线程的ThreadLocalStorage描述符loadTLS（next，cpu）；若当前特权级别是0且previopl！nextiopl，则恢复IOPL设置setioplmaskif（getkernelrpl（）unlikely（previopl！nextiopl））setioplmask（nextiopl）；根据threadinfo的TIF标志TIFWORKCTXSWPREV和TIFWORKCTXSWNEXT判断是否需要处理debug寄存器和IO位图if（unlikely（taskthreadinfo（prevp）flagsTIFWORKCTXSWPREVtaskthreadinfo（nextp）flagsTIFWORKCTXSWNEXT））switchtoxtra（prevp，nextp，tss）；设置cpu的lazy模式archleavelazycpumode（）；若fpucounter5则恢复nextp的FPU寄存器if（nextpfpucounter5）mathstaterestore（）；若需要，恢复gs寄存器if（prevgsnextgs）loadsegment（gs，nextgs）；x86writepercpu（currenttask，nextp）；returnprevp；｝
　　关于switchto的工作就是处理TSS（任务状态段）。
　　TSS全称taskstatesegment，是指在操作系统进程管理的过程中，任务（进程）切换时的任务现场信息。
　　linux为每一个CPU提供一个TSS段，并且在TR寄存器中保存该段。
　　linux中之所以为每一个CPU提供一个TSS段，而不是为每个进程提供一个TSS段，主要原因是TR寄存器永远指向它，在任务切换的适合不必切换TR寄存器，从而减小开销。
　　在从用户态切换到内核态时，可以通过获取TSS段中的esp0来获取当前进程的内核栈栈顶指针，从而可以保存用户态的cs，esp，eip等上下文。
　　TSS在任务切换过程中起着重要作用，通过它实现任务的挂起和恢复。所谓任务切换是指，挂起当前正在执行的任务，恢复或启动另一任务的执行。
　　在任务切换过程中，首先，处理器中各寄存器的当前值被自动保存到TR（任务寄存器）所指定的任务的TSS中；然后，下一任务的TSS被装入TR；最后，从TR所指定的TSS中取出各寄存器的值送到处理器的各寄存器中。由此可见，通过在TSS中保存任务现场各寄存器状态的完整映象，实现任务的切换。
　　因此，switchto核心内容就是将TSS中的内核空间（0级）堆栈指针换成nextesp0。这是因为CPU在穿越中断门或者陷阱门时要根据新的运行级别从TSS中取得进程在系统空间的堆栈指针。
　　threadstruct。esp0指向进程的系统空间堆栈的顶端。当一个进程被调度运行时，内核会将这个变量写入TSS的esp0字段，表示这个进程进入0级运行时其堆栈的位置。换句话说，进程的threadstruct结构中的esp0保存着其系统空间堆栈指针。当进程穿过中断门、陷阱门或者调用门进入系统空间时，处理器会从这里恢复期系统空间栈。
　　由于栈中变量的访问依赖的是段、页、和esp、ebp等这些寄存器，所以当段、页、寄存器切换完以后，栈中的变量就可以被访问了。
　　因此switchto完成了进程堆栈的切换，由于被切进的进程各个寄存器的信息已完成切换，因此next进程得以执行指令运行。
　　由于A进程在调用switchto完成了与B进程堆栈的切换，也即是寄存器中的值都是B的，所以A进程在switchto执行完后，A停止运行，B开始运行，当过一段时间又把A进程切进去后，A开始从switchto后面的代码开始执行。
　　schedule的调用流程如下：