2.5 调度机制

在多道程序设计系统中，操作系统需要为各个进程合理分配各种资源，从而使得不仅不会让它们的运行相互产生冲突，而且还能对这些资源进行充分利用。在计算机系统中，最宝贵并且最容易引起各进程竞争的资源就是处理器。如何公平合理地分配给各进程足够的处理器时间，并且尽可能提高处理器的利用率同样是操作系统原理研究的重要内容，而这个任务是由操作系统的调度机制完成的。

调度机制一向都是学术研究的热点，人们已经提出了很多调度算法，现在主要集中在多处理器调度上，同时还有进程的实时调度方面。

2.5.1 调度类型

前面已经讲过了，调度是多道程序设计的关键，可以将调度大致分为4种类型（表2-2），其中I/O调度留在后面的I/O设备章节阐述。这里主要阐述单处理器调度、多处理器调度和实时调度都会遇见的3种类型，即长期调度、中期调度和短期调度。长期调度在一个进程创建时起作用，它将决定哪一个程序会被系统选中并创建一个新的进程来运行它；中期调度则是决定进程在内存中的换入、换出，其主要机制在内存管理章节已经有阐述，归根到底中期调度是一个内存分页的换入、换出机制问题；短期调度则是真正决定哪个等待进程该获得处理器控制权的关键，这就是通常所说的调度，包括单处理器调度（Uniprocessor Scheduling）、多处理器调度（Multiprocessor Scheduling）和实时调度（Real-Time Scheduling）等。调度通过影响进程的行为来影响系统的性能。

下面来着重看看短期调度及其评价标准。

通常当某个事件的发生导致需要挂起某个进程或者需要某个进程以抢占式方式替换另外一个正在运行中的进程以取得处理器控制权的时候，短期调度就被激活。这样的事件可以是时钟中断、I/O中断、操作系统调用或者信号等。

短期调度的衡量标准是双重的，可以按照是用户相关还是系统相关来分，也可以按照是否是性能相关来分。用户相关的标准主要是以用户的主观感受为准，例如响应时间就是一个很典型的用户相关的评价标准；系统相关的标准主要是看处理器的使用效率等因素，例如计算任务的吞吐量。在不同的系统中，这两种评价标准所占有的地位显然是不一样的。比如说，在单用户系统中，我们评价一个调度算法的好坏主要看系统的响应时间，而不会去关心处理器的利用效率有多高。

系统性能相关的标准主要是一些可以量化的，并且通常是可以很方便测量出来的量，如反应时间和吞吐量。非系统性能相关的标准则是一些本质上的不能量化的或者不能很方便测量出来的量，如可预测性等。表2-4给出了按照这些标准的组合，一共有9项。

2.5.2 单处理器调度

已提出的单处理器调度算法主要包括这么几种：FCFS（First Come First Served）、SPN（Shortest Process Next）、SRT（Shortest Remaining Time）、HRRN（Highest Response Ratio First）、反馈算法（Feedback）和循环执行算法（Round Robin），下面分别给予阐述。

1.FCFS算法

FCFS算法是一种非常简单的调度算法，通常也被称为FIFO（First In First Out）。当一个进程转为就绪（准备）状态的时候，它就被加到一个等待进程队列的队尾。当某个正在运行中的进程停止运行时，根据FCFS调度算法，队首的一个进程，也是等待时间最长的那个进程将会出列并开始运行。该算法是非抢占式的。

2.循环执行算法

循环执行算法的基本指导思想是，将处理器时间分成一个一个的时间片（Time Slice），它从等待进程队列中选择下一个运行进程的方法和FCFS一样，所不同的是每一个被选中的进程一次所占有的处理器时间顶多是一个时间片，而后，下一个被选中的进程将会以抢占式的方式来顶替该进程取得处理器的控制权。将处理器时间分片是靠定时器中断来实现的，即每当一个时间片耗完之后，会有一个中断产生，告知调度程序，然后调度算法就会被激活，进而选取下一个要运行的进程，开始新一轮循环。

