进程调度即处理器调度。在多道程序设计环境中，进程数目往往多于处理器数，这将导致多个进程互相争夺处理器。进程调度的任务是控制、协调进程对处理器的竞争，按照一定 的调度算法，使某一就绪进程获得CPU的控制权，转换成运行状态。实际上进程调度完成 一个物理CPU转变成多个虚拟的（或逻辑的）处理器的工作。 需要说明的是由于进程调度的相关内容同样适用于线程调度，所以以下只介绍进程调度。

一、概述

1、进程调度的主要功能

功能：记录系统中所有进程的执行状况；根据一定的调度算法，从就绪队列中选出一个进程， 准备把处理器分配给它；把处理器分配给进程。即把选中进程的进程控制块内有关的现场信 息，如程序状态字、通用寄存器等内容送入处理器相应的寄存器中，从而让它占用处理器运行。

2.进程调度的时机

进程调度发生的时机（什么时候会发生进程调度呢？）：

(1)正在执行的进程运行完毕。

(2)正在执行的进程由于某种错误而终止。

(3)时间片用完，即有一个进程从运行状态变为就绪状态。

(4)正在执行的进程调用阻塞原语将自己阻塞起来，即一个进程从运行状态进入阻塞状态。

(5)创建了新的进程，即有一个新的进程进入就绪队列。

(6)正在执行的进程调用了唤醒原语操作激活了等待资源的进程，即一个等待状态的进程变为就绪状态。

处理器的调度方式有两种：抢占式和非抢占式（又称为不可抢占式）。所谓可抢占方 式，即就绪队列中一旦有优先级高于当前运行进程优先级的进程存在时，便立即进行调度， 转让处理器。而不可抢占方式，即一旦把处理器分配给一个进程，它就一直占用处理器，直到该进程自己因调用原语操作或等待I/O而进人阻塞状态，或时间片用完时才让出处理器， 重新执行进程调度。

以上6种调度时机中，(5)和(6)两种是在处理器调度方式为可抢占时会引起进程调度的原因，因为此时就绪队列中可能有优选级高于当前运行进程的优先级的进程出现。

二、调度算法设计原则

1.进程行为

几乎所有进程的（磁盘）I/O请求或计算都是交替突发的。例如，处理器运行一段时间 后，发出一个读写文件的系统调用。在完成系统调用之后，处理器又开始计算，直到它需要读写更多的数据为止。当然，某些I/0活动可以看作是计算。例如，当CPU向视频RAM复制数据以更新屏幕时，因为使用了处理器，所以这是计算，而不是I/O。按照这种观点，当 一个进程等待外部设备完成工作而被阻塞的行为属于I/O。

因此，某些进程花费了绝大多数时间在计算上(计算密集型)，而其他进程则在等待I/O上花费了绝大 多数时间(I/O密集型)。前者称为计算密集型（Compute-bound)，后者称为I/O密集型（I/0-boimd)。典型的计算密集型进程具有较长时间的处理器集中使用和较小频度的I/O等待。I/O密集型进程是I/O类的，因为这种进程在I/O请求之间较少进行计算，并不是因为它们有特别长的I/O请求。在I/O开始后无论处理数据是多还是少，它们都花费同样的时间提出硬件请求读取磁盘块。

随着CPU变得越来越快，更多的进程倾向为I/O密集型。这种现象之所以发生是因为处理器的改进比磁盘的改进快得多，其结果是，未来对I/O密集型进程的调度处理似乎更为重要。其基本思想是，如果需要运行I/O密集型进程，那么就应该让它尽快得到机会，以便发出磁盘请求并保持磁盘始终忙碌。而且，如果进程是I/O密集型的，则需要多运行一些这 类进程以保持处理器的充分利用。

2.系统分类

因为不同的应用领域（以及不同的操作系统）有不同的目标，所以，不同的环境需要不同的调度算法。

通常可以分为三类环境：批处理、交互式和实时系统。

批处理系统在商业领域仍在广泛应用，用来处理薪水册、存货清单、账目收人、账目支 出、利息计算（在银行）、索赔处理（在保险公司）和其他的周期性的进程。在批处理系统 中，不会有用户不耐烦地在终端旁等待一个短请求的快捷响应。因此，非抢占式算法，或对每个进程都有长时间周期的抢占式算法，通常都是可接受的。这种处理方式减少了进程的切换从而改善了性能。这些批处理算法实际上相当普及，并经常可以应用在其他场合，这使得 人们值得去学习它们，甚至是对于那些没有接触过大型机计算的人们。

