2.4 进程与中断管理

对每一个现代操作系统而言，其基本任务之一就是进程管理。操作系统需要为进程分配资源，实现进程间共享和交换信息、保护进程资源，以及实现进程间同步，为此，操作系统需要为每一个进程维护一个特定的数据结构用于描述该进程的状态和资源占用情况，从而实现对进程的管理和控制。

在一个单处理器多道程序设计系统中，多个进程是交替执行的，而在一个多处理器系统中，多个进程不仅可以在某个处理器上交替执行，而且还可以在多个处理器上被并行处理。不管是交替方式还是并行处理都会导致进程并发现象，这不仅会给操作系统也会给程序员带来一系列的麻烦。

在现代操作系统中，进程管理因为线程的引入变得更加复杂。在一个多线程系统中，进程成了资源管理器，而线程则成为了程序的基本执行单元。

中断是现代计算机系统普遍采用和支持的技术。中断响应的本质是占用一段处理器时间，这必然与进程有密切的联系，因此本节在介绍进程管理的同时也会对中断与定时管理做相应的阐释。

2.4.1 进程描述与控制

1.进程状态

进程状态的认定直接影响到进程描述与控制的复杂度，而人们对进程状态的认定也是随着对计算机系统本身的认识并结合进程管理与控制的需要来逐渐细化的。进程状态的最简单模型就是二值模型（图2-1），即运行态和非运行态。在这样一个简单模型中，由操作系统决定进程是否处于运行态，而处于非运行态的进程要么是永远退出，要么就是加入到一个先入先出的非运行态进程队列，等候下一次运行。

二值模型虽然简单，但是在现实中却很难应用。比如说在如图2-2所示的进程队列中，有A和B两个进程一前一后被加入到队列中，此时该分派A占用处理器，但是A这个时候正在等待某个I/O操作的完成，这样整个队列将会因此而等待，而事实上，进程B本来可以在这段等待时间里完成所有操作后正常退出的。换言之，二值模型虽然简单，但是却会造成处理器时间的浪费。为弥补这一缺憾，三值模型被提出了，即将原有二值模型中的非运行状态细化为（准备）就绪状态和阻塞状态，分别对应于如图2-2所示的进程B和A所处的状态。显而易见，三值模型是二值模型的进一步细化。另外，再加上两个实践证明有效的状态，即创建和退出，从而得到了普遍应用的进程状态描述的五值模型（图2-3）。

首先来看这个五值模型的各个状态转移情况。

（1）无→创建

一个新的进程被创建用于执行一个程序。

（2）创建→就绪

当操作系统可以执行其他进程时，它会首先将以前创建的进程转为就绪（准备）状态。大多数操作系统都会对存在的进程数或者给它们分配的虚拟内存空间的大小有某些限制，以确保系统性能不至于降低。

（3）就绪→运行

当轮到某个处于就绪（准备）状态的进程运行时，操作系统会将其状态转换为运行状态。究竟哪个进程被选择运行，需要依据一定的控制算法，后面将会提到。

（4）运行→退出

当某个进程已经完成自身的任务或者因为某种原因终止时，操作系统会将其状态从运行状态转换为退出状态。

（5）运行→就绪

事实上在现代操作系统中，尤其是在单处理器系统中，系统并非是一直在执行某个进程，而是往往分配给每个进程一个处理器时间片，在这个时间片里，进程完全占有处理器。这样，在大多数情况下，一个处于运行状态的进程往往是因为操作系统分配给自己的时间片已经耗尽，需要从运行状态退出，一般的处理方法是按照超时处理将其状态转换为就绪（准备）状态。

（6）运行→阻塞

当一个正在运行中的进程需要某个事件发生后才能继续运行时，操作系统会将其状态从运行状态转换为阻塞状态，这样操作系统就可以运行其他进程了。

（7）阻塞→就绪

当某个处于阻塞状态的进程被告知它所等待的事件已经发生之后，其状态就会被操作系统从阻塞状态转换为就绪（准备）状态，以便其下次继续运行。另外需要说明的是，还存在两种形式的状态转换，一个是从就绪（准备）状态到退出状态的转换，另一个是从阻塞状态到退出状态的转换。当父进程退出时，它所创建的子进程也会跟着退出，这时就可能出现这两种情况。

图2-4给出了进程状态描述的五值模型的两种队列图，图2-4（a）所示的是只有一种事件等待的情况，而图2-4（b）所示的则是多事件等待的情况。

2.进程描述

操作系统为了管理和控制进程，就必须知道进程的位置和进程属性，后者包括进程的标识、状态信息和控制信息。

（1）进程位置

谈到进程的位置就必须了解进程的物理形式。一说到某个进程我们就自然而然地将它和一段程序，以及和这段程序相关的数据联系了起来；同时，操作系统在执行该进程时需要维持一个或多个堆栈用于跟踪过程调用及过程间参数调用；最后，操作系统为了控制和管理该进程需要维护一系列与该进程相关的信息。操作系统所维护的这些信息通常被称为进程控制块（Process Control Block），与进程相关的程序、数据、堆栈和进程控制块信息被统称为进程映像。

进程映像如何在计算机系统中存储，和操作系统的内存管理机制有关。如前面所提到的，现代操作系统的内存管理基于分段或分页或者两者的综合。一般而言，进程映像总是有一部分驻留在物理内存中，而其他部分则存放在外围设备中。仅就进程的定位而言，操作系统会在物理内存中维护一个主进程表，其中的各个条目包含了一个指向一个进程映像的指针，从而标明了进程位置。

（2）进程标识

