：《Operating Systems: Design andImplementation Second Edition操作系统设计与实现 (第二版)安德鲁.坦尼鲍姆（Andrew S. Tanenbaum）阿尔伯特.伍德豪尔（Albert S. Woodhull）》

典型的操作系统由四部分构成：进程管理，I/O设备管理，存储器管理和文件管理。

第二章 进程

操作系统中最核心的概念是进程：一个对正在运行的程序的抽象。操作系统的其他所有内容都围饶着进程。

2.1 进程介绍

当一个用户程序正在运行时，计算机还能够同时读盘，并向屏幕或打印机输出正文。 在一个多道程序系统中，CPU由这道程序向那道程序切换，使每道程序运行几十或几百毫秒。 然而严格地说，在一个瞬间，CPU只能运行一道程序。在1秒钟期间，它可能运行多道程序，这样就给用户一种并行的错觉。有时人们所说的伪并行就是指CPU在多道程序之间快速地切换，以此来区分它与多处理机（两个或更多的CPU共享物理存储器）系统真正的硬件并行。人们很难对多个并行的活动进行跟踪。因此，经过多年的努力，操作系统的设计者发展了一种模型（顺序进程），使得并行更容易处理。

2.1.1 进程模型

在该模型中，计算机上所有可运行的软件，通常包括操作系统，被组织成若干顺序进程，简称进程（processes）。一个进程就是一个正在执行的程序，包括程序计数器、寄存器和变量的当前值。从概念上说，每个进程拥有它自己的虚拟CPU。 当然，实际上真正的CPU在各进程之间来回切换。但为了理解这种系统，考虑在（伪）并行情况下运行的进程集，要比我们试图跟踪CPU如何在程序间来回切换简单得多。这种快速的切换称作多道程序。

图2-1 （a）多道程序中的四道程序。 （b）四个独立、顺序进程的概念模型。 （c）在任意时刻仅有一个程序活跃。

在图2-1（a）中，我们看到在一个多道程序计算机的内存中有四道程序。在图2-1（b）中，我们看到四个进程各自拥有自己的控制流程（即自己的程序计数器），并且每个都独立地运行。在图2-1（C）中，我们看到在观察一段足够长的时间后，所有的进程都有所进展。但在一个给定的瞬间仅有一个进程真正在运行。

由于CPU在各进程之间来回切换，每个进程执行运算的速度是不确定的，而且当同一进程再次运行其运算速度通常也不可再现。所以，进程的编程绝不能对时序作任何固定的假设。例如考虑一个I/O进程用流式磁带机恢复被备份的文件，它执行一个10000次的空循环以等待磁带机达到正常速度，然后发出命令读取第一个记录。如果CPU决定在空循环期间将处理机调度给其他进程，则磁带机进程可能在第一条记录通过磁头之后还未被再次调度。 当一个进程具有此类严格的实时要求时，也就是一些特定事件一定要在所指定的若干毫秒中发生，那么必须采取特殊措施来保证它们一定在这段时间中发生。然而，通常大多数进程并不受CPU多道程序或其他进程相对速度的影响。

进程和程序之间的区别是很微妙的，但却非常重要。一个类比可以使我们更容易理解这一点。想象一位有一手好厨艺的计算机科学家正在为他的女儿烘制生日蛋糕。他有做生日蛋糕的食谱，厨房里有所需的原料：面粉、鸡蛋、糖、香草汁等等。在这个比喻中，做蛋糕的食谱就是程序（即用适当形式描述的算法），计算机科学家就是处理机（CPU），而做蛋糕的各种原料就是输入数据。进程就是厨师阅读食谱、取来各种原料、以及烘制蛋糕的一系列动作的总和。现在假设计算机科学家的儿子哭着跑了进来，说他被一只蜜蜂螫了。计算机科学家就记录下他照着食谱做到哪儿了（保存进程的当前状态），然后拿出一本急救手册，按照其中的指示处理螫伤。这里，我们看到处理机从一个进程（做蛋糕）切换到另一个高优先级的进程（实施医疗救治），每个（进程）拥有各自的程序（食谱和急救书）。当蜜蜂螫伤处理完之后，计算机科学家又回来做蛋糕，从他离开时的那一步继续做下去。

这里的关键思想是：一个进程是某种类型的一个活动，它有程序、输入、输出、及状态。单个处理机被若干进程共享，它使用某种调度算法决定何时停止一个进程的工作，并转而为另一个进程提供服务。

进程的层次结构：支持进程概念的操作系统必须提供某种途径来创建所需要的进程。在一些非常简单的系统，或那种设计为仅有一个应用运行的系统（例如，实时地控制一个设备）中，可能在系统启动时，以后所需要的所有进程都已存在。然而在多数系统中，需要有某种方法以便按需创建或撤销进程。在MINIX系统中，进程通过调用FORK系统调用来创建进程，它将创建一个与调用进程相同的进程。子进程同样也能执行FORK，所以有可能形成一棵完整的进程树。在其他操作系统中，也具有若干系统调用，用来创建一个进程、装入它的内存、并使其开始运行。不管系统调用的具体形式如何，系统都需为进程提供一种方法，使其能够创建其他进程。注意，每个进程只有一个父进程，但可以有O个、1个、2个或更多个子进程。

进程树初始化：在MINIX的引导映像中有一个称为init的特殊进程，当它开始运行时，它读取一个记录了存在多少个终端的文件，然后为每个终端创建一个新的进程，这些进程等待用户进行登录。如果登录成功，登录进程执行一个shell程序来接受命令。这些命令可能启动更多的进程，依次类推。这样，系统中的所有进程都属于一棵进程树，而init进程则是进程树的根（init 和shell的代码未列在本书中，它们可从其他地方取到）。

进程的状态：尽管每个进程是一个独立的实体，有它自己的程序计数器和内部状态，但进程之间经常需要交互作用。一个进程的输出结果可能作为另一个进程的输入。在shell命令 cat chapter1 chapter2 chapter3 | grep tree 中，第一个进程运行cat，将三个文件连接并输出。第二个进程运行grep，它从输入中选择所有包含单词“tree”的那些行。根据这两个进程的相对速度（这取决于这两个程序的相对复杂度和各自所分配到的CPU时间），可能发生“grep”准备就绪可以运行，但输入还没有到这种情况。于是它就必须被阻塞直到输入到来。

当一个进程在逻辑上不能继续运行时，它就阻塞，典型的例子是它在等待可以使用的输入。还可能有这样的情况，一个概念上能够运行的进程被迫停止，其原因是操作系统调度另一个进程占用处理机。这两种条件是完全不同的。第一种情况下，挂起是程序自身所固有的（在用户命令行被键入之前，你无法执行它）；第二种情况则是由系统引起的（没有足够的CPU，所以不能使每个进程都有一台它私用的处理机）。

进程三种状态的转换图：

图2-2 一个进程可处于运行态、阻塞态、就绪态。图中示出各状态之间的转换。

1 运行态（在该时刻实际占用处理机）

2 就绪态（可运行，因为其他进程正在运行而暂时地被挂起）

3 阻塞态（除非某种外部事件发生，否则不能运行）

前两种状态在逻辑上很类似。这两种状态下的进程都希望运行，只是在后者中，暂时没有CPU分配给它。第三种状态与前两种状态不同，该状态的进程不能运行，即使CPU空闲也不行。

这三种状态之间有四种可能的转换关系。转换1在进程发现它不能继续运行下去时发生。在某些系统中，进程需要执行一个系统调用－BLOCK，来进入阻塞状态。在其他系统中，包括MINIX，当一个进程从管道或设备文件（例如终端）读取数据时，如果没有可以使用的输入，则进程自动被阻塞。转换关系2和3是由进程调度程序引起的，它是操作系统的一部分，进程甚至感知不到调度程序的存在。在系统认为运行进程占用处理机的时间已经过长，决定让其他进程占用处理机时，发生转换2。在系统已让其他进程享有了它们应有的CPU时间而重新轮到该进程来占用处理机时，发生转换3。调度程序的主要内容是决定哪个进程应当运行，及它应运行多长时间。这是很重要的一点，我们将在本节的后边对其进行讨论。已经提出许多算法，它们力图从系统作为一个整体的角度平衡需求和效率之间的竞争，并公平地对待各进程。

