本文主要是介绍死锁避免——银行家算法(简述),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1.算法介绍
银行家算法最早是为解决银行贷款问题而提出的,在多个用户申请贷款时,首先要确定资源充足,也就是申请资源数目不应超过系统拥有的资源总量,如果符合,则认为系统处于安全状态,把资源分配给该进程,否者,认定系统处于不安全状态,让进程等待,等待其他进程释放资源后,再做处理。
2.算法变量
由于算法的需要,我们要设置4个变量,分别为:
- 当前可利用资源(Available):表示当前可利用的资源数目。这个比以下的三个变量要高一个层面。如果Available[j]=K,则表示系统中现有Rj类资源K个。
- 最大需求(Max): 表示某个进程对某种资源的最大需求。如果Max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K。
- 当前分配资源数(Allocation):表示某个进程当前以分得某类资源的数目。如果Allocation[i,j]=K,则表示进程i当前已分得Rj类资源的数目为K。
- 需求(Need):表示某个进程离完成任务还需的各类资源数。如果Need[i,j]=K,则表示进程i还需要Rj类资源K个,方能完成其任务。
注:R为资源集合的类型。
有关系:
Need[i, j]=Max[i, j]-Allocation[i, j]
3.算法内容
银行家算法又包含了安全性算法,两者共同构成了银行家算法,下面就来说一下两种算法的步骤和联系。
3.1银行家算法
设Request i是进程Pi的请求向量,如果Requesti[j]=K,表示进程Pi需要K个Ri类型的资源。当Pi发出资源请求后,系统按下述步骤进行检查:
-
因为,它所需要的资源数不能超过它的最大值。所以要满足:Requesti [j]<=Need[i,j]
-
然后要有足够多的资源,所以要满足:Requesti [j]≤Available[j]
-
系统试探着把资源分配给进程Pi,并修改下面数据结构中的数值:
Available[j]:= Available[j]-Requesti[j];
Allocation[i,j]:= Allocation[i,j]+Requesti[j];
Need[i,j]:= Need[i,j]-Requesti[j];
-
运用安全性算法来检查安全性,从而决定是否真正要分配资源。
3.2安全性算法
首先设置两个变量:
-
Work:它表示系统可提供给进程继续运行所需的各类资源数目,开始默认值Work=Available。
Finish:它表示系统是否有足够的资源分配给进程,使之运行完成。开始时Finish[i]=false;当有足够资源,再令Finish[i]=true。 -
从进程集合中找到一个能满足下述条件的进程:
(1). Finish[i]=false;
(2). Need[i,j]≤Work[j];
- 若能找到符合上面两个条件的进程,执行步骤3,依次对所以进程进行测试。
- 当所有进程满足Finish[i]=true 或者 有一个进程不满足 Need[i,j]≤Work[j]时,执行步骤4,来判断是否处于安全状态。
-
当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:
(1) Work[j]:= Work[j]+Allocation[i,j];
(2) Finish[i]:=true;
(3) 重复执行步骤2
-
如果所有进程的Finish[i]=true都满足,则表示系统处于安全状态;否则,系统处于不安全状态。
这篇关于死锁避免——银行家算法(简述)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!