在几乎所有的操作系统中，进程标识都是一个唯一的数值型标识。这个标识可以作为在操作系统运行环境中进程的“身份证”。根据它不仅可以找到对应的进程映像，而且它还可以在内存管理、I/O管理和文件系统管理等方面派上用场。另外每个进程内部仍然需要维护一些其他的标识，比如说创建它的父进程的标识、使用它的用户标识等，这些信息都有助于进程的管理和控制。

（3）进程状态信息

进程运行时的寄存器信息构成了进程状态信息。当某个运行中的进程被暂时停止时，相应的进程状态信息也需要作某些必要的处理，以便进程在恢复运行时能够恢复到暂停之前的状态，从而能够继续正常运行。

（4）进程控制信息

进程控制信息也就是前面所提到的进程控制块中所包含的信息，它是操作系统用于控制和协调各个运行进程所需要的额外信息，大体上可以分为6类，如表2-1所示。

3.进程控制

进程控制不仅包括对进程创建过程的控制而且还包括对进程状态切换的控制。另外，出于对操作系统某些关键数据如进程控制模块等的保护，进程的执行模式分为两种，即拥有更高权限的内核执行模式和拥有较低权限的用户执行模式，这样，进程控制就增加了对进程执行模式切换的控制。

进程创建的原因可能是多方面的，例如，有新的批处理任务移交给操作系统完成，有一个新的用户登录系统，需要提供一项新的服务，现有进程派生出来的子进程等。一旦操作系统决定创建一个新进程，它就需要完成一系列操作：赋予新进程一个唯一的标识，给其进程映像分配足够的存储空间，初始化其进程控制块，设置某些外部关系连接，例如，出于调度的需要，该进程需要放入一个就绪（准备）的进程链表中，因此在它被创建时需要反映这些外部关系，另外还有一些额外的数据结构如系统日志等的创建和增加。

进程状态的切换需要操作系统对要切换状态的进程按顺序完成以下动作。

（1）保存处理器上下文，这其中包括它的程序计数器和其他寄存器的内容。

（2）刷新其进程控制块的相关内容，这其中包括进程状态信息，也有其他一些相关信息比如状态切换的原因、日志等。

（3）将该进程的进程控制块转移到相应的新的队列中。

（4）如果有必要，比如，当该进程处于运行状态时，操作系统需要根据某个算法，选择下一个进程来取代该进程。

对于操作系统仅支持内核模式和用户模式的情况，处于内核模式的进程对内存、处理器及其所有指令、寄存器有完全的控制权，而当处于用户模式时赋予这样的权限则可能会因为用户进程的某个可能出现的错误（经常发生）使得系统完全崩溃，事实上也是不必要的。当用户进程需要访问一些敏感资源的时候，可以通过系统调用转入内核模式，获得更高级权限从而完成任务。

4.进程和线程

进程作为现代操作系统的一个重要特征，在提高计算机利用率等方面起了很重要的作用。通常人们认为，进程不仅是操作系统的基本执行单元，而且同时也充当了相应资源的管理角色。

随着线程概念的引入，这两个功能逐渐分离。进程就只是一个单纯的资源管理器，它管理着与进程相关的资源如进程映像、各类访问权限等；线程成为操作系统的基本执行单元，受操作系统的调度和控制。当然，线程也常常被称为轻量级进程，而这个时候的进程也常常被称做任务。

同样，与线程相联系的必然也有相应的描述和控制。线程的状态主要有（准备）就绪、阻塞和运行3种，而对线程可以有4种基本的操作，即线程的派生、挂起、唤醒和结束。线程和进程的一个很大的不同之处是线程的阻塞并不一定会导致它所属的进程的阻塞。从这一点来看，多线程比起多进程来将会有更大的灵活性。

另外需要特别指出的是多线程机制的实现可以分为两大类，一类是用户级线程实现，另一类是内核级线程实现。一个纯用户级线程实现的系统，线程管理完全由应用程序自己完成，内核完全不用管。系统的最小执行单位是进程，而一个纯内核级线程实现的系统，线程管理完全由操作系统内核完成。当然，实际的系统大多会是这两种实现方式的混合。

2.4.2 并发控制：互斥与同步

不管是基于单处理器的多道程序设计、基于多处理器的多处理设计，还是基于多机系统的分布式处理设计，对操作系统而言，最基本的东西就是并发控制（Concurrency Control）。并发控制涉及到一系列问题，例如，进程间通信、资源竞争和共享、进程同步、进程处理器时间分配等。

并发现象会在3种不同的情况下产生，即多道程序同时运行时、应用程序基于多进程或多线程设计时，以及操作系统基于多进程或多线程设计时。

并发控制实现的最基本方法就是进程间互斥，也就是说，当某个进程正在执行某个动作的时候，其他进程应当避免获得同样的权限。互斥的基本实现方法有两类，即软件方法和硬件方法。基本软件实现方法采用的是所谓的“忙碌-等待”（Busy-Waiting）技术，基本硬件方法的指导思想则是通过硬件方法使得进程在执行某个需要互斥的动作的时候不会被中断。另外还有第3 类方法，它们常常为操作系统或程序编译器所采用，即信号量（Semaphore）、管程（Monitor）和消息传递（Message Passing）。

1.并发

先来看一个并发的简单实例，以便对并发控制的必要性有一个初步认识。有一段例程，需要完成这样一个简单任务：首先从输入设备如键盘读入一个字符，然后将该字符存放在一个全局变量中，最后将该全局变量的值在输出设备如屏幕上输出。总共就这么3步。现在任何一个进程如果需要的话，就可以调用这一段例程来接收并显示一个字符。通过简单分析就知道，只有当这3个步骤不间断地完成，才会出现所希望的正确结果，否则就可能出现逻辑上的错误。