当一个进程等待的一个外部事件发生时（例如一些输入到达），发生转换4。如果此时没有其他进程运行，则转换3将立即被触发，该进程便开始运行。否则它将处于就绪态等待CPU空闲。

图2-3 按进程组织的操作系统中最低层处理中断和进程调度，其上是一些顺序进程。

图2-3的模型。这里最低层是操作系统的调度程序，在它上面有许多进程。所有关于中断处理、启动和中止进程的具体细节被隐藏在调度程序中。实际上，它是一段非常短小的程序。操作系统的其他部分被简洁地组织成进程形式。图2-3的模型被MINIX使用，但是其中的调度程序应不仅仅被理解为对进程的调度安排，同时也包括中断处理和所有的进程间通信。不过，作为近似描述，它示出了其基本结构。

2.1.2 进程的实现

操作系统维持着一张表格（一个结构数组）即进程表(process table)。 每个进程占用一个进程表项。该表项包含了进程的状态、它的程序计数器、栈指针、内存分配状况、打开文件状态、计费和调度信息，以及其他在进程由运行态转到就绪态时必须保存的信息，只有这样才能使进程随后被再次启动，就象从未被中断过一样。

在MINIX中，进程管理、内存管理和文件管理是由系统中的几个独立模块分别处理的，所以进程表被分为几个部分，各模块维护它们各自所需要的那些域。图2-4示出了一些重要的域。与本章有关的域位于第一列，给出其他两列仅仅是为了建立一点概念，即系统的其他部分需要哪些信息。

进程管理    内存管理    文件管理

图2-4 MINIX进程表的某些域。

对一台有单个CPU、多个I/O设备的计算机如何维持多个顺序进程的假象作更多的解释，从技术上说是对图2-3中MINIX调度程序如何工作的一个描述，但多数现代的操作系统从本质上来说都差不多。

与每类I/O设备（例如软盘、硬盘、定时器、终端）相关的都有一个靠近内存底部的位置，称作中断向量。它包含中断服务程序的入口地址。假设当一个磁盘中断发生时，用户进程3正在运行，则中断硬件将程序计数器、程序状态字、可能还有一个或多个寄存器压入（当前）堆栈，计算机随即跳转到磁盘中断向量所指的地址处。这是硬件做的操作，从这里开始，软件就接管了一切。

中断服务程序的工作从把当前进程全部寄存器值存入进程表项开始。当前进程号及一个指向其表项的指针被保存在全局变量中以便能够快速地找到它们。随后将中断存入的那部分信息从堆栈中删除，并将栈指针指向一个被进程管理者所使用的临时堆栈。一些动作，诸如保存寄存器值和设置栈指针等无法用C语言描述，所以由一个短小的汇编语言例程来完成。当该例程结束后，它调用一个C过程来完成剩下的工作。

MINIX中的进程间通信通过消息完成，所以下一步是构造一条发给磁盘进程的消息，这时磁盘进程正在阻塞并等待该消息。这条消息通知说发生了一条中断，以此将它和那些由用户进程发送的消息加以区分。那些消息发出读磁盘块之类的请求。现在磁盘进程的状态由阻塞转换到就绪，然后，中断服务程序调用调度程序。在MINIX中，不同的进程有不同的优先级，以此向I/O设备服务例程提供比用户进程更好的服务。如果当前磁盘进程是优先级最高的就绪进程，则它将被调度运行。如果被中断进程具有与它相等或更高的优先级， 则它将被再次调度运行，而磁盘进程将只得等待一会儿。

不论哪种情况，被汇编语言中断代码所调用的C过程现在返回，汇编语言代码为新的当前进程装入寄存器值和内存映像并启动它运行。图2-5中总结了中断处理和调度的过程。值得注意的是各系统在细节上略有不同。

图2-5 当一个中断发生后作为操作系统最低层的调度程序的工作步骤。

1、硬件堆栈程序计数器；

2、硬件从中断向量加载新程序计数器；

3、汇编语言程序保存寄存器；

4、汇编语言过程设置新堆栈；

5、C中断服务运行（通常读取和缓冲输入）；

6、调度程序将等待的任务标记为就绪；

7、调度程序决定接下来哪个程序运行；

8、C程序返回汇编代码；

9、汇编语言过程启动新的当前进程。

2.1.3 线程

传统的进程中，每个进程中只存在一条控制线索和一个程序计数器。但在有些现代操作系统中，提供了对单个进程中多条控制线索的支持。这些控制线索通常被称为线程(threads)，有时也称为轻量进程(lightweight processes)。

图2-6（a）三个进程各有一个线程。（b） 一个进程有三个线程。

在图2－6（a）中我们看到三个传统的进程。每个进程有自己的地址空间和单一的控制线索。与此相反，在图2－6（b）中我们看到一个进程有三条控制线索。尽管这两种情况都有三个线程，但在图2-6（a）中各线程在不同的地址空间中操作，而在图2－6（b）中所有三个线程共享同一个地址空间。

作为使用多线程的一个例子，我们考虑一个文件服务器进程。它接收读写文件的请求并将所请求的数据送回或者接收更新了的数据。为了提高性能，服务器在内存中维护一个高速缓存，里边存放最近用过的文件，在需要时从该缓存中读数据或向其中写数据。当一个请求到来时，将它递交给一个线程处理。如果这个线程因等待磁盘传输而中途阻塞，其他线程仍旧可以运行，这样服务器就可以在磁盘I/O进行的同时继续处理新的请求。

当同一地址空间中有多个线程时，图2-4中的几个域就不再针对进程，而是针对线程，于是就需要一张单独的线程表，每个线程占用一项。针对每个线程的信息包括程序计数器、寄存器值及状态。需要程序计数器是因为线程可以象进程一样被挂起和恢复运行。需要寄存器值是因为当线程被挂起时，它的寄存器值必须被保存下来。最后，线程象进程一样，可处于运行，就绪或阻塞态。

两种管理线程的方式：（1）线程完全在用户空间进行管理。操作系统感知不到线程的存在，当一个线程将被阻塞时，它在停止之前选择并启动它的后继线程。（2）操作系统知道每个进程中存在多个线程。当一个线程阻塞时，操作系统会选择下一个运行的线程，它可能来自同一个进程，或者其他进程。为了进行调度，核心必须有一张线程表，其中列出了系统中所有的线程，这与进程表很类似。

在用户空间管理的线程其切换速度比需要核心调用的情况快得多。这一事实有力地支持将线程管理放在用户空间。而另一方面，当线程完全在用户空间管理时，若一个线程阻塞（例如，等待I/O或处理页面故障），则核心将整个进程阻塞，因为它甚至不知道其他线程的存在。这一事实又有力地支持将线程放在核心进行管理。最后的结果是两种系统都被使用，同时还提出了各种混合方案。

一些线程问题：首先来考虑对FORK系统调用的影响。如果父进程有多个线程，那么子进程是否也应该有这些线程？如果不是，那么它可能无法正常工作，因为可能所有的线程都是必不可少的。然而，如果子进程获得了与父进程一样多的线程，那么当一个线程阻塞在一条READ调用时，比如键盘，这时是否两个线程都阻塞在键盘上？当键入一行内容时，是否两个线程都得到一份拷贝？还是只有父进程得到？还是只有子进程得到？对于打开网络连接也存在同样的问题。

