下面我们来讨论银行家算法
银行家算法是一种死锁避免的方法
它指的是说
我们以银行贷款分配的策略为基础
通过判断系统是否处于安全状态
来确定我这一次的资源分配是否同意
这里借用的银行贷款分配策略是这样的
客户在申请贷款的时候
那你必须告诉银行
你最大的资金申请量是多少
并且保证在你的项目执行完毕之后
能及时归还贷款
对于我们操作系统里的
银行家算法也是有类似的要求的
从银行这个角度来说
它只要保证用户贷款的数量
不超过银行的最大值
那么这银行就应该尽可能的
满足客户的需求
也就是说银行手里头没钱不行
有钱不把它借给客户
实际上它的利用效率也是很低的
那这个比喻呢
我们可以这样来进行对应
银行家对应着我们这是操作系统
银行家要来判断
我借出去这笔钱行是不行
安全不安全
操作系统需要来判断
我这个资源分配出去是否安全
那银行家借的是资金
这是它的资源
对于我们操作系统来说
我的CPU内存
这是我的资源
银行家应对的是客户
而操作系统应对的
是申请资源的线程或者是进程
具体怎么做呢
首先它要对系统的状态
有一系列的记录
你比如说在我们这里头
假定系统里的线程数目是N
然后资源的种类是M
这时候呢 它们有一个矩阵
M乘N的矩阵
表示每一个线程
它需要申请的每一类资源的总数
那有了这个数字之后呢
这里的一行
那肯定是小于我系统里
所拥有的所有资源的总量
这是一个最基本的限制
第二个是说我系统里的剩余资源
这地方是一个长度为M的向量
也就相当于系统里有M总资源
每一种资源当前还剩多少
再有一个是分配矩阵
这里描述是已经分配给
每一个线程的各类资源的数目
以便能够知道它和总量之间
到底是个什么样的关系
已经分配出去
不能大于每个进程
在起头的时候声称的总量
再有一个就是还有一个未来需要的量
这也是一个M乘N的矩阵
每一个线程它还需要M类的资源里的
每一种各需要多少 那从这
这几个向量和矩阵之间
有这样一个关系
最大的和未来需求的
和已经分配的它们构成一个等式
未来需要的等于最大的
减去你已经分配的
这是银行家算法在运行过程当中
需要维护的信息
也就是说它需要知道
我现在总共有多少资源
哪些已经分配出去了
哪些还是空闲的
这是它必须掌握的 否则的话
它没有办法判断到底是否处于安全
然后在这里就有一个安全的判断算法
这里头呢 它的做法是说
我们把现在可用的资源复制一下
作为我当前进行判断的一个工作场所
然后就看在这个状态下
是不是我可以满足
当前已经分配过资源的这些线程
它的总的需求
如果能满足
表示我当前这种状态下
可以把所有已经分配出去的资源
最后在用户用完之后能够回收回来
如果不是这样的话
它就是不安全的 那在这呢
每一个线程有一个状态
false表示当前还没有运行完
如何来判断当前是否安全呢
它就是在所有这些线程里头去查找
我未来需要的资源的总量
是否小于我当前有的这些资源总量
并且当前这个线程是没有执行完的
如果能找到这种情况
那实际上就说明我当前的可用资源
是可以满足某一个线程的
未来的所有需要的
那这时候呢
我能把它的资源给回收回来
如果你找了一圈之后没有找到
那这时候呢
就相当于是不安全了
如果找到那这时候呢
我就会把资源放回到可用资源里
就是放回到work里
同时把它的状态改为true
也就是说这个线程结束了
然后我再回到这来继续找
到最后所有的都满足
或者说有一个不满足
但是我找不着剩余的资源
可以满足某一个线程未来的需要
那这是最后一步
是否所有的线程
都已经变成完成状态
如果不是 它就是不安全的
如果是那这时候它就是安全的
这是银行家算法里头最核心的部分
基本的思路就是我当前的剩余资源
可以满足某一个线程的未来需要
并且这种迭代循环到最后
能够满足所有的线程的需要
也就相当于我找到了一个安全序列
有了这个基本的判断之后
我们的银行家算法说起来就简单了
每一次请求的时候
我来判断这个请求是否安全
首先第一个判断
这个请求的资源量
和最大的需求量比较
它是不是比它小
需要的资源量和你当前申请的资源量
如果说你现在就已经超了
那肯定这就已经报错了
那我就拒绝分配给你相应的资源
如果满足我需求的量
还没有到我声称的最大量
那这时候呢
就进入第二步判断
看我现在可用的资源是不是够你用的
如果不够用线程必须等待
如果说够用
再来判断我现在这个是不是安全
怎么来判断呢
假定你把当前的用户申请允许了
把资源分配给它了
然后看我是不是能找到一个安全序列
假定你已经把用户的请求分配完毕了
这三个矩阵或者是向量
它的状态发生变化
然后我们调用前边的
安全状态判断算法
来对它进行判断
判断完的结果有两个
一个是安全的
一个是不安全的
如果安全的 那我同意分配
并且把资源分配给相应用户
如果不安全那这时候
我前边就已经拒绝
或者说到这我也再拒绝
这是银行家算法
那这个算法到底怎么来用呢
我们下边通过一个例子来说明
最主要的部分就是
判断这个状态是否安全
假定给一个初始状态
这是我系统里的总的资源数目
R1、R2、R3
分别是9、3、6
它的资源总数
这是四个线程
它们所声称的资源需求总量
每一个的总量都小于我这个
比如最大是9
R1没有大于9的
如果说这时候就有一个
那你直接告诉它这事是不行的
这是我已经分配出去
到当前这个状态的
这两个矩阵相减就是未来它需要的
这时候我也可以告诉你我当前剩余的
那这个状态是否安全呢
我们需要判断的就是未来需要的量
和我当前所剩余的这些资源比较而言
是不是我可以找到一个序列
最后把所有的资源全部收回
我们对照了一下
第一次你可以找谁
1、2、3、4
最后一个资源只有这一个
T2是我正好所有的都满足的
因为它只要R3
我这里R3有 OK
这事行了
假定我把T2的需求满足分配
给它一个R3资源 这时候呢
我就可以把这里
它用到的资源就都给收回来了
那么这时候我这就变成6、2、3
我分配完之后的状态是这样的
原来这两个的状态就都清零了
我这的状态变成6、2、3
然后这时候说我是安全的吗
实际上我们看下去
我这的剩余资源可以满足
剩下的三个线程任何一个
当前执行都是可以的
那这样的话
我又可以把它们的都给回收回来
再来 这样的话
我们就看到最后剩一个
这肯定满足
所以我们说这个状态是安全的
那我们再换一个例子来看
在这地方同样是当前资源总数
各个线程需要的资源总量
以及与我已经分配出去的状态
和未来各个线程需要的资源量
和我当前的状态
用户再想分配一个变成这种状态
T1请求R1和R3各一个资源
变成现在这种状态了
那这种状态是安全的吗
我们说如果你敢这么分配
分配完了之后
剩余的资源就已经没有办法满足
这四个线程当中的任意一个
未来的需要了
这个可以满足剩下的R2
都是不满足的了
两个就不行
然后R3的话
那这两个不行
所以最后你就没有办法找到一个
当前资源够某一个线程未来所有的需要
所以这个状态是不安全的
如果说T1请求R1和R3资源数个数为一的话
那么这个请求呢
你是不能同意的
同意了你这个系统就是不安全的了