进程调度

进程有四个基本属性

　　1.多态性 从诞生、运行，直至消灭。

  

进程调度

2.多个不同的进程可以包括相同的程序 　　3.三种基本状态 它们之间可进行转换 　　4.并发性 并发执行的进程轮流占用处理器

进程的三种基本状态

　　1.等待态：等待某个事件的完成； 　　2.就绪态：等待系统分配处理器以便运行； 　　3.运行态：占有处理器正在运行。 　　运行态→等待态 往往是由于等待外设，等待主存等资源分配或等待人工干预而引起的。 　　等待态→就绪态 则是等待的条件已满足，只需分配到处理器后就能运行。 　　运行态→就绪态 不是由于自身原因，而是由外界原因使运行状态的进程让出处理器，这时候就变成就绪态。例如时间片用完，或有更高优先级的进程来抢占处理器等。 　　就绪态→运行态 系统按某种策略选中就绪队列中的一个进程占用处理器，此时就变成了运行态

处理机调度的分级

　　高级、中级和作业从提交开始直到完成，往往要经历下述三级调度： 　　：(High-Level Scheduling)又称为，它决定把后备作业调入内存运行； 　　低级调度：(Low-Level Scheduling)又称为进程调度，它决定把就绪队列的某进程获得CPU； 　　：(Intermediate-Level Scheduling)又称为在虚拟存储器中引入，在内、外存对换区进行进程对换。

进程调度的方式

非剥夺方式

　　分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生

  

进程调度

某事件而阻塞时，才把处理机分配给另一个进程。

剥夺方式

　　当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程。剥夺原则有：优先权原则、短进程优先原则、时间片原则。 　　例如，有三个进程P1、P2、P3先后到达，它们分别需要20、4和2个单位时间运行完毕。 　　假如它们就按P1、P2、P3的顺序执行，且不可剥夺，则三进程各自的周转时间分别为20、24、 　　26个单位时间，平均周转时间是23.33个时间单位。 　　假如用时间片原则的剥夺调度方式，可得到： 　　可见：P1、P2、P3的周转时间分别为26、10、6个单位时间(假设时间片为2个单位时间)，平均周转时间为14个单位时间。 　　衡量进程调度性能的指标有：周转时间、响应时间、CPU-I/O执行期。

进程调度的算法

先进先出算法

　　算法总是把处理机分配给最先进入就绪队列的进程，一个进程一旦分得处理机，便一直执行下去，直到该进程完成或阻塞时，才释放处理机。 　　例如，有三个进程P1、P2和P3先后进入就绪队列，它们的执行期分别是21、6和3个单位时间， 　　执行情况如下图： 　　对于P1、P2、P3的周转时间为21、27、30，平均周转时间为26。 　　可见，FIFO算法服务质量不佳，容易引起作业用户不满，常作为一种辅助调度算法。 　　最短CPU运行期优先调度算法(SCBF--Shortest CPU Burst First) 　　该算法从就绪队列中选出下一个“CPU执行期最短”的进程，为之分配处理机。 　　例如，在就绪队列中有四个进程P1、P2、P3和P4，它们的下一个执行

  

进程调度

期分别是16、12、4和3个单位时间，执行情况如下图： 　　P1、P2、P3和P4的周转时间分别为35、19、7、3，平均周转时间为16。 　　该算法虽可获得较好的调度性能，但难以准确地知道下一个CPU执行期，而只能根据每一个进程的执行历史来预测。

轮转法

　　前几种算法主要用于中，不能作为中的主调度算法，在分时系统中，都采用时间片轮转法。 　　简单轮转法：系统将所有就绪进程按FIFO规则排队，按一定的时间间隔把处理机分配给队列中的进程。这样，就绪队列中所有进程均可获得一个时间片的处理机而运行。 　　多级队列方法：将系统中所有进程分成若干类，每类为一级。

多级反馈队列

　　多级反馈队列方式是在系统中设置多个就绪队列，并赋予各队列以不同的优先权。

进程调度的实现

引起进程调度的原因

　　正在执行的进程执行完毕或因发生某事件而不能再继续执行； 　　执行中的进程因提出I/O请求而暂停执行； 　　在或同步过程中执行了某种原语操作如P操作、阻塞、挂起原语等； 　　在可剥夺式调度中，有比当前进程优先权更高的进程进入就绪队列； 　　在时间片轮转法中，时间片完； 　　△通常系统是按或优先权形式来组织调度队列。

进程调度算法

　　其中，RQ为就绪队列指针，EP为运行队列指针。

进程调度的功能

记录系统中所有进程的执行情况

