博客

操作系统设计中的核心问题是进程和线程的管理

那么关于进程和线程的管理涉及到的问题就包括：

1. 
   多道程序设计技术
   
   ：管理单处理器系统中的多个进程。
2. 
   多处理器技术
   
   ：管理多处理器系统中的多个进程。
3. 
   分布式处理器技术
   
   ：管理多台分布式计算机系统中多个进程的执行。最近迅猛发展的集群就是这类系统的典型例子。

要处理好上面所说的问题，就不得不提到并发，并发是所有问题的基础，也是操作系统设计的基础。并发包括很多设计问题，其中有进程间通信、资源共享与竞争（如内存、文件、I/O访问）、多个进程活动的同步以及给进程分配处理器时间等。我们将会看到这些问题不仅会出现在多处理器环境和分布式处理器环境中，也会出现在单处理器的多道程序设计系统中。

并发会在以下三种不同的上下文中出现：

1. 
   多应用程序
   
   ：多道程序设计技术允许在多个活动的应用程序间动态共享处理器时间。
2. 
   结构化应用程序
   
   ：作为模块化设计和结构化程序设计的扩展，一些应用程序可被有效地设计成一组并发进程。
3. 
   操作系统结构
   
   ：同样的结构化程序设计优点适用于系统程序，且我们已知操作系统自身常常作为一组进程或线程实现。

在接下来的描述中，你将会看到以下内容：

1. 首先介绍并发的概念和多个并发进程执行的含义。我们发现，支持并发进程的基本需求是加强互斥的能力。也就是说，当一个进程被授予互斥能力时，那么在其活动期间，它具有排斥所有其他进程的能力。
2. 接下来介绍支持互斥的硬件机制。
3. 最后介绍一些不需要忙等待，由操作系统或语言编译器支持的互斥解决方案。这里将讨论三种方法：信号量、管程和消息传递。

同时，本章通过两个经典的并发问题（1. 生产者/消费者问题 2.读者/写者问题）来说明并发的概念，并对本书中使用的解决并发的各种方法进行比较。

在介绍并发之前，我们先来看看关于并发的关键术语。

5.1 并发的原理

在单处理器多道程序设计系统中，进程会被交替地执行，因而表现出一种并发执行的外部特征。即使不能实现真正的并行处理，并且在进程间来回切换也需要一定的开销，交替执行在处理效率和程序结构上还是会带来很多好处。在多处理器系统中，不仅可以交替执行进程，而且可以重叠执行进程。

从表面上看，交替和重叠代表了完全不同的执行模式和不同的问题。实际上，这两种技术都可视为并发处理的一个实例，并且都代表了同样的问题。在单处理器情况下，问题源于多道程序设计系统的一个基本特性：进程的相对执行速度不可预测，它取决于其他进程的活动、操作系统处理中断的方式以及操作系统的调度策略。这就带来了下列困难：

1. 全局资源的共享充满了危险。
2. 操作系统很难对资源进行最优化分配。例如，进程A可能请求使用一个特定的I/O通道，并获得控制权，但它在使用这个通道前已被阻塞，而操作系统仍然锁定这个通道，以防止其他进程使用，这是难以令人满意的。事实上，这种情况有可能导致死锁，详见第6章。
3. 定位程序设计错误非常困难。这是因为结果通常是不确定的和不可再现的。

上述所有困难在多处理器系统中都有具体的表现，因为在这样的系统中进程执行的相对速度也是不可预测的。多处理器系统还必须处理多个进程同时执行所引发的问题，从根本上说，这些问题和单处理器系统中的是相同的，随着讨论的深入，这些问题将逐渐明了。

5.1.1 竞争条件

竞争条件发生在多个进程或线程读写数据时，其最终结果取决于多个进程的指令执行顺序。考虑下面两个简单的例子。

在第一个例子中，假设两个进程P1和P2共享全局变量a。在Pl执行的某一时刻，它将a的值更新为1，在P2执行的某一时刻，它将a的值更新为2。因此，两个任务竞争更新变量a。在本例中，竞争的“失败者”（即最后更新全局变量a的进程）决定了变量a的最终值。

在第二个例子中，考虑两个进程P3和P4共享全局变量b和c，且初始值为b=1，c=2。在某一执行时刻，P3执行赋值语句b=b+c，在另一执行时刻，P4执行赋值语句c=b+c。两个进程更新不同的变量，但两个变量的最终值取决于两个进程执行赋值语句的顺序。若P3首先执行赋值语句，则最终值为b=3，c=5；若P4首先执行赋值语句，则最终值为b=4，c=3。

总结为一句话的话，就是上面关于并发的关键术语中所说的：多个线程或进程在读写一个共享数据时，结果依赖于它们执行的相对时间的情形

操作系统必须保证一个进程的功能和输出结果必须与执行速度无关（相对于其他并发进程的执行速度）。这是本章的主题。为理解如何解决与执行速度无关的问题，我们首先需要考虑进程间的交互方式。

5.1.2 进程的交互

我们可以根据进程相互之间知道对方是否存在的程度，对进程间的交互方式进行分类。下表列出了三种可能的感知程度及每种感知程度的结果。

• 
  进程之间相互不知道对方的存在
  
  ：这是一些独立的进程，它们不会一起工作。关于这种情况的最好例子是多个独立进程的多道程序设计，可以是批处理作业，也可以是交互式会话，或者是两者的混合。尽管这些进程不会一起工作，但操作系统需要知道它们对资源的竞争情况。例如，两个无关的应用程序可能都想访问同一个磁盘、文件或打印机。操作系统必须控制对它们的访问。
• 
  进程间接知道对方的存在
  
  ：这些进程并不需要知道对方的进程ID，但它们共享某些对象，如一个I/0缓冲区。这类进程在共享同一个对象时会表现出合作行为（cooperation）。