循环执行算法有一个缺点就是，它在处理I/O操作密集型进程时和处理器使用密集型进程时会带来资源使用的不平衡。I/O密集型进程会导致I/O设备忙，而处理器使用却很少；处理器使用密集型进程则会让处理器连轴转，而I/O设备却往往处于空闲状态。这会导致该算法在进程间的公平性和资源使用的平衡度方面表现比较差，于是就有人提出了虚拟循环执行算法（图2-7）。

虚拟循环执行算法的进程创建、入列，以及被选中的运行部分与FCFS算法别无二致，所不同的是加入了一个辅助进程队列。这样，如果一个原来因为I/O操作挂起的进程申请的I/O操作已经完成的话，它不是进入普通的等待进程队列，而是进入辅助进程队列。当一个新的处理器时间片来临的时候，辅助进程队列里的进程比普通的等待进程队列里的进程优先获取处理器控制权，而其运行时间将不会超过它在上一次自己获取的时间片里用剩下来的时间。循环执行算法和虚拟循环执行算法都是抢占式的。

3.SPN算法

SPN算法是在一个进程运行完毕之后，选择需要最短运行时间的进程运行。SPN算法实践起来的一个难点就是如何对进程的运行时间进行估量。可以通过程序员来进行估量，但是这样做并不保险，因为可能会出现偏差。现在比较常用的方法就是通过实验，多次重复得到一组时间值，要么直接取平均，要么取加权平均，以便获得较为客观的运行时间估计。

SPN算法实施起来有一个危险，就是因为不断会有运行时间较短的进程出现在等待队列中，所以某些运行时间较长的进程可能会永远得不到处理器时间片。解决方法也不是没有，比如说可以对每个进程可等待的时间做一个上限，当达到这个上限值之后，不管三七二十一，它就得运行。该算法是非抢占式的。

4.SRT算法

SRT算法可以看做SPN算法的一个抢占式版本。在这个算法中，调度程序总是选择剩余时间最短的进程运行。当一个新的进程加入到等待进程队列时，它可能比现在正在运行的进程所需要的剩余时间更短，这个时候，调度程序就会中断现在正在运行的进程转而执行新加入的进程。和SPN算法类似，SRT算法仍然需要估算进程运行所需的时间。同样也面临需要较长运行时间的进程很难得到处理器时间的问题。

5.HRRN算法

HRRN算法的基本思想就是调度程序选择下一个运行进程时遵循最高响应时间比率原则。下面我们给出响应时间比率的计算方法。

其中，w是进程等待获取处理器控制权所耗费的时间，s是进程运行所耗费的时间预期。

6.反馈算法

如果我们事先不知道各进程运行时的时间参数，例如运行耗费时间、等待时间等，那么这个时候SPN、SRT、HRRN等算法是没法使用的。反馈算法的提出就是希望能够通过对进程运行已经耗费的时间进行统计，从而决定下一个运行进程该是哪一个，其指导原则就是过去运行总时间最短者最先得到处理器时间。

反馈算法的一个比较简单的实现可以是：当一个进程被创建时，它进入优先级最高的等待队列，每运行完一段时间后，它会被放入一个优先级较低的等待队列等待下一次运行，如此递推，直到它执行完任务为止。这里需要明确的一点就是，优先级高的等待队列里的进程比优先级较低的等待队列里的进程优先得到处理器控制权，这样使得运行时间比较短的进程可以更早地完成任务。

2.5.3 多处理器调度

多处理器系统按照各处理器之间的关系一般可以分为两类。

● 松耦合型：这样的系统通常是一些自治子系统的组合，每个子系统都有自己独立的处理器、内存、I/O及操作系统。

● 紧耦合型：这样的系统通常是一组处理器共用一个内存，并处于一个操作系统的控制之下。

