操作系统——银行家算法（银行家和房地产开发商的爱恨情仇）
操作系统——银行家算法
什么是银行家算法
银行家算法（Banker's Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。
银行家算法的产生背景
在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
银行家算法的通俗解释
银行家算法就是一种为了避免死锁的发生而设计出的一种资源分配的方法，这种算法通过预先假设分配资源来尽可能的满足需求，一步一步的推倒，最后判断分配完后系统是否处于一个安全状态，如果最后处于安全状态，则假设的分配方案成立，可以立即执行，否则，系统处于一个不安全的状态，应该拒绝资源的请求。
就好比有一个银行家开了一家小银行，有几个房地产商需要向银行家借贷一部分资金用来建房子，待他们把房子建成之后，就会立即把钱归还给银行家，而对于银行家来说，如何最大化的利用自己手上的资金去借贷给房地产商，并且不会使得发生死锁的现象（即银行家手头上剩下的资金无法满足任何一个房地产商的借贷需求，这样会造成没有任何一个房地产商能够成功的把房子建成，也就无法把借贷的资金归还给银行家了，而不归还资金，银行家又没有收回足够的资金，也无法继续提供借贷服务，这样就形成了银行家和房地产商两难的现象），这这就需要一种优质的算法来解决这个问题，就是我们现在讲的银行家算法。
银行家算法涉及到的数据结构
为了更加通俗的去解释银行家算法，我们假设每个房地产商建房子需要请不同国家的设计师来建设，不同国家的设计师需要支付不同种类的钱币，因此我们把5个进程分别比作房地产商P0，房地产商P1，房地产商P2，房地产商P3......把A，B，C三类资源看做是三种不同的钱币，例如人民币，美元和英镑。则n是房地产商的数目（此时n为 5），m是钱币的种类（此时m为3）。
还有一些其他重要的数据结构如下如所示，请务必仔细阅读并理解下图：
点击图片可放大观看！！！
上面是一些银行家算法利用到的数据结构，其中和银行家有关系的数据结构是：【Available】【Work】【Finish】
分别代表的意思是：
【Available】银行家手头可以用来借贷的数量
【Work】与上面的【Available】同样的功能，但是请注意！！！【Available】代表最开始银行家手头所拥有的钱数，而【Work】代表此时银行家手头所拥有的钱数，即【Available】是初始值，变化后的值都用【Work】来表示
【Finish】表示房地产商是否完成了最后的借贷
其中和房地产商有关的数据结构是：【Finish】【Need】【Allocation】【Max】，
分别代表的意思是：
【Finish】表示房地产商是否完成了借贷
【Need】表示房地产商仍然需要借贷的金额数
【Allocation】表示房地产商手头已经拥有的钱款
【Max】表示房地产商建完房子所需要花费的总金额
银行家算法的组成
银行家算法是由两种算法组成而来的，分为①安全状态判定算法和②资源请求算法。其中资源请求算法时建立在安全状态判定算法的基础上的。
①安全状态判定算法
假设你就是这个银行家，为了成功的经营这家银行，你需要实时的对银行目前的资金状况作出一个安全风险评估，那么怎样才能认为银行目前所处于的状态是一个安全的状态呢？我们只需要使用安全状态判定算法，如果能够得出任意一个安全序列的话，那么就能保证此时银行是处于一个安全的状态的，既不会发生死锁现象（银行家和房地产商都无法完成任务），否则，此时银行就处于一个危险的状态，很有可能会发生死锁的现象。
【安全序列】：房地产商向银行借贷的顺序。
安全状态判定算法的步骤如下：
1.初始化Work[]数组的值为Available[]数组（该数组只用一次，表示最开始的状况）的值。
把所有的Finish[i]都设置为False,表示此时所有的房地产商都没有完成借贷。
2.找到一个i同时满足下面两个条件：
①Finish[i]=false（房地产i未完成借贷任务）
②Need[i]<=Work（房地产i还需要的资金数量小于银行家手头拥有的资金数量）
如果不同时满足上述条件，跳转到第4步：
3.Work=Work+Allocation（银行家手头的资金数变多是因为已经有房地产商完成建房任务，并收回了其所有的贷款）
Finish[i]=true（标记房地产商已完成任务）
跳转到步骤2
4.如果所有的Finish[i]都为True，表示所有的房地产商按照上面产生出来的安全序列执行借贷任务的话，都能够成功地完成建房任务，则银行系统此时是处于一个安全的状态。
下面举一个具体的例子来讲解：
假设一个小镇上有5家房地产公司，分别标记为p0~p4，并且他们建房子都请了大量的国外设计师，需要三种货币来支工人们的薪水，分别是人民币，美元和英镑，我们也标记为A货币，B货币，C货币。起初，银行家一共拥有货币A（人民币）10万元，货币B（美元）5万元，货币C（英镑）7万元。房地产商们陆陆续续向银行家借贷了部分资金用来启动项目后，此时银行家和房地产商的资金状况如下所示：
Allocation:房地产商已经借贷数 Max：房地产商建房一共需要资金数 Avaliable:银行家手头上可用于放贷的资金数
问题来了，此时每个房地产商为了完成建房任务，分别还需要向银行家借贷多少钱呢？这个我们非常容易理解，还需要借贷的资金数就是最大需要的资金数减去已经借贷的资金数，即MAX-Allocation就是Need表示的值了。因此，我们可以很容易的得出目前房地产商仍然需要的资金数量如下表：
第二个问题是：此时银行的是否处于一个安全状态呢？如果是的话，安全序列又是怎样的呢？
所以银行家开始在办公室里用银行家算法如下图所示一步一步的推倒了一遍：
点击图片可放大观看！！！
银行家最后发现，竟然推倒出了一个安全序列出来，为P1,P3,P4,P0,P2,也就是说从目前这个状态开始，我只要按照P1,P3,P4,P0,P2的顺序给房地产商提供借贷，那么就一定不会发生死锁的现象，则银行此时出于一个安全的状态。
注意：安全序列并不唯一，可以有多种情况，只要能得到一个安全序列，就能够保证系统处于安全状态。
这就是如何去判断当前银行的状态是否为安全状态的安全状态判定算法。
②资源请求算法
资源请求算法其实并没有什么很难，其实就是在安全判定算法的基础上加了一步，即假设在某个安全状态后，有某个房地产商向银行家提出借贷请求，银行家需要考虑此时能不能够借贷给他，因为如果借贷给他，导致银行处于一个不安全的状态，就会很容易发生死锁，所以银行家需要小心翼翼的去模拟一遍借贷情况，先假设把钱借给了这个房地产商，然后在用上面讲到的安全判定算法测试以下银行是否仍然处于一个安全状态，如果仍然安全，则借贷之，否则拒绝之。
下面是具体的算法：
当银行家处于安全状态时，收到某个房地产商的借贷请求，银行家将按照下面的步骤进行演算模拟：
1.如果房地产商i的请求借贷资金数<=房地产商i仍然需要的资金数（requesti<=needi），跳转到第2步。否则，拒接请求，因为房地产商已经超出了他一共所需要的资金数。
2.如果房地产商i的请求借贷资金数<=银行家手头可放贷的资金数，跳转到第3步。否则拒绝之，因为银行家手头的钱无法满足房地产商的借贷需求。
3.假设银行家接受房地产商的借贷请求，则执行下面的操作：
银行家手头的资金将变少，房地产商的资金将变多，房地产商还需借贷的资金变少。
4.执行安全状态检查算法，检查银行资金是否处于安全状态，若是，则可借之，否则，拒接之。
下面还是举一个例子：
当银行处于安全状态时，房地产商P1向银行家提出了借贷请求，他需要借贷1万元的A货币和2 万元的C货币，请你帮银行家想想，能够把钱借给房地产商吗？
按照上面的算法，我们一步一步的进行模拟，看看能不能得出安全序列来，就决定了能不能把钱借给P1。
①首先假设把钱借给了房地产商P1,则银行将处于下面的一种状况：
②使用安全状态判断算法来判断此时的银行是否任然处于安全状态：
③最后，能够找出一个安全序列P1,P3,P4,P0,P2出来，则证明把钱借贷给P1后，银行家仍然有办法使得借贷能够顺利进行。
发生死锁的例子
还是接着上面的情况来看，如果在上面的安全状态后，不是P1房地产商向银行家借贷1万元的A货币和2万元的C货币，而是房地产商P0向银行家借贷2万元的货币B，那么银行家还能够答应他的借贷请求吗？
能不能，推倒一下就知道了，还是使用上面的算法：
| Allocation | Need | Available | |
| A B C | A B C | A B C | |
| p0 | 0 3 0 | 7 2 3 | 2 1 0 |
| p1 | 3 0 2 | 0 2 0 | |
| p2 | 3 0 2 | 6 0 0 | |
| p3 | 2 1 1 | 0 1 1 | |
| p4 | 0 0 2 | 4 3 1 |
此时，我们会发现，银行家如果接受了P0房地产商的借贷请求，则手上剩下的资金为A币种2万元，B币种1万元，C币种0元，此时，银行家剩下的资金无法满足P1，P2，P3，P4,任何一家房地产的请求，就算把剩下的2万元A币，1万元B币继续借贷给P0开发商，P0开发商也无法完成建房任务，因为P0开发商完成建房任务需要的资金数量太大了！也就是说，把资金借给P1开发商，银行找不到一个安全序列，则银行将处于危险状态。没有任何一家开发商能够完成建房任务，就意味着没有任何一家开发商能够把借贷的钱全部还给银行家，银行家没钱就无法放贷给开发商用于建房，这样，开发商没有足够的资金完成建房任务，银行家也没有足够的资金去放贷给开发商，最后谁都无法完成自己的任务，都将亏本而败。
以上就是关于银行家算法的内容，如果觉得本文讲的不错的话，可以点一波关注哦！~
参考资料
【1】《操作系统教程》（第5版） 费祥林 骆斌 著 高等教育出版社
【2】https://www.geeksforgeeks.org/operating-system-bankers-algorithm 作者：vikash Kumar 翻译：刘扬俊
博客文章版权说明
第一条 本博客文章仅代表作者本人的观点，不保证文章等内容的有效性。
第二条 本博客部分内容转载于合作站点或摘录于部分书籍，但都会注明作/译者和原出处。如有不妥之处，敬请指出。
第三条 在征得本博客作者同意的情况下，本博客的作品允许非盈利性引用，并请注明出处：“作者：____转载自____”字样，以尊重作者的劳动成果。版权归原作/译者所有。未经允许，严禁转载。
第四条 对非法转载者，“扬俊的小屋”和作/译者保留采用法律手段追究的权利。
第五条 本博客之声明以及其修改权、更新权及最终解释权均属“扬俊的小屋”。
第六条 以上声明的解释权归“扬俊的小屋”所有。