• 
  进程直接知道对方的存在
  
  ：这些进程可通过进程ID互相通信，以合作完成某些活动。同样，这类进程表现出合作行为。
  
  
  实际条件并不总是像表5.2中给出的那么清晰，例如几个进程可能既表现出竞争，又表现出合作。然而，对操作系统而言，分别检查表中的每一项并确定它们的本质是必要的。接下来，我们将对上面三项关系进行一一的阐述。

进程间的资源竞争：

当并发进程竞争使用同一资源时，它们之间会发生冲突。我们可以把这种情况简单描述如下：两个或更多的进程在它们的执行过程中需要访问一个资源，每个进程并不知道其他进程的存在，且每个进程也不受其他进程的影响。每个进程都不影响它所用资源的状态，这类资源包括IVO设备、存储器、处理器时间和时钟。

竞争进程间没有任何信息交换，但一个进程的执行可能会影响到竞争进程的行为。特别是当两个进程都期望访问同一个资源时，如果操作系统把这个资源分配给一个进程，那么另一个进程就必须等待。因此，被拒绝访问的进程的执行速度就会变慢。一种极端情况是，被阻塞的进程永远不能访问这个资源，因此该进程永远不能成功结束运行。

竞争进程面临三个控制问题。首先需要

互斥（mutual exclusion）

。假设两个或更多的进程需要访问一个不可共享的资源，如打印机。在执行过程中，每个进程都给该IVO设备发命令，接收状态信息，发送数据和接收数据。我们把这类资源称为

临界资源（critical resource）

，使用临界资源的那部分程序称为程序的

临界区（critical section）

。一次只允许有一个程序在临界区中，这一点非常重要。由于不清楚详细要求，我们不能仅仅依靠操作系统来理解和增强这个限制。例如在打印机的例子中，我们希望任何一个进程在打印整个文件时都拥有打印机的控制权，否则在打印结果中就会穿插着来自竞争进程的打印内容。

实施互斥产生了两个额外的控制问题。

1. 死锁（deadlock）。例如，考虑两个进程P1和P2，以及两个资源R1和R2，假设每个进程为执行部分功能都需要访问这两个资源，那么就有可能出现下列情况：操作系统把R1分配给P2，把R2分配给P1，每个进程都在等待另一个资源，且在获得其他资源并完成功能前，谁都不会释放自己已拥有的资源，此时这两个进程就会发生死锁。

2. 饥饿（starvation）。假设有三个进程（P1、P2和P3），每个进程都周期性地访问资源R。考虑这种情况，即P1拥有资源，P2和P3都被延迟，等待这个资源。当P1退出其临界区时，P2和P3都允许访问R，假设操作系统把访问权授予P3，并在P3退出临界区之前P1又要访问该临界区，若在P3结束后操作系统又把访问权授予P1，且接下来把访问权轮流授予P1和P3，那么即使没有死锁，P2也可能被无限地拒绝访问资源。

由于操作系统负责分配资源，竞争的控制不可避免地涉及操作系统。此外，进程自身需要能够以某种方式表达互斥的需求，如在使用前对资源加锁，但任何一种解决方案都涉及操作系统的某些支持，如提供锁机制。

进程间通过共享合作

通过共享进行合作的情况，包括进程间在互相并不确切知道对方的情况下进行交互。例如，多个进程可能访问一个共享变量、共享文件或数据库，进程可能使用并修改共享变量而不涉及其他进程，但却知道其他进程也可能访问同一个数据。因此，这些进程必须合作，以确保它们共享的数据得到正确管理。控制机制必须确保共享数据的完整性。

由于数据保存在资源（设备或存储器）中，因此再次涉及有关互斥、死锁和饥饿等控制问题。唯一的区别是可以按两种不同的模式（读和写）访问数据项，并且只有写操作必须保证互斥。

但是，除这些问题之外还有一个新要求：数据一致性。举个简单的例子，考虑一个关于记账的应用程序，这个程序中可能会更新各个数据项。假设两个数据项a和b保持着相等关系a=b，也就是说，为保持这一关系，任何一个程序如果修改了其中一个变量，也必须修改另一个变量。现在来看下面两个进程：

P1:
	a=a+1;
	b=b+1;
P2:
	b=2*b;
	a=2*a;

如果最初状态是一致的，则单独执行每个进程会使共享数据仍然保持一致状态。现在考虑下面的并发执行，两个进程在每个数据项（a和b）上都考虑到了互斥(也就是修改a或者b变量的时候不会被打断)：

	a=a+1;
	b=2*b;
	b=b+1;
	a=2*a;

按照这一执行顺序，结果不再保持条件a=b。例如，开始时有a=b=1，在这个执行序列结束时有a=4和b=3。为避免这个问题，可以把每个进程中的整个代码序列声明为一个临界区。

因此，在通过共享进行合作的情况下，临界区的概念非常重要。但是，在这种情况下，若使用临界区来保护数据的完整性，则没有确定的资源或变量可作为参数。此时，可以把参数视为一个在并发进程间共享的标识符，用于标识必须互斥的临界区（也就是需要互斥的代码序列）。

作为简单的理解，可以认为进程间的资源竞争是资源互斥，而共享合作则是代码序列互斥。前者自然是操作系统的责任，而后者则需要代码体现希望互斥的诉求，并且操作系统能明白这种诉求。

进程间通过通信合作：

在前面两种情况下，每个进程都有自己独立的环境，不包括其他进程，进程间的交互是间接的，并且都存在共享。在竞争情况下，它们在不知道其他进程存在的情况下共享资源；在第二种情况下，它们共享变量，每个进程并未明确地知道其他进程的存在，它只知道需要维护数据的完整性。当进程通过通信进行合作时，各个进程都与其他进程进行连接。通信提供同步和协调各种活动的方法。

典型情况下，通信可由各种类型的消息组成，发送消息和接收消息的原语由程序设计语言提供，或由操作系统的内核提供。如最linux操作系统中的ctrl+c的停止进程消息。

