chap5并发进程与死锁问题

chap5并发进程与死锁问题第一页，共25页。例：系统有打印机、读卡机各一台，被进程P、Q共享。两个进程并发执行，按以下顺序请求和释放资源：进程P A1：请求读卡机A2：请求打印机A3：释放读卡机A4：释放打印机进程Q B1：请求打印机B2：请求读卡机B3：释放读卡机B4：释放打印机A1、A2、A3、A4、B1、B2、B3、B4B1、B2、B3、B4、A1、A2、A3、A4A1、A2、B1、B2、A3、A4、B3、B4A1、B1、A2、B2、A3、B3、A4、B4分析上面四种执行顺序哪个可能会产生死锁第二页，共25页。产生死锁的必要条件

从以上分析可见，如果在计算机系统中同时具备下面四个必要条件时，那麽会发生死锁。换句话说，只要下面四个条件有一个不具备，系统就不会出现死锁。

〈1〉互斥条件。即某个资源在一段时间内只能由一个进程占有，不能同时被两个或两个以上的进程占有。这种独占资源如CD-ROM驱动器，打印机等等，必须在占有该资源的进程主动释放它之后，其它进程才能占有该资源。这是由资源本身的属性所决定的。如独木桥就是一种独占资源，两方的人不能同时过桥。

〈2〉不可抢占条件。进程所获得的资源在未使用完毕之前，资源申请者不能强行地从资源占有者手中夺取资源，而只能由该资源的占有者进程自行释放。如过独木桥的人不能强迫对方后退，也不能非法地将对方推下桥，必须是桥上的人自己过桥后空出桥面（即主动释放占有资源），对方的人才能过桥。

〈3〉占有且申请条件。进程至少已经占有一个资源，但又申请新的资源；由于该资源已被另外进程占有，此时该进程阻塞；但是，它在等待新资源之时，仍继续占用已占有的资源。还以过独木桥为例，甲乙两人在桥上相遇。甲走过一段桥面（即占有了一些资源），还需要走其余的桥面（申请新的资源），但那部分桥面被乙占有（乙走过一段桥面）。甲过不去，前进不能，又不后退；乙也处于同样的状况。

〈4〉循环等待条件。存在一个进程等待序列{P1，P2，...，Pn}，其中P1等待P2所占有的某一资源，P2等待P3所占有的某一源，......，而Pn等待P1所占有的的某一资源，形成一个进程循环等待环。就像前面的过独木桥问题，甲等待乙占有的桥面，而乙又等待甲占有的桥面，从而彼此循环等待。

上面我们提到的这四个条件在死锁时会同时发生。也就是说，只要有一个必要条件不满足，则死锁就可以排除。第三页，共25页。解决死锁的对策1、设计无死锁的系统两种途径：预防死锁、避免死锁2、允许系统出现死锁然后设法排除它加死锁检测手段---一旦发现死锁能够进行排除的死锁解除手段二、死锁的预防1、静态分配资源策略每个进程在开始执行前就申请它所需要的全部资源，仅当系统能满足进程的资源申请要求且把资源分配给进程后，该进程才能开始执行。（打破了（3）占有并申请）特点：简单安全，资源利用率低2、按序分配资源策略把系统中所有资源排一个顺序，对第一个资源给一个确定的编号，规定任何一个进程申请两个以上资源时总是先申请编号小的资源，后申请编号大的资源。（打中〈4〉循环等待条件）

