如果转载请注明出处：http://blog.csdn.net/gophers

银行家算法是一种可以用来预防死锁的检测算法，正像这种算法的名字一样，系统在分配资源情况就和银行家管理银行资金的情况是相似的。银行家要在贷款的时候协调各个客户之间的业务，最好的情况就是就是把当前的资金合理的分配出去，让余下来的资金依然足够应付近期的其他业务，而且能够确保在有新客户要贷款时之前贷出去的资金已经被收回。操作系统在协调各个进程之间的资源占用关系时也可以套用这种方法。

银行家算法主要由两个部分构成，一个是Safety Algorithm(安全状态检测算法)，另一个是Resource-Request Algorithm(资源请求算法)。这两个算法是协同工作的，它们相互合作以预防操作系统发生死锁的情况。资源请求算法不会单独使用的，通常每次调用完资源请求算法都会再去调用安全检测算法。

在讲解银行家算法之前，我们先来定义一些全局数据结构，这些数据结构的定义对理解银行家算法来说至关重要！请耐下性子看仔细，而且要看懂，在继续将下去的时候脑子里也应该随时反应到这些数据结构有什么用:

先假设系统中的进程有P个，资源有R种，我们要定义如下数组(或二位数组)

1. Available

Available是一个数组，它的长度等于R，也就是和资源的数量相同。数组里每一个元素的值代表了当前系统中该种资源可以获取的数目。简而言之，Available就是当前系统中各种资源的可用个数。一定要注意是当前哦～

2. Max

Max是一个二维数组，定义为Max[P][R]，代表P个进程每个进程要完成自己的任务所需的R种资源里每种资源的数量。比如Max[0][3]=5表示第0个进程要完成自己的任务总共需要第三种资源5个。

3. Allocation

Allocation是一个二维数组，定义为Allocation[P][R]，它表示每个进程已经被分配到的每种资源的个数。比如Allocation[0][3]=2表示第0个进程已经被系统分配了2个第三种资源。

4. Need

Need也是一个二维数组，定义为Need[P][R]，它表示每个进程要完成自己的任务(其实就是相应的Max值)还需要每种资源各多少个。比如通过上面的Max和Alloction我们可以知道Need[0][3]=3，因为第0个进程要完成自己的任务一共需要5个(Max)第三种资源，已经分配给了它2个(Allocation)，还需要3个(Need)才可以玩成任务。也就是说，Need = Max - Allocation 。

当然，如果你要实现一个具体的银行家算法程序的话就不必非要拘泥于是不是非要定义成数组这种问题了，具体的情况根据自己的实现来决定。

在搞懂了这4个数据结构之后我们就可以开始讲解银行家算法的两个算法了。

安全状态检测算法

安全状态检测算法的流程如下：

1. 先初始化两个数组，一个是Finish(长度为P)，另一个是Available(长度为R)，Finish表示某个进程是否已经执行完了它的任务，一开始把所有的元素都置为false，Available就是上面说过的那个啦，代表当前系统中每种资源的可用个数。

2. 不断扫描所有进程，当前扫描到了进程i，如果:

    a. Finish[i] == false

    b. Need[i] <= Available

这两个条件都成立的话就进行第3步，否则执行第4步。

3. Available += Allocation[i] 并置 Finish[i] = true，继续执行第2步。

4. 如果Finish中的元素都是true，即所有进程都已经执行完，则可以判定系统属于安全状态！

如果你仔细领悟的话就会发现安全状态检测算法原理是：

系统先把当前所有剩下的资源都像贷款一样分配给某个进程，但要确保这个进程拿了这笔“贷款”之后一定可以完成它的任务(也就是Allocation+Available >= Max)，在这个进程执行完了它的任务后系统就把“贷款”和之前分配给它的所有资源都回收回来，就好像银行家把贷款连同利息一起回收回来一样，这时系统的“本金”就成了“贷款+利息”，也就是当前的Available等于之前的Available加上已执行完的进程的Allocation.

这时系统可以用这笔更多的“本金”继续贷款给某个其他进程，同样，在这个进程执行完毕后系统会连同之前分配给它的资源一起回收回来，这样不断往复，系统就通过这样从给低需求的进程贷出所有可用资源并不断回收资源从而积累可用资源来解决更多需求更大的进程。如果系统的“本金”不足以带给任何一个进程，则表示系统目前处于不安全的状态，随时可能发生死锁。

资源请求算法

如果某个进程i发起了资源分配申请：

1. 如果 Request[i] > Need[i] 则拒绝申请

2. 如果 Request[i] > Available[i] 则拒绝申请

3. 如果1、2步都通过了就进行如下计算：

    Available -= Request[i]

    Allocation[i] += Request[i]

    Need[i] -= Request[i]

这个计算并不是真正改变了原先的Available、Allocation和Need，这些计算的值都是临时的

4. 用安全状态检测算法检测计算完毕后的系统状态是否处于安全状态，如果处于安全状态则进程i的这次请求生效，否则只能推迟这次的申请

资源请求算法的原理就是在进程请求的资源不超过系统当前可用资源的前提下，先同意分配试一下，然后通过安全态检测算法来检验这样分配后的系统是否安全，如果是安全的就真的同意这样分配，如果不安全就推迟这次分配。

如果讲解到这里还有点笼统，那么就据一个例子来说明一下银行家算法的具体实例，这个例子在Abraham Silberschatz的《Operation System Concepts》上可以找到：

假设现在有5个进程P0—P1，有三种资源ABC，系统目前的资源调配情况如下面这张列表：

我们先通过安全状态检测算法看一看目前的系统状态是否是安全的：

因为Need[P1] < Available，所以 Available = 3 3 2 + 2 0 0 = 5 3 2， Finish[P1] = true

这时Available就成了5 3 2，继续往下找

发现Need[P3] < Available，所以 Available = 5 3 2 + 2 1 1 = 7 4 3，Finish[P3] = true

在接下来

Need[P4] < Available, Available = 7 4 3 + 0 0 2 = 7 4 5，Finish[P4] = true

Need[P0] < Available, Available = 7 4 5 + 0 1 0 = 7 5 5，Finish[P0] = true

Need[P2] < Available, Available = 7 5 5 + 3 0 2 = 10 5 7，Finish[P2] = true

算到这里Finish中所有的元素都已经置为了true，也就是说所有的进程都已经执行完毕了，目前系统处于安全状态～

如果现在P1发出一个请求Request = 1 0 2

因为1 0 2既小于Need[P1]又小于Available，所以我们调用资源请求算法，计算之后的结果如下：

Available = 3 3 2 - 1 0 2 = 2 3 0

Allocation = 2 0 0 + 1 0 2 = 3 0 2

Need = 1 2 2 - 1 0 2 = 0 2 0

用红色标出的数据就是与前一状态不同的部分

然后我们在调用安全状态检测算法检查变化后的系统是否处于安全状态就可以了，步骤和一面完全一样，通过检验后会发现给P1分配1 0 2之后系统依然可以处于安全状态，所以同意此次分配。

预防死锁之银行家算法