由于在传递消息的过程中进程间未共享任何对象，因而这类合作不需要互斥，但仍然存在死锁和饥饿问题。例如，有两个进程可能都被阻塞，每个都在等待来自对方的通信，这时发生死锁。作为饥饿的例子，考虑三个进程P1、P2和P3，它们都有如下特性：P1不断地试图与P2或P3通信，P2和P3都试图与P1通信，如果P1和P2不断地交换信息，而P3一直被阻塞，等待与P1通信，由于P1一直是活动的，因此虽不存在死锁，但P3处于饥饿状态。

5.1.3 互斥的要求

要提供对互斥的支持，必须满足以下要求：

1. 必须强制实施互斥：在与相同资源或共享对象的临界区有关的所有进程中，一次只允许一个进程进入临界区。
2. 一个在非临界区停止的进程不能干涉其他进程。
3. 绝不允许出现需要访问临界区的进程被无限延迟的情况，即不会死锁或饥饿。
4. 没有进程在临界区中时，任何需要进入临界区的进程必须能够立即进入。
5. 对相关进程的执行速度和处理器的数量没有任何要求和限制。
6. 一个进程驻留在临界区中的时间必须是有限的。

满足这些互斥条件的方法有多种。

第一种方法是让并发执行的进程承担这一责任

，这类进程（不论是系统程序还是应用程序）需要与另一个进程合作，而不需要程序设计语言或操作系统提供任何支持来实施互斥。我们把这类方法称为软件方法。尽管这种方法已被证明会增加开销并存在缺陷，但通过分析这类方法，可以更好地理解并发处理的复杂性。

第二种方法涉及专用机器指令

，这种方法的优点是可以减少开销，但却很难成为一种通用的解决方案，详见5.2节。

第三种方法是在操作系统或程序设计语言中提供某种级别的支持

，5.3节到5.5节将介绍这类方法中最重要的三种方法。

5.2 互斥：硬件的支持

5.2.1 中断禁用

在单处理器机器中，并发进程不能重叠，只能交替。此外，一个进程在调用一个系统服务或被中断前，将一直运行。因此，为保证互斥，只需保证一个进程不被中断即可，这种能力可通过系统内核为启用和禁用中断定义的原语来提供。进程可通过如下方法实施互斥：

while（true）{
	/*禁用中断*/;
	/*临界区*/;
	/*启用中断*/;
	/*其余部分*/;
}

由于临界区不能被中断，故可以保证互斥。但是，这种方法的代价非常高。由于处理器被限制得只能交替执行程序，因此执行的效率会明显降低。另一个问题是，

这种方法不能用于多处理器体系结构中。

当一个计算机系统包括多个处理器时，通常就可能有一个以上的进程同时执行，在这种情况下，禁用中断并不能保证互斥。

5.2.2 专用机器指令

在多处理器配置中，几个处理器共享对内存的访问。在这种情况下，不存在主/从关系，处理器间的行为是无关的，表现出一种对等关系，处理器之间没有支持互斥的中断机制。

在硬件级别上，对存储单元的访问排斥对相同单元的其他访问。因此，处理器的设计者人员提出了一些机器指令，用于保证两个动作的原子性，如在一个取指周期中对一个存储器单元的读和写或读和测试。在这个指令执行的过程中，任何其他指令访问内存都将被阻止，而且这些动作在一个指令周期中完成。

5.3 信号量

现在讨论提供并发性的操作系统和程序设计语言的机制。表5.3总结了一般常用的并发机制。本节首先讨论信号量，后续两节分别讨论管程和消息传递。表中其他机制这里不做说明。

在解决并发进程问题的过程中，第一个重要的进展是1965年Dijkstra的论文。Dijkstra参与了一个操作系统的设计，这个操作系统设计为一组合作的顺序进程，并为支持合作提供了有效且可靠的机制。只要处理器和操作系统使这些机制可用，它们就可以很容易地被用户进程使用。

基本原理如下：


两个或多个进程可以通过简单的信号进行合作，可以强迫一个进程在某个位置停止，直到它接收到一个特定的信号。任何复杂的合作需求都可通过适当的信号结构得到满足。为了发信号，需要使用一个称为信号量的特殊变量。要通过信号量s传送信号，进程须执行原语semsigna1（s）；要通过信号量s接收信号，进程须执行原语semwait（s）；若相应的信号仍未发送，则阻塞进程，直到发送完为I止。

为达到预期效果，可把信号量视为一个值为整数的变量，整数值上定义了三个操作：

1. 一个信号量可以初始化成非负数。
2. semwait操作使信号量减1。若值变成负数，则阻塞执行semwait的进程，否则进程继续执行。
3. semsigna1操作使信号量加1。若值小于等于零，则被semwait操作阻塞的进程解除阻塞。

除了这三个操作外，没有任何其他方法可以检查或操作信号量。

对这三个操作的解释如下：开始时，信号量的值为零或正数。若值为正数，则它等于发出semwait

操作后可立即继续执行的进程的数量。若值为零（要么由于初始化，要么由于有等于信号量初值的进程已在等待），则发出semwait操作的下一个进程会被阻塞，此时该信号量的值变为负值。之后，每个后续的semwait操作都会使信号量的负值更大。该负值等于正在等待解除阻塞的进程的数量。在信号量为负值的情形下，每个semsigna1操作都会将等待进程中的一个进程解除阻塞。

这里给出信号量定义的三个重要结论：

• 通常，在进程对信号量减1之前，无法提前知道该信号量是否会被阻塞。
• 当进程对一个信号量加1之后，会唤醒另一个进程，两个进程继续并发运行。而在一个单处理器系统中，同样无法知道哪个进程会立即继续运行。
• 向信号量发出信号后，不需要知道是否有另一个进程正在等待，被解除阻塞的进程数要么没有，要么是为1。

