操作系统死锁同步互斥CH6c5

进程间的制约关系

第6章

计算机学院柴忠良6.1进程间的制约关系16.3死锁、高级进程通信3本章讲述内容6.2信号量与P、V操作1

本章将引入操作系统中的重要概念：信号量以及在信号量上的P、V操作。利用信号量以及在信号量上的P、V操作，可以很好地解决进程间的互斥与同步关系，保证进程程序的正确执行。

本章着重讲述四个方面的内容：（1）进程间的两种制约关系—互斥与同步。（2）正确处理互斥与同步的方法—信号量以及在信号量上的P、V操作。（3）死锁以及解决死锁的途径。（4）进程间的高级通信。进程的顺序性冯·诺依曼结构的基本特性是处理器顺序执行命令。当一个进程独占CPU时具有以下特性：顺序性：处理机的操作严格按照程序所规定的顺序执行。封闭性：进程执行的结果取决于进程本身，不受外界影响。可再现性：当进程再次重复执行时，必定获得相同的结果。进程的并发性如果系统中存在一组可同时执行的进程。并发进程之间可能是无关的，也可能是有关的—相互依赖。当多个进程共享CPU时具有以下特性：间断性：不再是一口气运行下去，出现走走停停现象，停的次数和地方不再相同。封闭性被打破：不同的时间运行的进程个数、是谁以及它们的执行时间不同，受外界影响。不可再现性：当进程再次重复执行时，运行的过程和运行的结果不一定相同。6.1进程间的制约关系

6.1.1与时间有关的错误在相同的前提条件下，两次执行的结果有可能不相同。在操作系统里，把这种由于时间因素的影响而产生的错误，称为“与时间有关的错误”。例：游乐场自动计数系统。Begin Count:integer; Count:=0;Cobegin

Coend;End;ProcessPIN R1:integer;Begin R1:=count; R1:=R1+1; count:=R1;End;ProcessPOUT R2:integer;Begin R2:=count; R2:=R2-1; count:=R2;End;例：飞机航班售票系统。Aj:j次航班余票数

j=1,2,3…mPi:i航班处理进程i=1,2,3…nRi:各进程工作单元售票处1售票处5售票处4售票处3售票处2例：飞机航班售票系统。ProcessPi(i=1,2,3…n) Ri:integer;Begin

按旅客要求找到Aj; Ri:=Aj; ifRi>=1then else输出“票已售完”End;Begin Ri:=Ri-1; Aj:=Ri;

输出一张票End;图6-1对输出井文件目录的管理图6-2通过双缓冲区复制文件图6-3GET→PUT→COPY导致错误6.1.2竞争资源—互斥在操作系统中，凡是牵扯到数据、队列、缓冲区、表格和变量等任何形式的共享资源时，都很容易出现类似的这种“与时间有关的错误”。

为了避免错误的发生，关键是要找到一种途径，来阻止多于一个进程同时使用它们。也就是说，保证对它们的使用是互斥进行的。

与一个共享变量（或临界资源）交往的多个进程，为了保证它们各自运行结果的正确性，当其中的一个进程正在对该变量（或临界资源）进行操作时，就不允许其他进程同时对它进行操作。进程间的这种制约关系被称为“互斥”。

进程A进程B共享变量COUNT对具有互斥关系的进程，要注意以下四点：（1）只有涉及共享变量的那一部分程序，才真正需要保证互斥地执行。通常，把进程程序中“真正需要保证互斥执行”的那一段程序，称为该进程的“临界区（或临界段）”。

进程A进程B共享变量COUNT例：游乐场自动计数系统。Begin Count:integer; Count:=0;Cobegin

Coend;End;ProcessPIN R1:integer;Begin

R1:=count; R1:=R1+1; count:=R1;End;ProcessPOUT R2:integer;Begin

R2:=count; R2:=R2-1; count:=R2;End;（2）具有互斥关系的进程，并不关心对方的存在性。即使对方不存在，自己也能够正确的运行，不会受到它存在与否的影响。（3）具有互斥关系进程的临界区，虽然都是针对同一个共享变量的程序段，但在其上的操作可以相同也可以不相同。相关临界区（4）进程的临界区是相对于某个共享变量而言的，不同共享变量的临界区之间，不存在互斥关系。XY相关临界区执行时必须遵循以下准则：（1）每次只允许一个进程进入临界区。（2）一个进程在临界区内逗留有限时间后，就应该退出，以便给其他进程创造进入临界区的机会。（3）不能强迫一个进程在临界区外无限期逗留。相关临界区三原则