　　进程调度的具体功能可总结为如下几点：作为进程调度的准备，模块必须

  

进程调度

将 系统中各进程的执行情况和状态特征记录在各进程的PCB表中。并且，根据各进程的状态特征和资源需求等、进程管理模块还将各进程的PCB表排成相应的队列 并进行动态队列转接。进程调度模块通过PCB变化来掌握系统中存在的所有进程的执行情况和状态特征，并在适当的时机从就绪队列中选择出一个进程占据处理 机。

选择占有处理机的进程

　　进程调度的主要功能是按照一定的策略选择—个处于就绪状态的进程，使其获得处理机执行。根据不同的系统设计目的，有各种各样的选择策略，例如较少的静态优先数调度法，适合于分时系统的轮转法(Round RoLin)和多级互馈轮转法(Round Robin with Multip1e feedback)等。这些选择策略决定了调度算法的性能。

进行进程上下文切换

　　—个进程的上下文(context)包括进程的状态、有关变量和的值、机器寄存器的值和PCB以及有关程序、数据等。一个进程的执行是在进程的上下文中执行。当正在执行的进程由于某种原因要让出处理机时，系统要做切 换，以使另一个进程得以执行。当进行上下文切换时点统要首先检查是否允许做上下文切换(在有些情况下，上下文切换是不允许的，例如系统正在执行某个不允许 中断的原语时)。然后，系统要保留有关被切换进程的足够信息，以便以后切换回该进程时，顺利恢复该进程的执行。在系统保留了CPU现场之后，调度程序选择 一个新的处于就绪状态的进程、并装配该进程的上下文，使CPU的控制权掌握在被选中进程手中。

进程调度的时机

引起进程调度的原因有以下几类

　　进程调度发生在什么时机呢？这与引起进程调度的原因以及进程调度的方式有关。 　　(1)正在执行的进程执行完毕。这时，如果不选择新的就绪进程执行，将浪费处理机资源。 　　(2)执行中进程自己调用阻塞原语将白己阻塞起来进入睡眠等状态。 　　(3)执行中进程调用了P原语操作，从而因资源不足而被阻塞；或调用了v原语操作激活了等待资源的进程队列。 　　(4)执行中进程提出I/O请求后被阻塞。 　　(5)在分时系统中时间片已经用完。 　　(6)在执行完等系统程序后返回用户进程时，这时可看作系统进程执行完毕，从而可调度选择一新的用户进程执行。 　　以上都是在可剥夺方式下的引起进程调度的原因。在CPU执行方式是可剥夺时．还有 　　(7)就绪队列中的某进程的优先级变得高于当前执行进程的优先级，从而也将引发进程调度。

两种占用CPU的方式

　　可剥夺式 (可 preemptive)：就绪队列中一旦有优先级高于当前执行的进程存在时，便立即发生进程调度，转让处理机。 　　不可剥夺式 (不可抢占式 non_preemptive)：即使在就绪队列存在有优先级高与当前执行进程时，当前进程仍将占用处理机直到该进程自己因调用原语操作或等待I/O而进入阻塞、睡眠状态，或时间片用完时才重新发生调度让出处理机。

进程调度的上下文切换

　　进程上下文由正文段、数据段、硬件寄存器的内容以及有关数据结构等组成。硬件寄存器主要包括存放CPU将要执行的下条指令的程序计数器PC，指出机器与进程相关联的硬件状态的处理机状态寄存器PS，存放过程调用(或系统调用)时所传递参数的通用寄存器R以及堆栈指针寄存器S等。数据结构则包括PCB等在内的所有与执行该进程有关的管理和控制用表格、、链等。在发生进程调度时系统要做进程上下文切换。 　　在进程（上下文）中切换的步骤 　　n保存处理器的上下文，包括程序计数器和其它寄存器 　　n用新状态和其它相关信息更新正在运行进程的PCB 　　n把原来的进程移至合适的队列-就绪、阻塞 　　n选择另一个要执行的进程 　　n更新被选中进程的PCB 　　n从被选中进程中重装入 　　CPU 上下文

进程调度的性能评价