图5.3

给出了关于信号量原语更规范的定义。semwait和semsignal原语被

假设是原子操作

。


图5.4

定义了称为二元信号量（binary semaphore）的更严格的形式。

二元信号量的值只能是0或1

，可由下面三个操作定义：






关于二元信号量

1. 二元信号量可以初始化为0或1。
2. semwaitB操作检查信号的值。若值为0，则进程执行semwaitB就会受阻。若值为1，则将值改为0，并继续执行该进程。
3. semsignalB操作检查是否有任何进程在该信号上受阻。若有进程受阻，则通过semwaitB
   
   操作，受阻的进程会被唤醒；若没有进程受阻，则值设置为1。

理论上，二元信号量更易于实现，且可以证明它和普通信号具有同样的表达能力（见习题5.16）。

为了区分这两种信号，非二元信号量也常称为计数信号量（counting semaphore）或一般信号量（general semaphore）。

与二元信号量相关的一个概念是互斥锁（mutex）。互斥是一个编程标志位，用来获取和释放一个对象。当需要的数据不能被分享或处理，进而导致在系统中的其他地方不能同时执行时，互斥被设置为锁定（一般为0），用于阻塞其他程序使用数据。当数据不再需要或程序运行结束时，互斥被设定为非锁定。二元信号量和互斥量的关键区别在于，为互斥量加锁（设定值为0）的进程和为互斥量解锁（设定值为1）的进程必须是同一个进程。相比之下，可能由某个进程对二元信号量进行加锁操作，而由另一个进程为其解锁。

阻塞在信号量上的进程调度问题：

不论是计数信号量还是二元信号量，都需要使用队列来保存于信号量上等待的进程。这就产生了一个问题：进程按照什么顺序从队列中移出？最公平的策略是先进先出（FIFO）：被阻塞时间最久的进程最先从队列释放。采用这一策略定义的信号量称为

强信号量（strong semaphore）

，而没有规定进程从队列中移出顺序的信号量称为

弱信号量（weak semaphore）

。图5.5是一个关于强信号量操作的例子。其中进程A、B和C依赖于进程D的结果，在初始时刻（1），A正在运行，B、C和D就绪，信号量为1，表示D的一个结果可用。当A执行一条semwait指令后，信号量减为0，A能继续执行，随后它加入就绪队列；然后在时刻（2），B正在运行，最终执行一条semwait指令，并被阻塞；在时刻（3），允许D运行；在时刻（4），当D完成一个新结果后，它执行一条semsigna1指令，允许B移到就绪队列中；在时刻（5），D加入就绪队列，C开始运行，当它执行semwait指令时被阻塞。类似地，在时刻（6），A和B运行，且被阻塞在这个信号量上，允许D恢复执行。当D有一个结果后，执行一条semsigna1指令，把C移到就绪队列中，随后的D循环将解除A和B的阻塞状态。

对于下节将要讲述的互斥算法（见图5.6），强信号量保证不会饥饿，而弱信号量则无法保证。

这里将采用强信号量，因为它们更方便，且是操作系统提供的典型信号量形式。

5.3.1 使用信号量进行互斥

图5.6给出了一种使用信号量s解决互斥问题的方法。设有n个进程，用数组P（i）表示，所有进程都需要访问共享资源。每个进程进入临界区前执行semwait（s），若s的值为负，则进程被阻塞；若值为1，则s被减为0，进程立即进入临界区；由于s不再为正，因而其他任何进程都不能进入临界区。

信号量一般初始化为1，这样第一个执行semwait（s）的进程可立即进入临界区，并把s的值置为0。接着任何试图进入临界区的其他进程，都将发现第一个进程忙，因此被阻塞，把s的值置为-1。可以有任意数量的进程试图进入，每个不成功的尝试都会使s的值减1，当最初进入临界区的进程离开时，s增1，一个被阻塞的进程（如果有的话）被移出等待队列，置于就绪态。这样，当操作系统下一次调度时，它就可以进入临界区。如下图所示：



图5.7显示了三个进程使用图5.6所示互斥协议后的一种执行顺序。在该例中，三个进程（A、B、C）访问一个受信号量lock保护的共享资源。进程A执行semwait（1ock）；由于信号量在本次semwait操作时值为1，因而A可以立即进入临界区，并把信号量的值置为0；当A在临界区中时，B和C都执行一个semwait操作并被阻塞；当A退出临界区并执行时，队列中的第一个进程B现在可以进入临界区。

图5.6中的程序也可公平地处理一次允许多个进程进入临界区的需求。这个需求可通过把信号量初始化成某个特定值来实现。因此，在任何时候，s.count的值都可解释如下：

• s.count ≥ 0：s.count 是可执行semwait（s）而不被阻塞的进程数【期间无semsignal（s）
  
  执行】。这种情形允许信号量支持同步与互斥。
• s.count < 0：s.count的大小是阻塞在s.queue队列中的进程数。

5.3.2 生产者/消费者问题

现在分析并发处理中最常见的一类问题：生产者（producer）/消费者（consumer）问题。这个访问通常描述如下：有一个或多个生产者生产某种类型的数据（记录、字符），并放置在缓冲区中；

有一个消费者从缓冲区中取数据，每次取一项；系统保证避免对缓冲区的重复操作，即在任何时候只有一个主体（生产者或消费者）可访问缓冲区。问题是要确保这种情况：当缓存己满时，生产者不会继续向其中添加数据；当缓存为空时，消费者不会从中移走数据。我们将讨论该问题的多种解决方案，以证明信号量的能力和缺陷。

首先假设缓冲区是无限的，且是一个线性的元素数组。用抽象的术语，可以定义如下的生产者和消费者函数：

producer：
while（true）{
	/*生产v*/;
	b[in]=v;
	in++;
}

