避免死锁-----银行家算法详解

​ 避免死锁同样属于事先预防的策略，但是并不是事先采取某种限制措施来破坏死锁的必要条件，而是在资源的动态分配过程中，防止系统进入不安全状态，以避免发生死锁。避免死锁这种方法对资源的分配限制条件较弱（相比于预防死锁），以期望获得更好的系统性能。

​ 关于安全状态和不安全状态的概念，可以参看这篇博文。

​ 银行家算法是我们的老朋友迪杰斯特拉为T.H.E系统设计的一种避免死锁产生的算法。该算法最初是为银行系统设计的，为了保证银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。

​ 银行家算法要求，每个新进程在进入系统时，它必须申明在运行过程中，可能需要每种资源类型的最大单元数目，其数目不应超过系统所拥有的的资源总量。当进程请求一组资源时，系统必须首先确定是否有足够的资源分配给该进程。若有，在进一步的检测将这些资源分配给进程后，是否会是系统处于不安全状态；如果不会，才将资源分配给该进程，否则让进程等待。

1.银行家算法中的数据结构

​ 为了实现银行家算法，在系统中必须设置这样四个数据结构，分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配、以及所有进程仍需要的资源情况。

1. 可利用资源向量Available：这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K，则表示系统中现有Rj类资源K个；
2. 最大需求矩阵Max：这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i, j]=K，则表示进程Pi需要Rj类资源的最大数目为K；
3. 分配矩阵Allocation：这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i, j]=K，则表示进程Pi当前已分得Rj类资源的数目为K；
4. 需求矩阵Need：这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i, j]=K，则表示进程Pi还需要Rj类资源K个，方能完成其任务。

​ 上述的三个矩阵Max、Allocation、Need存在下述关系：

​ $Need[i,j]=Max[i,j]-Allocation[i,j]$

2.银行家算法

​ 设Request_i是进程Pi的请求向量，如果Request_i[j]=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求Request_i(1,2,…,0)后（表示m类资源分别申请1,2,…,0个），系统按下述步骤进行检查：

1. 如果Request_i[j]<=Need[i, j]，（Request_i向量中的所有项都要判断）便转向步骤2；否则认为出错，因为他所需要的资源数（已经持有的+此次申请的）已经超过它之前声明的最大值。

2. 如果Request_i[j]<=Available[i, j]，（Request_i向量中的所有项都要判断）便转向步骤3；否则表示当前OS中尚无足够的资源满足进程Pi的此次申请，Pi进程阻塞，需要等待资源释放。

3. 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值（Request_i向量中的所有项都要操作）：

   ​ Available[j] = Available[j] - Request_i[j]; //可用资源减去此次申请的资源

   ​ Allocation[i, j] = Allocation[i, j] + Request_i[j];//已经持有的资源加上此次申请的资源

   ​ Need[i, j] = Need[i, j] - Request_i[j];//仍需求资源减去此次申请的资源

4. 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

3.安全性算法

​ 安全性算法是银行家算法在第4步执行的子算法，用于检查试探着把资源分配给进程Pi后OS的安全状态。为了保证安全性检查不影响Available、Max、Allocation和Need，其新建两个向量（临时变量）：

• 工作向量Work：表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素(对应OS中的m类资源)，在执行安全算法开始时，Work=Available（Work初始化为Available）;
• 结束标志向量Finsh：表示系统是否有足够的资源分配给所有进程，使之运行完成，它含有n个元素（对应OS中的进程数量n）。在执行安全算法开始时，Finsh中的所有位全为false，当有足够资源分配给进程Pi时，再令Finish[i] = true。

​ 安全性算法的执行步骤如下：

1. 从进程集合中找到一个能满足下述两个条件的进程：①Finsh[i] == false;②Need[i, j]<=Work[j]，其中0=<j<m，即进程Pi所需的所有资源可以申请获得；若找到，执行步骤2，否则执行步骤4。
2. 当进程Pi获得所需的所有资源后，可顺利执行完毕，并释放出分配给它的资源，所以需执行以下步骤：①Work[j] = Work[j] + Allocation[i, j]，其中0=<j<m，m为OS中的资源种类；②Finish[i] = true，表示进程Pi可以顺利执行完毕；③跳转到步骤1。
3. 如果Finish向量中的所有位全部为true，即所有进程都可顺利执行完毕，则表示系统处于安全状态；否则，系统处于不安全状态。