在交互式用户环境中，为了避免一个进程霸占处理器拒绝为其他进程服务，抢占是必须的。即便没有进程想永远运行，但是，某个进程由于一个程序错误也可能无限期地排斥所有其他进程。为了避免这种现象发生，抢占也是必要的。服务器也归于此类，因为通常它们要 服务多个突发的（远程）用户。

然而在有实时限制的系统中，抢占有时是不需要的，因为进程了解它们可能会长时间得 不到运行，所以通常很快地完成各自的工作并阻塞。实时系统与交互式系统的差别是，实时系统只运行那些用来推进现有应用的程序，而交互式系统是通用的，它可以运行任意的非协作甚至是有恶意的程序。

3.调度算法的设计目标

设计调度算法的目标取决于环境，例如批处理、交互式或实时，但是，有一些目标是适用于所有系统的。

在所有的情形中，公平是很重要的。相似的进程应该得到相似的服务。对一个进程给予较其他等价的进程更多的处理器时间是不公平的。当然，不同类型的进程可以采用不同方式处理。

与公平有关的是系统策略的强制执行。如果局部策略是只要需要就必须运行安全控制进 程，那么调度程序就必须保证能够强制执行该策略。

另一个共同的目标是保持系统的所有部分尽可能忙碌。如果处理器和所有I/O设备能够 始终运行，那么相对于让某些部件空转而言，每秒钟就可以完成更多的工作。例如，在批处 理系统中，调度程序控制哪个进程调入内存运行。在内存中既有一些处理器密集型进程又有 一些I/O密集型进程是一个较好的想法，好于先调人和运行所有的处理器密集型进程，然后 在它们完成之后再调人和运行所有I/O密集型进程的做法。如果使用后面一种策略，在处理 器密集型进程运行时，它们就要竞争处理器，而磁盘却在空转。稍后，当I/O密集型进程来 了之后，它们要为磁盘而竞争，而处理器又空转了。显然，通过对进程的仔细组合，保持整 个系统都在运行更好一些。

运行大量批处理进程的大型计算中心的管理者们为了掌握其系统的工作状态，通常检查 三个指标：吞吐量、周转时间以及处理器利用率。吞吐量（Throughout)是系统每小时完成 的进程数量。把所有的因素考虑进去之后，每小时完成50个进程好于每小时完成40个进 程。周转时间（Tumarmmd Time)是指从一个批处理进程提交时刻开始直到该进程完成时刻 为止的统计平均时间。该数据度量了用户要得到输出’所需的平均等待时间。其规则是：小就是好的。

能够使吞吐量最大化的调度算法不一定就有最小的周转时间。例如，对于一个确定的短进程和长进程的一个组合，总是运行短进程而不运行长进程的调度程序，可能会获得出色的吞吐性能（每小时大量的短进程），但是其代价是对于长的进程周转时间很差。如果短进程 以一个稳定的速率不断到达，长进程可能根本运行不了，这样平均周转时间是无限长，但是得到了高的吞吐量。

处理器利用率常常用于对批处理系统的度量。尽管这样，处理器利用率并不是一个好的度量参数。真正有价值的是，系统每小时可完成多少进程（吞吐量），以及完成进程需要多 长时间（周转时间）。把处理器利用率作为度量依据，就像用引擎每小时转动了多少次来比 较汽车的好坏一样。另一方面，知道什么时候处理器利用率接近100%比知道什么时候要求 得到更多的计算能力要有用。

对于交互式系统，特别是分时系统和服务器，则有不同的指标。最重要的是最小响应时间，即从发出命令到得到响应之间的时间。在有后台进程运行（例如，从网络上读取和存储电子邮件）的个人计算机上，用户请求启动一个程序或打开一个文件应该优先于后台的工作。能够让所有的交互式请求首先运行的则是好服务。

一个相关的问题是均衡性。用户对做一件事情需要多长时间总是有一种固有的（不过通常不正确）看法。当认为一个请求很复杂需要较多的时间时，用户会接受这个现实，但是当认为一个请求很简单，但也需要较多的时间时，用户就会急躁。例如，如果点击一个图标花费了 60s发送完成一份传真，用户大概会接受这个事实，因为他没有期望花5s得到传 真。另一方面，当传真发送完成，用户点击断开电话连接的图标时，该用户就有不一样的期 待。如果30s之后还没有完成断开操作，用户就可能会抱怨，而60s之后，他就要气得要命 了。之所以有这种情况，其原因是：一般用户认为拿起听筒并建立通话连接所需的时间要比挂掉电话所需的时间长。在有些情形下，调度程序对响应时间指标起不了作用; 但是在另外一些情形下，调度程序还是能够做一些事的，特别是在出现差的进程顺序选择时。