有限时间进一次一个有限时间出16.1.3协同工作—同步这里所描述的进程间的关系有如下特点：（1）具有这种关系的进程，需要在某些点上协调相互的动作，谁先到达谁后到达是有顺序要求的。图6-4GET和COPY协调一致地工作（2）这些进程都应该了解对方的工作，对方不存在，或任何一方单独运行，就会出现差错。（3）一方或双方的运行会直接地依赖于对方所产生的信息或发出的消息。

一个进程运行到某一点时，除非合作进程已经完成了某种操作或发来了信息，否则就必须暂时等待那些操作的完成或信息的到来。握手和均值

进程间的这种关系被称为“同步”。暂停等待以取得同步的那一点，称为“同步点”，需要等待一个进程完成的操作或发送的信息，称为“同步条件”。6.2信号量与P、V操作

通过信号量取不同的初值以及在其上做P、V操作，就能够实现进程间的互斥、同步，甚至用来管理资源的分配。6.2.1信号量与P、V操作的定义所谓“信号量”，是一个具有非负初值的整型变量，并且有一个队列与它关联。

在一个信号量S上，只能做规定的两种操作：P操作，记为P（S）；和V操作，记为V（S）。P、V操作的具体定义如下。（1）信号量S上的P操作定义:当一个进程调用P（S）时，应该顺序做下面不可分割的两个动作。Vs

=

Vs

−

1，即把当前信号量S的取值减1。若Vs

>=

0，则调用进程继续运行；若Vs<0，则调用进程由运行状态变为阻塞状态，到与该信号量有关的队列Vq上排队等待，直到其他进程在S上执行V操作将其释放为止。P(S)V(S)ProcedureP(VarS:semaphore)Begin S:=S-1; ifS<0thenW(S)End;{P}ProcedureV(VarS:semaphore)Begin S:=S+1; ifS<=0thenR(S)End;{V}（2）信号量S上的V操作定义:当一个进程调用V（S）时，应该顺序做下面不可分割的两个动作。Vs

=

Vs

+

1，即把当前信号量S的取值加1。若Vs

>

0，则调用进程继续运行；若Vs<=

0，则先从与该信号量有关的队列Vq上摘下一个等待进程，让它从阻塞状态变为就绪状态，到就绪队列里排队，然后调用进程继续运行。6.2.2用P、V操作实现互斥Begin PROCESSPi … s:semaphore; begin coend; s:=1; … end; … P(S);Cobegin {临界区Ci}; … V(S);

… end;例：游乐场自动计数系统。Begin Count:integer; Count:=0;Cobegin

Coend;End;ProcessPIN R1:integer;Begin

R1:=count; R1:=R1+1; count:=R1;End;ProcessPOUT R2:integer;Begin

R2:=count; R2:=R2-1; count:=R2;End;例：游乐场自动计数系统。Begin Count:integer;

S:semaphore; Count:=0;

S:=1;Cobegin

Coend;End;ProcessPIN R1:integer;Begin

P(S);

R1:=count; R1:=R1+1; count:=R1;

V(S);End;ProcessPOUT R2:integer;Begin P(S);

R2:=count; R2:=R2-1; count:=R2; V(S);End;S的范围例：飞机航班售票系统。ProcessPi(i=1,2,3…n) Ri:integer;Begin

按旅客要求找到Aj;

P(S)；

Ri:=Aj; ifRi>=1then else输出“票已售完”End;Begin Ri:=Ri-1; Aj:=Ri;

V(S);

输出一张票End;Begin

S:semaphore;

S:=1;Cobegin

Coend;End;例：飞机航班售票系统。ProcessPi(i=1,2,3…n) Ri:integer;Begin

按旅客要求找到Aj;

P(S)；

Ri:=Aj; ifRi>=1then else输出“票已售完”End;Begin Ri:=Ri-1; Aj:=Ri;