　 　进程调度虽然是在系统内部的低级调度，但进程调度的优劣直接影响作业调度的性能。那么，怎样评价进程调度的优劣呢？反映作业调度优劣的周转时间和平均周 转时间只在某种程度上反映了进程调度的性能，例如，其执行时间部分中实际上包含有进程等待(包括就绪状态时的等待)时间，而进程等待时间的多少是要依靠进 程调度策略和等待事件何时发生等来决定的。因此，进程调度性能的商量是设计的一个重要指标。 　　我们说进程调度性能的衡量方法可分为定形和定量两种。在定形衡量方面，首先是调度的可靠性。包 括一次进程调度是否可能引起数据结构的破坏等。这要求我们对调度时机的选择和保存CPU现场十分谨慎。另外，简洁性也是衡量进程调度的一个重要指标，由于 调度程序的执行涉及到多个进程和必须进行上下文切换，如果调度程序过于繁琐和复杂，将会耗去较大的系统开销。这在用户进程调用系统调用较多的情况下，将会 造成响应时间大幅度增加。 　　进程调度的定量评价包括CPU的利用率评价、进程在就绪队列中的等待时间与执行时间之比等。实 际上由于进程进入就绪队列的随机模型很难确定，而且进程上下文切换等也将影响进程的执行效率，LL而对进程调度进行解析是很困难的。一般情况下，大多利用 模拟或测试系统响应时间的方法来评价进程调度的性能。

实时系统的进程调度

综述

　　与 其他操作系统不同在于计算机要能及时响应外部事件的请求，在规定的严格时间内完成对该事件的处理，并控制所有实时设备和实时任务协调一致地工作，对于对时 间要求严格性的不同，实时系统又分为硬实时系统和软实时系统，其中硬实时系统是指这种时限的要求是绝对的，任何一个实时任务都能够在时限之前完成；而软实 时系统的要求就没有这么严格，允许偶尔有实时任务不满足时限的要求.实时系统一般用于嵌入式的系统中，分为实时过程控制和实时通信处理，其中实时过程控制 主要用于工业控制，军事控制领域；时事通信用于电信，银行，飞机订票等领域，正是由于在这些特殊领域的运用使得设计时主要追求的是：对外部请求在严格时间范围内做出反应，有高可靠性和完备性.为达到时间要求，进程的调度策略就显得尤为重要.

基于优先级的进程调度

　　最简单最直观的进程调度策略是基于优先级的调度，多数实时系统采用基于优先级的调度，每个进程根据它重要程度的不同被赋予不同的优先级，调度器在每次调度时，总选择优先级最高的进程开始执行. 　　首先要考虑的问题是如何分配优先级，对于进程优先级的分配可以采用静态和动态两种方式，静态优 先级调度算法：这种调度算法给那些系统中得到运行的所有进程都静态地分配一个优先级.静态优先级的分配可以根据应用的属性来进行，比如进程的周期，用户优 先级，或者其它的预先确定的策略.单调率算法(RM)调度算法是一种典型的静态优先级调度算法，它根据进程的执行周期的长短来决定调度优先级，那些具有小 的执行周期的进程具有较高的优先级.动态优先级调度算法：这种调度算法根据进程的资源需求来动态地分配进程的优先级，其目的就是在资源分配和调度时有更大 的灵活性.在实时系统中，最早期限优先算法(EDF)算法是使用最多的一种动态优先级调度算法，该算法给就绪队列中的各个进程根据它们的截止期限 (Deadline)来分配优先级，具有最近的截止期限的进程具有最高的优先级. 　　分配好优先级之后下一个要考虑的问题是何时让高优先级进程掌握CPU的使用权，这取决于操作系统的内核，有不可抢占式和可抢占式两种. 　　不可抢占式内核要求每个进程自我放弃CPU的所有权，各个进程彼此合作共享一个CPU.异步事 件还是由中断服务来处理.中断服务可以使一个高优先级的进程由挂起状态变为就绪状态.但中断服务以后控制权还是回到原来被中断了的那个进程，直到该进程主 动放弃CPU的使用权时，那个高优先级的进程才能获得CPU的使用权.这就出现了响应时间的问题，高优先级的进程已经进入了就绪状态但不能执行，这样进程 的响应时间变得不再确定这与实时系统的要求不符，因此一般的实时操作系统都要求是可抢占式的内核，当一个运行着的进程使一个比它优先级高的进程进入了就绪 态，当前进程的CPU使用权就被剥夺了，或者说被挂起了，那个高优先级的进程立刻得到了CPU的控制权，如果是中断服务子程序使一个高优先级的进程进入就 绪态，中断完成时，中断了的进程被挂起，优先级高的那个进程开始运行.在这种内核设置下，多个进程可能处于并发的状态，这就出现了多个进程共享资源的情 况，因此我们需要设置来保证临界资源的正确使用，任何一个想使用临界资源的进程在进入临界区之前必须拥有使用临界资源的信号量，否则不可以执行临界区代码. 　　这样基于优先级的可抢占式进程调度策略就基本架构完成，但此时仍然有的 危险，假设系统中有3个进程，分别为p1，p2和p3. p1的优先权高于p2，而p2的优先权高于p3.恰在此时p1和p2 因某种原因被阻塞，这时候系统调度p3执行.p3执行一段时间后，p1被唤醒.由于采取的是PBP的调度策略，因此p1抢占 p3的CPU， p1执行.p1执行一段时间后要进入临界区，但此时p3占有此临界资源的信号量.因此p1被阻塞，处于等待状态，等待p3 释放此信号量.经过这么一段时间后，p2此时此刻处于就绪状态.因此系统调度p2执行.如果p3在p2的执行期间一直没有能够被调度执行的话，那p1和 p3将一直等到p2执行完后才能执行，p1更要等到p3释放它所把持的信号量才能执行；而这段时间完全有可能超出p1的Deadline，使得p1崩溃. 我们看到在这个过程中，由于临界资源的使用问题使得优先级低的进程先于优先级高的进程先执行，这就出现了优先级反转的问题，从而造成了系统崩溃，对于这个 问题可以采用优先级继承的办法来进行解决.在优先级继承方案中，当高优先级进程在等待低优先级的进程占有的信号量时，让低优先级进程继承高优先级进程的优 先级，即把低优先级进程的优先权提高到高优先级进程的优先级；当低优先级进程释放高优先级进程等待的信号量时，立即把其优先权降低到原来的优先权.采用这 种方法可以有效地解决上面所述的优先权反转的问题.当高优先级进程p1想要进入临界区时，由于低优先级进程p3占有这个临界资源的信号量，导致p1被阻 塞.这时候，系统把p3的优先权升到p1的优先权，此时优先权处于p1和p3之间的进程p2，即使处于就绪状态也不可以被调度执行，因为此时p3的优先权 已经高于p2，所以p3此时被调度执行.当p3释放p1需要的信号量时，系统立即把p3的优先权降到原来的高度，来保证p1和p2正常有序执行.目前，有 许多实时系统是采用这种方法来防止优先级反转的，如VXWORKS.