从前面的内存管理机制我们知道虚拟内存可以很容易地实现进程间的共享，这种共享不仅包括执行代码也包括各种数据。上面这段例程的存储方法也采用这种方法，即将其存放在一个任何进程都可以访问的固定内存区域内，这样可以节省内存空间。

下面来看在没有并发控制的情况下，单处理器的交替执行模式和多处理器的并行处理模式下的两个进程都来调用这个例程时可能产生的后果。为了简便起见，两个进程分别被称为进程①、进程②。

（1）交替执行模式

考虑这样一种情况，当进程①执行到该例程的步骤二时，这个时候在全局变量中已经有了一个进程①希望输出的字符。此时，该轮到进程②执行该例程，进程①运行中断。同样，当进程②执行到例程的步骤二时，全局变量的内容就被赋予了新值，而这个时候，进程①重获处理器时间，进程②中断。进程①继续执行该例程的步骤三，结果是输出进程②接收的字符，最后，进程①结束。进程②重获处理器时间，执行步骤三，输出它希望输出的字符。显而易见，由于这两个进程交替执行，就导致进程①希望输出的字符被错误地换成进程②要输出的字符，这是不希望看到的。

（2）并行模式

在并行模式下，进程①和进程②同时运行，但是仍然需要调用同一块内存区域的这个例程，修改同一块内存区域的那个全局变量。显然，涉及到对同一个全局变量的访问时必然有先后顺序之分，假定进程①先于进程②去访问该全局变量。和交替执行模式一样，最后的输出结果仍然在进程①这里出错。

从以上的简单实例可以看出，尽管进程的交替执行模式和并行模式有着本质的不同，但是在并发控制方面遇到的问题却是类似的。

上面所提到的例程属于运行过程中不能中断只能连贯执行的程序段，称之为程序的临界区。另外，有些计算机资源，如打印机、部分I/O设备，在接到某个任务的时候，只能在完成该任务之后才能开始下一个任务，这样的计算机资源称之为临界资源。临界资源往往是和某个程序的临界区联系在一起的。例如，打印机属于临界资源，它在接到一个打印任务时，就进入了打印程序代码执行阶段，此时如果被中断的话，最后的打印结果可能是一个任务的输出与另外一个任务的输出交替出现，所以该段程序代码只能连贯执行。

2.并发控制：软件方法

首先应当说明的是软件方法的应用有一个限制，就是它只能在计算机系统共享内存的情况下使用。并且假定在这样的计算机系统中，对同一内存单元同时发出的访问请求只能是顺序进行的。事实上，这个假设是普遍成立的，其基本思想是使用一个或若干个内存单元存放一些标记，用于标志进程是否进入临界区或者是该轮到哪个进程进入临界区，而未进入临界区的进程则根据这些标记来决定自己是否应该进入临界区。例如，当标记表明该轮到自己进入临界区而其他进程没有进入临界区的话，该进程就可以通过进入临界区来完成自己的任务。

下面介绍两种常见的算法。

（1）Dekker算法

Dekker算法用于两个进程的互斥控制。Dekker算法的标记有3个：一个表明该轮到哪个进程进入临界区（用T表示），该标记是二值的，对应着两个进程；另外两个分别表明对应进程是否在临界区（用F表示）。当后两个进程中的一个希望进入临界区的时候，它会首先将自己的F标记设置为真；然后检查另外一个进程的F标记，如果该标记为假，则前一进程可以直接进入临界区。否则，它就会去查T标记，看是否轮到它进入临界区，如果是的话，它就会不断地去查询另外一个进程的标记F，当该标记被刷新为假的时候，该进程就可以进入临界区；等它跳出临界区后的第一件事就是刷新T标记，以便让另外一个进程进入该临界区，如此便完成了它运行时的一个循环。

（2）Peterson算法

Peterson算法比Dekker算法简单，而且其正确性更容易验证。并且，Peterson算法可以很容易地扩展以用于多个进程的互斥控制。先来看两个进程间互斥控制的处理方法。此时，Peterson算法的标记同样也是3个：一个是表明该轮到哪个进程进入临界区（用T表示），该标记是二值的，对应着两个进程；另外两个分别表明对应进程是否在临界区（用F表示）。当后两个进程中的一个希望进入临界区的时候，它会首先将自己的F标记设置为真，然后将T标记设置成轮到另外一个进程进入临界区对应的值，接着该进程就开始不断地检查T标记和与另外一个进程对应的F标记。当这两个标记不能表明该轮到另外一个进程进入临界区，并且这个进程就在临界区时，前一个进程就可以放心大胆地进入临界区了，而当它跳出临界区的第一件事就是将它对应的F标记设置为假，如此便完成它运行时的一个循环。

从上面对Peterson算法的描述可以发现它和Dekker算法的最大区别就在于Dekker算法对某一进程是否该进入临界区，其判断是属于嵌套结构的，这个嵌套结构会随着所判断进程的数量的增多而变得非常复杂，甚至是很难判定其有效性的，而Peterson算法只需要一步判断，对于多进程的互斥控制情况，它可以很方便地进行扩展，而不需要在程序结构上做大的改动，因此可以很方便地扩展到多个进程的互斥控制问题的解决上。

3.并发控制：硬件方法

并发控制的硬件方法有两种，一个是禁止中断法，另外一个是内置特殊机器指令法。禁止中断法的基本要领就是系统通过设置原子指令来保证进程在进入临界区的时间里其执行流程不会被中断。这种方法不是很理想，一是在单处理器的交替执行模式中，将会受到干扰，从而可能造成系统性能下降；二是在多处理器系统中，这种方法会失效。