另一类问题与多线程共享许多数据结构有关。若一个线程关闭一个文件而另一个线程正在读该文件，将有什么后果？假设一个线程注意到内存不够并开始申请更多的内存，但此时发生线程切换，新运行的线程也注意到这个问题并再次申请内存。那么这里是申请一次呢，还是两次？在几乎所有设计时未考虑线程的系统中，其库例程（例如申请内存的例程）都不可重入，如果前一个调用尚在激活时进行第二次调用，则必然会引起崩溃。

另一个问题就是错误报告。在UIX中，一条系统调用执行完之后，其状态将放在一个全局变量errno。如果一个线程执行系统调用，在它读取errno之前，另一个线程也执行一条系统调用并清除了errno原先的值，则情况会怎样？

信号问题：有些信号在逻辑上是针对线程的，另一些则不是。例如，当一个线程调用ALARM，则将产生的信号传递给执行调用的线程是很合理的。当核心能够感知到线程时，通常它可以保证由正确的线程获得该信号。当核心感知不到线程时，线程软件包必须以某种方式跟踪闹钟信号。对于用户级线程还有另一个麻烦：一个进程（例如在UNIX中）某一时刻只能定一个时间闹钟，而若干线程各自独立地调用ALARM，则将发生混乱。其他信号，例如键盘中断，不是特定于线程的。那么应该由谁来捕捉它们？是一个专门的线程？所有的线程？还是一个新创建的线程？这些方法都存在问题。进一步地，如果一个线程修改了信号处理程序而未通知其他线程，将发生什么情况？

堆栈管理问题：在许多系统中，当堆栈发生溢出时，核心只是自动地提供更多的堆栈空间。当一个进程有多个线程时，它必须也有多个堆栈。如果核心感知不到所有这些堆栈，则发生堆栈故障时它不能自动地将其扩展，实际上，它可能甚至意识不到内存故障与堆栈增长有关。

解决问题的思考：表明仅仅向一个现有系统中引入线程而不进行彻底的重新设计是根本不行的。起码系统调用的语义要重新定义，库例程也要重写。而且所有这些改变必须保持向后兼容，以保证现存的只有一个线程的进程的可用性。

2.2 进程间通信

进程间通信(IPC)：三方面内容，第一方面已经在上面提到过：一个进程如何向另一个进程传送信息。第二方面必须要保证两个或多个进程在涉及临界活动时不会彼此影响（设想两个进程都试图攫取最后100K内存的情况）。第三方面涉及存在依赖关系时进行适当的定序：如果进程A产生数据，进程B打印数据。则B在开始打印之前必须等到A产生了一些数据为止。

2.2.1 竞争条件

协作进程可能共享一些彼此都能够读写的公用存储区。两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序，就称为竞争条件(race conditions)。

2.2.2 临界区

如何避免竞争条件?实际上凡牵涉到共享内存、共享文件、以及共享任何资源的情况都会引发与前边类似的错误。要避免这种错误，关键是要找到某种途径来阻止多于一个的进程同时读写共享的数据。换言之，我们需要的是互斥(mutual exclusion) － 即某种手段以确保当一个进程在使用一个共享变量或文件时，其他进程不能做同样的操作。前述问题的症结就在于，在进程A对共享变量的使用未结束之前进程B就使用它。为实现互斥而选择适当的原语是任何操作系统的主要设计内容之一。

把对共享内存进行访问的程序片段称作临界区(critical region)，或临界段(critical section)。如果我们能够适当地安排使得两个进程不可能同时处于临界区，则就能够避免竞争条件。

尽管这样的要求防止了竞争条件，但它还不能保证使用共享数据的并发进程能够正确和高效地进行操作。对于一个好的解决方案，我们需要以下4个条件：

1 任何两个进程不能同时处于临界区。

2 不应对CPU的速度和数目作任何假设。

3 临界区外的进程不得阻塞其他进程。

4 不得使进程在临界区外无休止地等待。

2.2.3 忙等待的互斥

当一个进程在临界区中更新共享内存时，其他进程将不会进入其临界区。几种互斥方案：

关中断：进程在进入临界区后先关中断，在离开之前再开中断。中断被关掉后，时钟中断也被屏蔽。CPU只有在发生时钟或其他中断时才会进行进程切换，这样关中断之后CPU将不会被切换到其他进程。于是，一旦进程关中断之后，它就可以检查和修改共享内存，而不必担心其他进程的介入。缺点：由用户进程决定中断不合理，关中断对于操作系统本身是一项很有用的技术，但对于用户进程则不是一种合适的通用互斥机制。

锁变量：使用共享（锁）变量之前进行加锁，用完解锁。缺点：假设一个进程读锁变量的值并发现它为0，而恰好在它将其置为1之前，另一个进程被调度运行，将锁变量置为1。当第一个进程再次能运行时，它同样也将锁置为1，则此时同时有两个进程处于临界区中。

严格地轮换法：

图2-8 临界区问题的一种解法。

整型变量turn初值为0，它用于跟踪轮到哪个进程进入临界区来检查或更新共享内存。一开始进程0检查turn，发现它是0，于是进入临界区。 进程1同样也发现它是0，于是执行一个等待循环不停地检测它是否变成了1。 持续地检测一个变量直到它具有某一特定值就称作忙等待(busy waiting)。忙等待是应该避免的，因为它浪费CPU时间。只有在有理由预期等待时间很短时才使用忙等待。

缺点：当进程0离开临界区时，它将turn置为1，以允许进程1进入其临界区。假设进程1很快便离开了临界区，则这时两个进程都处于临界区之外，turn的值被置为0。现在进程0很快便执行完了其整个循环，它再次执行到非临界区的部分，并将turn置为1。此时，进程0结束了其非临界区的操作并回到循环的开始，但很不幸，这时它不能进入临界区，因为turn的值为1，而进程1还在忙于非临界区的操作。这说明，轮流进入临界区在一个进程比另一个慢很多的情况下并不是一个好办法。违反了以上条件3：进程0被一个临界区之外的进程阻塞。

Peterson方案：

图2-9 完成互斥的Peterson方案。

在使用共享变量（即进入其临界区）之前，各进程使用其进程号0或1作为参数来调用enter_region，该调用在需要时将使进程等待，直到能安全地进入。进程在完成对共享变量的操作之后，将调用leave_region，表示操作已完成，若其他进程希望进入临界区，则现在可以进入。

TSL指令：为多处理机设计的计算机，都有一条指令叫做测试并上锁（TSL）。其工作如下所述：它将一个存储器字读到一个寄存器中，然后在该内存地址上存一个非零值。读数和写数操作保证是不可分割的－即该指令结束之前其他处理机均不允许访问该存储器字。执行TSL指令的CPU将锁住内存总线以禁止其他CPU在本指令结束之前访问内存。

为了使用TSL指令，我们要使用一个共享变量lock来协调对共享内存的访问。当lock为0时，任何进程都可以使用TSL指令将其置为1并读写共享内存。当操作结束时，进程用一条普通的MOVE指令将lock重新置为0。

这条指令如何被用来防止两个进程同时进入临界区呢？解决方案示于图2-10中。其中示出了使用4条指令的汇编语言例程。第一条指令将lock原来的值拷贝到寄存器中并将lock置为1，随后这个原先的值与0相比较。如果它非零，则说明先前已被上锁，则程序将回到开头并再次测试。经过或长或短的一段时间后它将变成0（当前处于临界区中的进程退出临界区时），于是子例程返回，并上锁。清除这个锁很简单，程序只需将0存入lock即可，不需要特殊的指令。

图2-10 用TSL指令上锁和清除锁。

进程在进入临界区之前先调用enter_region。这将导致忙等待，直到锁空闲为止。随后它获得锁变量并返回。在进程从临界区返回时它调用leave_region，这将把lock置为0。与临界区问题的所有解法一样，进程必须在正确的时间调用enter_region和leave_region，解法才能奏效。如果一个进程有欺诈行为，则互斥将会失败。

2.2.4 睡眠和唤醒

