银行家算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了银行家算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

银行家算法概述

银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。

银行贷款案例

假设客户A、B、C 三人向银行贷款用于建房，分别需要贷款70万、60万、40万，而银行只有100万，已知A、B、C三人只有贷款额足够时，他们才能保证建房完成并归还贷款，否则将无法归还贷款。银行需要使用什么方式才能保证贷款是安全的？

分析：A、B、C三人合计的资金需求是170万，显然银行无法直接满足三者的需求。

如果刚开始ABC三人分布借走了20万，20万，20万

客户	最大需求	已借贷	最多还会借
A	70	20	50
B	60	20	40
C	40	20	20

可以算出，客户A、B、C最多还要借50、40、20，而银行已经借出60万(20+20+20)，银行剩余40万。

A再次申请50万，能批准吗？

那么此时，假设客户A申请借50万，而银行最多只能借出40万，那么如果银行将40万借给A。

客户	最大需求	已借贷	最多还会借
A	70	20+40	10
B	60	20	40
C	40	20	20

显然此时A无法完成建房的操作，B和C也不能完成建房的操作。这就导致A、B、C三个客户一直占有者已分配的钱，但是又无法归还银行，这种情况我们称为不安全序列。也就意味着A第二次申请50万的操作，银行不能批准。

B再次申请40万，能批准吗？或者C申请20万，能批准吗？

通过前面的图我们知道B还需要40万。那我们试着分配40万给B

客户	最大需求	已借贷	最多还会借
A	70	20	10
B	60	20+40	-
C	40	20	20

我们可以看到B再得到40万后，可以完成建房的操作，于是归还了全部的贷款60万，于是银行此时有60万。

客户	最大需求	已借贷	最多还会借
A	70	20	10
C	40	20	20

此时客户A申请50万，银行批准这50万的贷款，而此时银行剩余10万，当客户A完成了贷款的使用后，归还了贷款，此时银行剩余80万。

客户	最大需求	已借贷	最多还会借
C	40	20	20

此时C申请20万，银行当前余额80万，可以批准这个操作，于是C也完成了建房的操作。

我们把这个分配顺序（B > A > C）叫做安全序列。
安全序列可以有多个，按照上面的操作，也可以是B > C > A
或者 C > A >B ，C > B > A。
我们上面的操作是借出 > 归还 > 借出 > 归还，如果银行的资源比较多的时候，可以一次性满足多个客户，并且可以找到安全序列，那么也可以借出 D > 借出 E > 归还 E >…

安全序列和不安全序列

当资源分配过程的策略可以满足所有参与者能够完成执行的时候，我们称指为安全序列。如果分配过程出现无解的时候，我们称为不安全序列。
比如下面这个场景，银行已经分配90万，剩余10万，此时剩余的10万无论分配给谁，都无法保证A、B、C完成建房。

客户	最大需求	已借贷	最多还会借
A	70	50	20
B	60	30	30
C	40	10	30

于是这个无论如何都没有解，A、B 、C只能这样僵持着，我们称这个过程为死锁。
如果分配了资源之后，系统中找不到任何一种安全序列，系统将会进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。当然了，如果有进程提前归还了一些资源，那么系统也可能重新回到安全状态，不过我们分配资源之前总是要考虑到最坏的情况。
如果系统处于安全状态，就一定不会发生死锁。如果系统进入了不安全状态，就可能发生死锁(处于不安全状态未必就是发生了死锁，但发生死锁时一定是不安全状态)。
因此可以在资源分配前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求，这就是银行家算法的核心思想。

多维度资源分配

前面的案例，银行家算法，里面的资源只有钱，对于操作系统而言，它的资源是多种多样的。我们利用银行家算法这种思想，作为操作系统资源的分配策略，用于避免死锁。

核心思想：在进程提出资源请求时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。

对于计算机而言，计算机中有各种各样的资源，也有各种各样的进程，它们所需要的资源也不相同。
我们可以将资源扩展成多维度的向量。比如系统中有4个进程P0~03，有三种资源R0 ~ R2，系统持有的初始资源Avaiable(7，10，6)

客户	最大需求	已分配	最多还需要
P0	(7,4,5)	(3,1,3)	(4,3,2)
P1	(3,4,2)	(0,1,0)	(3,3,2)
P2	(4,1,1)	(1,1,1)	(3,0,0)
P3	(3,4,2)	(2,1,0)	(1,3,2)