特点：可以提高资源利用率，但资源的使用与实际使用顺序不一致，给用户编制程序带来麻烦。3、抢夺式分配资源策略仅当一个进程已经占有了某些资源又要申请新资源，而系统这时又不能满足其他资源的要求（已被其他进程占用）必须等待时，系统才可以抢夺该进程已占有的资源。（适用于CPU、内存，不能完全防止死锁）第四页，共25页。三、死锁的避免1、系统的安全与不安全状态系统能按某种进程顺序(P1,P2,…，Pn)(称〈P1,P2,…,Pn〉序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。★只要系统处于安全状态，系统就不会发生死锁★在系统处于不安全状态下未必一定发生死锁，但是安全状态下的系统是一定不会发生死锁的。第五页，共25页。我们通过一个例子来说明安全性。假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：进程最大需求已分配可用P1P2P310495223第六页，共25页。由安全状态向不安全状态的转换如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。因为，此时也无法再找到一个安全序列，例如，把其余的2台分配给P2，这样，在P2完成后只能释放出4台，既不能满足P1尚需5台的要求，也不能满足P3尚需6台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结果导致死锁。第七页，共25页。现有同类资源12个供3个进程共享，假定进程所需资源和已占资源的情况如下表所示。3个进程在执行中又都提出申请一个资源的要求，回答：a.如果先满足进程A的要求，系统将会出现什么现象？解释之。

b.你认为应按怎样的次序分配资源才合适？为什么？第八页，共25页。答：a.在当前状态下，尚余2个资源可供分配，如果先满足进程A的要求，把其中1个资源分配给A进程，此时A、B、C进程仍未拥有足够资源完成任务。系统进入不安全状态，随着进程的继续执行，剩余的1个资源无论分给哪个进程，均导至所有进程进入等告待而出现死锁。b.根据目前的资源占用情况，应该先满足B的要求，把剩下的2个资源分配给他，这样，B进程可执行完毕归还系统6个资源。这6个资源可以满足A和C进程的资源需求，从而使系统处于安全状态。

第九页，共25页。2、利用银行家算法避免死锁算法：把操作系统比作银行家，操作系统管理的各种资源比作银行的周转资金，申请资源的进程比作银行借款的主顾。银行家占有有限的资金，他不可能满足所有借款人的请求，但可以满足一部分人的借款请求，等这些人归还后，又可把这笔资金借给其他人，其原则是不能使银行家的钱被借完，使资金无法周转。特点：可避免死锁，比静态资源分配法资源利用率高但资源分配保守，每次分配前均要花较长时间计算时间，系统开销较大，而且必须知道每个进程对资源的最大需求量。第十页，共25页。3、区分死锁的避免与死锁的防止预防：是在运行之前，预先防止死锁的产生（主要通过破坏产生死锁的四个必要条件中任何一个来实现的）避免：是系统运行过程中注意避免死锁的发生（要求系统每当在进程申请资源时，都应根据一定的算法判断，仅当系统处于安全状态时才把资源分配给进程，使系统一直处于安全状态之中）第十一页，共25页。四、死锁的检测和解除死锁的检测：系统定时运行一个检查程序，来检测系统中是否存在死锁，当检测到死锁时再设法解除死锁。1.资源分配图凡属于E中的一个边e∈E，都连接着P中的一个结点和R中的一个结点，e={pi,rj}是资源请求边，由进程pi指向资源rj，它表示进程pi请求一个单位的rj资源。e={rj,pi}是资源分配边，由资源rj指向进程pi,它表示把一个单位的资源rj分配给进程pi。第十二页，共25页。2、利用资源图可以检测系统中是否存在死锁进程，判定死锁的法则如下：1）如果进程资源图中无环路，则此时系统内不存在死锁。2）如果进程资源图中有环路，且处于环路内的每类资源均只有一个，则此时系统内存在死锁；处于环路内的进程就是卷入死锁的进程。3）如果进程资源图中有环路，但处于环路内的每类资源个数不全为一个，则此时系统内是否存在死锁，还要化简进程资源图才能判定。3、进程资源的化简过程1）找出一个既不阻塞又非孤立的进程节点Pi(条件P137）2）进程Pi所占有的资源全部释放时，可唤醒等待此资源而进入阻塞的进程Pj，使原来处于阻塞的进程可能变成非阻塞进程。3）若进程资源状态图通过上述简化步骤后，都成为孤立点，则该图是可完全化简的，并且该进程资源图所代表的系统状态是安全的。第十三页，共25页。4、死锁定理对于较复杂的资源状态图可能存在着多个非阻塞点，若我们从不同的点开始化简是否可以得到同一个化简图呢？经证明：一个给定的进程资源图的所有化简顺序将导致同一个不可化简图。所以我们进一步可得到如下的死锁定理：若S是死锁状态的话，当且仅当S的进程资源图是不可完全化简的。如果得到一个可完全化简的进程资源状态图，我们就称该状态为安全态，反之为死锁状态。第十四页，共25页。第十五页，共25页。3、死锁的解除当死锁检测程序检测到有死锁存在时，一般采用两种方式来解除死锁。1）删除法：即终止一个或几个涉及死锁的进程的执行，收回它们所占的资源进程再分配，以破坏循环等2）剥夺法：即从涉及死锁的一个或几个进程中抢夺资源，把夺来的资源再分配给卷入死锁的其他进程，直至死锁解除第十六页，共25页。11.某系统中有10台打印机，有三个进程P1，P2，P3分别需要8台，7台和4台。若P1，P2，P3已申请到4台，2台和2台。试问：按银行家算法能安全分配吗？请说明分配过程。系统能为进程P3分配二台打印机。因为尽管此时10台打印机已分配给进程P14台，P22台和P34台，全部分配完，但P3已分配到所需要的全部4台打印机，它不会对打印机再提出申请，所以它能顺利运行下去，能释放占用的4台打印机，使进程P1，P2均可能获得乘余的要求4台和5台，按银行家算法是安全的。第十七页，共25页。4-2用PV操作解决读者写者问题的正确程序如下：beginS，Sr：Semaphore；rc：integer；S：=1；Sr：=1；rc：=0；cobeginPROCESSReaderi（i=1，2…）beginP（Sr）rc：=rc+1；ifrc=1thenP（S）；V（Sr）；readfile；P（Sr）；rc：=rc-1ifrc=0thenV（S）；V（Sr）；end；PROCESSWriterj（j=1，2…）beginP（S）；Writefile；V（S）end；coend；end；请回答：（1）信号量Sr的作用；（2）程序中什么语句用于读写互斥，写写互斥；（3）若规定仅允许5个进程同时读怎样修改程序？第十八页，共25页。（1）Sr用于读者计数rc的互斥信号量；（2）ifrc=1thenP（S）中的P（S）用于读写互斥，写者进程中的P（S）用于写写互斥，读写互斥。（3）程序中增加一个信号量S5，初值为5，P（S5）语句加在读者进程P（Sr）之前，V（S5）语句加在读者进程第2个V（Sr）之后第十九页，共25页。一台计算机有8台磁带机，它们由N个进程竞争使用，每个进程可能需要3台磁带机。请问N为多少时，系统没有死锁危险，并说明原因。当N取不大于3的正整数时，系统没有死锁的危险。因为当N=1或2时，最多需要6台磁带机，系统不会发生死锁。当N=3时，最坏情况是3个进程都需要3个磁带机，且每个进程都已拥有2个磁带机，但此时系统还有2台未分配的磁带，能满足其中两个进程的资源请求，使进程顺利推进后再释放资源，此时另外1个进程因为得到被释放的磁带机而能够获得足够的磁带机，也可以顺利执行，不会发生死锁。第二十页，共25页。14、某系统有A，B，C，D这4类资源供5个进程共享，进程对资源的需求和分配情况如下表所示。现在系统还剩资源A类1个，B类5个，C类2个和D类0个，请按银行家算法回答下面问题：

进程

已占资源数

最大需求数

A

B

C

D

A

B

C

D

P1

0

0

1

2

0

0

1

2

P2

1

0

0

0

1

7

5

0

P3

1

3

5

4

2

3

5

6

P4

0

6

3

2

0

6

5

2

P5

0

0

1

4

0

6

5

6

a.现在系统是否处于安全状态？

b.如果现在进程P2提出需要（0，4，2，0）个资源的要求，系统能否满足它的请求？

按照银行家算法，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请分配资源，否则就推迟分配。

当进程在执行继续申请资源时，先测试进程已占有的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源数，若能满足则按当前的申请量分配资源，否则也要推迟分配。第二十一页，共25页。答：a.在这里，进程P1已经拥有足够资源，在执行后可归还C和D资源，，同时，进程P3可以得到足够的资源完成执行，其后，P2，P4、P5可以依次得到足够的资源来完成，因此，用银行家算法分配资源时，系统处于安全状态。

b.系统不会满足进程P2的资源要求。根据银行家算法，P2进程首次申请B类资源4个，不大于其所需的最大资源数（7个)，也