Peterson解法和TSL解法都是正确的，但它们都有忙等待的缺点。这些解法在本质上是这样的：当一个进程想进入临界区时，先检查是否允许进入，若不允许，则进程将踏步等待，直到许可为止。这种方法不仅浪费CPU时间，还可能引起预料不到的结果。

考虑一台计算机有两个进程，H优先级较高，L优先级较低。调度规则规定只要H处于就绪态它就可以运行。在某一时刻，L处于临界区中，此时H变到就绪态准备运行（例如，一条I/O操作结束）。现在H开始忙等待，但由于当H就绪时L不会被调度，也就无法离开临界区，所以H将永远忙等待下去。这种情况有时被称作优先级翻转问题(priority inversion problem)。

进程间通信原语：它们在无法进入临界区时将阻塞，而不是忙等待。最简单的是睡眠（SLEEP）和唤醒（WAKEUP）。SLEEP系统调用将引起调用进程阻塞，即被挂起，直到另一进程将其唤醒。WAKEUP调用有一个参数，即要被唤醒的进程。另一种方法是SLEEP与WAKEUP各有一个参数，即一个用于匹配SLEEP和WAKEUP的内存地址。

生产者 － 消费者问题

作为如何使用这些原语的一个例子，我们考虑生产者－消费者问题（也称作有界缓冲区问题）。两个进程共享一个公共的固定大小的缓冲区。其中的一个，生产者，将信息放入缓冲区；另一个，消费者，从缓冲区中取出信息（该问题也可被推广到m个生产者，n个消费者的情况，但出于简单起见，我们只考虑一个生产者，一个消费者的情况）。麻烦之处在于当缓冲区已满，而此时生产者还想向其中放入一个新的数据项的情况。解决办法是让生产者睡眠，待消费者从缓冲区中取走一个或多个数据项时再唤醒它。同样地，当消费者试图从缓冲区中取数据而发现缓冲区为空时，它就睡眠，直到生产者向其中放入一些数据时再将其唤醒。这种方法听起来很简单，但它包含与前边Spooler目录问题一样的竞争条件。为了跟踪缓冲区中的数据项数，我们需要一个变量count。如果缓冲区最多存放N个数据项，则生产者代码将首先检查count是否达到N，若是，则生产者睡眠；否则生产者向缓冲区中放入一个数据项并递增count的值。消费者的代码与此类似：首先看count是否为0，若是则睡眠；否则从中取走一个数据项并递减count的值。每个进程同时也检测另一个是否应睡眠，若不应睡眠则唤醒之。生产者和消费者的代码示于图2-11。

图2-11 含有竞争条件的生产者－消费者问题。

现在回到竞争条件的问题。这里有可能会出现竞争条件，其原因是对count的访问未加限制。有可能出现以下情况：缓冲区为空，消费者刚刚读取count的值发现它为0。此时调度程序决定暂停消费者并启动运行生产者。生产者向缓冲区中加入一个数据项，将count加1。现在count的值变成了1。它推断认为由于count刚才为0，所以消费者此时很可能在睡眠，于是生产者调用wakeup来唤醒消费者。不幸的是，消费者此时在逻辑上并未睡眠，所以唤醒信号丢失。当消费者下次运行时，它将测试先前读到的count值，发现它为0，于是去睡眠。这样生产者迟早会添满整个缓冲区，然后睡眠。这样一来两个进程都将永远睡眠下去。

问题的实质在于发给一个（尚）未睡眠进程的唤醒信号丢失了。如果它没有丢失，则一切都很正常。一种快速的弥补方法是修改规则，加上一个唤醒等待位(wakeup waitingbit)。当向一个清醒的进程发送一个唤醒信号时，将该位置位。随后，当进程要睡眠时，如果唤醒等待位为1，则将该位清除，而进程仍然保持清醒。尽管在本例中唤醒等待位解决了问题，但很容易就可以构造出一些例子，其中有两个或更多的进程，这时一个唤醒等待位就不敷使用。我们可以再打一个补丁，加入第二个唤醒等待位，或者甚至是8个、32个，但原则上讲这并未解决问题。

2.2.5 信号量

信号量是E. W. Dijkstra在1965年提出的一种方法，它使用一个整型变量来累记唤醒次数，以供以后使用。在他的建议中引入一个新的变量类型，称作信号量(semaphore)。一个信号量的值可以为0，表示没有积累下来的唤醒操作；或者为正值，表示有一个或多个被积累下来的唤醒操作。

设两种操作：DOWN和UP（分别为推广后的SLEEP和WAKEUP）。对一信号量执行DOWN操作是检查其值是否大于0。若是则将其值减1（即，用掉一个保存的唤醒信号）并继续。若值为0，则进程将睡眠，而且此时DOWN操作并未结束。检查数值、改变数值、以及可能发生的睡眠操作均作为一个单一的、不可分割的原子操作(atomic action)完成。即保证一旦一个信号量操作开始，则在操作完成或阻塞之前别的进程均不允许访问该信号量。这种原子性对于解决同步问题和避免竞争条件是非常重要的。

图2-12使用信号量的生产者--消费者问题。

该解决方案使用了三个信号量：full用来记录满的缓冲槽数目，empty记录空的缓冲槽总数，mutex用来确保生产者和消费者不会同时访问缓冲区。full的初值为0，empty的初值为缓冲区内槽的数目，mutex初值为1。两个或多个进程使用的初值为1的信号量保证同时只有一个进程可以进入临界区，它被称作二进制信号量(binary semaphore)。如果每个进程在进入临界区前都执行一个DOWN操作，并在退出时执行一个UP操作，则能够实现互斥。

信号量mutex用于互斥。它用于保证任一时刻只有一个进程读写缓冲区和相关的变量。互斥是避免混乱所必需的。信号量的另一种用途是同步(synchronization)。信号量full和empty用来保证一定的事件顺序发生或不发生。在本例中，它们保证当缓冲区满的时候生产者停止运行，以及当缓冲区空的时候消费者停止运行。这种用法与互斥是不同的。

2.2.6 管程

有了信号量之后，进程间通信看来很容易了，对吗？答案是否定的。仔细看图2－12中向缓冲区放入数据项，以及从中删除数据项之前的DOWN操作。假设将生产者代码中的两个DOWN操作交换一下次序，将使得mutex的值在empty之前被减1，而不是在其之后。如果缓冲区完全是满的，生产者将阻塞，mutex值为0。这样一来，当消费者下次试图访问缓冲区时，它将对mutex的执行一个DOWN操作，由于mutex值为0，则它也将阻塞。两个进程都将永远地阻塞下去，无法做如何有效的工作，这种不幸的状况称作死锁(deadlock)。

指出这个问题是为了说明使用信号量时要何等的小心！一处很小的错误将导致很大的麻烦。这就象用汇编语言编程一样，甚至更糟，因为这里出现的错误都是竞争条件、死锁、以及其他不可预测和不可重现的行为。

一个管程是一个由过程、变量及数据结构等组成的一个集合，它们组成一个特殊的模块或软件包。进程可在任何需要的时候调用管程中的过程，但它们不能在管程外的过程中直接访问管程内的数据结构。

用一种想象的类Pascal语言描述的管程。图2-13 一个管程。

管程有一个很重要的特性，使它们能有效地完成互斥：任一时刻管程中只能有一个活跃进程。管程是一种编程语言的构件，所以编译器知道它们很特殊，并可以采用与其他过程调用不同的方法来处理它们。典型的，当一个进程调用管程中的过程时，前几条指令将检查在管程中是否有其他的活跃进程。如果有，调用进程将挂起，直到另一个进程离开管程。如果没有，则调用进程便进入管程。

对进入管程实现互斥由编译器负责，但通常的做法是用一个二进制信号量。因为是由编译器而非程序员来安排互斥，所以出错的可能性要小得多。在任一时刻，写管程的人无需关心编译器是如何实现互斥的。他只需知道将所有的临界区转换成管程中的过程即可，而绝不会有两个进程同时执行临界区中的代码。

