《计算机操作系统教程（第三版）》课件第3章 进程管理

第3章进程管理3.1进程的概述3.2进程的引入和定义3.3进程的状态和进程控制块3.4进程控制3.5线程的基本概念3.6进程调度3.7进程同步与互斥3.8进程通信3.9死锁问题本章学习目标在多道程序环境下，程序不能独立运行。作为资源分配和独立运行的基本单位是进程。操作系统所有的特征都是基于进程而体现的。所以，本章的主要问题是：

进程的概念进程的实体、状态及状态的演变进程的控制与调度进程之间的关系协调进程的通信死锁问题及解决返回本章首页3.1进程的概述处理机管理是操作系统的基本管理功能之一，它所关心的是处理机的分配问题。也就是说把CPU（中央处理机）的使用权分给某个程序，通常把这个正准备进入内存的程序称为作业，当这个作业进入内存后我们把它称为进程。处理机管理分为作业管理和进程管理两个阶段去实现处理机的分配，常常又把直接实行处理机时间分配的进程调度工作作为处理机管理的主要内容。

进程通常具有三种状态：运行状态（正在使用CPU）、阻塞状态（等待输入/输出）和就绪状态（等待分配CPU）。

返回本章首页3.2进程的引入和定义3.2.1进程的引入3.2.2进程的定义返回本章首页3.2.1进程的引入1．程序的顺序执行及其特性2．资源共享3．程序的并发执行及其特性

1．程序的顺序执行及其特性

由于各类软件的出现及日益复杂化，使得程序设计的概念和方法有了很大的发展，在单道程序工作环境中，我们把一个“程序”理解为“一个在时间上按严格次序前后相继的操作序列”。

一切顺序执行的程序都具有下列特性：

（1）顺序性。

（2）资源独占。

（3）结果的无关性。

2．资源共享

操作系统提供了两种实现资源共享的方法。

（1）由操作系统统一管理和分配。

（2）由进程自行使用。

3．程序的并发执行及其特性

无论是操作系统自身的程序还是用户程序，通常总是存在一些相对独立、但又能并发执行的程序段。由于这些程序段可以被多个用户作业调用，因此可在同一时间间隔内发生。这样一来，某个程序段可能对应多个“计算”，于是程序与“计算”已不具有一一对应关系了。这些“并发程序”就构成了一个“并发环境”。图3.2并行计算的先后次序程序的制约方式有如下两种：（1）间接制约方式。这是由于竞争相同资源而引起的，得到资源的程序段可以投入运行，而得不到资源的程序段就是暂时等待，直至获得可用资源时再继续运行。（2）直接制约方式。这通常是在那些逻辑上相关的程序段之间发生的。一般是由于各种程序段要求共享信息引起的。返回本节目录3.2.2进程的定义

进程与程序的区别和相互关系：（1）动态性和静态性。

（2）从结构上看每个进程的实体都是由程序段和相应的数据段两部分构成的，这一特征与程序的含义相近。（3）一个进程可以涉及到一个或几个程序的执行；反之一程序可以对应多个进程，即同一程序段可在不同数据集合上运行，可构成不同的进程。（4）并发性。

（5）进程具有创建其他进程的功能。

（6）操作系统中的每一个程序都是在一个进程现场中运行的。

返回本节目录3.3进程的状态和进程控制块

3.3.1进程的状态及状态变化图

3.3.2进程控制块

返回本章首页3.3.1进程的状态及状态变化图

（1）运行状态：进程正在处理机上运行的状态，该进程已获得必要的资源，也获得了处理机，用户程序正在处理机上运行。（2）阻塞状态：进程等待某种事件完成（例如，等待输入/输出操作的完成）而暂时不能运行的状态，处于该状态的进程不能参加竞争处理机，此时，即使分配给它处理机，它也不能运行。（3）就绪状态：该进程运行所需的一切条件都得到满足，但因处理机资源个数少于进程个数，所以该进程不能运行，而必须等待分配处理机资源，一旦获得处理机就立即投入运行。图3.3典型的进程状态演变图状态变化：（1）就绪状态变化到运行状态。（2）运行状态变化到就绪状态。

（3）运行状态变化到阻塞状态。

（4）阻塞状态变化到就绪状态。