consumer：
while（true）{
	while（in<=out）
		/*不做任何事*/;
	w=b[out];
	out++;
	/*消费w*/;
}

图5.8显示了缓冲区b的结构。生产者可以按自己的步调产生项目并保存在缓冲区中。每次，缓冲区中的索引（in）增1。消费者以类似的方法继续，但必须确保它不会从一个空缓冲区中读取数据，因此，消费者在开始进行之前应该确保生产者已经生产（即：in>out）。



现在用二元信号量来实现这个系统，图5.9是第一次尝试。这里不处理索引in和out，而用整型变量n

（=in-out）简单地记录缓冲区中数据项的个数。信号量s用于实施互斥，信号量delay用于迫使消费者在缓冲区为空时等待（semwait）。



这种方法看上去很直观。生产者可以在任何时候自由地向缓冲区中增加数据项。它在添加数据前执行semwaitB（s），之后执行 semsignalB（s），以阻止消费者或任何其他生产者在添加操作过程中访问缓冲区。同时，当生产者在临界区中时，将n的值增1。若n=1，则在本次添加之前缓冲区为空，生产者执行semsigna1B（delay）以通知消费者这个事实。消费者最初就使用 semwaitB（delay）等待生产出第一个项目，然后在自己的临界区中取到这一项并将n减1。如果生产者总能保持在消费者之前工作（一种普通情况），即n将总为正，则消费者很少会被阻塞在信号量delay上。因此，生产者和消费者都可以正常运行。

但这个程序仍有缺陷。当消费者消耗尽缓冲区中的数据项时，需重置信号量delay，因此它被迫等待到生产者向缓冲区中放置更多的数据项，这正是语句if(n==0)semwaitB（delay）的目的。考虑表5.4中的情况，在第14行，消费者执行semwaitB操作失败。但是消费者确实用尽了缓冲区并把n置为0（第8行），然而生产者在消费者测试到这一点（第14行）之前将n增1，结果导致semsigna1B

和前面的semwaitB不匹配。第20行的n值为-1，表示消费者已经消费了缓冲区中不存在的一项。仅把消费者临界区中的条件语句移出也不能解决问题，因为这将导致死锁（如在表5.4的第8行后）。

解决这个问题的方法是引入一个辅助变量，我们可以在消费者的临界区中设置这个变量供以后使用，如图5.10所示。仔细跟踪这个逻辑过程，可以确认不会再发生死锁。

使用一般信号量（也称为计数信号量），可得到一种更清晰的解决方法，如图5.11所示。变量n为信号量，其值等于缓冲区中的项数。假设在抄录这个程序时发生了错误，操作semsigna1B（s）和semsigna1B（n）被互换，这就要求生产者在临界区中执行semsigna1B（n）操作时不会被消费者或另一个生产者打断。这会影响程序吗？不会，因为无论何种情况，消费者在继续进行之前必须在两个信号量上等待。



现在假设semwait（n）和semwait（s）操作偶然被颠倒，这时会产生严重甚至致命的错误。如果缓冲区为空（n.count=0）时消费者曾进入过临界区，那么任何一个生产者都不能继续向缓冲区中添加数据项，系统发生死锁。这是一个体现信号量的微妙之处和进行正确设计的困难之处的较好示例。

最后，我们给生产者/消费者问题增加一个新的实际约束，即缓冲区是有限的。缓冲区被视为一个循环存储器，如图5.12所示，指针值必须表达为按缓冲区的大小取模，并总是保持下面的关系：





生产者和消费者函数可表示成如下形式（变量in和out初始化为0，n代表缓冲区的大小）：

producer：
while（true）{
	/*生产v*/
	while（（in+1）%n==out）
		/*不做任何事*/;
	b[in]=v;
	in=（in+1）%n;
}

consumer:
while（true）{
	while（in==out）
		/*不做任何事*/;
	w=b[out];
	out=（out +1）%n;
	/*消费w*/;
}

图5.13给出了使用一般信号量的解决方案，其中增加了信号量e来记录空闲空间的数量。

5.3.3 信号量的实现

如前所述，semwait和semsignal操作必须作为原子原语实现。一种显而易见的方法是用硬件或固件实现。如果没有这些方案，那么还有很多其他方案。问题的本质是互斥：任何时候只有一个进程可用semwait或semsigna1操作控制一个信号量。因此，可以使用任何一种软件方案，如Dekker

算法或Peterson算法，这必然伴随着处理开销。

另一种选择是使用一种硬件支持实现互斥的方案。例如，图5.14（a）显示了使用compare&swap

指令的实现。其中，信号量是图5.3中的结构，但还包括一个新整型分量s.flag。诚然，这涉及某种形式的忙等待，但semsait和semsignal操作都相对较短，因此所涉及的忙等待时间量非常小。对于单处理器系统，在semwait或semsignal操作期间是可以禁用中断的，如图5.14（b）所示。这些操作的执行时间相对很短，因此这种方法是合理的。

5.4 管程

信号量为实施互斥和进程间的合作，提供了一种原始但功能强大且灵活的工具。但是，如图5.9所示，

使用信号量设计一个正确的程序是很困难

的，难点在于semwait和semsignal操作可能分布在整个程序中，而很难看出信号量上的这些操作所产生的整体效果。管程是一种程序设计语言结构，它提供的功能与信号量相同，但更易于控制。管程结构在很多程序设计语言中都得以实现，包括并发 Pascal、Pascal-Plus、Modula-2、Modula-3和Java。它还被作为一个程序库实现。这就允许我们用管程锁定任何对象，对类似于链表之类的对象，可以用一个锁锁住整个链表，也可每个表用一个锁，还可为表中的每个元素用一个锁。

首先介绍Hoare的方案，然后对它进行改进。

5.4.1 使用信号的管程

管程是由一个或多个过程、一个初始化序列和局部数据组成的软件模块，其主要特点如下：