V(S);

输出一张票End;Begin

S:semaphore;

S:=1;Cobegin

Coend;End;例：飞机航班售票系统。ProcessPi(i=1,2,3…n) Ri:integer;Begin

按旅客要求找到Aj;

P(S)；

Ri:=Aj; ifRi>=1then elsebeginV(S);

输出“票已售完”

end;End;Begin Ri:=Ri-1; Aj:=Ri;

V(S);

输出一张票End;Begin

S:semaphore;

S:=1;Cobegin

Coend;End;序调用进程PV操作临界区内被S阻塞S的值112AP(S)A03AV(S)14BP(S)B05CP(S)BC-16DP(S)BCD-27EP(S)BCDE-38BV(S)DCE-29FP(S)DCEF-310DV(S)ECF-211非A-FECF-212EV(S)FC-113FV(S)C014CV(S)1图6-5P、V操作用于进程互斥

设置一个初值为1的信号量S，在进程A和B的进入点处安排关于信号量S的P操作，在进程A和B的退出点处安排关于信号量S的V操作。这样，就能够确保CSa和CSb互斥地执行。

例6-1在第2章的图2-2中，给出了一个“观察者-报告者”的例子。试用信号量上的P、V操作来保证它们正确地配合工作。图6-6“观察者-报告者”问题的P、V操作解法6.2.3用P、V操作实现同步互斥是特殊的同步：空间限制协调同步：时间限制记录和均值图6-7P、V操作用于进程同步

为了保证做到这一点，设置一个初值为0的信号量S，在进程A的X点处（即同步点），安排一个关于信号量S的P操作，在进程B的Y点处安排关于信号量S的V操作。

这样，就能够确保进程A在X点处与进程B取得同步了。

例6-2试用信号量上的P、V操作，来保证如图6-4所示的GET和COPY两者之间协调地工作。图6-8用P、V操作保证GET和COPY间的协作关系6.2.4用P、V操作实现资源分配如果把信号量的初始值，比如n，理解为是系统中某种资源的数目，那么，在它的上面做P操作，即是申请一个资源；在它的上面做V操作，即是释放一个用完的资源。

与该信号量有关的队列，是资源等待队列。

在用P、V操作实现资源分配时，把所设置的信号量初值设为资源的个数n。在进行资源分配的进程中对信号量做P操作。每做一次P操作，就分配一个资源。

在进行资源回收的进程里对信号量做V操作。每做一次V操作，就收回一个资源。

由于资源初启时共有n个，如果对资源进行连续n次申请，都能够立即得到满足。但第n+1个提出申请的进程就不得不在资源等待队列中等待了。

例“生产者-消费者”问题）假定有m个生产者和r个消费者，他们共享n个缓冲区。生产者容器消费者

1:1:11:n:1m:n:r

生产者容器消费者

1:1:11Begin buffer:integer; SP,SG:semaphore; SP:=1;SG:=0;Cobegin

生产者、消费者进程Coend;End;生产者、消费者进程ProcessproducerBegin L1: produceaproduct; P(SP); buffer:=product; V(SG); gotoL1;End;ProcessconsumerBegin L2: P(SG); takeaproduct; V(SP); consume; gotoL1;End;

例6-3（简单的“生产者-消费者”问题）假定有一个生产者和一个消费者，他们共享10个缓冲区。生产者不断地生产物品，将每个物品依次放入缓冲区中（一个缓冲区正好放一个物品）。

消费者依次从缓冲区中取出物品进行消费。只有在缓冲区中有空位时，生产者生产出来的物品才能往里面放；只有在缓冲区有物品时，消费者才能从它的里面取出物品。试用P、V操作来协调生产者和消费者之间的工作。图6-9P、V操作用于“简单生产者-消费者”问题

生产者容器消费者

1:n:1 k tB[0]B[1]…B[t]…B[k]…B[n-1]Begin

B:array[0…(n-1)]ofinteger; k,t:integer;k:=0;t:=0; SP,SG:semaphore; SP:=n;SG:=0;Cobegin

生产者、消费者进程Coend;End;生产者、消费者进程ProcessproducerBegin L1: produceaproduct; P(SP);