返回本节目录3.3.2进程的结构、进程控制块及组织方式为了刻画进程的动态变化，通常把进程表示为由程序段、私有数据块和进程控制块组成，如图3.4（a）所示。程序部分描述进程本身所要完成的功能，而“私有数据块”是接受程序规定操作的一组存储单元的内容，是操作的对象。进程控制块是在进程创建时产生的，当进程存在于系统时（运行），进程控制块就标识了这个进程。如图3.4（b）所示。

进程控制块是进程存在的标志，当系统或父进程创建一个进程时，实际上就是为其建立一个进程控制块。

进程控制块既能标识进程的存在，又能刻画出进程的动态特征，它是一个进程仅有的被系统真正感知的部分。对操作系统而言，所有进程控制块将构成并发执行控制和维护系统工作的依据。进程控制块的作用：返回本节目录进程控制块PCB的组织方式:为了进行PCB的有效管理，系统将PCB按照一定的方式组织起来。PCB常用的组织方式有：1）线性表方式：不论进程的状态如何，将所有的PCB连续地存放在内存的系统区。这种方式适用于系统中进程数目不多的情况。这种方式实现简单，但检索速度慢。2）索引表方式：该方式是线性表方式的改进，系统按照进程的状态分别建立就绪索引表、阻塞索引表等。3）链接表方式：系统按照进程的状态将进程的PCB组成队列，从而形成就绪队列、阻塞队列、运行队列等。3.4进程控制

3.4.1原语

3.4.2进程控制原语

返回本章首页3.4.1原语

在操作系统中，某些被进程调用的操作，例如队列操作、对信号灯的操作、检查启动外设操作等，一旦开始执行就不能被中断，否则就会出现操作错误，造成系统混乱。原语就是为实现这些操作而设置的。图3.5进程家族示例返回本节目录3.4.2进程控制原语创建原语撤消原语阻塞原语唤醒原语挂起原语激活原语返回本节目录3.5线程的基本概念3.5.1线程的引入3.5.2线程与进程的关系3.5.3线程的类型3.5.4线程的特点

返回本章首页3.5.1线程的引入（1）创建进程。系统在创建进程时，必须为之分配其所必需的、除处理机以外的所有资源。如内存空间、I/O设备以及建立相应的PCB结构。（2）撤消进程。系统在撤消进程时，又必须先对这些资源进行回收操作，然后再撤消PCB结构。（3）进程切换。在对进程进行切换时，由于要保留当前进程的CPU环境和设置新选中进程的CPU环境，为此需花费不少处理机时间。返回本节目录3.5.2线程与进程的比较1．调度：在传统的操作系统中，拥有资源的基本单位和独立调度、分派的基本单位都是进程。

2．并发性：在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行，因而使操作系统具有更好的并发性，从而能更有效地使用系统资源和提高系统吞吐量。

3．拥有资源：不论是传统的操作系统，还是设有线程的操作系统，进程都是拥有资源的一个独立单位，它可以拥有自己的资源。

4．系统开销：由于在创建或撤消进程时，系统都要为之分配或回收资源，如内存空间、I/O设备等。因此，操作系统所付出的开销将明显地大于在创建或撤消线程时的开销。

返回本节目录3.5.3线程的类型对于线程来说，则可分成两类。一类是内核支持线程，它们是依赖于内核的。即无论是在用户进程中的线程，还是系统进程中的线程，它们的创建、撤销和切换都由内核实现。在内核中保留了一个线程控制块，内核根据该控制块而感知该线程的存在并对线程进行控制。另一类是用户级线程。它仅存在于用户级中，对于这种线程的创建、撤销和切换，都不利用系统功能调用来实现，因而这种线程与内核无关。相应地，内核也并不知道有用户级的线程存在。返回本节目录比较两种线程的优缺点：1．线程的调度与切换速度：内核支持线程的调度和切换与进程的调度和切换十分相似。

2．系统功能调用：当传统的用户进程调用一个系统功能调用时，要由用户态进入核心态，用户进程将被阻塞。当内核完成系统调用而返回时，才将该进程唤醒，继续执行。

3．线程执行时间：对于只设置了用户级线程的系统，调度是以进程为单位进行的。在采用轮转调度算法时，各个进程轮流执行一个时间片，这对诸进程而言似乎是公平的。

3.5.4线程的特点操作系统为每个被创建的进程分配需要的资源，一个进程内的各个线程共享进程的资源。多线程技术有以下明显的优越性：（1）创建线程无需另外分配资源，因而创建线程的速度比创建进程的速度快，且系统开销小。（2）线程间的互操作在同一地址空间中进行，故在交换信息中不需要其他的通信机制，信息传递的速度更快。（3）线程能独立执行，能充分利用和发挥处理器和外围设备并行工作的能力。3.6进程调度

