银行家算法

﹏ヽ暗。殇╰゛Y 2022-05-30 12:23 282阅读 0赞

先假设系统中的进程有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》上可以找到：