尽管如我们上边所看到的，管程提供了一种实现互斥的简便途径，但这还不够。我们还需要一种办法以使得进程在无法继续运行时被阻塞。在生产者－消费者问题中，很容易将针对缓冲区满和缓冲区空的测试放到管程的过程中，但是生产者在发现缓冲区满的时候如何阻塞?

解决方法在于引入条件变量(condition variables)，及相关的两个操作：WAIT和SIGNAL。当一个管程过程发现它无法继续时（例如，生产者发现缓冲区满），它在某些条件变量上执行WAIT，如full。这个动作引起调用进程阻塞。它也允许另一个先前被挡在管程之外的进程现在进入管程。另一个进程，如消费者，可以通过对其伙伴正在其上等待的一个条件变量执行SIGNAL来唤醒正在睡眠的伙伴进程。为避免管程中同时有两个活跃进程，我们需要一条规则来通知在SIGNAL之后该怎么办。Hoare建议让新唤醒的进程运行，而挂起另一个进程。Brinch Hansen则建议要求执行SIGNAL的进程必须立即退出管程。换言之，SIGNAL语句只可能作为一个管程过程的最后一条语句。我们将采纳Brinch Hansen的建议，因为它在概念上更简单，并且更容易实现。如果在一个条件变量上正有若干进程等待，则对该条件变量执行SIGNAL操作，调度程序将在其中选择一个使其恢复运行。条件变量不是计数器，它们并不像信号量那样积累信号供以后使用，所以如果向一个其上没有等待进程的条件变量发送信号，则该信号将丢失。WAIT操作必须在SIGNAL之前。这条规则使得实现简单了许多。实际上这不是一个问题，因为用变量很容易跟踪每个进程的状态。一个原本要执行SIGNAL的进程通过检查这些变量便可以知道该操作是不需要的。图2-14中用类Pascal语言给出了使用管程解决生产者－消费者问题的解法。你可能会觉得WAIT和SIGNAL操作看起来很象前面提到的SLEEP和WAKEUP。它们确实很象，但存在一点很关键的区别：SLEEP和WAKEUP之所以失败是因为当一个进程想睡眠时另一个进程试图去唤醒它。使用管程将不会发生这种情况。对管程过程的互斥保证了这样一点：如果管程中的过程发现缓冲区满，它将能够完成WAIT操作而不用担心调度程序可能会在WAIT完成之前切换到消费者进程。消费者进程甚至在WAIT完成且生产者被标志为不可运行之前根本不允许进入管程。

图2-14 一个使用管程的生产者－消费者问题解法概要。 在一个时刻仅有一个管程过程活跃， 缓冲区有N个槽。

通过临界区互斥的自动化，管程使并行编程比用信号量更容易保证正确性。但它也有缺点。图2-14中之所以使用类Pascal，而不象其他例子那样使用C语言并不是没有原因的。正如我们早先说过的，管程是一个编程语言概念。编译器必须要识别出管程并用某种方式对互斥作出安排。C、Pascal、及多数其他语言都没有管程，所以指望这些编译器来实现互斥规则是不可靠的。实际上，编译器如何知道哪些过程属于管程内部，哪些不属于管程也是一个问题。

2.2.7 消息传递

消息传递：(message passing)这种进程间通信方法使用两条原语SEND和RECEIVE。它们象信号量一样，是系统调用；而不象管程那样是语言构件。因此，它们可以很容易地被加入库例程。例如 

send（destination，&message）;

和 receive（source，&message）；

前一个调用向一个给定的目标发送一条消息，后一个调用从一个给定的源（或者是任意源，如果接收者不介意的话）接收一条消息。如果没有消息可用，则接收者可能阻塞直到一条消息到达。或者它也可以立即返回，并带回一个错误码。

消息传递系统面临许多信号量和管程所未涉及的问题和设计难点：

（1）考虑消息本身被正确地接收，而应答信息丢失的情况。发送者将重发信息， 这样接收者将接收到两次。对于接收者来说，区分新消息和一条重发的老消息是非常重 要的。通常采用在每条原始消息中嵌入一个连续的序号来解决该问题。如果接收者收到一条消息，它具有与前一条消息一样的序号，则它就知道这条消息是重复的，可以忽略。

（2）消息系统还需要解决进程命名的问题，这样才能明确在SEND和RECEIVE调用中所指定的进程。身份认证也是一个问题：客户如何知道它是在与一个真正的文件服务器通信，而不是一个冒充者？

（3）对发送者和接收者在同一台机器上的情况，也存在若干设计问题。其中一点是性能。将消息从一个进程拷贝到另一个进段通常比信号量操作和进入一个管程要慢。为了使消息传递变得高效，已经做了许多工作。例如，Cheriton（1986）建议限制信息的大小，使其能装入机器的寄存器中，然后便可以使用寄存器进行消息传递。

（4）用消息传递解决生产者－消费者问题

图2-15 用N条消息的生产者消费者进程。

如何用消息传递而不是共享内存来解决生产者－消费者问题。图2－15中给出了一种解法。我们假设所有的消息都有同样的大小，并且尚未接收到的消息由操作系统自动进行缓冲。在该图中，共使用N 条信息，这就类似于一块共享内存缓冲区中的N个槽。消费者首先将N条空消息发送给生产者。当生产者向消费者传递一个数据项时，它取走一条空消息并送回一条填充了内容的消息。通过这种方式，系统中总的消息数保持不变，所以消息可以存放在预知数量的内存中。如果生产者的速度比消费者快，则所有的消息最终都将被填满，于是生产者将阻塞以等待消费者取用后返回一条空消息。如果消费者速度快，则正好相反：所有的消息均为空，等待生产者来填充它们，消费者阻塞以等待一条填充过的消息。

对消息编址：一种方法是为每个进程分配一个唯一的地址，按进程为消息指定地址。另一种方法是引入一种新的数据结构，称作信箱(mailbox)。一个信箱就是一个用来对一定数量的消息进行缓冲的地方，典型的情况是消息的数量在信箱创建时确定。当使用信箱时，SEND和RECEIVE调用中的地址参数使用信箱，而不是进程。当一个进程试图向一个满的信箱发消息时，它将被挂起，直至信箱内有消息被取走而为新消息腾出空间。

对于生产者－消费者问题，生产者和消费者均应创建足够容纳N条消息的信箱。生产者向消费者信箱发送包含数据的消息，消费者则向生产者信箱发送空消息。当使用信箱时，缓冲机制是很清楚的：目标信箱容纳那些被发送但尚未被目标进程接收的消息。

使用信箱的另一种极端情况是彻底去掉缓冲。采用这种方法时，如果SEND在RECEIVE之前执行，则发送进程被阻塞，直到RECEIVE发生。执行RECEIVE时消息可以直接从发送者拷贝到接收者，不用任何中间缓冲。类似地，如果RECEIVE先被执行，则接收者阻塞直到SEND发生。这种策略常被称为会合(rendezvous)原则。与带有缓冲的消息方案相比，这种方案实现起来更容易一些，但却降低了灵活性，因为发送者和接收者一定要以步步紧接的方式运行。在MINIX（及UNIX）中用户进程间的通信采用管道，它与信箱在效果上等价。采用信箱的消息系统和管道机制之间的区别实际在于管道没有预先设定消息的边界。换言之，如果一个进程向管道写入10条100字节的消息，而另一个进程从管道中读取1000个字节，则读进程将一次性地获得这所有10条消息。而在一个真正的消息系统中，每个READ操作将只返回一条消息。当然，如果进程能够达成一致：总是从管道中读写固定大小的消息，或者每条消息都以一个特殊字符（如换行符）结束，则不会有任何问题。构成MINIX操作系统的进程之间使用消息大小固定的真正的消息机制进行通信。

2.3 经典IPC 问题

2.3.1 哲学家进餐问题