3.6.1进程调度的职能3.6.2进程调度所用的主要数据结构3.6.3进程调度的方式3.6.4进程调度算法3.6.5综合的调度策略——调度用的进程状态切换图返回本章首页3.6.1进程调度的职能

（1）记录系统中所有进程的有关情况。

（2）确定分配处理机的原则。

（3）分配处理机给进程。

（4）从进程收回处理机。

返回本节目录3.6.2进程调度所用的主要数据结构通过3.3.2节的学习我们知道操作系统对进程的管理具体体现在对进程的PCB的管理。同时我们也了解到PCB的几种组织方式：线性表方式、索引表方式和链接表方式。一般情况下，PCB的组织方式采用的是链接表方式。因此，在进程调度中所用的主要数据结构是队列（PCB的链接方式在这里就不详细介绍了，若需要了解请参见3.3.2节）。3.6.3进程调度的方式进程调度的方式可分为非剥夺式和剥夺式。剥夺式调度是指当系统按照某种原则发现一个比现运行进程更合适、更应该占用CPU的进程时，系统将强迫处于运行状态的进程将CPU的使用权交给这个更适合的进程。常见的剥夺原则有优先权原则、短进程优先原则和时间片原则。采用剥夺式调度的系统能够及时处理紧急事件，它反映出了进程的优先级特征，但这势必会带来较大的系统开销，调度算法也会相对复杂一些。非剥夺式调度是指一旦某个进程占用了CPU，除非是由于它自身原因自动放弃CPU，否则它将一直运行下去直到完成。这种调度方式算法简单，系统开销也较小，但它不能反映出进程的优先级特征。3.6.4进程调度算法

1．先来先服务

2．轮转调度

3．分级轮转法4．优先数法

5．多级反馈队列调度算法1．先来先服务

这种调度算法按照进程进入就绪队列的先后顺序来调度进程，到达得越早，其优先数越高。获得处理机的进程，未遇到其他情况时，一直运行下去，系统只需具备一个先进先出的队列，在管理优先数的就绪队列时，这种方法是一种最常见策略，并且在没有其他信息时，也是一种最合理的策略。2．轮转调度

先来先服务的一个重要变形，就是轮转规则。轮转调度算法是系统把所有就绪进程按先后次序排队，处理机总是优先分配给就绪队列中的第一个就绪进程，并分配它一个固定的时间片（如100毫秒）。当该运行进程用完规定的时间片时，被迫释放处理机给下一个处于就绪队列中的第一个进程，分给这个进程相同的时间片，每个运行完时间片的进程，当未遇到任何阻塞时，就回到就绪队列的尾部，并等待下次转到它时再投入运行。于是，只要是处于就绪队列中的进程，按此种算法迟早总可以分得处理机投入运行。3．分级轮转法所谓分级轮转法就是将先前的一个就绪队列。根据进程的优先数不同划分两个或两个以上的就绪队列，并赋给每个队列不同的优先数。以两个就绪队列为例，一个具有较高优先数，另一个具有较低优先数，前者称为前台队列，后者称为后台队列。4．优先数法

根据已占有处理

机的进程是否可被剥夺而分为优先占有法和优先剥夺法两种。优先占有法的原理是：一旦某个最高优先数的就绪进程分得处理机之后，只要不是其自身的原因被阻塞（如要求I/O操作）而不能继续运行时，就一直运行下去，直至运行结束。优先剥夺法的原理是：当一个正在运行的进程即使其时间片未用完，无论什么时候，只要就绪队列中有一个比它的优先数高的进程，优先数高的进程就可以取代以前正在运行的进程，投入运行。确定进程的优先数通常应考虑如下几个因素：

（1）进程类型。

（2）运行时间。

（3）作业的优先数。

（4）动态优先数。