紧耦合型多处理器系统仍然可以进一步划分成两种。其中一种是主/从型，即其中一块处理器属于通用型，功能比较强，而另外的处理器则属于专用型，功能相对单一，两种类型的处理器组成主从关系。另外一种紧耦合型多处理系统是对等型系统，即各处理器在功能等方面是对等的，没有差别。我们后面要讲的多处理器调度算法就是针对这样一种对等型紧耦合多处理器系统的。

1.总体设计

多处理器系统与单处理器系统相比给调度算法的设计带来了几个新问题，一般需要考虑3方面的事情：按处理器分配进程问题、单个处理器上的多道程序设计问题和进程实际分派问题。不管是哪个问题，需要明白的就是具体算法的设计同具体应用的特点及处理器的个数是相关的。

（1）按处理器分配进程

如何将进程的运行和具体的处理器对应起来是多处理系统调度算法首先要考虑的问题。在对等型紧耦合多处理器系统中，最简单的调用方法就是将多个处理器统看成一个处理器资源库，当有进程需要使用处理器时，就从这个库中拿出相应的资源分配给它。这样，处理器的分配方法就有两种，即静态方法和动态方法。

处理器分配的静态方法是指当某个进程一旦分配到某个处理器上运行之后，在它的整个生命周期中，该进程不会再更改处理器了。静态分配方法比较简单，这是它的优势所在。但是却有一个缺点，就是它会经常导致各处理器负荷不均衡，也就是说，某些处理器可能一直忙着，而有的处理器则可能闲置着。处理器分配的动态方法则允许进程在其运行过程中可以选择不同的处理器。由于在紧耦合多处理器系统中，处理器共享内存，所以进程的各类信息对各个处理器都是可见的，且迁移代价是可以忽略的。

进程间的地位并非是平等的，有些是核心进程，有些只是一般的用户进程。不同种类的进程如何去占用处理器呢？其主要有两种方式。一种是主/从方式，在这种方式中，操作系统的核心部分总是运行在一个特定的处理器上，而另外的处理器只运行用户进程。这种方式比较简单，但是问题是，如果这个特定的处理器出现故障的话，将会导致整个系统崩溃，并且主处理器可能会存在性能瓶颈。另外一种方式就是对等方式，即操作系统可以在任何一个处理器上运行，并且每一个进程自己从处理器资源库中选择处理器以实现自动调度。这种方式比较复杂，事实上很多系统的实现是取这两种极端方式的折衷。

（2）单处理器上的多道程序设计

当采用处理器分配的静态方法时，一个新问题就随之而来：各个处理器是否应该采用多道程序设计？在单处理器系统中，如果不采用多道程序设计的话，处理器可能会因为进程在长时间等待某个I/O操作而造成计算资源的浪费。那么，在多处理器系统中是否也一定需要有这样的考虑呢？

在传统的多处理器系统中，各个处理器之间要求同步的频率很低，或者说各处理器之间相对独立地工作着。在这种情况下，每个处理器在功能上等同于一个单处理器系统，这个时候希望它们能够采用多道程序设计方式运作，这样能够显著提高处理器的利用率。但是如果各处理器之间的联系属于紧耦合型，需要不断地进行同步，这个时候，是不是要采用多道程序设计就不好说了。当有很多处理器存在的时候，主要关心的事情并不是某个或者某些处理器的利用率，而是这个系统整体上的性能。当一个应用程序是多线程时，只有当所有线程都在运行时，程序的性能才会有显著提高，反之，可能会表现很次。

（3）进程分派

首先需要明确的一点是，在单处理器系统中性能较好的调度算法在多处理器系统中并不见得就一样能取得好的性能。在单处理器系统中，基于优先级或者基于反馈的调度算法比起先到先运行这样的简单算法，性能更优越。但是在多处理系统中，可能一些简单的算法会更好一些，而类似基于反馈这样的算法反而可能会导致系统性能的下降。另外，需要注意的是，在多线程调度中，还有一些新的问题需要考虑。

2.进程调度