​ 最后，将检测结果返回给步骤四，来决定此次资源请求是否分配。

​ 安全性算法其实际目的就是看是否能找到一个安全序列，如果存在一个所有进程都可顺利推进完成的安全序列，则表示此时OS是处于安全状态，在这个状态下不会产生死锁

4.一个例子

​ 下面我们通过一个例子来讲解银行家算法的执行过程。

​ 例题：假定系统中有五个进程{P0, P1, P2, P3, P4}和三类资源{A, B, C}，各种资源的对应数量为10、5、7，在T0时刻的资源分配图如下图所示。

​ (1)请检查T0时刻的安全性。

​ 解：检查T0时刻的安全性，其实际就是使用安全性算法检测T0时刻OS的安全状态。我们通过安全性检查对T0时刻的资源分配状况进行分析：首先执行算法步骤1，因为此时所有的进程Finish全为false，且进程P1与P3的需求向量都小于Work向量，因此我们选取进程P1（选取哪个进程皆可，安全序列不唯一），并依次执行步骤2、3，完成后Work={5, 3, 2}，转为执行步骤1…

​ 经过安全性算法分析，分析过程如下图所示，OS在T0时刻存在一个安全序列{P1, P3, P4, P2, P0}，故系统是安全的。

​ (2)在T0时刻，进程P0发出请求向量Request₀(0, 3, 0)，OS是否可以把资源分配给进程P0?

​ 解：P0请求资源，系统按照银行家算法进行检查：

​ ①Request₀(0, 3, 0) <=Need₀(7, 4, 3);

​ ②Request₀(0, 3, 0)<=Available(3, 3, 2);

​ ③系统先假定可为进程P0分配资源，并修改相关数据：

​ Available = Available(3, 3, 2) - Request₀(0, 3, 0) = (3, 0, 2);

​ Allocation₀= Allocation₀(0, 1, 0) + Request₀(0, 3, 0) = (0, 4, 0);

​ Need₀ = Need₀(7, 4, 3) - Request₀(0, 3, 0) = (7, 1, 3);

​ 当前资源分配表如下所示:

​ ④进行安全性检查，可用资源Available(3, 0, 2)已经不能满足任何进程的需要，故系统进入不安全状态，进程P0请求的资源不能分配。

5.总结

​ 银行家算法是一个非常经典的算法，也是死锁避免算法中的最具代表性的算法，其思想是非常值得我们学习的。死锁处理的四种方法：预防死锁、避免死锁、检测死锁、解除死锁。其中预防死锁最为复杂，需要为OS设定各种定律、准则，较难实现，且较为影响系统的性能，最主要的就是并发效率下降；避免死锁可以让OS不必遵循特定的准则，因此给OS施加的限制较小，设计者也希望能通过此获得更好的系统性能，但是因为需要进程提前申明所需的最大资源，因此进程在进入系统前需要先对自身所需资源的进行一个最坏情况下的预估（要满足运行，必定是>=实际需要的，否则因为银行家算法在第一步就给卡死就非常冤了），但是这样，也必定会影响系统的并发，进而影响系统性能；死锁的检测和解除，是采用的“鸵鸟策略”，我不关心你会不会发生死锁，OS定时进行死锁检测，发现后进行解除，通过这种方式，反而可以获得更好的并发，因为在银行家算法中，许多情况下，不安全状态并不一定会转换为死锁。

​ 但是OS选取何种方法，也是需要根据自身设计的一个目的来选定，没有哪个方法一定比哪个好。

​ 本算法对应的Java实现请参考这篇博文。

​ 又到了分隔线以下，本文到此就结束了，本文内容全部都是由博主自己进行整理并结合自身的理解进行总结，如果有什么错误，还请批评指正。

​ 如有兴趣，还可以查看我的其他几篇博客，都是OS的干货，原创不易，喜欢的话还请点赞、评论加关注^_。

​ 操作系统武功修炼心法