5．多级反馈队列调度算法多级反馈队列（Multi-levelFeedbackQueues,MFQ）调度算法，不必事先知道各种进程所需的执行时间、优先级等，而且可以满足不同类型进程的需要，它采用动态分配优先数，调度策略实质上是抢占式的。它的调度策略如图3.8所示。图3.8多级反馈队列调度策略返回本节目录3.6.5综合的调度策略——调度用的进程状态切换图图3.6调度用的进程状态切换图返回本节目录3.7进程同步与互斥3.7.1进程互斥3.7.2互斥用的硬件机制3.7.3进程同步3.7.4用信号量实现进程同步3.7.5经典的同步/互斥问题3.7.6结构化的同步/互斥机制——管程返回本章首页3.7.1进程互斥几个进程若共享同一临界资源，它们必须以互斥的方式使用这个临界资源，即当一个进程正在使用临界资源且尚未使用完毕时，则其他进程必须推迟对该资源的进一步操作，在当前进程的使用完成之前，不能从中插进去使用这个临界资源，否则将会造成信息混乱和操作出错。临界区是一个进程访问临界资源的那段程序代码。有了临界资源和临界区的概念，进程间的互斥可以描述为禁止两个或两个以上的进程同时进入访问同一临界资源的临界区。几个并行进程对变量和队列等临界资源的互斥共享，可借助进程同步通信机构来完成。信号灯和P/V操作常用来实现进程对临界资源的互斥共享。返回本节目录3.7.2互斥用的硬件机制在许多系统中，都提供了专门用于解决临界区问题的硬件指令TestandSet（简称TS）。在不同的系统中，TS指令有所不同，但其基本功能是相同的。定义TS指令为：functionTS(varlock:boolean):boolean;beginTS:=lock;lock:=true;end为了实现用硬件指令TS实现进程互斥共享临界资源，系统为每个临界资源设置一个变量lock，该变量如上述有两种状态，其初始值为false，表示该资源空闲，进程可以对其进行访问。用TS指令实现互斥的循环进程可描述如下：repeat

whileTS(lock)doskip;criticalsection;lock:=false;

remaindersection;untilfalse返回本节目录3.7.3进程同步并发执行的多个进程，看起来好像是异步前进的，彼此之间都可以互不相关的速度向前推进，而实际上每一个进程在其运行过程中并非相互隔绝。一方面它们相互协作以达到运行用户作业所预期的目的，另一方面它们又相互竞争使用系统中有限的资源。所以它们总是存在着某种间接或直接的制约关系。同步：我们把进程间的这种必须互相合作的协同工作关系，称为进程同步。返回本节目录3.7.4用信号量实现进程同步lock和unlock大部分同步方案均采用某个物理实体（如锁、信号灯等）实现通信，进程通信原语中关锁（lock）和开锁（unlock）是最简单的原语。在这两个原语中设置一个公共变量x代表某个临界资源的状态。如：x=0，表示资源可用，x=1，表示资源正在使用。关锁原语1ock（x）：L：ifx＝1thengotoLelsex：=1；开锁原语unlock（x）：x：=0；图3.10开锁和关锁程序流程图P/V操作P/V操作由P操作原语和V操作原语组成，其意义是指，在一个整型变量S（亦称信号灯或信号量）上定义的两个操作。现欲向缓冲区Bufl输入/输出信息。设s1、s2初值为0，用P/V操作实现上述同步模型如下：返回本节目录3.7.5经典的同步/互斥问题1．生产者与消费者问题

2．读者与写者问题3.哲学家进餐问题1．生产者与消费者问题

Dijkstra把广义同步问题抽象成一种“生产者与消费者问题”（Producer-consumer-relationship）的抽象模型。事实上，计算机系统中的许多问题都可归结为生产者与消费者问题，生产者与消费者可以通过一个环形缓冲池（见图3.8）联系起来，环形缓冲池由几个大小相等的缓冲块组成，每个缓冲块容纳一个产品。每个生产者可不断地每次往缓冲池中送一个生产产品，而每个消费者则可不断地每次从缓冲池中取出一个产品。

图3.8环形缓冲池下面给出基于环形缓冲区的生产者与消费者关系的形式描述，设：（1）公用信号量mutex：初值为1，用于实现临界区互斥。（2）生产者私用信号量empty：初值为n，指示空缓冲块数目。（3）消费者私用信号量full：初值为0，指示满缓冲块数目。（4）整型量i和j初值均为0，i指示首空缓冲块序号，j指示首满缓冲块序号。模块设计如下：

Varmutex，empty，full：semaphore;i,j:integer；buffer：array[0…n一1]ofitem；Procedureproducer;生产者进程

begin

whiletruedobeginproduceaproduct;P(empty);

P(mutex);Buffer(i)：＝Product;i：＝(i+1)modn；V(mutex);V(full)endend;procedureconsumer;消费者进程

