2.8 死锁

2.8.5 死锁避免

　　死锁避免是将限制条件弱化，即允许死锁的存在，但不让它发生，设置一种安全状态，进程按照某种顺序来为其分配资源。
　　1．安全与不安全状态
　　某一时刻，系统能按某种顺序，如P1，P2，…，Pn来为每个进程分配其所需资源，直到最大需求，使每个进程都能顺利地完成，则称此时系统处于安全状态。反之，称之为不安全状态。在系统资源分配状态如表2-5所示时，系统处于安全状态。因此此时存在一个安全序列<P2，P1，P3>，其余的序列都是不安全的。

表2-5 安全状态下的系统资源分配状态

　　所以说，引入安全状态的目的在于在进行资源分配时，要使系统不发生死锁，只有保证当前的系统状态是安全的，即每次资源分配之后系统都处于安全状态。下面介绍一种算法，通过它就能知道当前系统状态是否安全，它就是著名的银行家算法。
　　2．银行家算法
　　银行家算法问题描述是：一个银行家把他的固定资金借给若干顾客，使这些顾客能满足对资金的要求又能完成其交易，也使银行家可以收回全部的现金。只要不出现一个顾客借走所有资金后还不够，银行家的资金就是安全的，银行家还需要一个算法保证借出去的资金在有限时间内可收回。假定顾客分成若干次进行，并在第一次借款时，能说明他的最大借款额。
　　为实现银行家算法，系统中必须设置如下的数据结构。
　　可利用资源向量Available：这是一个含有m个元素的数组，其中的每个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用的资源数目。其数值随该类资源的分配和回收动态地改变。如果Availavle[j]=k，表示系统中现有Rj类资源k个。
　　最大需求矩阵Max：它是一个n×m的矩阵，它定义了系统中n个进程中的每个进程对m类资源的最大需求。如果Max(i, j)=k，表示进程i需要Rj类资源的最大数目为k。
　　分配矩阵Allocation：它是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每个进程的资源数。如果Allocation(i, j)=k，表示进程i当前已分得Rj类资源的数目为k。
　　需求矩阵Need：它是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数，如果Need[i,j]=k，表示进程i还需要Rj类资源k个，方能完成其任务。
　　上述三个矩阵存在下述关系：

Need(i, j)=Max(i, j)-Allocation(i, j)

　　具体算法描述如下：
　　设Requesti是进程Pi的请求向量。如果Request[j]=k，表示进程Pi需要k个Rj类型的资源。当 发出资源请求后，系统按照下述步骤进行检查。
　　（1）如果  ，则转向步骤（2），否则认为出错，因为它所需要的资源数已经超过它所宣布的最大值。
　　（2）如果RequestiAvailable，则转向步骤（3）；否则表示尚无足够资源，Pi必须等待。
　　（3）系统试图把要求的资源分配给进程Pi，并修改下面数据结构中的数值：
　　Available：= Available-Requesti；
　　Allocationi= Allocationi+ Requesti；
　　Needi= Needi-Requesti；
　　（4）Requesti系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。
　　系统所执行的安全性算法描述如下。
　　①设置两个变量Work和Finish：Work表示系统可提供给进程继续运行的各类资源数目。它含有m个元素，开始执行安全性算法时，Work=Available。Finish表示系统是否有足够的资源分配给进程，使之运行完成。开始时，Finishi=false。当有足够资源分配给进程Pi时，令Finishi=true。
　　② 从进程集合中找到一个能满足下述条件的进程。
　　
　　如找到则执行步骤③，否则执行步骤④。
　　③当进程 获得资源后，顺利执行，直至完成，并释放出分配给它的资源，故应执行：
　　
　　④若所有进程 都为true，则表示系统处于安全状态，否则系统处于不安全状态。
　　银行家算法特点：
　　（1）进程间允许互斥、部分分配和不可抢占地使用资源，可提高资源利用率；
　　（2）要求事先说明进程的最大资源要求，在现实中较难实现。