问题描述：五个哲学家围坐在一张圆桌周围，每个哲学家面前都有一碟通心面，由于面条很滑，所以要两把叉子才能夹住。相邻两个碟子之间有一把叉子，餐桌如图2-16所示。

图2-16 哲学家就餐图。

分析：哲学家的生活包括两种活动：即吃饭和思考（这只是一种抽象，即对本问题而言其他活动都无关紧要）。当一个哲学家觉得饿时，他就试图分两次去取他左边和右边的叉子，每次拿一把，但不分次序。如果成功地获得了两把叉子，他就开始吃饭，吃完以后放下叉子继续思考。这里的问题就是：为每一个哲学家写一段程序来描述其行为，要求不能死锁。（要求拿两把叉子是人为规定的，我们也可以将意大利面条换成中国菜，用米饭代替通心面，用筷子代替叉子。）

解法：过程take_fork将一直等到所指定的叉子可用，然后将其取用。不幸的是，这种解法是错误的。设想所有五位哲学家都同时拿起左面的叉子，则他们都拿不到右面的叉子，于是发生死锁。

图2-17 哲学家进餐问题的一种不正确解法。

对图2－17中的算法可进行下列改进，它既不会发生死锁又不会发生饥饿：使用一个二进制信号量对五个think函数之后的语句进行保护。在哲学家开始拿叉子之前，先对信号量mutex执行DOWN。在放回叉子后，再对mutex执行UP。从理论上讲，这种解法是可行的。但从实际角度来看，这里有性能上的局限：同一时刻只能有一位哲学家进餐。而五把叉子实际上允许两位哲学家同时进餐。

图2-18 一个哲学家就餐问题的解决方案。

图2－18中的解法不仅正确，而且对于任意位哲学家的情况都能获得最大的并行度。其中使用一个数组state来跟踪一个哲学家是在吃饭、思考还是正在试图拿叉子。一个哲学家只有在两个邻居都不在进餐时才允许转移到进餐状态。第i位哲学家的邻居由宏LEFT和RIGHT定义，换言之，若i为2，则LEFT为1，RIGHT为3。该程序使用了一个信号量数组，每个信号量对应一位哲学家，这样在所需的叉子被占用时，想进餐的哲学家可以阻塞。注意每个进程将过程philosopher作为主代码运行，而其他过程take_forks、put_forks和test只是普通的过程，而非单独的进程。

哲学家问题对于多个竞争进程互斥地访问有限资源（如I/O设备）这一类问题的建模十分有用。

2.3.2 读者－写者问题

读者－写者问题，它为数据库访问建立了一个模型。

例如，设想一个飞机定票系统，其中有许多竞争的进程试图读写其中的数据。多个进程同时读是可以接受的，但如果一个进程正在更新数据库，则所有其他进程都不能访问数据库，即使读操作也不行。这里的问题是如何对读者和写者进行编程？图2-19给出了一种解法。

图2-19 一个读者与写者问题的解决方案。

解法中，第一个读者对信号量db执行DOWN。随后的读者只是递增一个计数器rc。当读者离开时，它们递减这个计数器，而最后一个读者则对db执行UP，这样就允许一个阻塞的写者（如果存在的话）可以访问数据库。

问题：这个解法在这里隐含了一条很微妙的规则值得讨论。设想当一个读者在使用数据库时，另一个读者也来访问数据库，由于同时允许多个读者同时进行读操作，所以第二个读者也被允许进入，同理第三个及随后更多的读者都被允许进入。现在假设一个写者到来，由于写操作是排他的，所以它不能访问数据库，而是被挂起。随后其他的读者到来，这样只要有一个读者活跃，随后而来的读者都被允许访问数据库。这样的结果是只要有读者陆续到来，它们一来就被允许进入，而写者将一直被挂起直到没有一个读者为止。假如每2秒钟来一个读者，而其操作时间为5秒钟，则写者将永远不能访问数据库。

改进解法：为了防止这种情况，程序可以略作如下改动：当一个读者到来而正有一个写者在等待，则读者被挂在写者后边，而不是立即进入。这样，写者只需等待它到来时就处于活跃状态的读者结束，而不用等那些在它后边到来的读者。这种解法的缺点是并发性较低，从而性能较差。

2.3.3 理发师睡觉问题

问题描述：理发店里有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子。如果没有顾客，则理发师便在理发椅上睡觉，如图2-20所示。当一个顾客到来时，他必须先叫醒理发师，如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，他们就坐下来等。如果没有空椅子，他就离开。这里的问题是为理发师和顾客各编写一段程序来描述他们的行为，要求不能带有竞争条件。

图2-20 睡觉的理发师。

解法：使用三个信号量：customers，用来记录等候理发的顾客数（不包括正在理发的顾客）；barbers，记录正在等候顾客的理发师数，为0或1；mutex，用于互斥。我们也需要一个变量waiting，它也用于记录等候的顾客数，它实际上是customers的一份拷贝。之所以使用waiting是因为无法读取信号量的当前值。在该解法中，进入理发店的顾客必须先看等候的顾客数，如果少于椅子数，他留下来等，否则他就离开。

图2-21 理发师问题的一种解法.

另一解法：示于图2-21。当理发师早晨开始工作时，他执行过程barber，这将导致他阻塞在信号量customers上，直到有人到来。这时他将去睡觉，如图2-20所示。当一个顾客到来时，他执行过程customer，首先获取信号量mutex以进入临界区。如果不久另一位顾客到来，则他只能等到第一位释放了mutex后才能做别的事。顾客随后检查是否等候的顾客少于椅子数，如果不是，他就释放mutex并离开。如果有一把椅子可坐，则他递增整型变量waiting，随后对信号量customers执行UP，然后唤醒理发师。此时顾客和理发师都处于清醒状态。当顾客释放mutex时，理发师获得mutex，他进行一些准备后开始理发。当理完发后，顾客退出该过程，并离开理发店。与前边的例子不同，这里顾客不执行循环，因为每个顾客只需理一次发。但理发师必须执行循环以服务下一位顾客。如果有顾客，则为顾客理发，否则就去睡觉。这里需要指出的是尽管读者－写者问题和理发师问题都不涉及数据传递，但它们仍属于IPC范围，因为它们涉及多进程间的同步。

2.4 进程调度

当有多个进程就绪时，操作系统必须决定先运行哪一个。操作系统中作出这种决定的部分称作调度程序(scheduler)，它使用的算法称作调度算法(scheduling algorithm)。

一个好的调度算法应当考虑很多方面，其中可能有：

1 公平 - 确保每个进程获得合理的CPU份额。

2 有效 - 使CPU百分之百地忙碌。

3 响应时间 - 使交互用户的响应时间尽可能短。

4 周转时间 - 使批处理用户等待输出的时间尽可能短。

5 吞吐量 - 使每小时处理的作业数最多。

调度程序必须面对的另一个麻烦是每个进程都不一样，而且不可预测。有些进程花费很多时间等待I/O，而另一些进程在允许的条件下将连续使用CPU达几个小时。 当调度程序启动运行某些进程时，它根本不知道进程在阻塞前要运行多久（阻塞可能是因为I/O、信号量、或者其他原因）。为了保证不让进程运行得太久，几乎所有的计算机都内置一个电子定时器或时钟，它将定期地发出中断，通常每秒钟50或60次（亦称作50或60赫兹，简写为Hz）。但在许多计算机上，操作系统能够根据需要将时钟频率设置成任意值。每发生一次时钟中断，操作系统都将运行，并决定当前进程是否应继续运行，还是它已经占用了足够长的CPU时间，应该暂停让其他进程运行。

允许将逻辑上可运行的进程暂时挂起的策略称作可剥夺调度(preemptive scheduling)，这与早期批处理系统使进程运行直到结束的方法正好相反。运行直到结束的调度方式称作非剥夺调度(nonpreemptive scheduling)。正如我们在本章中看到的，进程可在任意时刻被不加警告地挂起，以便让另一个进程运行。这导致了竞争条件以及防止竞争条件的信号量、管程、消息或其他复杂的方法。另一方面，允许一个进程运行它所希望的时间意味着一个计算圆周率小数点后边十亿位的进程将使其他进程永远得不到服务。