在很多传统的多处理器系统中，进程并不是直接分配给处理器的。所有的处理器统一起来形成一个计算资源库，进程则按照一定的规则，比如说FIFO或者基于优先级等，形成一个或者若干个队列，按照某种调度算法，这些进程会被一一选中在这个计算资源库中的某个特定的处理器上运行。不管怎么讲，都可以将这样的系统称为提供给进程队列的多路计算服务器。研究表明，调度算法的差异所带来的多处理器系统性能上的差异不是很明显，并且随着处理器数目的增加，这种影响会变得越来越小。

3.线程调度

现在针对多处理器系统的线程调度是学术界的一个研究热点，产生了很多方案。这其中有4种方案比较突出，即负荷共同承担法（Load Sharing）、组调度法（Gang Scheduling）、处理器指定分配法（Dedicated Processor Assignment）及动态调度法（Dynamic Scheduling），下面分别给予介绍。

（1）负荷共同承担

在这个调度方法中，进程并不会分配给某个特定的处理器，而是所有等待运行的线程用一个统一的等待队列来维护。当某个处理器空闲时，它会从这个队列中按照一定的规则选取一个线程来运行，而不需要去管这个线程到底是属于哪个进程的。

采用这个线程调度算法主要有这么3个优点。

● 系统的计算负荷在所有处理器中可以很方便地实现平均分布。

● 不需要有一个中央级的调度程序存在，当某个处理器空闲时，调度程序就在这个处理器上运行并选择下一个需要运行的线程。

● 该调度算法和单处理器调度算法存在天然联系，因此，单处理器调度算法可以很容易地推广到这里来使用。

但是，这个调度算法也存在一些缺点。例如，由于等待线程队列统一管理，所以对于多处理器而言，必须要有互斥控制。如果同时访问该队列的处理器数目较多，就会产生性能上的瓶颈，而且，所有线程统一管理就会使得一个应用程序的所有线程不大可能同时都获得处理器控制权，这样就会导致程序性能上的损失。

（2）组调度

组调度就是将一些相互存在耦合的线程同时一对一地指定给同样数目的处理器运行。组调度策略存在一些优点，比如说，对于几个相互关联的进程，如果并行处理的话，就会减少同步阻塞、减少进程切换，从而提高性能。另外，由于一个调度决策会同时影响一组进程，从而也就降低了调度程序执行的频度。

（3）处理器指定分配

处理器指定分配算法是组调度策略的一个极端情况，其主要思想是，在一个应用程序的生命周期中，将一组处理器都分配给该程序。也就是说，让这个程序的执行进程的每个线程在其生命周期中都能够占用一个处理器。尽管有的时候某个线程为了等待I/O操作的完成进入阻塞状态使得它所占用的处理器处于空闲状态造成了计算资源的浪费，但在处理器数目较多的情况下，应用程序的性能比单个处理器的利用率更重要，并且由于这种方式可以减少进程切换，从而提高了应用程序的性能，所以，采用这么一种调度方式在多处理器系统中还是不错的。

（4）动态调度

在某些应用中，可以借助一些编程语言工具或者系统工具对其中进程所拥有的线程数目做实时修改。这样就可以在进程运行过程中实时调整系统的负荷，从而使系统资源得到最大限度的利用，这就是动态调度的基本思想。

2.5.4 实时调度

实时系统逐渐成为人们研究的热点，而其中的操作系统，更确切地说是操作系统中的调度部分是实时系统的重中之重。小到实验室设备，大到航空航天，实时系统得到了广泛的应用。那么什么是实时系统呢？人们一般认为，实时系统的特征有两点，那就是系统不仅需要给出合乎逻辑的计算结果，而且其处理时间还需要满足一定的要求，例如不能超过某个截止时间等。可以把实时系统分为两类，一类是硬实时（Hard Real-Time），另外一类则是软实时（Soft Real-Time）。所谓硬实时是指如果系统对某个实时任务的处理未能在某个截止时间开始或者结束的话，最终的结果将是灾难性的，这就意味着即便是处理结果合乎逻辑但是仍然毫无意义。但在软实时系统中，处理任务启动或者结束的截止时间只是一个期望值，并不见得必须满足，即便处理时间超过了截止时间，也是有意义的。