实时系统有着与交互式系统不一样的特性，所以有不同的调度目标。实时系统的特点是或多或少必须满足截止时间。例如，如果计算机正在控制一个以正常速率产生数据的设备， 若一个按时运行的数据收集进程出现失败，就会导致数据丢失。所以，实时系统最主要的要 求是满足所有的（或大多数）截止时间要求。

三、进程调度算法

进程调度算法解决以何种次序对各就绪进程进行处理器的分配以及按何种时间比例让进程占用处理器。

1、先来先服务算法

在所有调度算法中，最简单的是非抢占式的先来先服务（First-Come First-Served, FCFS)算法。使用该算法，进程按照它们请求处理器的顺序使用处理器。当第一个进程从 外部进人系统，就立即开始并允许运行它所期望的运行时间。不会中断该进程，因为它需要 很长的时间运行。当其他进程进入时，它们就被安排到队列的尾部。当正在运行的进程被阻塞时，队列中的第一个进程就接着运行。在被阻塞的进程变为就绪时，就像一个新来到的进程一样，排到队列的末尾。

这个算法的主要优点是易于理解并且便于在程序中运用。在这个算法中，一个单链表记录了所有就绪进程。要选取一个进程运行，只要从该队列的头部移走一个进程即可；要添加 一个新的进程或阻塞一个进程，只要把该进程或进程附加在相应队列的末尾即可。

不过，先来先服务算法也有明显的缺点。这里举一个例子，有3个进程A、B、C，运 行时间分别为24, 3, 3s。现在使用先来先服务算法运行这3个进程，若进程到达顺序为A、 B、C，周转时间分别为24、27、30s，平均周转时间为27s。调整进程运行顺序为B，C，A。 则A，B，C的周转时间分别为30, 3, 6s，平均周转时间为13s。可见，先来先服务算法公平、简单，但是在处理长进程之后的短进程需要等待很长时间，不利于用户的交互体验。

2、最短进程优先算法

一种适用于运行时可以预知的另一个非抢占式的批处理调度算法。例如，一家保险公司，因为每天都做类似的工作，所以人们可以相当精确地预测处理1000个索赔的一 批进程需要多少时间。当输人队列中有若干个同等重要的进程被启动时，调度程序应使用最短进程优先（ShortestJobHrst，SJF)算法。这里举一个例子，有4个进程A、B、C、D， 运行时间分别为8, 4, 4, 4s。若按A、B、C、D的次序运行，则A的周转时间为8s，B为 12s，C 为 16s，D 为 20s，平均为 14s。

现在考虑使用最短进程优先算法运行这4个进程，运行顺序为B、C、D、A。则周转时 间分别为4、8、12和20s，平均为11s。可以证明最短进程优先是最优的。考虑有4个进程的情况，其运行时间分别为a，b，c，d。第一个进程在时间a结束，第二个在时间a + b 结束，依次类推。平均周转时间为（4a+3b+2c+d) /4。显然a对平均值影响最大，所以 它应是最短进程，其次是b，再次是c，最后的d只影响它自己的周转时间。对任意数目进 程的情况道理完全一样。有必要指出，只有在所有的进程都同时可运行的情形下，最短进程优先算法才是最优化的。作为一个反例，考虑5个进程，从A到E，运行时间分别是2, 4, 1，1和1。它们的到达时间是0, 0, 3, 3和3。开始，只能选择A或B，因为其他的进程还 没有到达。使用最短进程优先，将按照A，B，C，D, E的顺序运行进程，其平均等待时间 是4.6。但是，按照B，C，D, E，A的顺序运行进程，其平均等待时间则是4.4。

3、最短剩余时间优先算法

最短进程优先算法的抢占式版本是最短剩余时间优先（Shortest Remaining Time Next， SRTN)算法。使用这个算法，调度程序总是选择其剩余运行时间最短的那个进程运行。当 一个新的进程到达时，其整个时间同当前进程的剩余时间做比较。如果新的进程比当前运行进程需要更少的时间，当前进程就被挂起，而运行新的进程。这种方式可以使新的短进程获 得良好的服务。

4、最高响应比优先算法

