chap5并发进程及死锁问题.ppt

3.3 死锁 一、死锁的概念 死锁：指多个进程在运行的时候因为竞争资源而陷入的一种僵局，陷入这种僵局的进程，若无外力的作用将无法再向前推进。 产生死锁的原因： 1、进程对资源的竞争 当若干进程需求资源的总数大于系统能提供的资源数时，进程间就会出现竞争资源的现象，若管理不当就可能引起死锁。 2、资源分配策略 如果按某种资源分配策略分配资源时使得某些进程各自占用了部分资源后又都在等待其他进程所占的资源，且互不相让，则出会引起死锁。 3、并发进程执行速度 并发进程执行的速度不能由进程自己来控制，如果协调不好的话也会出现循环等待资源的情况。 例：系统有打印机、读卡机各一台，被进程P、Q共享。两个进程并发执行，按以下顺序请求和释放资源： 进程P A1：请求读卡机 A2：请求打印机 A3：释放读卡机 A4：释放打印机 产生死锁的必要条件 ? 从以上分析可见，如果在计算机系统中同时具备下面四个必要条件时，那麽会发生死锁。换句话说，只要下面四个条件有一个不具备，系统就不会出现死锁。 ??? 〈1〉互斥条件。即某个资源在一段时间内只能由一个进程占有，不能同时被两个或两个以上的进程占有。这种独占资源如CD-ROM驱动器，打印机等等，必须在占有该资源的进程主动释放它之后，其它进程才能占有该资源。这是由资源本身的属性所决定的。如独木桥就是一种独占资源，两方的人不能同时过桥。 ??? 〈2〉不可抢占条件。进程所获得的资源在未使用完毕之前，资源申请者不能强行地从资源占有者手中夺取资源，而只能由该资源的占有者进程自行释放。如过独木桥的人不能强迫对方后退，也不能非法地将对方推下桥，必须是桥上的人自己过桥后空出桥面（即主动释放占有资源），对方的人才能过桥。 ??? 〈3〉占有且申请条件。进程至少已经占有一个资源，但又申请新的资源；由于该资源已被另外进程占有，此时该进程阻塞；但是，它在等待新资源之时，仍继续占用已占有的资源。还以过独木桥为例，甲乙两人在桥上相遇。甲走过一段桥面（即占有了一些资源），还需要走其余的桥面（申请新的资源），但那部分桥面被乙占有（乙走过一段桥面）。甲过不去，前进不能，又不后退；乙也处于同样的状况。 ??? 〈4〉循环等待条件。存在一个进程等待序列{P1，P2，...，Pn}，其中P1等待P2所占有的某一资源，P2等待P3所占有的某一源，......，而Pn等待P1所占有的的某一资源，形成一个进程循环等待环。就像前面的过独木桥问题，甲等待乙占有的桥面，而乙又等待甲占有的桥面，从而彼此循环等待。 ? 上面我们提到的这四个条件在死锁时会同时发生。也就是说，只要有一个必要条件不满足，则死锁就可以排除。 解决死锁的对策 1、设计无死锁的系统 两种途径：预防死锁、避免死锁 2、允许系统出现死锁然后设法排除它 加死锁检测手段---一旦发现死锁能够进行排除的死锁解除手段 二、死锁的预防 1、静态分配资源策略 每个进程在开始执行前就申请它所需要的全部资源，仅当系统能满足进程的资源申请要求且把资源分配给进程后，该进程才能开始执行。（打破了（3）占有并申请） 特点：简单安全，资源利用率低 2、按序分配资源策略 把系统中所有资源排一个顺序，对第一个资源给一个确定的编号，规定任何一个进程申请两个以上资源时总是先申请编号小的资源，后申请编号大的资源。（打中〈4〉循环等待条件） 特点：可以提高资源利用率，但资源的使用与实际使用顺序不一致，给用户编制程序带来麻烦。 3、抢夺式分配资源策略 仅当一个进程已经占有了某些资源又要申请新资源，而系统这时又不能满足其他资源的要求（已被其他进程占用）必须等待时，系统才可以抢夺该进程已占有的资源。（适用于CPU、内存，不能完全防止死锁） 三、死锁的避免 1、系统的安全与不安全状态 系统能按某种进程顺序(P1, P2, …，Pn)(称〈P1, P2, …, Pn〉序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。 ★只要系统处于安全状态，系统就不会发生死锁 ★在系统处于不安全状态下未必一定发生死锁，但是安全状态下的系统是一定不会发生死锁的。 我们通过一个例子来说明安全性。假定系统中有三个进程P1、 P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示： 由安全状态向不安全状态的转换 如果不按照安全序列分配资源，则系统可