beginWhiletruedobeginP(full)；P(mutex)goods：＝buffer(j);j：＝(j+1)modn;V(mutex);V(empty);Consumeaproduct;end

end;beginseminitial;i:＝j:＝0;cobeginproducer；consumer；coendend2．读者与写者问题

设某航空公司有2个售票处，它们通过远程终端访问设在公司总部的航空订票系统，并要查询或修改系统中记录所有班机当前订票数的数据库B。设Bi为某班机的当前订票数，P1和P2分别代表2个售票处的售票进程，R1和R2为进程执行时使用的工作寄存器。由于售票进程并发执行，且各自访问数据库B的时间是随机的，故有可能出现下面的访问序列（假定Bi的当前值为x）：P1:R1:=Bi;R1:=R1+1P2:R2=Bi;R2:=R2+1;P1:Bi:=R1;P2:Bi:=R2

可见，Bi的新值是X+1，而不是X+2。这里的P1和P2均为写者，显然，对于写者Bi为临界资源，因此写者应该互斥。下面给出读者进程与写者进程的一般结构。varmutex,wrt:semaphore;readcount:integer;beginseminit;readcount:=0cobeginprocedurereader;beginP(mutex);Readcount:=readcount+1;Ifreadcount=1thenP(wrt);V(mutex);Readingisperforming;P(mutex);readcount:=readcount-1ifreadcount=0thenV(wrt);V(mutex);End

Procedurewriter;BeginP(wrt);writingisperforming;V(wrt);EndCoendEnd;3.哲学家进餐问题五个哲学家围坐在一张圆桌周围，每个哲学家面前都有一碟通心面，由于面条很滑，所以要两把叉子才能夹住。相邻两个碟子之间有一把叉子，餐桌如图3.12所示。哲学家的生活包括两种活动：即吃饭和思考(这只是一种抽象，即对本问题而言其他活动都无关紧要)。当一个哲学家觉得饿时，他就试图分两次去取他左边和右边的叉子，每次拿一把，但不分次序。如果成功地获得了两把叉子，他就开始吃饭，吃完以后放下叉子继续思考。这里的问题就是：为每一个哲学家写一段程序来描述其行为，要求不能死锁。下面给出了最浅显的解法#defineN5 /*

哲学家数目

*/voidphiloiopher(inti) /*哲学家号从0到4号

*/{

while(TRUE){

think(); /*

哲学家正在思考

*/

take_fork(i); /*

取左面叉子

*/

take-fork((i+1)%N); /*

取右面叉子,%为取余*/

eat(); /*

吃面

*/

put_fork(i); /*

放回左面叉子

*/

put_fork((i+1)%N); /*

放回右面叉子

*/

}}过程take_fork将一直等到所指定的叉子可用，然后将其取用。不幸的是，这种解法是错误的。设想所有五位哲学家都同时拿起左面的叉子，则他们都拿不到右面的叉子，于是发生死锁。下面的解法不仅正确，而且对于任意位哲学家的情况都能获得最大的并行度。其中使用一个数组state来跟踪一个哲学家是在吃饭、思考还是正在试图拿叉子。一个哲学家只有在两个邻居都不在进餐时才允许转移到进餐状态。第i位哲学家的邻居由宏LEFT和RIGHT定义，换言之，若i为2，则LEFT为l，RIGHT为3。#defineN5 /*

哲学家数目

*/#defineLEFT(i-1)%N /*

i的左邻号码

*/#defineRIGHT(i+1)%N /*

i的右邻号码

*/#defineTHINKING0 /*

哲学家正在思考

*/#difineHUNGRY1 /*

哲学家想取得叉子

*/#defineEATING2 /*

哲学家正在吃面

