linux内核--进程调度（一）
引言：无论是在批处理系统还是分时系统中，用户进程数一般都多于处理机数、这将导致它们互相争夺处理机。另外，系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程，以使之执行。
进程调度的具体功能可总结为如下几点：
作为进程调度的准备，进程管理模块必须将系统中各进程的执行情况和状态特征记录在各进程的PCB表中。并且，根据各进程的状态特征和资源需求等、进程管理模块还将各进程的PCB表排成相应的队列并进行动态队列转接。进程调度模块通过PCB变化来掌握系统中存在的所有进程的执行情况和状态特征，并在适当的时机从就绪队列中选择出一个进程占据处理机。
选择占有处理机的进程
进程调度的主要功能是按照一定的策略选择—个处于就绪状态的进程，使其获得处理机执行。根据不同的系统设计目的，有各种各样的选择策略，例如系统开销较少的静态优先数调度法，适合于分时系统的轮转法(Round RoLin)和多级互馈轮转法(Round Robin withMultip1e feedback)等。这些选择策略决定了调度算法的性能。
进行进程上下文切换
—个进程的上下文(context)包括进程的状态、有关变量和数据结构的值、机器寄存器的值和PCB以及有关程序、数据等。一个进程的执行是在进程的上下文中执行。当正在执行的进程由于某种原因要让出处理机时，系统要做进程上下文切换，以使另一个进程得以执行。当进行上下文切换时点统要首先检查是否允许做上下文切换(在有些情况下，上下文切换是不允许的，例如系统正在执行某个不允许中断的原语时)。然后，系统要保留有关被切换进程的足够信息，以便以后切换回该进程时，顺利恢复该进程的执行。在系统保留了CPU现场之后，调度程序选择一个新的处于就绪状态的进程、并装配该进程的上下文，使CPU的控制权掌握在被选中进程手中。
Unix进程调度
进程是程序的执行系统中活动的实体. 在UNIX系统中进程被定义为映像的执行. 映像是计算机的执行环境,它包括各种寄存器及存储器的值、打开文件的状态及现行目录等等.进程映像的组成部分:寄存器、进程控制块proc结构和user结构、进程数据区ppda (共享正文段(由text 结构控制) 、数据段和栈段( 含用户栈和核心栈) ) . 对于一个进程的映像来说,proc 结构、进程页表、text 结构是常驻内存的,而user 结构、正文段、数据段是非常驻内存部分. 它们在用户虚拟空间形成一个整体,一起换进换出.
在Unix操作系统中，所以的程序，不论是用户级上还是在内核级上执行的，都出现在某个进程的现场内，所有的用户程序都在它们自己的进程现场中运行。当这些用户进程通过系统调用请求内核服务的时候，实现该系统调用的内核代码继续在请求进程的现场内执行，这就能让内核方便的访问进程的所有状态及其他地址空间。它还提供了一种代表用户程序记录内核执行的当前状态的方式。例如，如果需要挂起一次系统调用的执行来等待I/O操作完成，那么内核有关系统调用处理的状态就要保存在进程中。
因为系统的所有活动，无论是用户级上的还是内核级上的，都发生在某个进程的现场内，所有UNIX内核只调度需要执行的进程。当使用传统的分时调度策略的时候，在用户级执行的进程不会被分入时间内执行。只有当前的内核进程明确允许的情况下，才能切换到在内核执行的另一个进程。
UNIX进程调度核心思想
进程状态转换图
进程调度机制问量
在传统Unix中．进程优先级的设置是通过nice和set priority完成的；但不幸的是，速两种系统调用无法使用最高优先级的进程得以立即进行，这是因为在循环调度(时间片调度)机制下．当进程的时闻片用完后．不论扰先级如何都让出CPU．另外，由于它是非抢占式内核，优先级高的进程不能 立即打断当前正在运行的进程，获得CPU资源．这对一些要求进程立即抢占CPU，并且一次运行完成的实时应用是不能满足要求的．
UNIX系统是一个多用户分时系统,其分时性是通过对用户进程频繁的调度来实现的,系统的调度程序分成两部分,即处理机调度程序( swtch) 和进程对换程序(sched) . 在这里我涉及的是处理机调度程序.在如下几种情况下会调用处理机调度程序: (1) 若一个进程已到达它不能超过的某个点,这时它就要调用“sleep”,而“sleep”则调用“swtch”;(2) 一个在核心态下运行的进程,当它将要转入用户态之前,会测试变量“runrun”,如果其值非0 ,则意味着更高优先权的进程已为运行准备就绪. 此时核心态进程也将调用“swtch”.UNIX进程调度策略是基于动态优先数,优先数的设置有如下特点:
swtch 由“trap”、“sleep”、“expand”、“exit”、“stop”、“xalloc”调用. 它是一个非常特殊的过程,分为三段执行,涉及3 个核心态进程.
①第一阶段属于当前进程的部分,若当前进程不是进程0 ,则调用savu过程将当前进程的环境变量保存在u. u- rsav. 调用retu过程恢复进程0 的环境变量.
②第二阶段属于进程0 ,首先清runrun 标志,该标志指示一个较当前进程具有更高优先权的进程已为运行准备就绪.swtch通过do循环寻找最高优先权进程(重新计算各进程的优先级) . 若找到了满足条件的就绪进程,则将其从就绪队列中取出,并将该进程的优先级设置为当前的优先级curpri.
③第三阶段属于被选中的进程. 该进程已成为当前进程开始运行,根据该进程的SSWAP 标志是否设置,调用aretu过程从u. u-ssav 中恢复进程的环境变量(r5 和r6) .
程序发现某进程优先级高于当前运行进程的优先级时,就要设置该标志,而在中断陷入处理程序结束之前,检查该标志是否设置,若已设置则调用swtch()程序进行调度,另外,在时钟中断处理中每隔1 秒也将runrun 标志设置一次,并通过软件中断方式,执行swtch() 程序,这是为了增加调度机会,保证良好的分时性.Swtch 程序调用了savu、retu、idle、aretu 等过程。
savu 程序的作用:这是一个汇编语言过程,它将r5 和r6 的值存放到一个数组中,该数组的地址作为一个参数传递至savu ;
retu 程序的作用:汇编语言过程,它复位第七个核心态段地址寄存器,然后从“u. u- rsa”最新可存取副本中复位r6 和r5 ;
aretu 程序的作用:汇编语言过程,它从作为参数传递过来的地址重装r5 和r6 ;
idle 程序的作用:汇编语言过程,让处理机空转等待.
swtch 程序功能强大而其程序代码简洁精练(共71行代码,其中注释语句等有30 行,有效代码是41行) ,这也是整个UNIX系统代码的突出的特点.
Unix系统是多用户，多任务的操作系统，它通过向进程提供与机器无关的抽象服务，从而在Unix实现之间提供了高度的程序的可移植性。程序的执行被限制在保持程序当前状态的进程内，这些状态包括虚拟地址空间，程序的变量值以及硬件状态。内核给每个进程提供了一个环境让这个环境显得好像该进程是系统中正在执行的唯一进程那样。这主要是赋予每个进程自己的虚拟地址空间来实现的。系统调用可以创建新进程，改变进程正在执行的程序，以及终止进程，还可以使用其他许多系统调用，其中包括动态分配未初始化数据的系统调用。
Linux的进程调度
传统Unix操作系统的调度算法必须实现几个互相冲突的目标：进程响应时间尽可能快，后台作业的吞吐量尽可能高，进程的饥饿现象尽可能避免，低优先级和高优先级进程的需要尽可能调和等等。决定什么时候以怎样的方式选择一个新进程运行的这组规则就是所谓的调度策略（scheduling policy）。
Linux的进程调度是基于分时技术（time-sharing）。允许多个进程“并发”运行就意味着CPU 的时间被粗略地分成“片”，给每个可运行进程分配一片。
当然，单处理器在任何给定的时刻只能运行一个进程。当一个并发执行的进程其时间片或时限（quantum）到期时还没有终止，进程切换就可以发生。分时依赖于定时中断，因此，对进程是透明的。为保证CPU 分时，不需要在程序中插入额外的代码。
调度策略也是基于依照优先级排队的进程。有时用复杂的算法求出进程当前的优先级，但最后的结果是相同的：每个进程都与一个值相关联，这个值表示把进程如何适当地分配给CPU。在Linux 中，进程的优先级是动态的。调度程序跟踪进程做了些什么，并周期性地调整它们的优先级。在这种方式下，在较长的时间间隔内没有使用CPU的进程，通过动态地增加它们的优先级来提升它们。相应地，对于已经在CPU上运行了较长时间的进程，通过减少它们的优先级来处罚它们。每个进程在创建之初有一个基本的优先级，执行期间调度系统会动态调整它的优先级，交互性高的任务会获得一个高的动态优先级，而交互性低的任务获得一个低的动态优先级。类进程的时间片计算如下图所示：
当谈及有关调度问题时，传统上把进程分类为“I/O 范围（I/O-bound）”或“CPU
范围（CPU-bound）”。前者频繁地使用I/O 设备，并花费很多时间等待I/O操作的完成；而后者是需要大量CPU 时间的数值计算应用程序。Linux操作系统支持多进程，进程控制块PCB(Process ControlBlock)是系统中最为重要的数据结构之一。用来存放进程所必需的各种信息，PCB用结构task—struct来表示，包括进程的类型、进程状态、优先级、时钟信息等。Linux系统中，进程调度操作由schedule()函数执行，这是一个只在内核态运行的函数，函数代码为所有进程共享。
Linux进程调度时机
Linux的进程调度时机与现代操作系统中的调度时机基本一致，为了判断是否可以执行内核的进程调度程序来调度进程，Linux中设置了进程调度标志need—resched，当标志为1时，可执行调度程序．通常，Linux调度时机分以下两种情况：(1)主动调度：指显式调用schedule()函数明确释放CPU，引起新一轮调度．一般发生在当前进程状态改变，如：进程终止、进程睡眠、进程对某些信号处理过程中等．(2)被动调度：指不显示调用schedule()函数，只是PCB中的need_resched进程调度标志，该域置位为1将引起新的进程调度，而每当中断处理和系统调用返回时，核心调度程序都会主动查询need—resched的状态(若置位，则主动调用schedule()函数。一般发生在新的进程产生时、某个进程优先级改变时、某个进程等待的资源可用被唤醒时、当前进程时间片用完等．
Linux进程调度策略
一般来说，不同用途的操作系统的调度策略是不同的，Linux进程调度是将优先级调度、时间片轮转法调度、先进先出调度综合起来应用．Linux系统中。不同类型的进程调度策略也不一样。
1．与进程调度相关的数据结构
每个进程都是一个动态的个体，其生命周期依次定义的数据结构为：TASK—RUNNING，TASK—INTERRUPTIBLE。TASK—UNINTERRUPTIBLE，TASK—ZOMBIE和TASK—STOPPED，一个进程在其生存期间，状态会发生多次变化。与其数据结构相对应的即是Linux进程的状态，分别是：运行态、等待态、暂停态和僵死态。
2．进程状态及其转换过程的描述
进程创建时的状态为不可打断睡眠，在do—fork()结束前被父进程唤醒后。变为执行状态，处于执行状态的进程被移到run—queue就绪任务队列中等待调度。适当时候由schedule0按调度算法选中，获得CPU，若采用轮转法，即时，由时钟中断触发timer—interrupt()，其内部调用schedule()，引起新一轮调度，当前进程的状态仍处于执行状态，因而把当前进程挂蛰Jruil—queue队尾。获得CPU且正在运行的进程若申请不到某资源。则调用sleep—on()或interruptible—sleep—on()睡眠，其task—struct进程控制块挂到相应资源的wait—queue等待队列如果调用sleep—on()。则其状态变为不可打断睡眠，如果调用interruptible—sleep—on()，则其状态变为可打断睡眠，Sleep—on()或interruptible—sleep—on()将调用schedule()函数把睡眠进程释放。
3．进程分类和相应的进程调度策略
Linux系统中，为了高效地调度进程，将进程分威两类：实时进程和普通进程(又称非实时进程或一般进程)，实时进程的优先级要高于其他进程，如果一个实时进程处于可执行状态，它将先得到执行．实时进程又有两种策略：时间片轮转和先进先出，在时间片轮转策略中。每个可执行实时进程轮流执行一个时间片，而先进先出策略每个进程按各自在运行队列中的顺序执行且顺序不能变化。
在Linux中，进程调度策略共定义了3种：
Linux系统中的每个进程用task，struct结构来描述，进程调度的依据是task—struct结构中的policy、priority、counter和rt—priority，PCB中设置Policy数据项，其值用于反映针对不同类型的进程而采用的调度策略。SCHED—RR和SCHED—FIFO用于实时进程。分别表示轮转调度策略和先进先出调度策略；SCHED—OTHER表示普通进程，也按照轮转调度策略处理。这三类调度策略均基于优先级．PCB中设置Priority数据项，其值为普通进程的调度优先级．普通进程的可用时间片的初始值即为该值，该值通过系统调用是可以改变的。PCB中设置rt～p riority数据项，其值是实时进程专用的调度优先级，实时进程的可用时间片的初始值即为该值．该优先级也可以用系统调用来修改，PCB中设置counter数据项。用于进程可用时间片时值的计数，初始值为rt—priority或Priority。进程启动后该值随时钟周期递减。
Windows进程
与进程调度相关的数据结构
每个windows进程都是由一个执行体进程块来表示的。EPROCESS块中除了包含许多与进程有关的属性以外，还包含和指向了许多其他的相关数据结构。例如，每个进程都有一个或多个 线程，这些线程由执行体线程块来表示。执行体进程块和相关的数据结构位于系统空间中，不过，进程块环境是个例外，它位于进程地址空间中（因为它包含了一些需要由用户模式代码来修改的信息）。
除了EPROCESS块以外，windows子系统进程为每个windows进程维护了一个类似的结构。而且，windows子系统的内核模式部分有一个针对每个进程的数据结构，当一个线程第一次调用windows的USER或GDI函数时，此数据结构就会被创建。
下图是一个简化的关于进程和线程数据结构的框图：
Windows 系统的进程调度方法分析
Windows 中的每一个进程都是EPROCESS结构体。此结构体中除了进程的属性之外还引用了其它一些与实现进程紧密相关的结构体。例如，每个进程都有一个或几个线程,线程在系统中就是ETHREAD 结构体。简要描述一下存在于这个结构体中的主要的信息,这些信息都是由对内核函数的研究而得知的。首先，结构体中有KPROCESS 结构体,这个结构体中又有指向这些进程的内核线程(KTHREAD)链表的指针(分配地址空间),基优先级,在内核模式或是用户模式执行进程的线程的时间,处理器affini ty(掩码，定义了哪个处理器能执行进程的线程)，时间片值。在ETHREAD 结构体中还存在着这样的信息:进程ID、父进程ID、进程映象名。
在EPROCESS结构体中还有指向PEB的指针。ETHREAD 结构体还包含有创建时间和退出时间、进程ID 和指向EPROCESS 的指针,启动地址，I/O请求链表和KTHREAD 结构体。在KTHREAD 中包含有以下信息:内核模式和用户模式线程的创建时间，指向内核堆栈基址和顶点的指针、指向服务表的指针、基优先级与当前优先级、指向APC的指针和指向T E B的指针。KTHREAD中包含有许多其它的数据,通过观察这些数据可以分析出KTHREAD的结构。通过遍历KPROCESS结构体中的ETHREAD,找到系统中当前所有的KTHREAD 结构,这个结构中的偏移量为0x124处的Affinity域(WindowsXPsp3)即为设置CPU亲缘性掩码的内存地址。
Windows实现了一个优先驱动的，抢先式的调度系统——具有最高优先级的可运行线程总是运行，而该线程可能仅限于在允许它运行的处理器上运行，这种现象称为处理器亲和性，在默认的情况下，线程可以在任何一个空闲的处理器上运行，但是，你可以使用windows调度函数，或者在映像头部设置一个亲和性掩码来改变处理器亲和性。
在此重点解释CPU亲缘性的概念,CPU亲缘性就是指在系统中能够将一个或多个进程或线程绑定到一个或多个处理器上运行,这是期待已久的特性。也就是说“: 在1号处理器上一直运行该程序”或者是“在所有的处理器上运行这些程序，而不是在0 号处理器上运行”。然后, 调度器将遵循该规则，程序仅仅运行在允许的处理器上。
Windows 的进程调度代码是在它的System 进程下的，所以它不属于任何用户进程上下文。调度代码在适当的时机会切换进程上下文,这里的切换进程上下文是指进程环境的切换, 包括内存中的可执行程序, 提供程序运行的各种资源.进程拥有虚拟的地址空间,可执行代码, 数据, 对象句柄集, 环境变量, 基础优先级, 以及最大最小工作集等的切换。
而Windows最小的调度单位是线程, 只有线程才是真正的执行体，进程只是线程的容器。Windows调程序在时间片到期，或有切换线程指令执行(如Sleep,KeWaitForSingleObject 等函数)时, 将会从进程线程队列中找到下一个要调度的线程执行体，并装入到KPCR(Kernel 's Processor Control Region ,内核进程控制区域) 结构中,CPU 根据KPCR结构中的KPRCB 结构执行线程执行体代码。
而在多核CPU下，当Windows调度代码执行时,从当前要调度执行的KTHREAD结构中取出Affinity,并与当前PC 机上的硬件配置数据中的CPU 掩码作与操作,结果写入到指定的CPU，例如双核CPU 的设备掩码为0x03,如果当前KTHREAD里的Affinity 为0x01,那么0x01&0x03=0x01,这样执行体线程会被装入CPU1的KPRCB 结构中得以执行,调度程序不会把这个线程交给CPU2 去执行。此过程如图2 所示。这就是为线程选择指定CPU 核的原理。
小结：进程调度策略的选择对整个系统性能有至关重要的影响，一个好的调度算法应该考虑很多方面：公平、有效、响应时间、周转时间、系统吞吐量等等。但这些因素之间又是相互矛盾的，最终的取舍根据系统要达到的目标而定,同时我们也可以看出多进程的管理是～种非常复杂的并发程序设计．每个进程的状态不仅由其自身决定，而且还要受诸多外在因素的影响．而在此基础上的进程调度，为了保证操作系统的稳定性、提高效率和增加灵活性，还必须采用很多方法，这些都是值得我们去研究和探讨的：。