B(k):=product; k:=k+1; V(SG); gotoL1;End;ProcessconsumerBegin L2: P(SG);

takeaproductfromB(t); t:=t+1; V(SP); consume; gotoL1;End;生产者、消费者进程ProcessproducerBegin L1: produceaproduct; P(SP);

B(k):=product; k:=(k+1)modn; V(SG); gotoL1;End;ProcessconsumerBegin L2: P(SG);

takeaproductfromB(t); t:=(t+1)modn; V(SP); consume; gotoL1;End;6.2.5互斥/同步的样例分析

例6-4（“生产者-消费者”问题）假定有i个生产者和j个消费者，他们共享k个缓冲区。生产者不断地生产物品，将每个物品依次放入缓冲区中（一个缓冲区正好放一个物品）。

消费者依次从缓冲区中取出物品进行消费。只有在缓冲区中有空位时，生产者生产出来的物品才能往里面放；只有在缓冲区有物品时，消费者才能从它的里面取出物品。试用P、V操作来协调生产者和消费者之间的工作。图6-10P、V操作用于“生产者-消费者”问题

生产者容器消费者

m:n:r k tS1 S2 B[0]B[1]…B[t]…B[k]…B[n-1]Begin

B:array[0…(n-1)ofinteger; k,t:integer;k:=0;t:=0;

S1,S2,SP,SG:semaphore;

S1=1;S2:=1;SP:=n;SG:=0;Cobegin

生产者、消费者进程Coend;End;生产者、消费者进程Processproduceri(i=1,2…m)Begin L1: produceaproduct; P(SP);

P(S1);

B(k):=product; k:=(k+1)modn; V(S1); V(SG); gotoL1;End;Processconsumerj(j=1,2…r)Begin L2: P(SG);

P(S2);

takeaproductfromB(t); t:=:=(t+1)modn;

V(S2); V(SP); consume; gotoL1;End;

互斥、资源分配，只是同步的不同表现形式罢了。互斥是特殊的同步：空间限制协调同步：时间限制

例6-5（“读者-写者”问题）若一批数据被多个并发进程共享使用。其中一些进程只要求读数据，称为“读者”；另一些会对数据进行修改，称为“写者”。

多个读者同时工作时，访问不会有问题。但是读者和写者或写者和写者同时工作时，就可能导致错误的访问结果。

假定在有读者访问时，又来写者要求访问，那么写者只能等待，而后续到来的读者则可以进行访问（这就是隐含读者比写者有更高的访问权）。试用P、V操作来协调读者和写者之间的工作。图6-11P、V操作用于“读者-写者”问题过铁桥、过隧道Begin

E,W,Flag:Semaphore; E=1;W:=1;Flag:=1; CE,CW:integer; CE:=0;CW:=0;Cobegin

过铁桥或过隧道进程Coend;End;过铁桥、过隧道进程ProcessEastBegin L1:P(E); ifCE=0ThenP(Flag); CE:=CE+1; V(E);

过桥或过隧道；

P(E); ifCE=1ThenV(Flag); CE:=CE-1; V(E); gotoL1;End;ProcessWestBegin L2:P(W); ifCW=0ThenP(Flag); CW:=CW+1; V(W);

过桥或过隧道；

P(W); ifCW=1ThenV(Flag); CW:=CW-1; V(W); gotoL2;End;过铁桥、过隧道进程ProcessEastBegin

P(E); ifCE=0ThenP(Flag); CE:=CE+1; V(E);

过桥或过隧道；

P(E); ifCE=1ThenV(Flag); CE:=CE-1; V(E);End;ProcessWestBegin

P(W); ifCW=0ThenP(Flag); CW:=CW+1; V(W);

过桥或过隧道；

P(W); ifCW=1ThenV(Flag); CW:=CW-1; V(W); End;过铁桥、过隧道进程ProcessEastBegin

P(E); CE:=CE+1;

ifCE=1ThenP(Flag); V(E);

过桥或过隧道；

P(E); CE:=CE-1; ifCE=0ThenV(Flag); V(E);End;ProcessWestBegin

P(W); ifCW=0ThenP(Flag); CW:=CW+1; V(W);

过桥或过隧道；

P(W); ifCW=1ThenV(Flag); CW:=CW-1; V(W); End;图6-12不正确的解法图6-13又一个不正确的解法补充：水果问题看似2:1:2

父 儿母 女盘子Begin S,SP,SO:semaphore; S:=1;SP:=0;SO:=0;Cobegin

生产者父母、消费者儿女进程Coend;End;ProcessfatherBegin L1: haveanapple; P(S); putanappleintoplate; V(SP); gotoL1;End;ProcessmotherBegin L2: haveanorange; P(S); putanorangeintoplate; V(SO); gotoL2;End;ProcesssonBegin L3:P(SO); getanorangefromplate; V(S); eatanorange; gotoL3;End;ProcessdaughtBegin L4: P(SP); getanapple; V(S); eattheapplefromplate; gotoL4;End;作业：分奇偶数

W1R W2

缓冲区B输入设备输出设备输出设备Begin B:integer; S,SE,SO:semaphore; S:=1;SE:=0;SO:=0;Cobegin

一输入二输出进程Coend;End;ProcessR x:integer;Begin L1: 读数；

X:=所读的数；

P(S)；

B:=x;

ifB=奇数thenV(SO);

elseV(SE); gotoL1;End;ProcessW1 y:integer;Begin L2: P(SO)；

y:=B;

V(S);

输出y; gotoL2;End;ProcessW2 z:integer;Begin L3: P(SE)；

z:=B;

V(S);

输出z; gotoL3;End;司机与票员的同步进程ProcessBus-DriverBegin L1:P(Run);

启动车辆;

正常行驶;

到站停车；

V(Open); gotoL1;End;ProcessCondctorBegin L2:售票；

P(Open);

开启车门;

服务乘客上车;

关闭车门；

V(Run); gotoL2;End;请用PV操作来实现司机与票员的同步Begin

Open,Run:Semaphore; Open=0;Run:=1;Cobegin

司机、售票员进程Coend;End;司机与票员的同步进程ProcessBus-DriverBegin L1:P(Run);

启动车辆;

正常行驶;

到站停车；

V(Open); gotoL1;End;ProcessCondctorBegin L2:售票；

P(Open);

开启车门;

服务乘客上车;

关闭车门；

V(Run); gotoL2;End;6.3死锁、高级进程通信

6.3.1死锁与产生死锁的必要条件常用方框代表资源，圆圈代表进程，如果画一条由资源到进程的有向边，则表示把该资源分配给了这个进程。

如果画一条由进程到资源的有向边，则表示该进程申请这个资源，这样的图就是所谓的“资源分配图”。图6-14资源分配图

例6-6现在有进程A对资源的需求序列是申请R，申请S，释放R，释放S；进程B对资源的需求序列是申请S，申请T，释放S，释放T；进程C对资源的需求序列是申请T，申请R，释放T，释放R。

请对序列：（1）“A申请R、B申请S、C申请T、A申请S、B申请T、C申请R”；（2）“A申请R、C申请T、A申请S、C申请R、A释放R、A释放S”分别画出对应的资源分配图，说明谁能够运行，谁无法运行。图6-15第1个序列的资源分配图图6-16第2个序列的资源分配图

所谓“死锁”，即指系统中若存在一组（至少两个或以上）进程，它们中的每一个都占用了某种资源而又都在等待其中另一个所占用的资源，这种等待永远不会结束，这就是“死锁”，或说这一组进程处于“死锁”状态。

一个系统出现死锁，会存在四个必要条件：（1）互斥条件（2）部分分配（占用并等待）条件（3）非剥夺条件（4）循环等待条件死机不一定死锁出现环路也不一定死锁

R1R2P1P4P3P2

解决系统中的死锁问题，有下面几种对策：（1）忽略死锁（2）预防死锁（3）避免死锁（4）检测死锁并恢复（解除）6.3.2死锁的预防所谓“死锁的预防”，是指破坏产生死锁四个必要条件中的一条或几条，以使系统不会产生死锁。（1）破坏“互斥条件”。（2）破坏“部分分配（占用并等待）条件”。（3）破坏“非剥夺条件”。（4）破坏“循环等待条件”。图6-17用顺序编号破坏“循环等待条件”哲学家吃面Begin S1,S2,S3,S4,S5:semaphore; S1:=1;S2:=1;S3:=1;S4:=1;S5:=1;Cobegin

进程Coend;End;f1f4f5f3f2人1人3人2人4人5ProcessP1Begin L1: 思考; P(S1);

取F1; P(S2);

取F2;

吃面； 放下F1和F2; V(S2); V(S1); gotoL1;End;ProcessP2Begin L2: 思考; P(S2);

取F2; P(S3);

取F3;

吃面； 放下F2和F3; V(S3); V(S2); gotoL2;End;ProcessP3Begin L3: 思考; P(S3);

取F3; P(S4);

取F4;

吃面； 放下F3和F4; V(S4); V(S3); gotoL3;End;ProcessP4Begin L4: 思考; P(S4);

取F4; P(S5);

取F5;

吃面； 放下F4和F5; V(S5); V(S4); gotoL4;End;ProcessP5Begin L5: 思考; P(S5);

取F5; P(S1);

取F1;

吃面； 放下F1和F5; V(S1); V(S5); gotoL5;End;ProcessP5Begin L5: 思考; P(S1);

取F1; P(S5);

取F5;

吃面； 放下F1和F5; V(S5); V(S1); gotoL5;End;按序分配6.3.3死锁的避免死锁的防止是在运行前采取的措施，相当于小孩打防疫针，不会死锁。但这些措施会大大影响系统的速度。死锁的避免就是如果能够找到一个执行次序，那么也不会死锁。死锁的避免是指虽然系统中存在有产生死锁的条件，但小心对待进程提出的每一个资源请求。

在接到一个资源请求时，不是立即进行分配，而是根据当时资源的使用情况，按照一定的算法去模拟分配，探测出模拟分配的结果。共12个资源，剩余3个

只有在探测结果表明绝对不会出现死锁时，才真正接受这次资源请求。进程最大需求数已占资源尚缺资源P1P2P39104252752共12个资源，剩余2个进程最大需求数已占资源尚缺资源P1P2P391042+1=352652

如果能在有限的时间内，保证所有进程得到自己需要的全部资源，那么称系统处于“安全状态”；否则称系统处于“不安全状态”。安全状态不安全状态死锁银行家算法的基本思想当一个用户对资金的最大需求量不超过银行家现有的资金时就接纳该用户。用户可以分期贷款，但贷款总数不能超过最大需求量。当银行家现有资金不够时可推迟支付，但时间有限。当用户得到全部贷款后，必须按时归还所有贷款。图6-18银行家算法的基本思想银行家算法之例

假定系统中有五个进程｛P0,P1,P2,P3,P4｝和三类资源｛A,B,C｝，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图3-15所示。图3-15T0时刻的资源分配表(1)T0时刻的安全性：图3-16T0时刻的安全序列Max最大ABC1057Allacation已分ABCNeed尚需ABCWork工作区ABC332Sort执行次序Finish完成p075401074410575Tp13222001221221Tp290230260010474Tp32222110117432Tp44330024317453TT0时刻存在安全序列{p1,p3,p4,p2,p0}，因此不会死锁Max最大ABC1057Allacation已分ABC221Need尚需ABCWork工作区ABC111Sort执行次序Finish完成p0754010231744523Fp13222001225222Tp2902302600Fp32222110113221Tp4433002431FT1时刻找不到安全序列，在不安全状态，系统不分配图6-19一个导致安全状态的请求图6-20一个导致不安全状态的请求

银行家算法可以推广用于处理多种资源。此时，系统要为算法设置两张表，一张记录已分配给各进程的资源数，一张记录各进程还需要的资源数。

另外还要有3个向量：向量E记录各种资源的总数，向量P记录各种资源已分配数，向量A记录各种资源的剩余数。图6-21多种资源的银行家算法

多种资源银行家算法的执行步骤如下：（1）假定接受一个进程提出的资源请求，修改向量P和A。（2）检查还需资源表中是否有一个进程的行向量小于或等于向量A。如果没有，那么系统就可能会死锁，因为现在任何进程都无法完成了。（3）如果存在这种进程，那么假定它已获得需要的所有资源，并完成工作，把它的“能执行完”标志