*/typdefintsemaphore; /*

信号量是一个特殊的整型变量*/intstate[N]; /*

记录每个人状态的数组

*/semaphoremutex=1; /*

临界区互斥

*/semaphores[N]; /*

每个哲学家一个信号量

*/voidphilosopher(inti) /*

哲学家号码，从0到N-1

*/{

while(TRUE){ /*

哲学家号码，从0到N-1

*/

think(); /*

哲学家正在思考

*/

take_forks(i); /*

需要两只叉子，或者阻塞

*/

eat(); /*

进餐

*/

put_forks(i); /*

把两把叉子同时放回桌子

*/

}}voidtake_forks(inti) /*

哲学家号码从0到N-1

*/{

P(&mutex)； /*

进入临界区

*/state[i]=HUNGRY; /*

记录下哲学家i饥饿的事实

*/

test(i); /*

试图得到两只叉子

*/

v(&mutex); /*

离开临界区

*/

p(&s[i]); /*

如果得不到叉子就阻塞

*/}voidput_forks(inti) /*

哲学家号码从0到N-1

*/{

p(&mutex)； /*

进入临界区

*/

state[i]=THINKING; /*

哲学家进程结束

*/

test(LEFT); /*

看一下左邻居现在是否能进餐*/

test(RIGHT) /*

看一下右邻居现在是否能进餐*/

v(&mutex); /*

离开临界区

*/}voidtest(inti) /*

哲学家号码从0到N-1

*/{

if(state[i]==HUNGRY&&state[LEFT]!=EATING&&state[RIGHT]!=EATING)

{

state[i]=EATING;

v(&s[i]);

}}返回本节目录3.7.6结构化的同步/互斥机制——管程建立管程的基本理由是：由于对临界区的执行分散在各进程中，这样不便于系统对临界资源的控制和管理，也很难发现和纠正分散在用户程序中的对同步原语的错误使用等问题。为此，应把分散的各同类临界区集中起来。并为每个可共享资源设立一个专门的管程来统一管理各进程对该资源的访问。这样既便于系统管理共享资源，又能保证互斥访问。管程主要由两部分组成：（1）局部于该管程的共享数据，这些数据表示了相应资源的状态。（2）局部于该管程的若干过程，每个过程完成关于上述数据的某种规定操作。为了实现对临界资源的互斥访问，管程每次只允许一个进程进入其内（即访问管程内的某个过程），这是由编译系统保证的。

monitorringbuffer;varrbuffer：array[0．．n-1]ofitem；k,nextempty,nextfull:integer;empty,full:condition;procedureentryput(varproduct:item);beginifk=nwait(empty);rbuffer[nextempty]:product;k:=k+1；nextempty:=(nextempty+1)modn;signal(full);end;例：以环形缓冲池为例，给出环形缓冲池的管程结构

procedureentryget(vargoods:item);beginifk=0wait(full);goods:=rbuffer[nextfull];k:=k-1;nextfull:=(nextfull+1)modn;signal(empty);end;begink:=0;nextempty:=0;nextfull:=0;end;在利用管程解决生产者、消费者问题时，其中的生产者和消费者可描述为：producer：beginrepeatproduceanitem；ringbuffer.put(item)；untilfalse；endconsumer：beginrepeatringbuffer.get(item)；consumetheitem；end返回本节目录3.8进程通信3.8.1共享存储区通信机制3.8.2消息系统3.8.3管道通信返回本章首页进程通信IPC（InterProcessCommunication），指的是并发进程之间相互交换信息，信息量是可大可小的。操作系统提供了多种进程间的通信机制，可分别适用于不同的场合。从广义上讲，上节所讨论的进程间的同步与互斥也是一种通信，只不过信号量与PV操作只能传递信号，没有传递数据的能力。但本节所讨论的通信，强调的是进程之间有较大信息量的交换，比如传送大量的计算结果。解决进程之间的通信问题总体上有三个方案：共享存储区、消息系统和管道通信。其中共享存储区通信方式由于交换的信息量少且效率低下，故称为低级通信机制，仅适用于集中式操作系统。消息传递机制属于高级通信机制，共享文件通信机制是消息传递机制的变种，这两种通信机制，既适用于集中式操作系统，又适用于分布式操作系统。3.8.1共享存储区通信机制共享存储区通信机制要求通信进程之间共享某些变量，并通过这些变量交换信息。但这些共享变量一定要在多个进程之间互斥使用，否则就会导致不确定性错误。具体的实现方法为在内存中开辟一个共享存储区，如图3.13所示，各进程通过该存储区实现通信，这是进程通信中最快捷和有效的方法。进程通信之前，向共享存储区申请一个分区段，并指定关键字；若系统己为其他进程分配了这个分区，则返回关键字给申请者，于是该分区段就可连到进程的虚地址空间，以后，进程便像通常存储器一样共享存储区段，通过对该区段的读、写来直接进行通信。3.8.2消息系统1．SEND(A)（发送消息）原语

2．READ（A）（读取消息）原语1．SEND(A)（发送消息）原语