基于比例共享的进程调度

　 　虽然基于优先级的调度简单而且易于实现，是目前使用最广泛的实时系统的进程调度策略，但对于一些软实时系统而言这种方法不再适用，比如实时多媒体会议， 在这种情况下我们可以选择基于共享的进程调度算法，其基本思想就是按照一定的权重(比例)对一组需要调度的进程进行调度，让它们的执行时间与它们的权重完 全成正比.我们可以通过两种方法来实现比例共享调度算法：第一种方法是调节各个就绪进程出现在调度队列队首的频率，并调度队首的进程执行；第二种做法就是 逐次调度就绪队列中的各个进程投入运行，但根据分配的权重调节分配个每个进程的运行时间片.比例共享调度算法的一个问题就是它没有定义任何优先级的概念； 所有的进程都根据它们申请的比例共享CPU资源，当系统处于过载状态时，所有的进程的执行都会按比例地变慢.所以为了保证系统中实时进程能够获得一定的 CPU处理时间，一般采用一种动态调节进程权重的方法.

基于时间的进程调度

　 　对于那些具有稳定，已知输入的简单系统，可以使用时间驱动的调度算法，它能够为数据处理提供很好的预测性.这种调度算法本质上是一种设计时就确定下来的 离线的静态调度方法.在系统的设计阶段，在明确系统中所有的处理情况下，对于各个进程的开始，切换，以及结束时间等就事先做出明确的安排和设计.这种调度 算法适合于那些很小的嵌入式系统，自控系统，传感器等应用环境.这种调度算法的优点是进程的执行有很好的可预测性，但最大的缺点是缺乏灵活性，并且会出现 有进程需要被执行而 CPU 却保持空闲的情况. 　　对于不同要求下的实时系统可以采用不同的进程调度策略来进行设计，也可以将这些方法进行综合之后得到更适合的调度策略.

Linux 进程调度原理

进程调度依据

　 　调度程序运行时，要在所有可运行状态的进程中选择最值得运行的进程投入运行。选择进程的依据是什么呢？在每个进程的task_struct结构中有以下 四项：policy、priority、counter、rt_priority。这四项是选择进程的依据。其中，policy是进程的调度策略，用来区 分实时进程和普通进程，实时进程优先于普通进程运行；priority是进程(包括实时和普通)的静态优先级；counter是进程剩余的时间片，它的起 始值就是priority的值；由于counter在后面计算一个处于可运行状态的进程值得运行的程度goodness时起重要作用，因 此，counter也可以看作是进程的动态优先级。rt_priority是实时进程特有的，用于实时进程间的选择。 　　Linux用函数goodness()来衡量一个处于可运行状态的进程值得运行的程度。该函数 综合了以上提到的四项，还结合了一些其他的因素，给每个处于可运行状态的进程赋予一个权值(weight)，调度程序以这个权值作为选择进程的唯一依据。 关于goodness()的情况在后面将会详细分析。