另外还可以按照处理任务的特点将实时系统划分为周期性（Periodic）和非周期性（Aperiodic）两种。一个非周期性的任务启动或者结束必须要有一个截止时间；周期性任务则是指处理任务需要在某个时间周期里面完成。

1.实时操作系统的特点

实时操作系统与普通操作系统的区别主要表现在5个方面，即其任务处理的确定性、响应灵敏度、用户参与控制、可靠性及故障保护措施。实时操作系统应当能够做到这一点：实时任务处理的开始时间和结束时间应当是确定的、可预测的。这在实时处理上显得非常重要。从这方面来讲，在实时操作系统中，系统的吞吐量和确定的任务处理相比要次要得多，实时操作系统的任务处理具备一定的确定性。

衡量系统的确定性有一个比较好的指标，就是系统从接到要求处理的中断和对应的处理任务启动这两个事件发生的时间间隔。一般操作系统的这个时间参数很大，而且可能会有几个数量级的变动。但在实时操作系统中，它应当很小，并且比较稳定，有一个上限值。和系统的确定性相关联的是系统的响应灵敏度，它可以定义为系统响应请求的时间。它所关心的是，系统在确认任务请求之后，需要花费多长时间来处理完相关的计算任务。不难看出，系统的确定性和系统的响应灵敏度共同构成了系统对外界的反应时间。用户参与控制是实时操作系统不同于一般操作系统的又一重要特点。在一般操作系统中，用户所能做的只能是希望系统如何，而最后系统完成的如何，那就看系统自己的了。但实时操作系统就不同了。当用户发出控制指令后，系统应严格按照指令办事，并且用户可以实现对系统尽可能多的控制，甚至于在系统的调度算法上。

实时操作系统为了完成一些对处理时间敏感的计算任务，必须要强调可靠性。对于一般的系统而言，某个运行错误可能导致的系统重启或者处理能力下降等问题对系统本身影响并不大，而在实时系统中，这样的错误可能是灾难性的。

计算机系统在运行过程中，难免会出现某些运行故障，并且这些突发故障可能会带来灾难性的后果。一般实时系统都有比较完备的故障保护措施，用于系统发生运行故障之后，尽可能多地保护系统的运行结果，从而为系统的再恢复打下基础。另外，有些系统会有冗余设计，以便降低系统运行的故障率。

2.实时调度

在考察实时调度（Real-Time Scheduling）算法时，可以从3个方面对各种各样的调度算法进行分类：首先看系统是否做调度分析；如果有的话，就看是静态分析还是动态分析；最后看这个分析结果是否直接影响到进程的实时分派。据此，可以将各种实时调度算法大体上分为4类，即ST类、SPP类、DP类、DBE类。

（1）ST（Static Table-driven）类

ST（Static Table-driven）类调度算法就是根据相关信息做出一个切实可行的实时调度计划表，并在系统实时运行时严格按照这个表来调度进程，这类方法比较适合周期性任务。调度分析所需要的信息包括周期性到达时间、执行时间、周期性结束时间，以及各个任务的优先级等。调度算法希望能够制定出一个进程调度计划表来满足所有周期任务的要求，这个方法是确定性的，可以预测实际运行效果，但是却不灵活，并且如果某个任务的特征有所改变的话，就需要把整个调度计划表重新编制。

（2）SPP（Static Priority-driven Preemptive）类

SPP（Static Priority-driven Preemptive）类调度算法也需要做出一个静态调度计划表，但是这么一个表只是在赋予各个任务优先级的时候提供参考，在系统实际运行时，则按赋予任务的优先级来进行抢占式调度。这类调度算法的典型代表就是后面要讲到的RMS调度算法。