所以尽管非剥夺调度算法简单且易于实现，但它通常不适于具有多个竞争用户的通用系统。另一方面，对于专用系统，如一个数据库服务器，主进程在收到请求时启动一个子进程并让其运行直到结束或阻塞则是很合理的。这种系统与通用系统的区别在于数据库系统中的所有进程都处于单个主进程的控制之下，该主进程知道各子进程将做什么，以及将花费的时间。

2.4.1 时间片轮转调度

时间片调度：每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束，则CPU当即进行切换。时间片轮转调度很容易实现。调度程序所要做的就是维护一张就绪进程列表，如图2-22（a）所示，当进程用完它的时间片后，它被移到队列的末尾，如图2-22（b）所示。

图2-22 时间片轮转调度。 a）就绪进程列表。 （b）进程B用完它的时间片后的就绪进程列 表。

时间片轮转调度中唯一有趣的一点是时间片的长度。从一个进程切换到另一个进程是需要一定时间的 - 保存和装入寄存器值及内存映像，更新各种表格和队列等。假如进程切换(process switch) - 有时称为上下文切换(context switch)，需要5毫秒。再假设时间片设为20毫秒。则在做完20毫秒有用的工作之后，CPU将花费5毫秒来进行进程切换。CPU时间的20%被浪费在了管理开销上。为了提高CPU效率，我们可以将时间片设为500毫秒。这时浪费的时间只有1%。但考虑在一个分时系统中，如果有十个交互用户几乎同时按下回车键，将发生什么情况？这时十个进程被挂在就绪队列中，如果CPU空闲，则立即启动第一个进程，第二个进程在大约1/2秒之后启动，依次类推。假设所有其他进程都用足它们的时间片的话，最后一个不幸的进程不得不等待5秒钟才获得运行机会。多数用户无法忍受一条简短命令要5秒钟才能做出响应。同样的问题在一台支持多道程序的个人计算机上也会发生。

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

2.4.2 优先级调度

优先级调度：基本思想很清楚：每个进程被赋予一个优先级，优先级最高的就绪进程被率先运行．即使在只有一个用户的PC机上，也可能有多个重要程度不同的进程。例如，一个在后台收发电子邮件的精灵进程应被赋予一个较低的优先级，而在屏幕上实时地播放电影的进程则应赋予较高的优先级。

为了防止高优先级进程无休止地运行下去，调度程序可能在每个时钟滴答（即每一个时钟中断）降低当前进程的优先级。如果这个动作导致其优先级低于次高优先级，则将进行进程切换。或者给每个进程设定一段它能够连续使用CPU的时间片，一旦这段时间用完，则运行次高优先级的进程。优先级可以为静态或动态。在一台军用计算机上，将军启动的进程优先级为100，上校为90，少校为80，上尉为70，中尉为60，依次类推。或者在一个商业计算中心，高优先级作业每小时费用为100美元，中等优先级每小时75美元，低优先级每小时50美元。UNIX系统中有一条命令nice，它允许用户为了照顾别人而自愿降低其进程的优先级，但从未有人用它。

优先级也可以被系统动态地确定以达到某种目的。例如，有些进程为I/O密集型，其多数时间用来等待I/O结束。当这样的进程需要CPU时，它应被立即分配CPU，以便启动下一个I/O请求，这样就可以在另一个进程计算的同时执行I/O操作。使这类进程长时间等待CPU只会造成它无谓地长时间占用内存。使I/O密集进程获得较好服务的一种简单算法是将其优先级设为1/f，f为该进程上一时间片中计算时间所占的比重。一个在100毫秒中计算只占用2毫秒的进程优先级为50，而计算占用50毫秒的进程优先级则为2。全部时间都在计算的进程则为1。很方便就可以将一组进程按优先级分成若干类。在各类之间采用优先级调度，而各类进程内部采用时间片轮转调度。图2-23显示了一个有4类优先级的系统，调度算法如下：只要存在优先级为第4类的就绪进程，就按照时间片轮转法使其运行一个时间片，此时不理会较低优先级的进程。若第4类进程为空，则运行第3类进程。若第4、第3类均为空，则按时间片法运行第2类进程。如果对优先级不经常进行调整，则低优先级进程很可能会发生饥饿。

图2-23 一个有四类优先级的调度算法。

2.4.3 多重队列

CTSS（Corbato et al., 1962）是最早使用优先级调度的系统之一。但是CTSS存在进程切换速度太慢的问题，其原因是IBM 7094内存中只放得下一个进程，每次切换都需要将当前进程换出到磁盘，并从磁盘上读入一个新进程。CTSS的设计者很快便认识到为CPU密集的进程设置较长的时间片，比频繁地分给它们很短的时间片要高效（减少交换次数）。另一方面，如前所述，给进程长时间片又会影响响应时间。他们的解决办法是设立优先级类。属于最高级类的进程运行一个时间片，属于次高优先级类的进程运行2个时间片，再次一级运行4个时间片，依次类推。当一个进程用完分配的时间片后，它被移到下一类。

例子，有一个进程需要连续计算100个时间片。它最初被分配1个时间片，然后被换出。下次它将获得2个时间片，接下来分别是4、8、16、32和64。当然最后一次它只使用64个时间片中的37个便可以结束工作。该过程需要7次交换（包括最初的装入），而如果采用纯粹的时间片轮转则需要100次交换。而且，随着进程优先级的不断降低，它的运行频度逐渐放慢，从而为短的交互进程让出CPU。

2.4.4 最短作业优先

一种适用于运行时间可以预知的批作业的调度算法。

例如一家保险公司，因为每天都做类似的工作，所以人们可以相当精确地预测一个处理1000起索赔的作业需要多长时间。当输入队列中有若干个同等重要的作业将被启动时，调度程序应使用最短作业优先算法。请看图2-24，这里有4个作业A、B、C、D，运行时间分别为8、4、4、4分钟。若按图中的次序运行，则A的周转时间为8分钟，B为12分钟，C为16分钟，D为20分钟，平均为14分钟。

图2-24 一个最短作业优先调度的例子。

现在考虑使用最短作业优先算法。如图2-24（b）所示。现在周转时间分别为4、8、12和20分钟，平均为11分钟。可以证明最短作业优先是最优的。考虑有4个作业的情况，其运行时间分别为a，b，c，d。 第一个作业在时间a结束，第二个在时间a+b结束，依次类推。平均周转时间为（4a+3b+2c+d）/4，显然a对平均值影响最大，所以它应是最短作业，其次是b，再次是c，最后的d只影响它自己的周转时间。对任意数目作业的情况道理完全一样。

一种办法是根据进程过去的行为进行推测，并执行估计运行时间最短的那个。假设某终端上每条命令的估计运行时间为T0，现在假设测量到其下一次运行时间为T1，我们可以将这两个值的加权和来改进我们的估计时间，即aT0+（1-a）T1。通过选择a的值，我们可以决定是尽快忘掉老的运行时间，还是在一段长时间内还记住它们。当a=1/2时，我们可以得到如下序列：

T0，T0/2+T1/2，T0/4+T1/4+T2/2，T0/8+T1/8+T2/4+T3/2

我们看到，三轮过后，T0在新的估计值中的占的比重下降到1/8。这种通过将当前测量值和先前估计值进行加权平均而得到下一个估计值的技术有时称作老化。它适用于许多预测值必须基于先前值的情况。老化算法在a=1/2时特别容易实现，只需将新值加到当前估计值上然后除以2（即右移一位）。需要指出的是，最短作业优先算法只在所有作业同时可用的情况下才是最优的。作为一个反例，考虑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。

2.4.5 保证调度算法