发送消息原语被进程用于把消息发送到存放消息的缓冲区。A是原语的参数，表示发送区的地址。其工作原理是：首先调用“寻找目标进程的PCB”的程序查找接收进程的PCB，如果接收进程存在，申请一个存放消息的缓冲区，消息缓冲区为空时，接收此消息的进程因等待此消息的到来而处于阻塞状态，则唤醒此进程，并把消息的内容、发送原语的进程名和消息等，复制到预先申请的存放消息的缓冲区，且将存放消息的缓冲区连接到接收进程的PCB上；如果接收进程不存在，则由系统给出一个“哑”回答；最后控制返回到发送消息的进程继续执行，或转入进程调度程序重新分配处理机。如果消息缓冲区已满，则返回到非同步错误处理程序入口进行特殊处理。如图3.9所示。图3.14发送消息过程流图2．READ（A）（读取消息）原语

READ(A)原语用来读取消息，接收进程读取消息之前，在自己的空间中确定一个接收区。当接收进程想要读取消息时，使用READ(A)原语，A是接收进程提供的接收区开始地址。如图3.10所示。图3.15读取消息返回本节目录3.8.3管道通信管道（pipeline）是连接读写进程的一个特殊共享文件，允许进程按先进先出方式传送数据，也能使进程同步执行操作。如图3.16所示使用管道通信实现进程之间的相互通信，基本上可以使用文件系统的原有机制实现，包括文件的建立、打开、关闭和读写等。但是，发送和接收进程之间的相互协调并不是单靠文件系统的机制所能解决的。相互协调在这里有三个方面的含义。一是进程对通信机构的使用应该是互斥的，即一个进程正在使用某个信道进行读或写操作时，其他进程就不能使用它；二是发送者和接收者双方都能以一定方式了解到对方的存在，即一个发送进程了解到其信息的接受进程并不存在，就不发送其信息；三是发送和接收信息之间要有一定的同步关系。3.9死锁问题

3.9.1死锁产生的原因和必要条件3.9.2预防死锁3.9.3避免死锁3.9.4检测与解除死锁

返回本章首页3.9.1死锁产生的原因和必要条件

死锁产生的原因：当某个进程提出申请资源后，使得有关进程在无外力协助下，永远分配不到必需的资源而无法继续运行，这就产生了一种特殊的现象——死锁。在许多实时应用中，比如计算机控制运输和监视系统方面，死锁问题也极为重要。

死锁产生例子1：我们先来看一个申请不同类型资源的死锁例子，假定有两个进程Pl和P2都要修改文件F，修改时都需要一条暂时存放信息的磁带，而只有一台磁带机T可用。又假定由于某种原因，在进行修改之前，P2需要一暂存磁带（例如为了修改，要重新组织输入数据）。设F和T都是可重用资源，它们分别表示允许更新文件和允许使用磁带机。于是Pl和P2。可有如下形式：分析：从上面的申请-释放过程可以看出，进程Pl和P2有可能“同时”分别到达rl和r2处，例如，P2首先得到T，然后Pl得到F，接着Pl到达r1，最后P2到达r2，此时，若Pl继续运行，则占有F的进程Pl将阻塞在T上，若P2继续运行，则占有T的进程P2将阻塞在F上，如果P2不能前进，则P1也不能继续下去，反之亦然。我们说这两个进程处在死锁状态。图3.11简单的死锁例子死锁产生例子2：现在我们再来看一个关于相同类型资源共享的死锁例子，假设有一类可再使用资源R，例如主存或外存，它包含有m个页面或扇区，由n个进程P1，P2…，Pn（2≤m≤n）共享。假定每个进程按右图顺序申请和释放页面（或扇区）：分析：这里每次申请和释放只涉及R的一个分配单元（页或扇区）。因此，当把所有单元全部分配完毕时，便很容易发生死锁；占有R的单元的所有进程（前m个进程）会永远阻塞在第二次申请上，而有些进程（n~m个进程）类似地会阻塞在它们的第一次申请上，在图3.12中说明了n＝3，m＝2时这种系统的状态，这类死锁是相当普遍的。

图3.12同类资源共享时的死锁现象产生死锁有四个必要条件：

产生死锁有四个必要条件：（1）互斥条件。

（2）不剥夺条件。（3）请求和保持条件。（4）环路等待条件。

返回本节目录3.9.2预防死锁

1．破坏“请求与保持条件”

2．破坏环路条件

3．资源受控动态分配

1．破坏“请求与保持条件”