下面来看内置特殊机器指令法。前面已经提到，在共享内存的情况下，同时访问某个内存地址的动作只能按顺序执行。受这个启发，从互斥控制的角度考虑，计算机硬件设计者就开始在处理器内设置一些在一个指令周期完成的不会被中断的却能按顺序完成若干动作的特殊机器指令以辅助实现互斥控制，这其中包括附加判断的设置指令（Test and Set Instruction）和交换指令（Exchange Instruction）。由于这两个指令在很多常见的指令集中都涉及到，下面给予简单介绍。

（1）附加判断的设置指令（TSI）

该指令的基本要领就是对指令的传入参数进行判断，如果该值是0的话，则将其重置为1，并返回真值，否则不对传入参数进行修改，直接返回假值。在该指令的基础上可以很方便地给出多个进程的互斥控制算法，如下：系统需要维护一个全局变量B，该值初始化为0，当某个进程发现该值为0的时候就可以进入临界区了。

现在，有一个进程希望进入临界区，它就会去不断地使用指令TSI，它的传入参数是全局变量B，当TSI返回值为真的时候，该进程就可以安全地进入临界区了，并且当它跳出临界区后的第一件事就是要将B重置为0，如此便完成它运行时的一个循环。显然，由于TSI指令属于原子操作，不可能同时有数量多于一个的进程获得全局变量B的值为0的情况发生，所以就杜绝了同时有数量多于一个的进程进入临界区的状况，从而保证了互斥。

（2）交换指令（EI）

交换指令是实现一个寄存器和一个内存单元的内容互换的原子操作。下面来看这个指令是如何来实现多个进程互斥的：系统需要维护一个全局变量B，其初始值是0，而每个进程需要维护一个局部变量k。

如果某个进程希望进入临界区，它会首先将自己的局部变量k设置为1，然后和B不断互换各自的值（这个动作使用交换指令EI），直到k为0为止。当k为0的时候该进程跳出前面的这个循环，直接进入临界区，等它跳出临界区之后第一件事就是使用EI指令互换B和k的内容，如此便完成了它运行时的一个循环。

同样，使用EI指令，也不可能同时有数量多于一个的进程获得全局变量B的值为0的情况发生，这样也就杜绝了同时有数量多于一个的进程进入临界区的状况，从而保证了互斥。

综上所述，可以看出，互斥控制的硬件方法有着很多优点：对共享内存的计算机系统都适用；可以方便地实现多个进程的互斥控制；比较简单而且容易判定其有效性；能够支持多个临界区，而每个临界区都有一个与之相对应的标志性变量。当然，它也有一些缺点，比如说，“忙碌-等待”机制的存在，导致了处理器时间的浪费，并且死锁情况可能发生。

4.信号量

互斥控制的信号量方法遵循这样一个基本原理：两个或更多的进程可以通过某些简单的信号来相互协调，这样一个进程就可以被强制在程序的某个特定位置停止执行，直到它接收到某个特定信号为止。为了传递这些信号，需要引入一个被称为信号量（Semaphore）的特殊变量。如果某个进程需要通过信号量传递一个信号，那它只需要执行一个发送信号的原语即可；如果它想要通过信号量来接收一个信号的话，也只需执行一个等待信号的原语就行了；如果对应的信号没有收到的话，该进程就会一直在这个特定位置停留，直到它收到指定信息为止。

设定信号量为s，发送信号的原语是signal（s），等待信号的原语是wait（s），则可以得到这样一个有着一个成员变量和两个成员函数的对象。

● s为整体变量，初始值为非负整数值。

● wait（s）执行s减1操作，如果在进程执行完该原语之后，s为负，则该进程进入阻塞状态。

● signal（s）执行s加1操作。如果在执行完该原语之后，s非正，则一个被wait（s）抛进阻塞状态的进程就可以从阻塞状态转为运行状态，继续执行后续操作了。

需要提醒注意的有两点：一是对信号量而言，只有上面所提到的两种操作，别无其他；二是上面的两个原语属于原子操作，即在运行过程中是不能被中断的。上面所讲的信号量是一个一般化定义，事实上还有一个二值型的信号量，其取值只能是0和1。从理论上讲，二值型信号量和一般化形式的信号量功能相同，并且更容易实现。

对于任何一种形式的信号量，都需要有一个队列容纳用于等待信号量的进程。从理论上来讲，没有限定究竟是哪个进程首先出列，只知道最公平的方式就是遵循先进先出规则，但是，也不能不考虑优先级问题而让某个进程无限期地呆在队列里。

下面来看利用信号量如何实现互斥。系统需要维护一个全局变量，即信号量s，并初始化为1。进程实现互斥的程序流程就是：第一步，执行等待信号的原语wait（s）；第二步，进入临界区，第三步，在跳出临界区之后的第一个操作是执行原语signal（s）。下面对该互斥控制算法的有效性进行分析：如果某个进程需要进入临界区，它会首先执行等待信号的原语wait（s），如前所述，如果此时无进程在临界区中，则在s减1之后，s为0，这个时候进程直接就进入临界区；如果此时已经有进程在临界区了，也就是说，已经有进程执行了原语wait（s），且信号量s为负，那么这个进程就只有进入阻塞进程队列中等待处于临界区内的进程跳出临界区。

当某个进程跳出临界区之后，它的第一件事就是执行原语signal（s），这个时候，如果在阻塞进程队列中有进程的话，系统就会依据一定的选择算法将在阻塞队列中等待的某个进程选中，并将其状态从阻塞状态转为运行状态，这样，该进程就可以进入临界区了。如此便完成了它运行时的一个循环。

从上面的分析不难看出，在临界区中的同一时刻只能有一个进程运行。可见，信号量机制在互斥控制方面是有效的。

5.管程