1. 局部数据变量只能被管程的过程访问，任何外部过程都不能访问。
2. 一个进程通过调用管程的一个过程进入管程。
3. 在任何时候，只能有一个进程在管程中执行，调用管程的任何其他进程都被阻塞，以等待管程可用。

前两个特点让人联想到面向对象软件中对象的特点。的确，面向对象操作系统或程序设计语言很容易把管程作为一种具有特殊特征的对象来实现。

通过给进程强加规定，管程可以提供一种互斥机制：管程中的数据变量每次只能被一个进程访问。因此，可以把一个共享数据结构放在管程中，从而对它进行保护。如果管程中的数据代表某些资源，那么管程为访问这些资源提供了互斥机制。

要进行并发处理，管程必须包含同步工具。例如，假设一个进程调用了管程，且当它在管程中时必须被阻塞，直到满足某些条件。这就需要一种机制，使得该进程不仅被阻塞，而且能释放这个管程，以便某些其他的进程可以进入。以后，当条件满足且管程再次可用时，需要恢复该进程并允许它在阻塞点重新进入管程。

管程通过使用**条件变量（condition variable）**来支持同步，这些条件变量包含在管程中，并且只有在管程中才能被访问。有两个函数可以操作条件变量：

• cwait（c）：调用进程的执行在条件c上阻塞，管程现在可被另一个进程使用。
• csignal（c）：恢复执行在cwait之后因某些条件而被阻塞的进程。若有多个这样的进程，选择其中一个；若没有这样的进程，什么也不做。

图5.15给出了一个管程的结构。尽管一个进程可以通过调用管程的任何一个过程进入管程，但我们仍可视管程有一个入口点，保证一次只有一个进程可以进入。其他试图进入管程的进程被阻塞并加入等待管程可用的进程队列中。当一个进程在管程中时，它可能会通过发送cwait（x）把自己暂时阻塞在条件x上，随后它被放入等待条件改变以重新进入管程的进程队列中，在cwait（x）调用的下一条指令开始恢复执行。



若在管程中执行的一个进程发现条件变量x发生了变化，则它发送csignal（x），通知相应的条件队列条件已改变。

5.5 消息传递

进程交互时，必须满足两个基本要求：同步和通信。为实施互斥，进程间需要同步；为实现合作，进程间需要交换信息。提供这些功能的一种方法是消息传递。消息传递还有一个优点，即它可在分布式系统、共享内存的多处理器系统和单处理器系统中实现。

消息传递系统有多种形式(在很多软件编程的书中都会提到的进程间的通信)，本节简述这类系统的典型特征。消息传递的实际功能以一对原语的形式提供：

send(destination,message)
receive(source,message)

这是进程间进行消息传递所需的最小操作集。一个进程以消息（message）的形式给另一个指定的目标（destination）进程发送信息；进程通过执行 receive原语接收信息，receive原语中指明发送消息的源进程（source）和消息（message）。

表5.5中列出了与消息传递系统相关的一些设计问题，本节的其他部分将依次分析这些问题。

5.5.1 同步

两个进程间的消息通信隐含着某种同步的信息：只有当一个进程发送消息后，接收者才能接收消息。

此外，一个进程发出send或receive原语后，我们需要确定会发生什么。

考虑send原语。首先，一个进程执行send原语时有两种可能：要么发送进程被阻塞直到这个消息被目标进程接收到，要么不阻塞。类似地，一个进程发出receive原语后，也有两种可能：

1. 若一个消息在此之前已被发送，则该消息被接收并继续执行。
2. 若没有正等待的消息，则（a）该进程被阻塞直到所等待的消息到达，或（b）该进程继续执行，放弃接收的努力。

因此，发送者和接收者都可阻塞或不阻塞。通常有三种组合，但任何一个特定系统通常只实现一种或两种组合：

• 阻塞send，阻塞receive：发送者和接收者都被阻塞，直到完成信息的投递。这种情况有时也称为会合（rendezvous），它考虑到了进程间的紧密同步。
• 无阻塞send，阻塞receive：尽管发送者可以继续，但接收者会被阻塞直到请求的消息到达。这可能是最有用的一种组合，它允许一个进程给各个目标进程尽快地发送一条或多条消息。在继续工作前必须接收到消息的进程将被阻塞，直到该消息到达。例如，一个服务器进程给其他进程提供服务或资源。
• 无阻塞send，无阻塞 receive：不要求任何一方等待。

对大多数并发程序设计任务来说，无阻塞send是最自然的。例如，无阻塞send用于请求一个输出操作（如打印），它允许请求进程以消息的形式发出请求，然后继续。无阻塞send有一个潜在的危险：错误会导致进程重复产生消息。由于对进程没有阻塞的要求，这些消息可能会消耗系统资源，包括处理器时间和缓冲区空间，进而损害其他进程和操作系统。同时，无阻塞send增加了程序员的负担，由于必须确定消息是否收到，因而进程必须使用应答消息，以证实收到了消息。

对大多数并发程序设计任务来说，阻塞receive原语是最自然的。通常，请求一个消息的进程都需要这个期望的信息才能继续执行下去，但若消息丢失（在分布式系统中很可能发生这种情况），或者一个进程在发送预期的消息之前失败，则接收进程会无限期地阻塞。这个问题可以使用无阻塞receive

来解决。但该方法的危险是，若消息在一个进程已执行与之匹配的receive之后发送，则该消息将被丢失。其他可能的方法是允许一个进程在发出receive之前检测是否有消息正在等待，或允许进程在receive原语中确定多个源进程。若一个进程正在等待从多个源进程发来的消息，且只要有一个消息到达就可以继续下去时，则后一种方法非常有用。

5.5.2 寻址

显然，在send原语中确定哪个进程接收消息很有必要。类似地，大多数实现允许接收进程指明消息的来源。

