操作系统重点知识——银行家算法

操作系统重点知识——银行家算法

首先来介绍一下什么是银行家算法,银行家算法是最具代表性的避免死锁的方法。
这个算法因为本来是为银行设计的而得名,这种算法的提出能保证银行在发送贷款的时候,不会发生不满足所有用户需要的情况。
联系到操作系统上就是:每一个新进程进入系统时,必须声明需要每种资源的最大数目,其数目不能超过系统所拥有的的资源总量。当进程请求一组资源时,系统必须首先确定是否有足够的资源分配给该进程,若有,再进一步计算在将这些资源分配给进程后,是否会使系统处于不安全状态如果不会才将资源分配给它,否则让进程等待。
银行家算法中的数据结构
(1)Available向量:系统中可利用的资源数目
(2)Max矩阵:每个进程对每种资源的最大需求
(3)Allocation矩阵:每个进程已分配的各类资源的数目
(4)Need矩阵:每个进程尚需的各类资源数

书本上面的算法介绍太枯燥,这里就不再拿出来讲解,直接用一个例子来说明一下吧。

假定系统中有五个进程{p0,p1,p2,p3,p4}和三类资源{A,B,C}各类资源的数目分别是10,5,7,已知T0时刻资源分配情况如下:
操作系统重点知识——银行家算法_第1张图片如上图所示是我们的已知条件也就是我们开始时候的资源分配状态,接下来我们要求这个状态下的安全序列,也就是将可利用的资源分配给某个需要资源小于可利用资源的进程,让这个进程运行完成,进程运行完成之后已分配的资源就会被释放,然后继续执行上述操作,只要能找到满足Need小于Available,就分配资源,让该进程运行完成,最后将资源释放,也就是将已分配的资源加到可利用的资源,如果最后每一个进程都能运行完成就得到了我们的安全序列,所以系统就是安全的,如果存在一个进程,可利用资源不能满足需求就不再分配。

我们来简单介绍一下过程:
(1)将Available和Need对比,P0的Need>Available,不满足,往后找,
(2)P1的Available小于Need分配给P1,P1就能运行完成,最后释放资源{2,0,0}
所以现在的资源就是{3,3,2}+{2,0,0}={5,3,2}
(3)然后继续向下找,p2不满足条件,P3满足条件,将资源分配给P3,让其运行完成,并释放空间{2,1,1},所以现在的资源就是{5,3,2}+{2,1,1}={7,4,3}
(4)依次类推得到安全序列为{P1,P3,P4,P2,P0}

过程如下图,其中finish表示进程运行完成
操作系统重点知识——银行家算法_第2张图片因此,我们知道该系统是安全的。

下来再来一个问题假设P1请求资源Request{1,0,2},要怎样处理呢?
首先要检测看请求资源是不是比可利用资源和需要资源小,如果其中一个或两个条件都不满足,进程等待,如果满足进行下面操作,
这里{1,0,2}是满足这两个条件的
我们进行的操作就是将请求资源加到Allocation上面,也就是已分配的资源得到扩充,同样的请求的资源一定是来自可利用资源的,所以可利用资源要减上一个请求资源数目,因为Need和Allocation的和是一个固定值max所以相应的Allocation加上一个数值,Need就要减上一个数值,变化之后如下图所示:
操作系统重点知识——银行家算法_第3张图片然后再像前面一样,把这个表当成T0时刻的资源分配状态,再来找安全序列,判断系统是不是安全的。

好了,银行家算法就讲解到这里,希望对大家有所帮助。

你可能感兴趣的