信号量机制为互斥控制提供了一个比较粗糙但是功能却很强并且很灵活的实现方式。但是，实践证明，采用信号量机制来实现进程间互斥给编程带来了一定困难。对于一个比较复杂的程序，可能有多个临界区，从而就需要有多个信号量来对这些临界区进行控制，这样问题就出来了。虽然对应每个信号量只有两个原语操作，但是多个信号量最终将导致多个操作在程序里面四处散布，这样就很难看出这些操作对它们各自作用的信号量的整体作用效果，从而为程序设计和分析带来一定的难度。

管程机制是专为编程语言设计的一个互斥控制方法，它和信号量机制功能相同，但是却更容易控制。该控制方法已经在很多编程语言中实现了，甚至已经有了它的程序库，可以很方便地将它插入到自己需要有互斥控制的对象或程序中。

管程一般被定义成这样一个软件模块，它拥有自己的内部数据块，一个或多个例程，以及一个初始化程序块。管程的主要特征如下。

● 内部数据块只能由管程所拥有的例程来访问，拒绝外部数据访问。

● 进程要进入管程，必须是通过调用它的例程进入。

● 一次只能有一个进程进入管程，其他发出进入管程请求的进程只能延缓进入，直到管程允许为止。

因为管程一次只能让一个进程进入，所以可以保证进程间互斥。管程的内部数据块在同一时刻只能由一个进程访问，因此，某个共享数据就可以被当做管程的内部数据块得到保护。如果该内部数据块对应的是某个计算机资源，那么管程就可以为进程提供对该资源的互斥访问手段。

在进程执行过程中，会碰见这样一种情况：某个进程进入临界区内的同时因为某个条件没有得到满足而被挂起。在这种情况下，如果简单套用管程的话，就会造成其他希望进入管程的进程因为该进程而毫无意义地等待。为此，需要引入一种机制，使得进入管程的进程不仅可以挂起，而且还可以释放管程以便其他进程能够进入管程。因此，在管程内部增加了一些条件变量。管程的具体实现可以有两种，一种是结合信号量的实现，一种是结合通报和广播（Notify and Broadcast）机制的实现（图2-5）。

由于后一种比前一种有着明显的优势，所以只介绍后一种实现方式。结合通报和广播的管程实现需要定义两个原语。

● 等待原语cwait（c）：某个已经获得管程的进程需要等待条件c满足时调用该原语操作后挂起，并列入与条件c对应的进程队列中，同时释放管程给其他进程。

● 通报原语cnotify（c）：当某个拥有管程的进程调用该原语操作后，对应条件c的进程队列就会被告知条件c已经满足，从而使该进程继续运行。结果，当管程空闲时，该等待进程队列中的某个进程就可以重新获得管程。

下面来看多个进程利用这个管程实现的一般程序流程：如果某个进程想要获取管程，必须在管程入口处排队，根据一定的选择算法（通常是FIFO算法），被选择进入管程。在进入管程之后，如果不需要等待某个继续执行条件，或者要将某个条件满足的消息通报给对应的等待进程队列，该进程可以继续执行相关操作直到释放管程退出。另外，如果进程在拥有管程时需要等待某个条件，这时候，它会调用等待原语后挂起并释放管程给其他进程。当某个等待进程队列被告知其等待的条件已经满足的时候，该进程队列中的某个进程将由挂起状态转为就绪（准备）状态，此时，该进程会不断地检测其等待条件的满足情况，一旦管程被释放之后，它就会重新进入管程继续其操作。如此便完成了它运行时的一个循环。

另外为了防止某些进程可能无限期地等待下去，通报原语可以再增加一个操作：给每个等待进程赋予一个看门狗时间。这样，当该进程得知其等待条件已经满足并且等待时间已经超出这个时间赋值时，它可以直接继续其后续操作。

另外，使用通报原语可以很方便地被另外一个操作即广播原语cbroadcast（c）代替。cbroadcast（c）与cnotify（c）所不同的就是前者会通知与条件c对应的等待进程队列的所有进程该条件已经被满足，这样，该队列中的所有进程都将从挂起状态转为就绪（准备）状态。

6.消息传递

当两个进程需要交互的时候，有两个基本条件需要满足，即同步和通信。进程间需要同步以便实现互斥，并要通过通信来交换信息。有一种方法可以同时满足这两点要求，这就是消息传递机制。消息传递除了在单处理器和多处理器系统中得到了应用之外，还广泛应用于分布式系统中。

消息传递系统有多种形式，在这里对这类系统的典型特征给予阐述。通常，消息传递机制包括两个原语，一个是发送原语，用于向某个指定目标发送特定信息；另外一个是接收原语，用于从某个指定消息源接收某个消息，形式化描述为send（destination，message）、receive（ource，message）。

消息传递机制的实现需要解决一系列问题，其中包括同步、寻址、消息格式及其排队算法，下面给予分别阐述。

（1）同步

一个进程只有当另外一个进程向它发送消息之后才能接收该消息，从而可知两进程交互必然需要某种程度上的同步。通常一个进程发送或接收消息时的状态有两种，即阻塞和非阻塞，因此其发送或接收方式也就有了阻塞方式和非阻塞方式。先来看进程发送消息的情况。在一般情况下，从进程的执行效率的角度来看，希望这样一个发送进程在发送消息的过程中处于非阻塞方式，这样不仅能够使得它在相同的时间里可以发送多条消息，而且能够完成更多其他的工作。但是有一种情况不能忽视，即如果发生某条消息在传送过程中遗失的情况就会导致进程重复发送消息，如此反复对计算机资源的消耗将会很大。另外，由于非阻塞方式下的发送原语无法保证某条消息会被正确接收，因此，程序员必须要考虑消息接收的认定，进程必须要通过接收相应的消息来判断它所发送的消息是否被正确接收。