在send和receive原语中确定目标或源进程的方案分为两类：直接寻址和间接寻址。对于直接寻址（direct addressing），send原语包含目标进程的标识号，而receive原语有两种处理方式。一种是要求进程显式地指定源进程，因此该进程必须事先知道希望得到来自哪个进程的消息，这种方式对于处理并发进程间的合作非常有效。另一种是不可能指定所期望的源进程，例如打印机服务器进程将接受来自各个进程的打印请求，对这类应用使用隐式寻址更为有效。此时，receive原语的source参数保存接收操作执行后的返回值。

另一种常用的方法是

间接寻址（indirect addressing）

。此时，消息不直接从发送者发送到接收者，而是发送到一个共享数据结构，该结构由临时保存消息的队列组成，这些队列通常称为信箱（mailbox）。因此，两个通信进程中，一个进程给合适的信箱发送消息，另一个进程从信箱中获取这些消息。

间接寻址通过解除发送者和接收者之间的耦合关系，可更灵活地使用消息。发送者和接收者之间的关系可以是一对一、多对一、一对多或多对多（见图5.18）。一对一（one-to-one）关系允许在两个进程间建立专用的通信链接，隔离它们间的交互，避免其他进程的错误干扰；多对一（many-to-one）关系对客户服务器间的交互非常有用，一个进程给许多其他进程提供服务，这时信箱常称为一个端口（port）；一对多（one-to-many）关系适用于一个发送者和多个接收者，它对于在一组进程间广播一条消息或某些信息的应用程序非常有用。多对多（many-to-many）关系可让多个服务进程对多个客户进程提供服务。



进程和信箱的关联既可以是静态的，也可以是动态的。端口常常静态地关联到一个特定的进程上，也就是说，端口被永久地创建并指定到该进程。一对一关系就是典型的静态和永久性关系。当有很多发送者时，发送者和信箱间的关联可以是动态的，基于这一目的可使用诸如 connect和disconnect之类的原语。

一个相关的问题是信箱的所有权问题。对于端口来说，信箱的所有都通常是接收进程，并由接收进程创建。因此，撤销一个进程时，其端口也会随之销毁。对于通用的信箱，操作系统可提供一个创建信箱的服务，这样信箱就可视为由创建它的进程所有，这时它们也同该进程一起终止；或视为由操作系统所有，这时销毁信箱需要一个显式命令。

5.5.3 消息格式

消息的格式取决于消息机制的目标，以及该机制是运行在一台计算机上还是运行在分布式系统中。对某些操作系统而言，设计者会优先选用定长的短消息来减小处理和存储的开销。需要传递大量数据时，可将数据放到一个文件中，然后让消息引用该文件。更为灵活的一种方法是使用变长消息。

图5.19给出了操作系统支持的变长消息的典型格式。该消息分为两部分：包含相关信息的消息头和包含实际内容的消息体。消息头包含消息源和目标的标识符、长度域及判定各种消息类型的类型域，还可能含有一些额外的控制信息，例如创建消息链表的指针域、记录源和目标之间所传



递消息的数量、顺序和序号，以及一个优先级域。

5.5.4 排队原则

最简单的排队原则是先进先出，但当某些消息比其他消息更紧急时，仅有这一原则是不够的。

一个替代原则是允许指定消息的优先级，即根据消息的类型来指定或由发送者指定；另一个替代原则是允许接收者检查消息队列并选择下一次接收哪个消息。

5.5.5 使用消息来实现互斥

图5.20给出了用于实施互斥的消息传递方式。假设使用阻塞 receive原语和无阻塞 send原语，且一组并发进程共享一个信箱box，该信箱可供所有进程在发送和接收消息时使用，并初始化为一个无内容的消息。希望进入临界区的进程首先试图接收一条消息，若信箱为空，则阻塞该进程；一旦进程获得消息，它就执行其临界区，然后把该消息放回信箱。因此，消息函数可视为在进程之间传递的一个令牌。



上面的解决方案假设有多个进程并发地执行接收操作，因此

• 若有一条消息，则它仅传递给一个进程，而其他进程被阻塞。
• 若消息队列为空，则所有进程被阻塞；一条消息可用时，仅激活一个阻塞进程活，并得到这条消息。

这些假设实际上对所有消息传递机制都为真。

作为使用消息传递的另一个例子，图5.21给出了解决有界缓冲区生产者/消费者问题的一种方法。

使用消息传递最基本的互斥能力，该问题可通过类似于图5.13的算法结构解决。图5.21利用了消息传递的能力，除了传递信号之外，它还传递数据。它使用了两个信箱。当生产者产生数据后，数据将作为消息发送到信箱mayconsume，只要该信箱中有一条消息，消费者就可开始消费。从此之后mayconsume用做缓冲区，缓冲区中的数据被组织成消息队列，缓冲区的大小由全局变量 capacity确定。信箱mayproduce最初填满空消息，空消息的数量等于信箱的容量，每次生产使得mayproduce中的消息数减少，每次消费使得mayproduce中的消息数增多。

这种方法非常灵活，可以有多个生产者和消费者，只要它们都访问这两个信箱即可。系统甚至可以是分布式系统，所有生产者进程和mayproduce信箱在一个站点上，所有消费者进程和mayconsume信箱在另一个站点上。

5.6 读者/写者问题

在设计同步和并发机制时，若能与一个著名的问题关联，检测该问题的解决方案对原问题是否有效，则这种方法是非常有用的。很多文献中都有一些频繁出现的重要问题，它们不仅是普遍性的设计问题，而且具有教育价值。前面介绍的生产者/消费者问题就是这样一个问题，本节介绍另一个经典问题：读者/写者问题。

读者/写者问题定义如下：存在一个多个进程共享的数据区，该数据区可以是一个文件或一块内存空间，甚至可以是一组寄存器；有些进程（reader）只读取这个数据区中的数据，有些进程（writer）

只往数据区中写数据。此外，还必须满足以下条件：

