秒懂算法 | 银行家算法
最具有代表性的避免死锁的算法是Dijkstra的银行家算法，由于该算法可能用于银行现金贷款而得名。一个银行家把他的固定资金贷给若干顾客，只要不出现一个顾客借走所有资金后还不够，银行家的资金应是安全的。银行家需要一个算法保证借出去的资金在有限时间内可以收回。
假定顾客分成若干次进行贷款，并在第一次贷款时说明他的最大借款额。具体算法如下：
（1） 顾客的贷款操作依次顺序进行，直到全部操作完成。
（2） 银行家对当前顾客的贷款操作进行判断，以确定其安全性，看能否支持顾客贷款，即该客户能否运行完成。
（3） 安全时，贷款；否则，暂不贷款。
01、银行家算法中的数据结构
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个才能完成任务。
显然，前三个矩阵之间存在如下关系：
02、银行家算法的实现
1. 进程申请资源的情况
设 Requesti 是进程 Pi 的请求向量，如果Requesti ［j］=K，表示进程Pi 需要Rj 类资源的个数为K。Requesti 与Need［i］的关系可能为以下三种情况。
（1） Requesti>Need［i］。这种情况表示该进程的资源需求已超过系统所宣布的最大值，因此认为出错。
（2） Requesti=Need［i］。这种情况表示该进程现在对它所需的全部资源一次申请完成。
（3） Requesti<need［i］。这种情况表示该进程现在对它所需资源再进行部分的申请，剩余的资源以后可再次申请。
2. 银行家算法的描述
当进程Pi 发出资源请求后，系统按下述步骤进行检查。
（1） 如果Requesti ≤Need［i］，便转向步骤（2）；否则显示出错，因为它所需的资源数已超过它事先要求的最大值。
（2） 如果Requesti ≤Available，便转向步骤（3）；否则，表示尚无足够资源，Pi 须等待。
（3） 假设系统将资源分配给Pi ，则需修改如下数据结构的值：
3. 安全性算法
工作向量Work表示在算法执行过程中，系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，初始值Work∶=Available。
完成向量Finish表示系统能否运行完成。它有n个分量，分别表示各进程是否可执行完成。若Finish［i］∶=true，表示第i个进程能够获得足够的资源，运行完成；若Finish［i］∶=false，表示该进程不能获得所需全部资源，不能运行完成。
设初值Finish［i］∶=false，i=0,1,2,…,n-1。当有足够资源分配给第i个进程时，再令Finish［i］∶=true。
安全算法的步骤如下。
（1） 设置两个工作向量。设置工作向量Work、完成向量Finish，并赋初值。
（2） 进行安全性检查。从进程集合中查找一个能满足下述条件的进程i：
若找到这样的进程，执行步骤（3）；若找不到这样的进程，则转步骤（4）。
（3）
返回步骤（2）。
因为进程Pi 若能执行完成，则能够释放它所占的资源。
（4） 若所有进程的Finish［i］：=true都满足，则表示系统处于安全状态，正式将资源分配给进程Pi；否则，系统处于不安全状态，系统不能进行这次试探性分配，恢复原来的资源分配状态，让进程Pi等待。
如果已判定系统处于安全状态，则通过运算过程同时可以找到一个安全序列。
银行家算法具有较好的理论意义。但由于在实际系统中，难以预见或获得各个进程申请的最大资源向量，且实际运行进程的个数是动态变化的，因此银行家算法在实际系统中难以实施，或实施过程代价过大。
03、银行家算法的应用
例1 某系统有A、B、C类型的三种资源，在T0 时刻进程P1 、P2 、P3 、P4 对资源的占用和需求情况如表1所示，此刻系统可用资源向量为（2，1，2）。
表 1 各进程对资源的占用和需求情况
（1） 将系统中各种资源总数和进程对资源的需求数目用向量或矩阵表示出来。
（2） 判定此刻系统的安全性。如果是安全的，写出安全序列，如果是不安全的，写出参与死锁的进程。
（3） 如果此时P1和P2均再发出资源请求向量Request为(1,0,1)，为了保持系统安全性，应如何分配资源给这两个进程？说明所采用策略的原因。
（4） 如果（3）中的请求都立刻满足后，系统此刻是否处于死锁状态？最终能否进入死锁状态？若能，说明参与死锁的进程；若不能，说明原因。
- 点赞
- 收藏
- 关注作者
评论（0）