在批处理系统中，最高响应比优先算法（Highest Response Rate First，HRRF)的性能是介于先来先服务和最短进程优先算法之间的折中的算法，先来先服务算法在调度中最为公 平，但是一旦出现计算密集型的长进程则会对其他进程造成较长时间的等待；最短进程优先算法又偏好短进程，当短进程源源不断进入后备池时，长进程将会长时间滞留在后备池中， 其运行将得不到保证，出现这种现象我们称为长进程处于“饥饿（Starvation)”。

如果能为每个进程引人响应比，情况就会有所改善。响应比的计算式为：

响应比Rp =(等待时间+预计运行时间)/预计运行时间=周转时间/预计运行时间

每个进程随着在后备池等待时间的增涨其响应比也不断增加，而且，预计运行时间越短的进程响应比增涨越快，最高响应比优先算法在每次调度时选择响应比最高的进程投入运 行。这种算法较好地适应了长短进程混合的系统，使得调度的性能指标趋于合理。

这里举一个例子，有三个进程A、B、C，它们到达的相对时间为0s，20s，60s，需要的 运行时间分别为80s，20s，40s。

当这三个进程全部到达后，系统按照最高响应比优先算法进行调度。假设执行进程调度 的时间选在进程全部到达之后开始进行调度。此时，A、B、C分别等待了 60s、40s、0s， 计算三个进程的响应比如下。

A 的响应比=1 +60/80 = 1.75。

B的响应比=1 +40/20二3。

C的响应比=1 +0/20 = 1。

由此得出，B的响应比最高，所以优先选择B装入内存执行。B执行结束后，重新进行 调度时，由于等待时间发生了变化，计算三个进程的新的响应比如下。

A的响应比为1 +80/80 =2, B的响应比为1 +20/40 = 1.5。得出A的响应比高于C的 响应比，因而应选择A执行。最后再让C执行。

最高响应比优先算法在一定程度上改善了调度的公平性和调度的效率，响应比在每次调度前进行计算，进程运行期间不计算。计算需要消耗系统的资源，存在一定的系统开销。

5、轮转算法

轮转（Roimd-Robin，RR)算法最早来自分时系统。轮转算法的基本思想是，将处理器的处理时间划分成一个个时间片，就绪队列中的诸进程轮流运行一个时间片。当时间片结束时，就强迫运行进程让出处理器，该进程进人就绪队列，等待下一次调度。同时，进程调度又去选择就绪队列中的一个进程，分配给它一个吋间片，以投人运行。如此轮流调度，使得就绪队列中的所有进程在一个有限的时间内都可以依次轮流获得一个时间片的处理器时间，从而满足了系统对用户分时响应的要求。

在轮转算法中，时间片长度的选取非常重要，将直接影响系统开销和响应时间。如果时间片长度很小，则调度程序剥夺处理器的次数频繁，加重系统开销；反之，如果时间片长度选择过长，例如一个时间片就能保证就绪队列中所有进程都执行完毕，则轮转法就退化成先来先服务算法。

下面是影响时间片值设置的几个主要因素。

(1) 系统响应时间：当进程数目一定时，时间片Q值的大小正比于系统对响应时间的要求，例如进程数目为N，要求的响应时间为T，则Q=T/N，Q值随T值的大或小而大或小。

(2)就绪进程的数目：当系统响应时间T一定时，时间片值的大小反比于就绪进程数。

(3)计算机的处理能力：计算机的处理能力直接决定了每道程序的处理时间，显然，处理速度越高，时间片值就可以越小。

此外，从一个进程切换到另一个进程是需要一定时间进行管理事务处理的——保存和装入寄存器值及内存映像，更新各种表格和列表，清除和重新调入内存高速缓存等。假如进程 切换（又称为上下文切换），需要1ms，包括切换内存映像，清除和重新调人高速缓存等。 再假设时间片设为4ms。有了这些参数，则处理器在做完4ms有用的工作之后，处理器将花 费lms来进行进程切换。因此，处理器时间的20%被浪费在管理开销上。很明显，这一管 理时间太多了。

为了提高处理器的效率，我们可以将时间片设置成100ms，这样浪费的时间只有1%。 但是，如果在一段非常短的时间间隔内到达50个请求，并且对处理器有不同的需求，那么， 考虑一下，在一个服务器系统中会发生什么呢？ 50个进程会放在可运行进程的列表中。如果CPU是空闲的，第一个进程会立即幵始执行，第二个直到100ms以后才会启动，以此类推。假设所有其他进程都用足了它们的时间片的话，最不幸的是最后一个进程在获得运行机会之前将不得不等待5s。大部分用户会认为5s的响应对于一个短命令来说是缓慢的。如果 一些在队列后端附近的请求仅要求几毫秒的处理器时间，上面的情况会变得尤其糟糕。如果使用较短的时间片，它们将会获得更好的服务。 另一个因素是，如果时间片设置长于平均的处理器突发时间，那么不会经常发生抢占。