1. 任意数量的读进程可同时读这个文件。
2. 一次只有一个写进程可以写文件。
3. 若一个写进程正在写文件，则禁止任何读进程读文件。

也就是说，读进程不需要排斥其他读进程，而写进程需要排斥其他所有进程，包括读进程和写进程。

在继续介绍之前，首先让我们区分这个问题和另外两个问题：一般互斥问题和生产者/消费者问题。在读者/写者问题中，读进程不会向数据区中写数据，写进程不会从数据区中读数据。更一般的情况是，允许任何进程读写数据区，此时可以把该进程中访问数据区的部分声明为一个临界区，并强行实施一般互斥问题的解决方法。

之所以关注这种更受限制的情况，是因为对这种情况可以有更有效的解决方案，一般问题的低效方法由于速度过慢而很难被人们接受。

例如，假设共享区是一个图书馆目录，普通用户可通过读目录来查找一本书，一位或多位图书管理员可以修改目录。在一般解决方案中，每次对目录的访问都可视为访问一个临界区，并且用户每次只能读一个目录，这将会带来无法忍受的延迟。同时，避免写进程间互相干扰非常重要，此外还要求在写的过程中禁止读操作，以避免访问到不正确的信息。

生产者/消费者问题是否可视为只有一个写进程（生产者）和一个读进程（消费者）的特殊读者/写者问题呢？答案是不能。生产者不仅仅是一个写进程，它必须读取队列指针，以确定向哪里写下一项，还必须确定缓冲区是否已满。类似地，消费者也不仅仅是一个读进程，它必须调整队列指针以显示它已从缓冲区中移走了一个单元。

现在开始分析读者/写者问题的两种解决方案。

5.6.1 读者优先

图5.22是

使用信号量的一种解决方案

，它给出了一个读进程和一个写进程的实例，该方案无须修改就可用于多个读进程和写进程的情况。写进程非常简单，信号量wsem用于实施互斥，只要一个写进程正在访问共享数据区，其他写进程和读进程就都不能访问它。读进程也使用wsem实施互斥，但为了允许多个读进程，没有读进程正在读时，第一个试图读的读进程需要在wsem上等待。当至少已有一个读进程在读时，随后的读进程无须等待，可以直接进入。全局变量 readcount用于记录读进程的数量，信号量x用于确保 readcount被正确地更新。

5.6.2 写者优先

在前面的解决方案中，读进程具有优先权。一个读进程开始访问数据区时，只要至少有一个读进程正在读，就为读进程保留对这个数据区的控制权，因此写进程有可能处于饥饿状态。

图5.23给出了另一种解决方案，它保证在一个写进程声明想写时，不允许新的读进程访问该数据区。对于写进程，在已有定义的基础上还必须增加下列信号量和变量：

• 信号量rsem：至少有一个写进程准备访问数据区时，用于禁止所有的读进程。
• 变量writecount：控制rsem的设置。
• 信号量y：控制writecount的更新。
  
  
  
  对于读进程，还需要一个额外的信号量。在rsem上不允许建造长队列，否则写进程将无法跳过这个队列，因此只允许一个读进程在rsem上排队，而所有其他读进程在等待rsem前，在信号量z上排队。表5.6概括了这些可能性。
  
  
  
  图5.24给出了另一种解决方案，这种方案赋予写进程优先权，并
  
  通过消息传递来实现
  
  。在这种情况下，有一个访问共享数据区的控制进程，其他要访问这个数据区的进程给控制进程发送请求消息，若请求得到同意，则会收到应答消息“OK”，并通过“finished”消息表示访问完成。控制进程备有三个信箱，每个信箱存放一种它可能接收到的消息。
  
  
  
  要赋予写进程优先权，控制进程就要先服务于写请求消息，后服务于读请求消息。此外，必须实施互斥。要实现互斥，需要使用变量count，它被初始化为一个大于可能的读进程数的最大值。
  
  在该例中，我们取其值为100。控制器的动作可总结如下：
• 若count>0，则无读进程正在等待，可能有也可能没有活动的读进程。要清除活动读进程，首先要服务于所有“finished”消息，然后服务于写请求，再服务于读请求。
• 若count=0，则唯一未解决的请求是写请求。允许该写进程继续执行并等待“finished”消息。
• 若count<0，则一个写进程已发出一条请求，且正在等待消除所有活动的读进程。因此，只有“finished”消息将得到服务。

5.7 小结

现代操作系统的核心是多道程序设计、多处理器和分布式处理器，这些方案和操作系统设计技术的基础都是并发。当多个进程并发执行时，不论是在多处理器系统的情况下，还是在单处理器多道程序系统中，都会出现冲突和合作的问题。

并发进程可按多种方式进行交互。互相之间不知道对方的进程可能需要竞争使用资源，如处理器时间或对I/O设备的访问。进程间由于共享访问一个公共对象，如一块内存空间或一个文件，可能间接知道对方，这类交互中产生的重要问题是互斥和死锁。

互斥指的是，对一组并发进程，一次只有一个进程能够访问给定的资源或执行给定的功能。互斥技术可用于解决诸如资源争用之类的冲突，也可以用于进程间的同步，使得它们能够合作。后一种情况的例子是

生产者/消费者模型

（这里使用了模型这个名词，意义为问题模型，在日后编程的时候，你可能会经常遇到这些类似的问题），在该模型中，一个进程向缓冲区中放数据，另一个或更多的进程从缓冲区中取数据。

支持互斥的第一种方法是使用专用机器指令，这种方法能降低开销，但由于使用了忙等待，效率较低。

支持互斥的另一种方法是在操作系统中提供相应的功能，其中最常见的两种技术是

信号量和消息机制

。信号量用于在进程间发信号，能很容易地实施一个互斥协议。消息对实施互斥很有用，还为进程间的通信提供了一种有效的方法。