至于某进程接收信息，在通常情况下，这样一个进程只有在接收到某条信息之后才能继续其后继动作。因为，对于一个接收进程而言，其最理想的工作方式就是阻塞式，即当它需要接收某条信息的时候就进入阻塞状态，等待信息到来。但是这样一种方式依然存在缺点，比如说，在分布式系统中，可能出现的情况就是消息遗失，从而导致该接收进程没有收到它所等待的消息，那样的话接收进程就会无限期地等待下去。这时我们可以考虑采用非阻塞接收方式，或者给出等待时间上限。这样的解决方案虽然解决了进程从阻塞状态恢复的问题，但是依然可能导致消息丢失问题，例如，接收进程执行接收原语操作，然后发送进程执行发送原语操作，就会导致消息丢失。还有一个解决方案就是在接收进程执行接收原语操作之前先测试一下是否有消息已经发出，确定之后再考虑是否执行接收原语操作。

（2）寻址

发送消息需要知道消息的接收方的地址，而接收消息则需要知道消息的提供方的地址，这就涉及到一个消息的寻址问题。消息的寻址方式多种多样，大致可以分为两大类，一类是直接寻址方式，一类是间接寻址方式。

在直接寻址方式中，消息在发送时需要指明接收方的地址，而消息的接收方式可以随意。在间接寻址方式中，消息并不是直接发送给接收方，而是发送到某个共享数据结构如小溪队列中，这里可以暂时存放消息，通常这样的数据结构被称为邮箱，发送进程将信息发给邮箱，而接收进程则从邮箱中取出它所需要的消息。

由于间接寻址方式使得需要交互的进程间的耦合度低，从而为消息传递机制的实现带来了更大的灵活度，因而得到了广泛使用。

（3）消息格式

消息的格式取决于其实现目标和应用环境。在通常情况下，消息长度是固定的，这样可以减少一些不必要的开销，如额外的计算和判断。当然也有消息不等长的情况，这个时候消息格式本身可能就复杂些，例如，需要加入有关自身长度方面的信息等，而且信息的发送方和接收方也需要对此进行额外的判断。

（4）消息排队算法

当有多个消息需要接收时，就涉及到该如何选取下一个要接收的消息的问题，一般可以采用先入先出（FIFO）算法来应付。但是如果某些消息紧急，需要提前被接收该怎么办？这个时候可以考虑赋予每个消息一个合适的优先级，然后，让接收到的消息按照优先级的高低进行排序。另一个可选择的算法就是赋予接收进程查看消息队列的权限，这样它就可以在查看过程中选择它认为最先需要处理的消息了。

（5）互斥

下面来看看如何使用消息传递机制来实现进程间互斥。对于多个需要借用消息传递机制来实现互斥的进程，它们之间的消息传递的寻址方式采用了间接方式并共享同一个邮箱，且该邮箱初始化后仅有一个不含任何内容的消息。

首先我们需要对消息传递机制的两个原语操作做进一步限定：send（destination，message）非阻塞方式，receive（source，message）阻塞方式。

如果邮箱中有一个消息，则它只传递给一个等待进程，其他进程则进入阻塞状态；如果邮箱里没有任何消息，则所有进程都会进入阻塞状态，直到有一个消息，其中某个进程将会被激活并收到这个消息。

下面来看在采用消息传递机制时，某个进程的一般程序流程。

进程从邮箱接收消息，执行接收原语操作。如果邮箱中有一个消息，并且该进程接收到这个消息的话，则进程直接进入临界区继续运行，当它跳出临界区的第一件事就是将它接收到的这个消息再返回邮箱，这个时候就是执行发送原语操作了。如此便完成了它运行时的一个循环。

2.4.3 并发控制：死锁处理

并发控制在有了比较好的互斥算法之后，并不一定能够保证各进程合乎逻辑地正常运行，事实上还存在一个非常让人头疼的问题，这就是死锁问题。死锁问题的简单描述就是若干个进程在争夺系统资源或者进行交互的时候陷入永久性的阻塞状态。此时，计算机只是在做无用功。针对死锁问题，没有一个通用的有效解决方案，只是存在一些比较常用的应对方案，比如，死锁的预防、检测和避免。

1.死锁

死锁现象必然在牵涉到若干个进程请求资源时产生。举个很简单的例子：有两个进程A和B，都需要资源x和y才能正常完成其任务。只就资源而言，A的一般程序流程是获取资源x，获取资源y，释放资源x，释放资源y；B的一般程序流程则是获取资源y，获取资源x，释放资源y，释放资源x。假如两个进程在运行开始时，分别获取了资源x和y，并在各自完成相应操作之后，开始等待另外一个进程释放自己所需要的资源，但是每个进程又只有当获取了对方占用的资源之后才会释放自己占用的资源，这样的话，两个进程就陷入了无休止的阻塞状态，运行陷入停滞，即出现所谓的死锁现象。

考察各种死锁现象不难看出死锁现象发生的4个条件。

● 进程间互斥：每次只能有一个进程使用某个资源。

● 占用并等待：进程已经占用了某个资源并且同时等待其他资源空闲以供占用。

● 非抢占：进程所占用的资源只能由进程自己释放，而不能由外力强迫它释放。

事实上在很多情况下，这3个条件都是我们所希望的。比如说条件一可以保证进程执行结果合乎逻辑，而进程在对其所占用资源进行操作的中途如果被强制释放自己所占用的资源，不仅可能会给系统运行增加不必要的负担，如需要保存和恢复进程所占用资源的内容等，而且在某些情况下会导致进程执行过程中的逻辑混乱。上面3个条件只是死锁现象发生的必要条件，而只有当这第四个条件发生的时候，死锁才真正发生了。

● 循环等待：由于相互需要对方占有的资源，从而形成了一个闭合的等待进程链。