相反，在时间片耗费完之前多数进程会完成一个阻塞操作，引起进程的切换。抢占的消失改善了性能，因为进程切换只会发生在确实逻辑上有需要的时候，即进程被阻塞不能够继续运行。

可以归结如下结论：时间片设得太短会导致过多的进程切换，降低了处理器效率；而设 得太长又可能引起对短的交互请求的响应时间变长。将时间片设为20〜50ms通常是一个比 较合理的折衷。

为每个进程分配固定时间片的方法显然简单易行，微型计算机分时系统多采用之。也可采用可变时间片的方法，以进一步改善轮转算法的调度性能。例如，根据进程的优先数分配 适当的时间片，优先数较高的进程，给予较大的时间片；又如，依据在某段时间中系统中存 在的就绪进程数目动态调整时间片值。

6、最高优先级算法

最高优先级（Highest Priority First，HPF)进程调度算法每次将处理器分配给具有最高优先级的就绪进程。进程的优先级由进程优先数决定。

进程优先数的设置可以是静态的，也可以是动态的。静态优先数是在进程创建时根据进程初始特性或用户要求而确定的，在进程运行期间不能再改变。动态优先数则是指在进程创建时先确定一个初始优先数，以后在进程运行中随着进程特性的改变（如等待时间增长）， 不断修改优先数。在有的系统中，优先数小的进程优先级高。

最高优先级算法还可以和不同的处理器调度方式结合起来，从而形成可抢占式最高优先级算法和不可抢占式最高优先级算法。显然，抢占式算法更好地反映了优先级的特征，可以使高优先级进程尽可能快地完成其任务的目标，从而获得了较好的服务质量。但是抢占式算法无疑也增加了系统的开销。

为达到某种目的，优先级也可以由系统动态确定。例如，有些进程为I/O密集型，其多数时间用来等待I/O结束。当这样的进程需要处理器时，应立即分配给它处理器，以便启动 下一个I/O请求，这样就可以在另一个进程计算的同时执行I/O操作。使这类I/O密集型进 程长时间等待处理器只会造成它无谓地长时间占用内存。使I/O密集型进程获得较好服务的 一种简单算法是，将其优先级设为1/f，f为该进程在上一时间片中所占的部分。一个在其 50ms的时间片中只使用lrns的进程将获得优先级50,而在阻塞之前用掉25ms的进程将具 有优先级2,而使用掉全部时间片的进程将得到优先级1。

可以很方便地将一组进程按优先级分成若干类，并且在各类之间采用优先级调度，而在 各类进程的内部采用轮转调度。例如，有一个具有4类优先级的系统，其调度算法如下：只要存在优先级为第4类的可运行进程，就按照轮转法为每个进程运行一个时间片，此时不理 会较低优先级的进程。若第4类进程为空，则按照轮转法运行第3类进程。若第4类和第3 类均为空，则按轮转算法运行第2类进程。如果不对优先级进行调整，则低优先级进程很可 能会产生饥饿现象。

7、多级反馈队列算法

在实际的计算机系统中，进程的调度模式往往是几种调度算法的结合。例如，可以以最 高优先级算法作为主要的调度模式，但对于具有相同优先数的进程则按先进先出调度算法处理。又如，可以将时间片轮转算法和最高优先级算法结合，对于具有相同优先数的进程按时 间片轮转调度算法处理。多级队列反馈法就是综合了先进先出调度算法、时间片轮转算法和可抢占式最高优先级算法的一种进程调度算法。

多级反馈队列法的基本思想有如下几个基本要点。

(1)被调度队列的设置。系统按优先级别设置若干个就绪队列；不同优先级别的队列有不同的时间片，对级别较高的队列分配较小时间片Si（i = l，2,…n)，从而有S1<S2<…<Sn。

(2)在同一个队列之内的调度原则。除了第n级队列是按轮转算法调度之外，其他各级队列均按先进先出调度算法调度。

(3)在不同队列之间的调度原则。系统总是先调度级别较高的队列，仅当级别较高的队 列为空时才去调度次一级队列中的进程。

(4)进程优先级的调整原则。当正在执行的进程用完其时间片之后，便被换出并进入次一级的就绪队列。当等待进程被唤醒时，它进入与其优先级同的就绪队列；若该进程优先级高于正在执行的进程，便抢占处理器。