进程间的制约关系

进程间的制约关系第一页，共六十四页，编辑于2023年，星期五在多道程序的环境中，系统中的多个进程可以并发执行，同时它们又要共享系统中的资源，这些资源有些是可共享使用的，如磁盘，有些是以独占方式使用的，如打印机。由此将会引起一系列的矛盾，产生错综复杂的相互制约的关系。产生这种错综复杂的相互制约关系的原因有二：

资源共享——间接制约关系

进程合作——直接制约关系6.1进程间制约关系第二页，共六十四页，编辑于2023年，星期五进程间的同步

2.进程间的互斥

一、进程间的同步和互斥

第三页，共六十四页，编辑于2023年，星期五临界资源：某段时间仅允许一个进程使用的资源称为临界资源。宿舍电话打印机电话和打印机都属于临界资源。除此之外，还有内存变量、指针、数组等等也是临界资源。几个进程若共享同一临界资源，它们必须以互斥的方式使用这个临界资源，即当一个进程正在使用临界资源且尚未使用完毕时，则其他进程必须推迟对该资源的进一步操作。一、进程间的同步和互斥

第四页，共六十四页，编辑于2023年，星期五临界区(criticalsection)每个进程中访问临界资源的那段程序段称为相对于临界资源的临界区。访问临界资源的进程互斥的进入各自的临界区。第五页，共六十四页，编辑于2023年，星期五这种方法使用了一个物理实体，称为锁，用

W

来表示，锁有两种状态，W=0

表示锁已打开；W=1表示锁被关闭。加锁原语用LOCK(W)表示，其操作为：测试W，若W=1，表示资源正在使用，继续反复测试；若W=0，置W=1(加锁)。加锁原语用LOCK(W)可描述为L：ifW=1thengotoLelseW：=1；开锁原语用UNLOCK(W)表示，可描述为

W：=0；

二、实现临界区互斥的锁操作法

第六页，共六十四页，编辑于2023年，星期五两个进程P1、P2使用如下程序实施进程的互斥：

进程P1进程P2LOCK(W)LOCK(W)

S1S2UNLOCK(W)UNLOCK(W)其中S1和S2分别为进程P1和P2的临界区。

第七页，共六十四页，编辑于2023年，星期五三、实现临界区互斥的TS指令法

Test-and-Set指令FunctionTS(VARboolean:lock)：booleanBeginTS=lock;lock=TRUE;ENDlock表示临界资源的两种状态：lock=TRUE表示临界资源正被占用，lock=FALSE表示临界资源空闲；lock的初值为FALSE。第八页，共六十四页，编辑于2023年，星期五互斥算法（TS指令）利用TS实现进程互斥：每个临界资源设置一个公共布尔变量lock，初值为FALSE

whileTS(lock)doskip;lock:=FALSE;criticalsectionremaindersection第九页，共六十四页，编辑于2023年，星期五1965年，荷兰学者Dijkstra提出的信号量机制是一种卓有成效的进程同步工具，在长期广泛的应用中，信号量机制又得到了很大的发展，它从整型信号量机制发展到记录型信号量机制，进而发展为“信号集”机制。现在信号量机制已广泛应用于OS中。6.2信号量和P、V操作第十页，共六十四页，编辑于2023年，星期五信号量按联系进程的关系分成二类：公用信号量（互斥信号量）：它为一组需互斥共享临界资源的并发进程而设置，代表共享的临界资源，每个进程均可对它施加P、V操作，即都可申请和释放该临界资源，其初始值置为1。信号量s取值意义如下：

s＝1；表示资源空闲，可供使用。

s＝0；表示资源已被占用，无其它进程等待。

s＝-n；表示资源已被占用，还有n个进程因等待资源而阻塞。私用信号量（同步信号量）：它为一组需同步协作完成任务的并发进程而设置，只有拥有该资源的进程才能对它施加P操作（即可申请资源），而由其合作进程对它施加V操作（即释放资源）。第十一页，共六十四页，编辑于2023年，星期五P、V操作是定义在信号量S上的两个操作，其定义分别如下：

P(S)：S：=S-1若S≥0，则调用P(S)的进程继续运行；若S＜0，则调用P(S)的进程被阻塞，并把它插入到等待信号量S的阻塞队列中。V(S)：S：=S+1；若S＞0，则调用V(S)的进程继续运行；若S≤0，从等待信号量S的阻塞队列中唤醒头一个进程，然后调用V(S)的进程继续运行。第十二页，共六十四页，编辑于2023年，星期五P、V操作可表示为如下两个过程：

P操作：Procedure

P(VarS:Semaphore)BeginS:=S-1;//表示申请一个资源;If

s<0//表示没有空闲资源;then

W(S)//调用进程进入等待队列;End;

第十三页，共六十四页，编辑于2023年，星期五V操作：Procedure

V(Vars:semaphore)BeginS:=S+1;//表示释放一个资源；

If

S≤0

//表示有进程处于阻塞状态；