事实上，条件四中描述的情况也正是死锁的一个定义，也是死锁发生的充分条件。正是由于前3个条件的存在，所以当条件四具备时，死锁才会无可避免地发生，这4个条件就构成了死锁发生的充分必要条件。

2.死锁的预防

如果上面所讲到的4个条件无法同时满足，那么死锁现象就不会发生。由于这4个条件的前3个为死锁发生的必要条件，只有第4个为充分条件，因此，预防死锁发生的方法可以有两类，一类是防止死锁的3个必要条件不会同时发生，即所谓的间接预防方法；另外一类是不让条件四发生，即所谓的直接方法。

（1）进程间互斥

一般而言，进程间互斥是进程正常运行所必需的，所以无法废弃。当然，对有些资源的访问，可能在某些情况下可以不需要互斥，例如，多进程对某个文件执行读操作。为了避免死锁的发生，应当在程序设计中尽量少地使用进程间互斥。

（2）占用并等待

对于占用并等待的情况有一个解决方法就是如果某个进程非要一次性占用所有它所需要的资源的话，那就索性让它在那里一直等到所有资源都空闲的时候再发出资源占用申请。这样可以避免该进程陷入死锁，但是事实上，却是很不可取的，因为这样可能会让进程进入漫长的等待中。

当然也还有别的解决方法，如引入多线程机制。像上面所提到的进程A和B竞争资源x和y的情况，可以考虑，A和B都设计成拥有两个线程的进程，各自的两个线程分别用于对两个资源的占用和相应处理。这样，当出现起始时的A、B分别占有x、y时，实际上是各自内部的某个线程在分别占用这两个资源。当这两个线程完成相应操作后，会将处理结果送达进程的某个数据区域，然后死掉，同时也会释放自己所占用的资源。这样，两个进程内部的另外两个线程就可以启动去占有刚刚释放的资源，这就避免了死锁。

（3）非抢占

在实际应用中对正在占用资源的进程实施抢占式的做法是可能的，但不见得可行。由于某个进程在对其所占用的资源进行操作时，如果被要求强制释放资源，那它为了在未来的某个时刻重新占有该资源并正常运行，就必须涉及到与该资源相关信息的保存和恢复。只有当这样的信息能够很容易保存和恢复时，对互斥资源实施抢占式的做法才是可行的。

（4）循环等待

循环等待的一个解决方法就是对进程访问互斥资源的顺序有一个限定。假如将所有可供进程访问的互斥资源按照先后顺序排成一个队列，并且进程已经占用了其中某个资源的话，那当它想申请占有新的资源时，这新的资源只能来自于排在它已经占有资源的后面的那些正在闲置的资源了。

这个解决方法的有效性很容易通过反证法证明。事实上，假如仍然存在循环等待的话，必然存在两个资源，其申请顺序在占有它们的两个进程中是相反的。这是上述解决方案所不允许的，因此在采用该解决方案之后不可能再出现循环等待的情况。

这种方法的不足之处就在于它限定了进程访问互斥资源的顺序，缺乏一定的灵活性。

3.死锁的避免

在上面讨论的死锁的预防方法中，总是对进程本身的实现或者进程对互斥资源的访问有一定限制，这样的做法会削弱计算机系统的并发功能。为此，提出了死锁的避免方法，这种方法可以赋予进程更大的并发性和灵活性。

避免死锁的方法主要有两种，一种是限制进程启动法，即如果在某个进程启动后会导致死锁，那么就不要启动该进程；另一种是限制资源分配法，即如果某个资源在分配给进程后会导致死锁的话，那就不要分配。这两种方法都涉及到了是否导致死锁的判定问题，它们虽然能够在系统运行过程中对死锁进行动态判定，但是都需要对进程的未来资源请求状况有足够的了解。下面对这两种方法分别作一些阐述。

（1）限制进程启动法

假设系统有n个进程和m种不同类型的资源，并有以下向量和矩阵定义。

R=(R1,R2,…Rm)V=(V1,V2,…Vm)

其中，Rj是第j种资源的总量，R称为系统资源向量；

Vj是第j种资源的剩余量，V称为系统剩余资源向量；

Cij是进程i对第j种资源的最大需求量，C称为进程资源最大需求矩阵；

Aij是进程i实际占有的第j种资源的数量，A称为进程实际资源占有矩阵。

i=1，2，…，n；j=1，2，…，m。

显然有以下关系成立。

Ckj≤Rj

Akj≤Ckj

其中，k=1，2，…，n，其余下标定义与上同。

有了以上定义，我们可以如下给出下一个新进程即第（n+1）个进程启动的必要条件。

其中各下标定义与上同。

（2）限制资源分配法

限制资源分配法也被称做银行家算法。为便于阐述这个算法，首先给出两个定义，一个是系统状态，另外一个是系统的安全状态。所谓系统状态是指在某个指定时刻系统的各个进程对互斥资源的占用情况，反过来讲，也就是互斥资源的分配情况。系统的安全状态则是指能够让所有进程都能完成其任务并且不会导致死锁的系统状态。系统的不安全状态则是与其安全状态相对的。

限制资源分配法的基本原则就是确保系统永远处于安全状态。如果某个进程要求分配给它一些资源，那可以假设其申请全部满足，这样可以相应地刷新系统状态，然后检查系统是否仍然处于安全状态。如果是的话，就满足该进程的资源分配申请，否则挂起该进程，直到能够保证安全地分配给它资源为止。

死锁的避免方法比起它的预防方法来讲，有着很多优越性，当然它也存在一些不足之处。

● 需要预先给出每个进程对每种资源的最大需求量。

● 所考虑的进程是相互独立的，也就是说它们执行的先后顺序是不受限制的。