一种完全不同的调度算法是向用户作出明确的性能保证，然后去实现它。一种很实际并很容易实现的保证是：若你工作时有n个用户登录，则你将获得CPU处理能力的1/n。类似的，在一个有n个进程运行的单用户系统中，若所有的进程都平等，则每个进程将获得1/n的CPU时间。为了实现其所作的保证，系统必须跟踪各进程自创建以来已使用了多少CPU时间。然后它计算各进程应获得的CPU时间，即自从创建以来的时间除以n。由于各进程实际获得的CPU时间已知，所以很容易计算出真正获得的CPU时间和应获得的CPU时间之比。比率为0.5说明一个进程只获得了应得时间的一半，而比率为2.0则说明它获得了应得时间的2倍。于是该算法随后转向比率最低的进程，直到该进程的比率超过次最低进程为止。

2.4.6 彩票调度算法

不过有另一种算法可以给出类似的可预见结果，而且实现起来简单许多，这种算法称为彩票调度法（Waldspurger和Weihl 1994）。其基本思想是为进程发放针对系统各种资源（如CPU时间）的彩票。当调度程序需作出决策时，随机选择一张彩票，持有该彩票的进程将获得系统资源。对于CPU调度，系统可能每秒钟抽50次彩票，每次的中奖者获得20毫秒的运行时间。George Orwell对此解释为：“所有进程都是平等的，而某些进程则需要更多的机会。”更重要的进程被给予更多的额外彩票，以增加其中奖机会。如果共发出100张彩票，而一个进程持有20张，它就有20%的中奖概率，对于长时间运行，它将获得大约20%的CPU时间。彩票算法与优先级调度完全不同，在后者中很难说清楚优先级为40说明了什么，而在前者则很清楚：进程拥有多少彩票份额，它就将获得多少资源。彩票调度法有几点有趣的特性。例如，如果一个新进程创建并得到一些彩票，则在下次抽奖时，它中奖的机会与其持有的彩票数成正比。换言之，彩票调度的反应非常迅速。合作进程如果愿意的话可以交换彩票。例如，一个客户进程向服务器进程发送一条消息并阻塞，它可以把所有的彩票都交给服务器进程，以增加其下一次被运行的机会。当服务器进程结束后，它又将彩票交还给客户进程以使其能够再次运行。实际上，在没有客户时，服务器根本不需要彩票。

彩票调度能用来解决其他算法难以解决的问题。例如，一个视频服务器，其中有若干个进程将视频信息传送给各自的客户，但帧频不同。假设其分别需要为10、20和25帧/秒的速度，则通过为这些进程分别分配10、20和25张彩票，它们将自动地按照正确的比例分配CPU资源。

2.4.7 实时调度

实时系统通常分为硬实时(hard real time)系统和软实时(soft real time)系统。前者意味着存在必须满足的时间限制；后者意味着偶尔超过时间限制是可以容忍的。这两种系统中，实时性的获得是通过将程序分成许多进程，而每个进程的行为都预先可知。这些进程通常生存周期都很短，往往在一秒内便运行结束。当检测到一个外部事件时，调度程序按满足它们最后期限的方式调度这些进程。实时系统要响应的事件进一步分为周期性（每隔一段固定的时间发生）和非周期性（在不可预测的时间发生）。一个系统可能必须响应多个周期的事件流。根据每个事件需要多长的处理时间，系统可能根本来不及处理所有事件。例如，有m个周期性事件，事件I的周期为Pi，其中每个事件需要Ci秒的CPU时间来处理。则只有满足以下条件

时，才可能处理所有的负载。满足该条件的实时系统称作是可调度的(schedulable)。

举例来说，一个软实时系统处理三个事件流，其周期分别为100，200和500毫秒。如果事件处理时间分别为50，30和100毫秒，则这个系统是可调度的，因为0.5+0.15+0.2 < 1。如果加入周期为1秒的第4个事件，则只要其处理时间不超过150毫秒，该系统仍将是可调度的。这个运算的隐含条件是上下文切换的开销很小，可以忽略。

实时调度算法可以是动态或静态。前者在运行时作出调度决定，后者在系统启动之前完成所有的调度决策。我们简要地考虑几种实时调度算法。

经典的算法是发生率单调算法（Liu和Layland，1973）。该算法事先为每个进程分配一个与事件发生频率成正比的优先级。例如，周期为20毫秒的进程优先级为50，而周期为100毫秒的进程为10。运行时，调度程序总是调度优先级最高的就绪进程，必要时将剥夺当前进程。Liu和Layland证明了该算法是最优的。

另一种流行的实时调度算法是最早截止优先算法。当一个事件发生时，对应的进程被加到就绪队列中。该队列按照截止期限排序，对于一个周期性事件，其截止期限即为事件下次发生的时间。该算法首先运行队首进程，即截止时间最近的那个。

第三种算法首先计算各进程的富余时间，称做作裕度(laxity)。如果一个进程需要运行200毫秒，而它必须在250毫秒内完成，则其裕度为50 毫秒，该算法称作最少裕度法，即选择裕度最少的进程。

尽管在理论上通过使用这三种调度算法中的一种可以将一个通用操作系统转变为一个实时系统，但实际上，通用操作系统的上下文切换开销太大，以至于只对那些时间限制较松的应用才能达到其实时性能要求。这就导致多数实时系统使用专用的实时操作系统。这些系统具有一些很重要的特征，典型的包括：规模小、中断时间很短、进程切换很快、中断被屏蔽的时间很短，以及能够管理毫秒或微秒级的多个定时器等。

2.4.8 两级调度法

如果没有足够的内存，则某些就绪进程将全部或部分地被放在磁盘上，这种情况对调度有很大影响，因为从盘上读入一个进程运行比单纯在内存中进行进程切换要慢几个数量级。处理被对换到外存的进程可以使用一种更实际的办法，即使用两级调度。就绪进程的一个子集首先被装入内存，如图2-25（a）所示。调度程序在随后的一段时间里只在这个子集中进行调度。一个高级调度程序周期性地将那些在内存中驻留时间足够长的进程换出，而将那些在磁盘上等候时间过长的进程换入。当这个操作完成后，如图2-25（b）所示，低级调度程序再次在那些驻留在内存中的进程间进行调度。这样，低级调度程序只关心当时在内存中的就绪进程，而高级调度程序则关心将进程在内存和磁盘间来回交换。

图2-25 两级调度程序必须将进程在磁盘和内存间来回移动，并从驻留在内存的进程中进行 选择。 三个不同时刻的情况示于（a）、（b）、（c）。

高级调度程序用于决策的标准包括：

1 进程自上次被换入或换出以来的时间

2 进程最近使用的CPU时间

3 进程的大小（小进程不参与高级调度）

4 进程的优先级

这里我们可以再次用到时间片轮转、优先级调度，或其他各种算法。高级和低级调度程序可以使用相同或不同的算法。

2.4.9 策略与机制

隐含地假设系统中所有进程分属不同的用户，并且相互间竞争CPU。尽管通常是这样，但有时会有这样的情况：一个进程有许多子进程在其控制之下运行。例如，一个数据库管理系统可能有许多子进程，每个子进程可能处理不同的请求，或者每个子进程实现不同的功能（请求的语法分析，访问磁盘等）。主进程完全可能掌握哪个子进程最重要（或最紧迫），哪个最不重要。但不幸的是，以上讨论的调度算法中没有一个从用户进程接受有关的调度决策信息。这就导致调度程序很少能够作出最优的选择。

解决该问题的方法是将调度机制(scheduling mechanism)和调度策略(scheduling policy)分开。亦即将调度算法以某种形式参数化，而参数可以由用户进程来填写。我们再来看数据库的例子。假设核心使用优先级调度算法，但提供一条系统调用，一个进程可以使用它来设置或改变其子进程的优先级。这样尽管父进程本身并不进行调度，但它可以控制子进程如何被调度的细节。在这里，机制位于核心，而策略则由用户进程设定。