3.5产生死锁的原因和必要条件.ppt

习题 P115 第18、21、22 题 三、由安全状态向不安全状态的转换 当系统不按照安全序列分配资源时，则系统可能由安全状态进入不安全状态。 2 9 P3 2 4 P2 3 5 10 P1 可用 已分配 最大需求 进程 3 9 P3 2 4 P2 2 5 10 P1 可用 已分配 最大需求 进程 T0时刻安全状态 T1时刻不安全状态 3.6.3 利用银行家算法避免死锁 最具有代表性的避免死锁的算法，是Dijkstra的银行家算法。这是由于该算法可能用于银行现金贷款而得名的。一个银行家把他的固定资金贷给若干顾客。只要不出现一个顾客借走所有资金后还不够，银行家的资金应是安全的。银行家需一个算法保证借出去的资金在有限时间内可收回。 一、银行家算法中的数据结构 1．可利用资源向量Available 也称为空闲向量。这是一个含有m个元素的数组。其中的每一个元素，代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目。其数值随该类资源的分配和回收而动态地改变。 如果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个，才能完成其任务。 显然，以上三个矩阵之间存在如下关系： Need[i,j] = Max[i,j] - Allocation[i,j] 二、银行家算法 设Requesti是进程Pi的请求向量，如果Requesti[j]=K，表示进程Pi需要Rj类型的资源的个数为K。这里要提及的是，Requesti与Needi的关系可能为以下三种情况： （1）RequestiNeed[i]：表示该进程的资源需求已超过它所宣布的最大值，因此认为出错。 （2）Requesti=Need[i]：表示该进程现在对它所还需的全部资源一次申请完成。 （3）RequestiNeed[i]：表示该进程现在对它所需资源再进行部分的申请，剩余的资源以后可再次申请。 当进程Pi发出资源请求后，系统按下述步骤进行检查： （1）如果Requesti≤Need[i]，转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所事先要求的最大值。 （2）如果Requesti≤Available，转向步骤3；否则，表示尚无足够资源，Pi须等待。 （3）假设系统将资源分配给Pi，则需修改如下数据结构的值： Available:= Available -Requesti; Allocation[i]:=Allocation[i]+Requesti; Need[i]:=Need[i]-Requesti; （4）系统执行安全性算法，检查若此次资源分配后，系统是否处于安全状态。如果是安全的，则将资源真正地分配给进程Pi，否则，将本进程的试探分配作废，恢复原来的资源分配状态，进程Pi等待。 三、安全性算法 系统所执行的安全性算法可描述如下： （1）设置两个向量： 工作向量Work。 它表示在算法执行过程中，系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，初始置Work:=Available。 完成向量Finish。 它表示系统能否运行完成。它有n个分量，分别表示系统是否有足够的资源分配给进程，使之运行完毕。 开始时，Finish[i]:=false；当有足够资源分配给进程时，令Finish[i]:=true。 （2）从进程集合中找到一个能满足下述条件的进程i： Finish[i]=false; Needi≤Work； 若找到这样的进程，执行步骤（3）； 若找不到这样的进程，则转步骤（4）。 （3）当进程Pi获得资源后，可顺序执行，直至完成，并释放出分配给它的资源，即执行： Work:= Work+Allocation[i]； Finish[i]:= true； Go to 步骤（2）； （4）若所有进程的Finish[i]=true，则表示系统处于安全状态，正式将资源分配给进程Pi；否则，系统处于不安全状态，系统不能进行这次