这种方法的基本思想是：每个进程在运行之前，必须预先提出自己所要使用的全部资源，调度程序在该进程所需要的资源末得到满足之前，不让它们投入运行，并且当资源一旦分配给某个进程之后，那么在该进程的整个运行期间相应资源一直被它占有，这就破坏了产生死锁的请求与保持条件。2．破坏环路条件

这种方法的基本思想是：对系统提供的每一项资源，由系统设计者将它们按类型进行线性排队，并赋予不同的序号。例如，设卡片输入机为1，打印机为2，磁带机为3，磁盘机为4，……。所有的进程都只能严格地按照编号递增（或递减）的次序去请求资源，亦即，只有低编号的资源要求满足后，才能对高编号资源提出要求；释放资源时，应按编号递减的次序进行。由此可以看出，对资源请求采取了这种限制之后，所形成的进程—资源图不可能再产生环路。如图3.13所示.图3.13资源申请和释放顺序图3．资源受控动态分配

为了避免死锁发生，操作系统必须根据预先掌握的关于资源用法的信息控制资源分配，使得共同进展路径的下一步不致于进入危险区，即只要有产生死锁的可能性，就避免把一种资源分配给一个进程。

返回本节目录3.9.3避免死锁避免死锁是指通过某种算法，当系统分配资源时始终能作出是否分配的正确选择，从而避免死锁。目前运用的避免死锁的算法是E.W.Dijkstra提出的银行家算法。下面我们用现实生活中的例子来说明该算法的思想：假设一家银行拥有资金2000万，现有10家公司向其贷款进行筹建，每家均需300万才能建成。如果这家银行将2000万的资金平均贷给这10家公司，则每家公司将得到200万的贷款，都不能筹建成功，也就不能还贷，那么这10家公司都将“死锁”。若这家银行给其中的4家各贷300万，另4家各贷200万，这样将还有2家公司得不到贷款，不能开工建设，但有4家可筹建完成，这4家公司运营所得利润可向该银行还贷，银行可以利用还贷的资金继续向其他的公司贷款，从而保证所有公司筹建成功投入运营。银行家算法是为了把一定数量的资金供多个用户周转，并保证资金的安全。银行家算法可归纳为：（1）当一个用户对资金的最大需求量不超过银行家现有的资金时，就可接纳该用户。（2）用户可以分期贷款，但贷款总数不能超过最大需求量。（3）当银行家现有的资金不能满足用户的尚需贷款数时，可以推迟支付，但总能使用户在有限的时间里得到贷款。（4）当用户得到所需的全部资金后，一定能在有限时间里归还所有的资金。我们可以把操作系统看作银行家，把进程看作用户，把操作系统管理的资源看作银行家管理的资金，把进程向操作系统请求资源看作用户向银行家贷款。操作系统按照银行家规定的规则为进程分配资源。当进程首次申请资源时，要测试该进程对资源的最大需求量。如果系统现存的资源可以满足它的最大需求量，则按当前的申请量分配资源，否则推后分配。当进程在执行中继续申请资源时，先测试该进程已占有的资源数与本次申请的资源数之和是否超过该进程对资源的最大需求量。如果超过，则拒绝分配资源，否则再测试系统现存的资源能否满足该进程尚需的最大资源量。若能满足，则按当前的申请量分配资源，否则也要推迟分配。这样做，能保证在任何时刻至少有一个进程可以得到所需要的全部资源而执行到结束，执行结束后归还资源，并把这些资源加入到系统的剩余资源中，用同样的方法为其他的进程分配资源。银行家算法的数据结构包括：（1）可用资源向量Available。它是一个一维数组，数组中的每一个元素表示某一类可用的资源数目，如Available[i]=k，表示系统中现有Ri类资源k个。每个元素的初始值为系统中所配置的该类全部可用资源数目，该值将随着该类资源的分配和回收而动态地发生变化。（2）最大需求矩阵Max。它是一个二维数组。系统中有几个进程，它就有几行；系统中有几类资源，它就有几列。其中的每一个元素表示它所在的行所表示的进程对它所在的列表示的那类资源的最大需求量，如Max[i,j]=k，表示进程i对Rj类资源的最大需求数目是k个。（3）分配矩阵Allocation。它是一个二维数组。系统中有几个进程，它就有几行；系统中有几类资源，它就有几列。其中的每一个元素表示它所在的行所表示的进程已分配它所在的列所表示的那类资源的数目，如Allocation[i,j]=k，表示进程i当前已分得Rj类资源的数目是