thenR(S)//从等待队列s中取出一个进程是其进入就绪队列;End;其中W(S)表示将调用该过程的进程置成等待信号量S的阻塞状态，并插入相应的阻塞队列中。R(S)表示要唤醒等待信号S阻塞队列中的头一个进程。第十四页，共六十四页，编辑于2023年，星期五为临界资源设置一个互斥信号量mutex(MUTualExclusion)，其初值为1；在每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间必须成对使用P和V原语：遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放（给其他等待的进程）；P、V原语不能次序错误、重复或遗漏利用信号量实现互斥第十五页，共六十四页，编辑于2023年，星期五为使多个进程能互斥地访问某临界资源，只需为该资源设置一个互斥信号量mutex,并设其初值为1，然后将各进程的临界区CS置于P（mutex）和V(mutex)操作之间即可。利用信号量实现共享打印机的A、B两进程互斥的类并行PASCAL程序描述如下：利用信号量实现进程互斥第十六页，共六十四页，编辑于2023年，星期五varmutex.value=1:semaphore；beginparbeginA:beginB:beginInputdata1fromI/01；Inputdata2fromI/O2；

Compute……；Compute……；

P(mutex)；P(mutex)；

Printresults1byprinter;Printresults2byprinter;

V(mutex)；V(mutex)；

endendparendend第十七页，共六十四页，编辑于2023年，星期五mutex:互斥信号量（mutualexclusion），最多只允许一个进程进入临界区,相当于一把锁！初值=1，在n个进程间实现互斥,则只有一个进程能用P操作把mutex.vaule减为0，而执行其临界区！第二个进程对mutex执行P操作时，mutex.vaule=-1,进程被阻塞。如此继续...某进程对mutex执行V操作，mutex.vaule加1，当mutex.vaule<=0时唤醒等在mutex上的一个进程使之进入就绪状态继而进入临界区！信号量mutex.vaule的取值范围：1..-(n-1)最多n-1个进程等待进入临界区第十八页，共六十四页，编辑于2023年，星期五利用信号量实现进程同步利用信号量能解决进程间的同步问题，这里以下图所示的计算进程C和打印进程P通过单缓冲区Buffer传送数据的同步问题为例说明。BufferCP第十九页，共六十四页，编辑于2023年，星期五C和P两进程基本算法如下：C：beginP:beginrepeatrepeatComputenextnumber;takefromBuffer;addtoBuffer;printlastnumber;untilfalseuntilfalseendendC和P两进程并发执行，必须在执行序列上遵循以下规则，才能避免错误。只有当C进程把数据送入Buffer后，P进程才能从Buffer中取出数据来打印，否则P进程只能等待。只有当P进程从Buffer中取走数据后，C进程才能将新计算的数据再存入Buffer,否则C进程也只能等待。第二十页，共六十四页，编辑于2023年，星期五经典的同步/互斥问题

1．生产者与消费者问题

2．读者与写者问题

第二十一页，共六十四页，编辑于2023年，星期五1．生产者与消费者问题

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

下一页第二十二页，共六十四页，编辑于2023年，星期五环形缓冲池第二十三页，共六十四页，编辑于2023年，星期五问题描述：若干进程通过有限的共享缓冲区交换数据。其中，"生产者"进程不断写入，而"消费者"进程不断读出；共享缓冲区共有N个；任何时刻只能有一个进程可对共享缓冲区进行操作。共享缓冲区生产指针消费指针Producer1Producer2...ProducerMConsumer1Consumer2...ConsumerN满空指针移动方向第二十四页，共六十四页，编辑于2023年，星期五下面给出基于环形缓冲区的生产者与消费者关系的形式描述，设：（1）公用信号量mutex：初值为1，用于实现临界区互斥。（2）生产者私用信号量empty：初值为n，指示空缓冲块数目。（3）消费者私用信号量full：初值为0，指示满缓冲块数目。（4）整型量i和j初值均为0，i指示首空缓冲块序号，j指示首满缓冲块序号。第二十五页，共六十四页，编辑于2023年，星期五采用信号量机制：full是"满"数目，初值为0，empty是"空"数目，初值为N。实际上，full和empty是同一个含义：full+empty==Nmutex用于访问缓冲区时的互斥，初值是1每个进程中各个P操作的次序是重要的：先检查资源数目，再检查是否互斥――否则可能死锁(为什么？)第二十六页，共六十四页，编辑于2023年，星期五

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;第二十七页，共六十四页，编辑于2023年，星期五procedureconsumer;消费者进程beginWhiletruedobeginP(full)；

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

end;第二十八页，共六十四页，编辑于2023年，星期五beginseminitial;i:＝j:＝0;cobeginproducer；

consumer；

coendend第二十九页，共六十四页，编辑于2023年，星期五P(empty);P(mutex);Buffer(i)：＝Product;i：＝(i+1)modn；

V(mutex);V(full)P(full)；