经过计算，已经分配的资源（6，4，4），剩余的资源（1，6，2）
此时系统是否处于安装状态?
尝试找到一个安全序列
一次检查剩余的资源(2,6,2)是否满足各进程的需求。
可以发现剩余资源数不能满足P0，P1，P2 进程的运行，当检查P3时发现，剩余资源数（1，6，2）可以满足P3进程的需求，于是把P3加入到安全序列，于是P3可以顺利执行结束，并将P3持有的全部资源归还给系统，此时系统状态如下

客户	最大需求	已分配	最多还需要
P0	(7,4,5)	(3,1,3)	(4,3,2)
P1	(3,4,2)	(0,1,0)	(3,3,2)
P2	(4,1,1)	(1,1,1)	(3,0,0)

P3结束后，剩余可用资源数为(3，7，2)
继续一次检查剩余资源可满足满足的进程，可以发现不能满足P0进程的运行，可以满足P1或者P2的运行，可以将P1加入到安全序列(也可以将P2加入到安全序列)，我们此时取P1
于是当资源满足P1时，P1执行完成，并归还资源

客户	最大需求	已分配	最多还需要
P0	(7,4,5)	(3,1,3)	(4,3,2)
P2	(4,1,1)	(1,1,1)	(3,0,0)

当P1结束后，归还资源，那么剩余资源是（3，8，2）
继续检查，可以发现剩余资源不能满足P0，但是可以满足P2的运行，于是我们分配资源给P2

客户	最大需求	已分配	最多还需要
P0	(7,4,5)	(3,1,3)	(4,3,2)

当P2运行完成，归还资源后，系统剩余资源（4，9，3），于是满足了P0，那么此时P0申请资源，P0也能顺利完成。
那么按照刚才的执行过程，P3 > P1 > P2 > P0 这个分配过程就可以满足所有进程的执行，我们称这个分配过程为安全序列。
实际操作用，我们可以让还需要资源数少的进程先运行，因为它们更容易满足剩余资源的分配。

操作系统资源分配

假设系统有n个进程，m种资源，每个进程在运行前先声明对各种资源的最大需求数，则可以按照nm的矩阵(可以使用二维数组实现)表示所有进程对各种资源的最大需求数。不妨称为最大需求矩阵Max，则Max[i,j]=k表示进程Pi最多需要K个资源Rj。同理，系统看可以用一个nm的分配矩阵Allocation表示对所有进程的资源分配情况。Max-Allocation=Need矩阵，表示各进程最多还需要多少各类资源。另外，还需要一个长度为m的一维数组Avaiable表示当前系统中还有多少可用资源。
某进程Pi向系统申请资源，可用一个长度为m的以为数组 $Request_i$ 表示本次申请的各种资源量。
可用银行家算法预判本次分配是否会导致系统进入不安全状态
①如果 $Request_i$ [j]<=Need(i，j)(0<=j<=m) 便转向②；否则认为出错。
②如果 $Request_i$ [j]<=Avaiable(j)(0<=j<=m) 便转向③；否则表示尚无足够的资源，Pi需要等待。
③系统试探着把资源分配给进程Pi，并修改相应的数据(并非真的分配，修改数据只是为了做预判)：
Avaiable = Avaiable - $Request_i$ ；
Allocation[i，j] = Allocation[i，j] + $Request_i$ [j];
Need[i，j]=Need[i，j] - $Request_i$ [j];
④操作系统执行安全性算法，检查此资源分配后，系统是否处于安全状态。如果安全，则才正式分配；否则，恢复相应数据，让进程阻塞等待。

银行家算法,算法,算法

银行家算法总结

数据结构

长度为m的一维数组Available 表示还有多少可用资源
n * m矩阵Max 表示各进程对资源的最大需求数
n * m矩阵Allocation表示已经给各进程分配了多少资源
Max-Allocation=Need 矩阵表示各进程最多还需要多少资源
用长度为m的一维数组Request表示各进程此次申请的各种资源数

银行家算法的步骤

检查此次申请是否超过了之前声明的最大需求数
检查此次系统剩余的可用资源是否还能满足这次请求
试探着分配，更改各种数据结构
用安全性算法检查此次分配是否会导致系统进入不安全状态

安全性算法步骤

检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入到安全序列，并把该进程持有的资源全部回收。

系统处于不安全状态未必死锁，但死锁时一定处于不安全状态。系统处于安全状态一定不会死锁。

死锁的避免

最后，我们知道了银行家算法的核心思想，就可以在每次的资源请求分配之前预判该次资源分配是否安全，利用银行家算法，我们就可以知道哪些资源请求是不安全的，哪些资源请求是可以被允许的，这样就可以让程序始终处于安全状态，就可以避免死锁的产生。文章来源地址https://www.toymoban.com/news/detail-784317.html

到了这里，关于银行家算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！