● 可供分配的互斥资源的数目是一定的。

● 当进程占用资源的时候不能退出。

4.死锁的检测

死锁的预防方法过于保守，主要表现在对互斥资源的访问和进程执行的限制上，而死锁的避免方法则走向了另外一个极端：它不存在对互斥资源的访问和进程执行的限制。死锁的检测方法要优于前两种方法，使用这种方法，互斥资源只要空闲就能被分配给需要它的进程，操作系统会周期性地执行某种算法以便能够发现前面所讲过的循环等待的情况。

（1）死锁的检测算法

检测算法执行的周期可快可慢，这要看死锁发生的频率到底如何。下面介绍一种比较常见的检测算法。前面在死锁的避免方法中给出的向量和矩阵R，V，C，A依然有效。另外需要给出一个请求矩阵Q：

其中，Qij代表进程i对第j种资源的需求量。

在该检测方法的进程过程中，不会死锁的进程会被标识。在初始阶段，所有进程都未被标识，算法执行的步骤如下。

（1）标识出矩阵A中的元素全为零的行所对应的进程。

（2）初始化一个临时向量W等于系统剩余资源的向量V。

（3）在Q中找出某一行使其序号i满足条件Qik≤Wk，k=1，2，…，m。如果找不出这么一行，则算法停止执行。

（4）如果找到了这么一行，则标识其对应的进程i并执行赋值操作Wk=Wk+Aik，k=1，2，…，m。当该算法停止执行之后，如果依然还有进程没有被标识，那就说明存在死锁现象。

（2）恢复操作

当检测到死锁现象之后，需要执行某种恢复操作以便让系统继续有效运行。下面是一些可能的操作，按复杂程度排序。

● 放弃所有的死锁进程，这是最常用的方法。

● 将所有进程的状态恢复到过去的某个时刻的状态，然后重新启动所有的进程。

● 一个跟着一个地退出某个死锁中的进程，直到死锁现象消失。

● 对某些资源实行抢占式再分配，直到死锁现象消失。

5.一个综合处理方案

根据前面的阐述，可以看出死锁的处理方法各有自己的优缺点。一个很自然的想法是能否把它们融合起来提出一个综合的死锁处理方案。这是可能的，比如下面的一个方案。

● 将资源分成不同的类。

● 对不同的资源类按先后顺序排成一个线性队列。

● 在每一个资源类内部，采用最适合该类的死锁处理方法。

2.4.4 中断及中断处理

几乎所有的计算机系统都提供了中断机制，以便让系统中的其他模块能够中断正在执行的进程，从而完成一些紧急任务，这就是中断。最常见的中断类型主要有4类，即软件中断、定时中断、I/O中断和硬件故障（表2-2）。

中断主要是用来提高计算机系统的处理效率的，例如，多数外围设备的动作速度和处理器相比要慢很多。在需要打印机打印某个文档时，如果没有中断机制存在的话，进程就会在每次写操作完成之后等待打印机完成相应操作并告知处理器，而后处理器才能继续下一个指令的执行。但是，如果引入中断机制的话，处理器只需要执行一些简单指令，比如初始化打印机，告诉打印机要打印的文档数据在内存中的位置，最后在向打印机发送打印指令之后，就可以转到后继指令的执行了，而这个时候，打印机正在慢吞吞地执行相关的打印任务。当打印机打印完所交给的任务之后，会采用中断方式，告诉处理器其指派的打印任务已经完成，这个时候，处理器会中断当前任务并处理这个中断。显然，在引入中断之后，处理器的利用率提高了，可以在同样的时间里处理更多的指令或任务。

1.中断

从进程角度看，中断可以看成是其正常执行过程的一个小插曲。进程本身无须关心中断如何处理，等中断处理结束之后，进程继续原来正常的执行过程。为引入中断机制，一般的指令周期需要加入中断处理（如图2-6所示）。

在中断处理周期中，处理器会检查是否有中断发生。如果没有中断发生，处理器就继续其正常的指令处理，在进程看来，就是自己没有受丝毫影响地持续运行着；如果有中断发生，处理器就会跳出其正常的指令处理顺序，转为执行与所发生中断对应的一个中断处理例程。通常，中断处理例程是操作系统的一部分，用于判断中断的类型并采取相应的处理措施。

2.中断处理

中断会引发一系列的事件，中断的一般处理流程如下。

（1）某个中断源（如软件、I/O、定时器，甚至是硬件故障）向处理器发出中断信号。

（2）处理器在响应中断之前完成当前指令。

（3）处理器检测是否存在中断，并发给中断源一个确认信号，这个确认信号可以让中断源撤出其中断信号。

（4）处理器将处理器时间交给中断处理例程之前需要做一些准备工作，这其中主要包括保存在中断点当前程序的状态。最低限度地保存信息应该包括程序状态字信息和当前程序下一条指令的地址。

（5）处理器执行中断处理例程。

（6）在中断例程执行完毕后，处理器保存与中断例程相关的必要信息，处理器恢复到中断发生前的状态。

（7）处理器继续原来的指令执行过程。

3.多中断

多中断是指同时有多个中断需要处理的情况，通常有两种基本方法来处理。一种就是在处理某个中断的时候不能被打断，如果这时有新的中断信号进来，就只能先挂起；另外一种方法就是允许中断处理嵌套，也就是说，可以给不同的中断定义合理的优先级，这样当某个较低优先级的中断正在处理时，可以被一个更高优先级的中断打断，从而形成一个嵌套结构。

前一种方法比较简单，但是如果某个中断处理时间过长，就会导致新的中断等待时间过长，即便后来被处理也毫无意义。后一种方法比较可行，但是如果嵌套层次太深的话，实现起来就比较繁琐了。