243_死锁的处理策略—避免死锁
# 2.4_3_死锁的处理策略—避免死锁
各位同学大家好，在这个小节中我们会介绍死锁处理的第二种策略，避免死锁。
我们会用一个例子来说明什么是安全序列，什么是系统的不安全状态，安全序列，不安全状态，他们之和死锁之间有什么联系，最后我们会给出银行家算法的具体步骤，银行家算法是用于避免死锁的最著名的一个算法，这个算法很容易在小题和大题当中进行考察，所以这个小节的内容是十分重要的。
# 安全序列
那么我们首先来看一下什么是安全序列，假设你是一个成功的银行家，手里掌握着 100 个亿的资金，有三个企业想要找你贷款，分别是企业 b，企业 a，和企业 t，简称 BAT 是吧？各个企业在找你贷款之前都和你约定好了，他们最多会跟你借多少钱，但是江湖中有一个不成文的规矩，如果你给这些企业借的钱，借的总数达不到你最开始给的承诺的数字的话，那么不管之前你给他们借多少钱，这些钱都拿不回来了。所以由于规矩，我们在给这些企业借钱放贷款的时候需要格外的小心。假如说刚开始 bat 这三个企业分别从你这借了 20 ，10 和 30 亿，我们可以把这些已知数据把它整理成一个表，这三个企业对钱的需求分别是 70，40 和 50 亿，他们已经从你的手里借走了 20，10 和 30 亿，如果说用他们的最大需求减掉，此时已经借走了多少钱的话，我们就可以计算出每一个，企业在之后最多还有可能向你借多少钱。此时 BAT 总共从你手上借走了 60 亿，所以你手上还会有 40 亿的资金。接下来如果说企业 b 还想跟你借 30 亿，你敢借吗？
假如说我们答应了他的请求的话，情况会变成这个样子。企业 B 从你手上借走了，以前的 20 再加新借的 30，总共借走了 30 亿，那之后他最多还会再借 20 亿，但是这个时候由于你手里只有了 10 亿的资金，所以如果说之后 BAT 这三个企业同时向你提出再结 20 亿的请求，那么你手里的资金是不是就没办法满足这些企业的请求了？所以经过慎重的考虑，给 b 借 30 亿，这个请求是不能答应的，会不安全。
如果说此时是 a 想再跟你借 20 亿，敢借吗？还是用之前的思路来分析。如果给 a 再借 20 亿的话，那么 a 的数据会有一定的变化，就变成这个样子。你的手里就只剩是 20 亿，接下来其实可以这么弄，手里的 20 亿可以先全部借给 T，由于 T 最多还只会接 20 亿，所以如果给他 20 亿的话，那么肯定已经可以满足 T 的最大需求了。那之后等 T 把钱用完了之后再还回来，于是你的手里的钱就变成了 20 亿，再加上 T 手里的这 30 亿，总共会有 50 亿的资金，之后这 50 亿就可以再借给 b 企业，于是 b 企业的最大需求也可以得到满足。等 b 企业用完钱再还回来之后，你手里的钱就变成了 70 亿，之后再把 A 想需要的 10 亿再借给他，于是所有的钱就都可以收回来了。
所以和之前所说的给 b 借 30 亿那种情况不同，如果给 a 借了 20 亿，这个局并不是一个死局，我们只需要按 TBA 这样的顺序依次给各个企业借钱，那么这些企业总是可以依次的得到满足的。
其实我们还可以换一种顺序，比如说这 20 亿先给 a 再借 10 亿，那么 a 用完钱之后，他会把手里的 30 亿也全部还回来，于是你手里的钱就变成了 20 加上 a 手里的 30 亿，也就是 50 亿。之后再把其中的 20 亿给 t 于是 t 用完了之后再把钱还回来，你就有 80 亿，最后你再把 b 需要的 50 亿全部给 b，于是 b 的需求也可以得到满足，最后 b 也会把钱全部还回来。
所以如果我们按 atb 这样的顺序依次满足各个企业的需求的话，那么其实这些钱也并不是一个死局。因此经过考虑，a 想借 20 亿的请求，我们是可以答应的，是安全的
所以通过刚才的分析，我们发现有的资源请求我们是不能答应的，而有的资源请求我们是可以答应的，比如说给 a 借 20 亿之后，我们依然可以找到像 tba 这样的所谓的安全序列。
安全序列就是指如果说系统按照安全序列的顺序，依次给各个进程或者说各个企业分配资源，那么这些企业进程就都可以顺利的完成，最后都把自己手里的资源依次归还系统。所以如果我们能够找到一个安全序列的话，那么我们就称此时这个系统就是处于安全状态的。
当然通过之前的分析，我们也知道安全序列是不有时候并不唯一，如果分配了资源之后，再也找不到任何一个所谓的安全序列，那么系统就进入了不安全状态，这就意味着之后有可能所有的进程就都无法顺利的执行下去。
比如说假如之后 BAT 都提出再借 20 亿的请求的话，那么这些请求都暂时得不到满足，所以所有的企业都会被阻塞，于是系统就进入了死锁的状态。
当然如果说有一些进程提前归还了一些资源的话，那么系统有可能重新回到安全状态，比如说 a 企业先归还了 10 亿，于是你的手里就会有 20 亿，之后你就可以找到一个安全序列 tba 按照这样的顺序给各个企业依次借钱的话，整个系统就不会死。
如果系统中能找到一个所谓的安全序列，说明系统是处于安全状态的，在这种情况下一定不会发生死锁。而如果系统进入了不安全状态，也就是找不到任何一个安全序列，那么就有可能会发生死锁，注意只是有可能并不一定发生死锁。
比如说在这个系统中，如果 bat 没有提出再借 20 亿的请求的话，那么这个系统虽然是处于不安全状态，但是暂时还没有发生死锁。一直到 bat 提出这个请求之后，所有的企业进程都没办法顺利的执行下去，都会被阻塞，这种情况下系统才是真正的发生了死锁。因此进入不安全状态未必发生死锁，但是如果发生了死锁，一定是处于不安全状态，这个地方很容易作为选择题考察，大家一定要理清楚这几个状态的关系。
根据之前的这些分析，我们得到了一个新的处理死锁的思路，我们可以在分配资源之前，预先判断一下这次分配是不是会导致系统进入不安全的状态。如果系统会进入不安全状态，那么就意味着这次分配之后有可能会发生死锁，我们就不应该允许这次分配。
如果系统不会进入不安全状态，那么就意味着这次分配是安全的，即使进行了分配系统也暂时不可能发生死锁，所以这也是银行家算法的一个核心思想。
# 银行家算法
银行家算法刚开始是荷兰学者迪杰斯特拉提出来的，又是这个人刚开始设计这个算法的时候，是为了确保银行在发放现金贷款的时候，不会发生不能满足所有客户需求的这种情况，就像刚才咱们分析的那样，但之后这个算法又被用在了操作系统当中，用于避免死锁。我们来看一下怎么把这种思想应用于操作系统的避免死锁。
首先来思考一下，之前咱们提到 BAT 的这个例子当中，只有一种类型的资源就是钱，但是在计算机当中可能会有打印机，有扫描仪、有摄像头，各种各样的资源，我们怎么把刚才那种算法思想拓展到有多种资源的情况？其实很简单，我们只需要把单维的数字拓展为多维的向量，就可以很方便的计算了。
比如说 1 个系统当中有 5 个进程，p0 到 p4，然后有 3 种资源，r0、r1、r2，这三种资源刚开始的数量分别是 10,5,7，比如说 p0 对这三种资源的最大需求，我们可以用一个三维的向量来表示，就是（7,5,3），现在系统给 p0 分配了这三种资源分别是 010 这么多。如果我们把系统已经给各个进程分配的这些资源依次加起来，我们就可以得到此时已经总共分配出去了 725 这么多的资源，剩余的资源数我们用它初始数量减掉已分配的数量就可以得到了，也就是 332。
那么和之前的这种思想一样，我们可以用各个进程对资源的最大需求，减掉此时已经给进程分配的资源数，就可以得到此时各个进程最多还需要多少资源，于是就得到了这样的结果。
那么我们根据刚才分析的情况来看一下此时这个系统到底是不是处于安全状态。我们可以尝试找到一个安全序列，由于此时系统当中还剩余的资源数分别是 332，我们可以用这个数字，和此时各个进程最多还需要多少资源这个数字进行一个对比。
首先和 p0 进程对比发现剩下的这些资源满足不了 p0 的最大需求。
接下来和 p1 对比，经过对比发现，此时剩余的这些资源数量是可以满足 p1 的最高需求的，所以就意味着如果我们把这些资源全部分配给 p1 的话， p1 肯定是可以顺利的执行结束。等 P1 结束了，他又会把自己手里的这些资源给归还给系统，所以等 p1 结束了，系统的资源数就可以增加到这么多，其实就是把 p1 的这些已占有资源数和此时的剩余资源数一相加，就可以得到 p1 归还之后的资源数，也就是 532，所以我们可以把 p1 先加入安全序列，然后把剩余可用资源值改成 532 这么多。
接下来再进行第二轮的对比，首先是 p0 进程，此时的剩余资源数暂时满足不了 p0 的最大需求，
接下来是 p2 进程，发现第一种资源的数量也满足不了 p2 的最大需求
之后是 p3 竞争，发现此时的剩余资源数已经可以满足 p3 的最大需求了。所以接下来如果把这些资源全部分配给 p3 的话，那么 p3 肯定可以顺利的执行结束，并且会把他手里的这些资源归还给系统，于是系统当中的资源数量就可以变为 743 这么多，
那么我们再把剩余资源数进行一个更新，再进行第三轮的对比，接下来的对比其实和之前是一样的，这就不再赘述了。经过 5 轮循环之后，可以把 p0，P2，P4 这些进程也依次加入到安全序列当中，最终我们就得到了一个包含所有进程的安全序列。刚才所说所谓的安全性算法。
我们可以很方便的用代码来实现上面的这些流程，无非就是一些数组再加上一些循环的逻辑，我们可以每一轮都从编号比较小的这些进程开始检查，但是实际上如果我们在考试当中一般来说是用笔算的，可以用一种更快的方法来找到安全序列。
比如说刚开始系统当中剩余的资源是 332 这么多，那么经过快速的对比，我们会发现 332 这么多的资源可以满足 p1 和 p3 这两个进程的需求，于是我们可以把 p1 和 p3 直接就都加入安全序列当中。等 p1 和 p3 运行结束，并且归还了自己手里的资源之后，系统当中的资源数就可以 743 这么多。
于是第二轮对比发现，743 这么多的资源已经可以满足剩下的 p0，P2，P4 所有的这些进程的需求了。因此我们就可以把 p0，P2，P4 这些竞争全部都加入安全序列当中，所以这种方法就可以更快的找到一个安全序列。而既然此时是有安全序列的，说明此时系统是处于安全状态的，暂时不可能发生死锁。
接下来我们再来看一个找不到安全序列的例子，我们把各个进程的最大需求稍微数据稍微改一下，相应的最多还需要多少，这个数据也会有一定的更改。
那么刚开始剩余 332 这么多资源，经过对比发现 p1 和 p3 这两个进程是可以得到满足的，所以 p1 和 p3 可以先加入安全序列
但是等 p1 和 p3 归还了系统资源之后，系统的资源数量总共还会有 743 这么多。经过下一轮的对比发现，p0，P2，P4 这几个进程的需求都得不到满足，对于 p0 来说，第一个资源的数量是不够的，对于 p2 来说，第二个资源的数量是不够的。对于 p4 来说，第三个资源的数量是不够的，所以到这一步分析，我们就发现在这种情况下，我们并找不到一个完整的安全序列，所以如果系统的资源分配情况是这样的，就说明此时系统处于不安全状态，是有可能发生死锁的。
那么经过刚才的分析，相信大家应该已经能够理解怎么用安全性算法来判断系统到底是不是处于安全状态了。那么接下来我们来看一下用代码应该怎么实现银行家算法。假设 1 个系统中有 n 个进程，m 种资源，比如说之前咱们举的这个例子就是有 5 个进程，然后 3 种资源，我们可以让每个进程在运行之前先声明一下自己对各种资源的最大需求数，于是可以用一个 n 行 m 列的矩阵，叫做 max 的矩阵来表示各个进程对各种资源的需求最大需求数量。这种 n 行 m 列的矩阵其实可以用二维数组就可以很方便的实现了。
同样的我们可以用一个 n 行 m 列的矩阵，叫做 allocation 的矩阵来表示，此时系统已经给各个进程分配了多少资源，如果把这两个矩阵一相减，我们就可以得到一个逆的矩阵，就是用来表示各个进程最多还需要多少各种资源。
另外我们还可以用一个长度为 m 的一维数组 available，来表示此时系统当中到底还剩余多少资源。像刚才的例子就是还剩余 332，同样的某一个进程向系统申请的资源，我们也可以用一个长度为 m 的一维数组叫做 request 的数组来进行表示。比如说此时进程 p0 向系统提出申请，要第一种资源两个，第二种资源一个，第三种资源一个。
那么根据银行家算法的思想，我们可以预判一下，如果我们答应了这次申请资源的请求，那么是否会导致系统进入不安全状态。
第一步我们需要先检查进程提出的资源申请是否超过了他之前承诺的最大的需求量。我们可以用 request 数组和逆的矩阵对应的那一行进行这些元素依次进行对比。如果说进程提出的请求并没有超过他自己之前所承诺的所需要的最大值的话，那么我们就认为这次申请是合理的，于是我们就可以进入第二步，否则我们就认为出错。
第二步，我们需要判断此时系统当中剩余的资源数量是不是能够满足他的这一次申请的量，如果能够满足，那么我们就可以跳到下一步，如果不能够满足，就意味着此时系统当中尚且没有足够的资源，这样的话进程就应该阻塞等待。
第三步我们需要试探着把资源分配给进程，也就是按照他的请求给他进行分配，并且修改一些相应的数据，但是要注意的是这个地方并不是真的分配，只是用来做预判使用的，如果我们答应了他的请求的话，系统当中可用的资源数就需要减少，也就变成了 121。另外已分配给进程的这些资源数量，也需要做相应的改变，就是 0+2，1+1，0+1，于是这个数值变为了 221 这么多。最后我们还需要更新一下 need，矩阵对应的值就是用前面的减掉，于是得到了一个新的值 532。
所以我们试探着把资源分配给进程的时候，其实改变了这样三组数据之后，我们就可以根据这组数据来用刚才的安全性算法来判断一下此时系统是不是处于安全状态，也就是尝试着找到一个安全序列。如果说安全的话，我们才可以真正的把这些资源分配给进程。如果说此时系统进入了不安全状态，那么我们就需要把这些数据回退到之前的那一步，然后不答应进程的请求，让进程暂时阻塞等待，所以这就是银行家算法的一个流程。
# 小结
所以银行家算法其实也就做了这样几件事，
- 首先是检查本次申请的资源数量是否超过了他之前声明的最大需求数。
- 第二，要检查此时系统剩余的可用资源数是否还能满足这次的请求。如果这两个判断都能通过的话，
- 接下来就可以开始试探着分配，更改各个数据结构。
- 第四步就是结合我们新得到的这一系列数据和安全性算法，来检查这次分配是否会导致系统进入不安全的状态。
那么安全性算法其实要做的事情也很简单，就是要检查当前剩余的可用资源数是否能够满足某个进程的最大需求，如果可以的话，那么进程就可以被加入安全序列，并且之后是肯定可以把进程的资源全部回收的。于是我们更新了系统当中的剩余可用资源数之后，再进行下一轮的检查，不断重复这样的过程，我们就可以知道最终是否可以让所有的进程都加入安全序列
如果能找到安全序列，就证明这次分配是安全的，于是我们就可以真正的把这些资源都分配给进程
而如果找不到安全序列，就说明这次分配是不安全的，所以我们就需要让进程暂时阻塞等待。
在考察银行家算法的时候，一般来说会告诉我们此时系统当中还有多少可用资源，并且会告诉我们 max 矩阵和 allocation 矩阵，我们可以根据这两个矩阵自己来算出逆的矩阵到底是多少，之后我们就可以用这一系列的流程来判断此时系统的安全性如何。那么大家在学习这个算法的时候，一定要先理解他这个算法的逻辑，然后再尝试着用自己用这个代码去实现这个逻辑，而不是反过来先钻到代码里，再来想代码表示的逻辑是什么样的，这样的话很容易蒙圈。那么除了这个算法的具体步骤之外，之前提到的不安全状态和死锁还有安全状态，他们之间的关系也经常容易在选择题当中进行考察，这个小节的内容十分重要，大家还需要再回归课本，并且结合课后习题进一步的巩固。
