前言

写这篇文章的目的，能够更简单的去理解银行家算法，这个算法可把我给想秃了😖。

银行家算法是由 Dijkstra 在 1965 年提出的，它是一个非常著名的死锁避免算法。其实吧，我觉得应该叫 花呗 算法更合适😂。以下，我会利用花呗的方式来理解这个算法。

还有就是期末考试要到了，祝大家逢考必过呀😊😊😊。

逢考必过

算法介绍

银行家算法的实质就是要设法保证系统动态分配资源后不进入不安全状态，以避免可能产生的死锁。即没当进程提出资源请求且系统的资源能够满足该请求时，系统将判断满足此次资源请求后系统状态是否安全，如果判断结果为安全，则给该进程分配资源，否则不分配资源，申请资源的进程将阻塞。

前面的都是 FIFA 可以忽略🐶🐶，但还是建议看一下。

银行家算法的执行有个前提条件，即要求进程预先提出自己的最大资源请求，并假设系统拥有固定的资源总量。下面介绍银行家算法所用的主要的数据结构。

什么是向量？向量其实就是一个一维数组。什么是矩阵，矩阵就是一个二维数组。

  1. 可用资源向量 available，记录着系统当前可以使用的资源数目。（花呗公司还剩多少钱）
  2. 最大需求矩阵 max，记录着进程对各类资源的最大需求量。（用户使用花呗的最大额度）
  3. 分配矩阵 allocation，记录着每个进程的当前占有量。（用户已经使用了多少的花呗）
  4. 需求矩阵 need，记录着每个进程对各类资源尚需要的数据。等于“最大需求矩阵 - 分配矩阵”之差。（用户剩余的花呗额度）
  5. 请求向量 request，记录着某个进程当前对各类资源的申请量，是银行家算法的入口参数。（用户想要使用多少花呗）

算法步骤

  1. 检查资源的安全性。安全，申请请求。不安全，退出检查。
  2. 如果 request[i] > need[i]，则进程 P[i] 出错 （如果你想用花呗借 400，可是你的剩余额度才只有 20，你想想，能借吗？）
  3. 如果 request[i] > available[i]，则进程 P[i] 阻塞（如果你想用花呗借 400，可是花呗公司只有 200，你想想，能借吗？）
  4. 如果 request[i] ≤ need[i] 且 request[i] ≤ available[i]。则需要对相应的数据结构进行修改。
    1. available[i] = available[i] - request[i]。（比如花呗公司有 2000，用户向花呗借 20，此时花呗公司还剩 1980）
    2. allocation[i] = allocation[i + request[i]。（比如用户已经向花呗借了 500，用户在向花呗借 20，此时用户已经借了 520）
    3. need[i] = need[i] - request[i]。（比如用户的花呗剩余的额度为 300，用户向花呗借了 20，此时用户剩余的花呗额度为 280）
  5. 继续检查资源的安全性

算法的执行过程如下

执行过程

例题

aaa
bbb

问题

1、利用安全性算法，分析T(0)时刻的资源分配情况，如果安全，请写出安全序列。
2、假设T时刻，进程P1申请资源，其请求向量为Request(0,0,1)，系统能否将资源分配给它。

第1问解答

这个安全性算法，其实就是。用户剩余的花呗额度（也就是 need）能否全部借过去。

然后借完之后，还回去，怎么还？将已使用的额度全部还回去就好了，此时的花呗公司的可用的金额为：已使用的额度 (allocation) + 花呗公司还剩的钱 (available)

T(0)时刻的资源分配情况如下

process work need allocation work + allocation finish
P2 0 1 1 0 0 1 6 1 2 6 2 3 true
p1 6 2 3 2 2 2 1 0 0 7 2 3 true
p3 7 2 3 1 0 3 2 1 1 9 3 4 true
p4 9 3 4 4 2 0 0 0 2 9 3 6 true

其中 work 是当前的 available 数量。
由安全序列算法，结合表可知，安全序列为 <p2, p1, p3, p4>

但是安全序列是不唯一的。这个安全序列出现的原因是因为在检查 P1 的时候，出现了阻塞。当 P2 的资源释放了，p1再去尝试，可用资源是否能够满足 P1 的需求。

所以才有 <p2, p1, p3, p4>

第2问解答

1、判断 request(0,0,1) ≤ available(0,1,1) 通过（如果花呗公司的金额够借）
2、判断 request(0,0,1) ≤ need(1,0,3) 通过（如果用户借的额度比用户剩余额度小）

available = available - request = 0,1,1 - 0,0,1 = 0,1,0（向花呗公司借了0,0,1，花呗公司还剩0,1,0）
allocation = allocation + request = 1,0,0 + 0,0,1 = 1,0,1（用户向花呗借了0,0,1。加起来就是已使用的花呗额度）
need = need - request = 2,2,2 - 0,0,1 = 2,2,1（用户向花呗借了0,0,1，用户可用的花呗额度就是减去已经借的额度）

所以，此时的资源分配情况如下

process max allocation need available
P1 3,2,2 1,0,1 2,2,1 0,1,0
P2 6,1,3 6,1,2 0,0,1
P3 3 1 4 2 1 1 1 0 3
P4 4 2 2 0 0 2 4 2 0

经过分析发现，可用的资源数已经不能满足所有进程，该系统不安全。进程P1阻塞。

原来 Hexo 主题之间的表格需要前后空两行才能正常显示，我麻了，搞了我很久。😂😂😂

参考资源

https://blog.csdn.net/qq_33414271/article/details/80245715
https://www.cnblogs.com/wkfvawl/p/11929508.html
https://www.jianshu.com/p/e19eff4311f4