死锁与银行家算法介绍.ppt

《死锁与银行家算法介绍.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、死锁、银行家算法1.死锁概念指多个进程因竞争共享资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。即：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。思考：如果系统中有n个进程，则在等待队列中进程的个数最多为（）个有n个进程的系统出现死锁时，死锁进程的个数k应满足的条件是（）产生死锁的原因1.竞争资源（资源不足）2.进程的推进顺序不当1.竞争系统资源若系统中只有一台打印机R1和一台读卡机R2，可供进程P1和P2共享。若形成环路，这样会产生死锁。由于进程的调度是独立的，请求和释放操作可按如下

2、序列进行：Ar1,Ar2,Ar3,Ar4,Br1,Br2,Br3,Br4Br1,Br2,Br3,Br4,Ar1,Ar2,Ar3,Ar4Ar1,Ar2.Br1,Ar3,Ar4,Br2,Br3,Br4Ar1,Br1,Ar2,Br2,Ar3,Ar4,Br3,Br4对序列①②③三个进程都能顺利进行，④则会产生死锁。进程A、B对资源的请求和释放2.进程推进顺序不当引起死锁思考：某系统中有3个并发进程都需要4个同类资源，该系统不会发生死锁的最少资源是（）个P341例82.死锁避免死锁避免定义:在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系

3、统可能发生死锁，则不予分配，否则予以分配。由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的避免死锁算法是银行家算法。3.安全状态与不安全状态安全状态指系统能按某种进程顺序{P1，…，Pn}来为每个进程Pi(1≤i≤n）分配其所需资源，直至最大需求，使每个进程都可顺序完成。若系统不存在这样一个序列，则称系统处于不安全状态。如果存在，则称序列为安全序列。说明并非所有的不安全状态都必然会转为死锁状态，但当系统进入不安全状态后，便有可能进入

4、死锁。安全状态一定是没有死锁发生的。避免死锁的实质：系统进行资源分配时，如何使系统不进入不安全状态。2)安全状态之例假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：进程最大需求已分配可用P1P2P310495223问：T0时刻是否安全？3)由安全状态向不安全状态的转换如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便

5、进入不安全状态。因为，此时也无法再找到一个安全序列，例如，把其余的2台分配给P2，这样，在P2完成后只能释放出4台，既不能满足P1尚需5台的要求，也不能满足P3尚需6台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结果导致死锁。P3的请求应拒绝。安全状态与不安全状态不安全状态:不存在一个安全序列，不安全状态不一定导致死锁4.利用银行家算法避免死锁1)银行家算法中的数据结构(1)可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。

6、如果Available［j］=K，则表示系统中现有Rj类资源K个。(2)最大需求矩阵Max。这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max［i,j］=K，则表示进程i需要Rj类资源的最大数目为K。(3)分配矩阵Allocation。这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation［i,j］=K，则表示进程i当前已分得Rj类资源的数目为K。(4)需求矩阵Need。这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need［i,j］=K，则表示进程i还需要Rj类资源K个，方能完成其任

7、务。Need［i,j］=Max［i,j］-Allocation［i,j］2)银行家算法设Requesti是进程Pi的请求向量，如果Requesti［j］=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：(1)如果Requesti［j］≤Need［i,j］，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。(2)如果Requesti［j］