linux内核的三种调度方法

　　1，SCHED_OTHER 分时调度策略， 　　2，SCHED_FIFO实时调度策略，先到先服务 　　3，SCHED_RR实时调度策略，时间片轮转 　　实时进程将得到优先调用，实时进程根据实时优先级决定调度权值，分时进程则通过nice和counter值决定权值，nice越小，counter越大，被调度的概率越大，也就是曾经使用了cpu最少的进程将会得到优先调度。 　　SHCED_RR和SCHED_FIFO的不同： 　　当采用SHCED_RR策略的进程的时间片用完，系统将重新分配时间片，并置于就绪队列尾。放在队列尾保证了所有具有相同优先级的RR任务的调度公平。 　　SCHED_FIFO一旦占用cpu则一直运行。一直运行直到有更高优先级任务到达或自己放弃。 　　如果有相同优先级的实时进程（根据优先级计算的调度权值是一样的）已经准备好，FIFO时必须等待该进程主动放弃后才可以运行这个优先级相同的任务。而RR可以让每个任务都执行一段时间。 　　相同点： 　　RR和FIFO都只用于实时任务。 　　创建时优先级大于0(1-99)。 　　按照可抢占优先级调度算法进行。 　　就绪态的实时任务立即抢占非实时任务。 　　所有任务都采用linux分时调度策略时。 　　1，创建任务指定采用分时调度策略，并指定优先级nice值(-20~19)。 　　2，将根据每个任务的nice值确定在cpu上的执行时间(counter)。 　　3，如果没有等待资源，则将该任务加入到就绪队列中。 　　4，调度程序遍历就绪队列中的任务，通过对每个任务动态优先级的计算(counter+20- nice)结果，选择计算结果最大的一个去运行，当这个时间片用完后(counter减至0)或者主动放弃cpu时，该任务将被放在就绪队列末尾(时间片 用完)或等待队列(因等待资源而放弃cpu)中。 　　5，此时调度程序重复上面计算过程，转到第4步。 　　6，当调度程序发现所有就绪任务计算所得的权值都为不大于0时，重复第2步。 　　所有任务都采用FIFO时， 　　1，创建进程时指定采用FIFO，并设置实时优先级rt_priority(1-99)。 　　2，如果没有等待资源，则将该任务加入到就绪队列中。 　　3，调度程序遍历就绪队列，根据实时优先级计算调度权值(1000+rt_priority)，选择权值最高的任务使用cpu，该FIFO任务将一直占有cpu直到有优先级更高的任务就绪(即使优先级相同也不行)或者主动放弃(等待资源)。 　　4，调度程序发现有优先级更高的任务到达(高优先级任务可能被中断或任务唤醒，再或被当前运行的任务唤醒，等等)，则调度程序立即在当前任务堆栈中保存当前cpu寄存器的所有数据，重新从高优先级任务的堆栈中加载寄存器数据到cpu，此时高优先级的任务开始运行。重复第3步。 　　5，如果当前任务因等待资源而主动放弃cpu使用权，则该任务将从就绪队列中删除，加入等待队列，此时重复第3步。 　　所有任务都采用RR调度策略时 　　1，创建任务时指定调度参数为RR，并设置任务的实时优先级和nice值(nice值将会转换为该任务的时间片的长度)。 　　2，如果没有等待资源，则将该任务加入到就绪队列中。 　　3，调度程序遍历就绪队列，根据实时优先级计算调度权值(1000+rt_priority)，选择权值最高的任务使用cpu。 　　4，如果就绪队列中的RR任务时间片为0，则会根据nice值设置该任务的时间片，同时将该任务放入就绪队列的末尾。重复步骤3。 　　5，当前任务由于等待资源而主动退出cpu，则其加入等待队列中。重复步骤3。 　　系统中既有分时调度，又有和先进先出调度 　　1，RR调度和FIFO调度的进程属于实时进程，以分时调度的进程是非实时进程。 　　2，当实时进程准备就绪后，如果当前cpu正在运行非实时进程，则实时进程立即抢占非实时进程。 　　3，RR进程和FIFO进程都采用实时优先级做为调度的权值标准，RR是FIFO的一个延伸。 FIFO时，如果两个进程的优先级一样，则这两个优先级一样的进程具体执行哪一个是由其在队列中的未知决定的，这样导致一些不公正性(优先级是一样的，为 什么要让你一直运行？)，如果将两个优先级一样的任务的调度策略都设为RR，则保证了这两个任务可以循环执行，保证了公平。