P(mutex)goods：＝buffer(j);j：＝(j+1)modn;V(mutex);V(empty);第三十页，共六十四页，编辑于2023年，星期五2．读者与写者问题

设某航空公司有2个售票处，它们通过远程终端访问设在公司总部的航空订票系统，并要查询或修改系统中记录所有班机当前订票数的数据库B。设Bi为某班机的当前订票数，P1和P2分别代表2个售票处的售票进程，R1和R2为进程执行时使用的工作寄存器。由于售票进程并发执行，且各自访问数据库B的时间是随机的，故有可能出现下面的访问序列（假定Bi的当前值为x）：第三十一页，共六十四页，编辑于2023年，星期五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为临界资源，因此写者应该互斥。第三十二页，共六十四页，编辑于2023年，星期五

一个数据集（如文件）如果被几个并行进程所共享，有些进程只要求读数据集内容，它称读者，而另一些进程则要求修改数据集内容，它称写者，几个读者可以同时读这些数据集，而不需要互斥，但一个写者不能和其它进程（不管是写者或读者）同时访问些数据集，它们之间必须互斥。读者和写者,共享一组数据区要求：允许多个读者同时执行读操作不允许读者、写者同时操作不允许多个写者同时操作设置互斥信号量wrt表示写者间、读者和写者间互斥第三十三页，共六十四页，编辑于2023年，星期五读者与写者问题读者：beginP(mutex);readcount:=readcount+1;ifreadcount=1thenP(wrt);V(mutex);读P(mutex);readcount:=readcount-1;ifreadcount=0thenV(wrt);V(mutex);End写者：beginP(wrt);写V(wrt);End第三十四页，共六十四页，编辑于2023年，星期五varmutex,wrt:semaphore;readcount:integer;beginseminit;readcount:=0cobeginprocedurereader;beginP(mutex);Readcount:=readcount+1;Ifreadcount=1thenP(wrt);V(mutex);Readingisperforming;第三十五页，共六十四页，编辑于2023年，星期五P(mutex);readcount:=readcount-1ifreadcount=0thenV(wrt);V(mutex);End

Procedurewriter;BeginP(wrt);writingisperforming;V(wrt);EndCoendEnd;第三十六页，共六十四页，编辑于2023年，星期五由于readcount是读者间共享变量，属于临界资源，它也需互斥，为此又增设互斥信号量rmutex.第三十七页，共六十四页，编辑于2023年，星期五读者：beginP(mutex);readcount:=readcount+1;ifreadcount=1thenP(wrt);V(mutex);读P(mutex);readcount:=readcount-1;ifreadcount=0thenV(wrt);V(mutex);End写者：beginP(wrt);写V(wrt);End第三十八页，共六十四页，编辑于2023年，星期五第三十九页，共六十四页，编辑于2023年，星期五6.3死锁问题和高级进程通信6.3.1死锁产生的原因和必要条件

6.3.2预防死锁

6.3.3发现死锁

6.3.4解除死锁6.3.5高级进程通信

第四十页，共六十四页，编辑于2023年，星期五6.3.1死锁产生的原因和必要条件

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

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

第四十六页，共六十四页，编辑于2023年，星期五同类资源共享时的死锁现象第四十七页，共六十四页，编辑于2023年，星期五产生死锁有四个必要条件：

互斥条件：一个资源一次只能被一个进程所使用，即是排它性使用。不可剥夺/抢占条件：一个资源仅能被占有它的进程所释放，而不能被别的进程抢占。请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源要求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对已经获得的其它资源保持不放。第四十八页，共六十四页，编辑于2023年，星期五环路等待条件：前一进程占有的资源正是后一进程所需要的资源，在发生死锁时，必然存在一个进程---资源的环形链。如一系统状态的资源分配图所示，P1正在等待一个P2

占用的资源R2，P2正在等待一个P1占用的资源R1。第四十九页，共六十四页，编辑于2023年，星期五6.3.2预防死锁

预防死锁的方法是破坏四个产生死锁的必要条件之一。1.破坏互斥条件互斥使用是资源本身特征所决定的。2.破坏不可剥夺/不可抢占条件抢占式调度法主要用于处理机和存贮器资源调度，它们的状态容易保存和恢复。但此法对外部设备和私存数据不宜使用。第五十页，共六十四页，编辑于2023年，星期五3．破坏“请求与保持条件”

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

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

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

第五十四页，共六十四页，编辑于2023年，星期五6.3.3发现死锁

假定系统有n个进程P1，P2，…，Pn和Pm种类型资源Rl，R2，…，Rm。.建立资源分配表S和进程等待表W，分别如表3.1和表3.2所示，其中aij表示分配给进程Pi的资源Rj的数目，bij表示进程Pi请求资源Rj的数目。另外为每一个进程设置一个等待资源计数器C1，C2，…，Cn，它们表示引起相应进程被阻塞的资源数目，将末阻塞的进程组成一个表L（或队列）。

第五十五页，共六十四页，编辑于2023年，星期五资源