（3）DP（Dynamic Planning-based）类

在DP（Dynamic Planning-based）类调度算法中，一个实际有效的调度计划不是在系统运行之前制定的，而是在运行中动态规划的。一个新的计算任务只有当它提出的要求能够被满足时才会被系统接受并处理，调度算法将决定何时会分派该任务。

（4）DBE（Dynamic Best Effort）类

在DBE（Dynamic Best Effort）类调度算法中，不需要做任何调度分析，系统竭力去满足所有计算任务所提出的要求，并且会毫不留情地将不可能满足要求的进程丢弃掉，即便这样的进程已经被启动了。这类算法是很多商业化实时操作系统所广泛应用的，比较容易实现，但是有一个缺点，就是对任务的截止时间等参数无法预知，这样就会在一些没法满足条件的任务身上花费不必要的处理器时间。

3.时限调度（Deadline Scheduling）

目前大多数的实时操作系统都有一个相同的设计目标，那就是获得尽可能快的中断处理和任务分派速度。事实上，这对实时操作系统的性能并不见得有益，实时操作系统更关心的是能否在规定的时间内完成处理任务，并且不会受系统负荷变化的干扰。近些年来有一些很好的实时调度算法出现，只是这些算法需要提供关于任务本身的更多的信息，这其中包括以下内容。

● 任务准备运行的时间。

● 任务开始处理的时间上限。

● 任务完成处理的时间上限。

● 任务处理所耗费的时间。

● 资源需求。

● 任务的优先级。

● 一个计算任务最好能够分成两个子任务：一个是迫切需要处理的部分，这部分一般有一个硬性的时限规定；一个是有更多选择余地的部分。

在进行实时调度时，如果考虑各种时间上限的话，就需要认真回答几个问题，例如下一个供调度的任务是谁，选择何种抢占方式？

对于第一个问题的回答，这里给出一个不仅在单处理器系统而且在多处理器系统中都成立的结论，即下一个供调度的任务的时间上限与调度时刻离得越近，最终未能满足时间上限要求的任务所占的比例就越少。

另一个问题是关于抢占方式的选择的。如果强调的是任务开始处理的时间上限，那么一个非抢占式的调度方法就很有效。在这种情况下，获得处理器控制权的任务可以在它处理完自己迫切需要处理掉的部分之后进入阻塞状态，从而使得其他任务得以尽快启动。

4.RMS调度

RMS调度（Rate Monotonic Scheduling）算法前面已经提过，它采用静态调度法赋予各个任务在实时运行时所需要的优先级，各个任务在实际运行时依照这个优先级来实现运行时的调度。优先级的指定是以任务的周期时间为基础的，显而易见，RMS方法是面向周期性处理任务的，图2-8 给出了周期性任务的相关参数。一个周期性任务的任务周期是指这样一个任务相邻两次重复处理的开始时间的间隔，其对应的处理频率（赫兹）则是这个周期的倒数（周期单位取秒），其中处理时间是指周期性任务的实际处理所占用的时间。

在RMS调度算法中，任务的优先级的高低与其任务周期的长短成反比，也就是说，一个任务的任务周期越短，它的优先级就越高。按照优先级的规定，如果有多个任务等待处理，那么总是任务周期最短的那个先开始处理。

一个判别周期性调度算法是否有效的依据就是看是否所有的硬性截止时间要求都被满足了。假设有n个周期性任务，每一个都有一个固定的周期和一个固定的执行时间，则要使这个依据成立的前提就是下面这个不等式必须成立。

其中，Ck是第k个任务的处理时间，Tk是第k个任务的任务周期，k=1，2，…，n。

也就是说如果一个周期性调度算法能够满足所有的硬性截止时间的要求，那么所有任务对处理器的利用率的总和应该不会超过1这个上限，而对于一个具体的算法而言，这个上限会更低一些。比如说，对于RMS，就有下面这个不等式成立。

不等式中的各个变量和下标的意义与上同。