进程调度策略

　　调度程序运行时，要在所有处于可运行状态的进程之中选择最值得运行的进程投入运行。选择进程的依据是什么呢？在每个进程的task_struct 结构中有这么四项： 　　policy， priority ， counter， rt_priority 　　这四项就是调度程序选择进程的依据.其中，policy是进程的调度策略，用来区分两种进程- 实时和普通；priority是进程(实时和普通)的优先级；counter 是进程剩余的时间片，它的大小完全由priority决定；rt_priority是实时优先级，这是实时进程所特有的，用于实时进程间的选择。 　　首先，Linux 根据policy从整体上区分实时进程和普通进程，因为实时进程和普通进程度调度是不同的，它们两者之间，实时进程应该先于普通进程而运行，然后，对于同一类型的不同进程，采用不同的标准来选择进程： 　　对于普通进程，Linux采用动态优先调度，选择进程的依据就是进程counter的大小。进 程创建时，优先级priority被赋一个初值，一般为0～70之间的数字，这个数字同时也是计数器counter的初值，就是说进程创建时两者是相等 的。字面上看，priority是“优先级”、counter是“计数器”的意思，然而实际上，它们表达的是同一个意思-进程的“时间片”。 Priority代表分配给该进程的时间片，counter表示该进程剩余的时间片。在进程运行过程中，counter不断减少，而priority保持 不变，以便在counter变为0的时候（该进程用完了所分配的时间片）对counter重新赋值。当一个普通进程的时间片用完以后，并不马上用 priority对counter进行赋值，只有所有处于可运行状态的普通进程的时间片(p->；；counter==0)都用完了以后，才用 priority对counter重新赋值，这个普通进程才有了再次被调度的机会。这说明，普通进程运行过程中，counter的减小给了其它进程得以运 行的机会，直至counter减为0时才完全放弃对CPU的使用，这就相对于优先级在动态变化，所以称之为动态优先调度。至于时间片这个概念，和其他不同 操作系统一样的，Linux的时间单位也是“时钟滴答”，只是不同操作系统对一个时钟滴答的定义不同而已（Linux为10ms）。进程的时间片就是指多 少个时钟滴答，比如，若priority为20，则分配给该进程的时间片就为20个时钟滴答，也就是20*10ms=200ms。Linux中某个进程的 调度策略(policy)、优先级(priority)等可以作为参数由用户自己决定，具有相当的灵活性。内核创建新进程时分配给进程的时间片缺省为 200ms(更准确的，应为210ms)，用户可以通过系统调用改变它。 　　对于实时进程，Linux采用了两种调度策略，即FIFO(先来先服务调度)和RR（时间片轮 转调度）。因为实时进程具有一定程度的紧迫性，所以衡量一个实时进程是否应该运行，Linux采用了一个比较固定的标准。实时进程的counter只是用 来表示该进程的剩余时间片，并不作为衡量它是否值得运行的标准。实时进程的counter只是用来表示该进程的剩余时间片，并不作为衡量它是否值得运行的 标准，这和普通进程是有区别的。上面已经看到，每个进程有两个优先级，实时优先级就是用来衡量实时进程是否值得运行的。 　　这一切看来比较麻烦，但实际上Linux中的实现相当简单。Linux用函数 goodness()来衡量一个处于可运行状态的进程值得运行的程度。该函数综合了上面提到的各个方面，给每个处于可运行状态的进程赋予一个权值 (weight)，调度程序以这个权值作为选择进程的唯一依据。 　　Linux根据policy的值将进程总体上分为实时进程和普通进程，提供了三种调度算法：一 种传统的Unix调度程序和两个由POSIX.1b(原名为POSIX.4)操作系统标准所规定的“实时”调度程序。但这种实时只是软实时，不满足诸如中 断等待时间等硬实时要求，只是保证了当实时进程需要时一定只把CPU分配给实时进程。 　　非实时进程有两种优先级，一种是静态优先级，另一种是动态优先级。实时进程又增加了第三种优先级，实时优先级。优先级是一些简单的整数，为了决定应该允许哪一个进程使用CPU的资源，用优先级代表相对权值-优先级越高，它得到CPU时间的机会也就越大。 　　？ 静态优先级(priority)-不随时间而改变，只能由用户进行修改。它指明了在被迫和其他进程竞争CPU之前，该进程所应该被允许的时间片的最大值（但很可能的，在该时间片耗尽之前，进程就被迫交出了CPU）。 　　？ 动态优先级(counter)-只要进程拥有CPU，它就随着时间不断减小；当它小于0时，标记进程重新调度。它指明了在这个时间片中所剩余的时间量。 　　？ 实时优先级(rt_priority)-指明这个进程自动把CPU交给哪一个其他进程；较高权值的进程总是优先于较低权值的进程。如果一个进程不是实时进程，其优先级就是0，所以实时进程总是优先于非实时进程的（但实际上，实时进程也会主动放弃CPU）。 　　当policy分别为以下值时： 　　1) SCHED_OTHER：这是普通的用户进程，进程的缺省类型，采用动态优先调度策略，选择进程的依据主要是根据进程goodness值的大小。这种进程在运行时，可以被高goodness值的进程抢先。 　　2) SCHED_FIFO：这是一种实时进程，遵守POSIX1.b标准的FIFO(先入先出)调度规则。它会一直运行，直到有一个进程因I/O阻塞，或者主 动释放CPU，或者是CPU被另一个具有更高rt_priority的实时进程抢先。在Linux实现中，SCHED_FIFO进程仍然拥有时间片-只有 当时间片用完时它们才被迫释放CPU。因此，如同POSIX1.b一样，这样的进程就象没有时间片(不是采用分时)一样运行。Linux中进程仍然保持对 其时间片的记录（不修改counter）主要是为了实现的方便，同时避免在调度代码的关键路径上出现条件判断语句 if (！(current->；；policy&；；SCHED_FIFO)){...}-要知道，其他大量非FIFO进程都需要记录时间片， 这种多余的检测只会浪费CPU资源。（一种优化措施，不该将执行时间占10%的代码的运行时间减少到50%；而是将执行时间占90%的代码的运行时间减少 到95%。0.9+0.1*0.5=0.95>；；0.1+0.9*0.9=0.91） 　　3) SCHED_RR：这也是一种实时进程，遵守POSIX1.b标准的RR(循环round-robin)调度规则。除了时间片有些不同外，这种策略与 SCHED_FIFO类似。当SCHED_RR进程的时间片用完后，就被放到SCHED_FIFO和SCHED_RR队列的末尾。 　　只要系统中有一个实时进程在运行，则任何SCHED_OTHER进程都不能在任何CPU运行。 每个实时进程有一个rt_priority，因此，可以按照rt_priority在所有SCHED_RR进程之间分配CPU。其作用与 SCHED_OTHER进程的priority作用一样。只有root用户能够用系统调用sched_setscheduler，来改变当前进程的类型 (sys_nice，sys_setpriority)。 　　此外，内核还定义了SCHED_YIELD，这并不是一种调度策略，而是截取调度策略的一个附加位。如同前面说明的一样，如果有其他进程需要CPU，它就提示调度程序释放CPU。特别要注意的就是这甚至会引起实时进程把CPU释放给非实时进程。

