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