主要的进程调度的函数分析

　 　真正执行调度的函数是schedule(void)，它选择一个最合适的进程执行，并且真正进行上下文切换，使得选中的进程得以执行。而 reschedule_idle(struct task_struct *p)的作用是为进程选择一个合适的CPU来执行，如果它选中了某个CPU，则将该CPU上当前运行进程的need_resched标志置为1，然后向它 发出一个重新调度的处理机间中断，使得选中的CPU能够在中断处理返回时执行schedule函数，真正调度进程p在CPU上执行。在 schedule()和reschedule_idle()中调用了goodness()函数。goodness()函数用来衡量一个处于可运行状态的进 程值得运行的程度。此外，在schedule()函数中还调用了schedule_tail()函数；在reschedule_idle()函数中还调用 了reschedule_idle_slow()。这些函数的实现对理解SMP的调度非常重要，下面一一分析这些函数。先给出每个函数的主要流程图，然后 给出，并加注释。 　　goodness()函数分析 　　goodness()函数计算一个处于可运行状态的进程值得运行的程度。一个任务的 goodness是以下因素的函数：正在运行的任务、想要运行的任务、当前的CPU。goodness返回下面两类值中的一个：1000以下或者1000 以上。1000或者1000以上的值只能赋给“实时”进程，从0到999的值只能赋给普通进程。实际上，在单处理器情况下，普通进程的goodness值 只使用这个范围底部的一部分，从0到41。在SMP情况下，SMP模式会优先照顾等待同一个处理器的进程。不过，不管是UP还是SMP，实时进程的 goodness值的范围是从1001到1099。 　　goodness()函数其实是不会返回-1000的，也不会返回其他负值。由于idle进程的counter值为负，所以如果使用idle进程作为参数调用goodness，就会返回负值，但这是不会发生的。 　　goodness()是个简单的函数，但是它是linux调度程序不可缺少的部分。运行队列中的每个进程每次执行schedule时都要调度它，因此它的执行速度必须很快。 　　//在/kernel/sched.c中 　　static inline int goodness(struct task_struct * p， int this_cpu， struct mm_struct *this_mm) 　　{ int weight； 　　if (p->；；policy ！= SCHED_OTHER) {/*如果是实时进程，则*/ 　　weight = 1000 + p->；；rt_priority； 　　goto out； 　　} 　　/* 将counter的值赋给weight，这就给了进程一个大概的权值，counter中的值表示进程在一个时间片内，剩下要运行的时间.*/ 　　weight = p->；；counter； 　　if (！weight) /* weight==0，表示该进程的时间片已经用完，则直接转到标号out*/ 　　goto out； 　　#ifdef __SMP__ 　　/*在SMP情况下，如果进程将要运行的CPU与进程上次运行的CPU是一样的，则最有利，因此，假如进程上次运行的CPU与当前CPU一致的话，权值加上PROC_CHANGE_PENALTY，这个宏定义为20。*/ 　　if (p->；；processor == this_cpu) 　　weight += PROC_CHANGE_PENALTY； 　　#endif 　　if (p->；；mm == this_mm) /*进程p与当前运行进程，是同一个进程的不同，或者是共享地址空间的不同进程，优先选择，权值加1*/ 　　weight += 1； 　　weight += p->；；priority； /* 权值加上进程的优先级*/ 　　out： 　　return weight； /* 返回值作为进程调度的唯一依据，谁的权值大，就调度谁运行*/ 　　} 　　schedule()函数分析 　　schedule()函数的作用是，选择一个合适的进程在CPU上执行，它仅仅根据'goodness'来工作。对于SMP情况，除了计算每个进程的加权平均运行时间外，其他与SMP相关的部分主要由goodness()函数来体现。 　　流程： 　　①将prev和next设置为schedule最感兴趣的两个进程：其中一个是在调用 schedule时正在运行的进程(prev)，另外一个应该是接着就给予CPU的进程（next）。注意：prev和next可能是相同的 -schedule可以重新调度已经获得cpu的进程. 　　②中断处理程序运行“下半部分”. 　　③内核实时系统部分的实现，循环调度程序（SCHED_RR）通过移动“耗尽的”RR进程-已经用完其时间片的进程-到队列末尾，这样具有相同优先级的其他RR进程就可以获得CPU了。同时，这补充了耗尽进程的时间片。 　　④由于代码的其他部分已经决定了进程必须被移进或移出TASK_RUNNING状态，所以会经 常使用schedule，例如，如果进程正在等待的硬件条件已经发生，所以如果必要，这个switch会改变进程的状态。如果进程已经处于 TASK_RUNNING状态，它就无需处理了。如果它是可以中断的（等待信号），并且信号已经到达了进程，就返回TASK_RUNNING状态。在所以 其他情况下（例如，进程已经处于TASK_UNINTERRUPTIBLE状态了），应该从运行队列中将进程移走。 　　⑤将p初始化为运行队列的第一个任务；p会遍历队列中的所有任务。 　　⑥c记录了运行队列中所有进程最好的“goodness”-具有最好“goodness”的进程是最易获得CPU的进程。goodness的值越好。 　　⑦遍历执行任务链表，跟踪具有最好goodness的进程。 　　⑧这个循环中只考虑了唯一一个可以调度的进程。在SMP模式下，只有任务不在cpu上运行时，即can_schedule宏返回为真时，才会考虑该任务。在UP情况下，can_schedule宏返回恒为真. 　　⑨如果循环结束后，得到c的值为0。说明运行队列中的所有进程的goodness值都为0。 goodness的值为0，意味着进程已经用完它的时间片，或者它已经明确说明要释放CPU。在这种情况下，schedule要重新计算进程的 counter；新counter的值是原来值的一半加上进程的静态优先级（priortiy），除非进程已经释放CPU，否则原来counter的值为 0。因此，schedule通常只是把counter初始化为静态优先级。（中断处理程序和由另一个处理器引起的分支在schedule搜寻 goodness最大值时都将增加此循环中的计数器，因此由于这个原因计数器可能不会为0。显然，这很罕见。）在counter的值计算完成后，重新开始 执行这个循环，找具有最大goodness的任务。 　　⑩如果schedule已经选择了一个不同于前面正在执行的进程来调度，那么就必须挂起原来的进程并允许新的进程运行。这时调用switch_to来进行切换。