今热点:什么是银行家算法 是最著名的死锁避免算法 会测试进程对资源的最大需求量

1、银行家算法介绍

银行家算法是最著名的死锁避免算法。当进程首次申请资源时,要测试该进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量时,则按当前的申请量分配资源,否则,推迟分配。

2、数据结构描述


【资料图】

2.1、可利用资源矢量Avaiable

含有m个元素的数组,其中的每一个元素代表一类可用的资源数目。Available[j]=k,则表示系统中现有Rj类资源K个。

2.2、最大需求矩阵Max

为n×m矩阵,定义了系统中n个进程中的每一个进程对m类资源的最大需求。Max[i,j]=K,则表示进程i需要Rj类资源最大数目为K

2.3、分配矩阵Allocation

为n×m矩阵,定义了系统中每一类资源当前已分配给每一进程的资源数。Allocation[i,j]=K,则表示进程i当前已分配得Rj类资源的数目为K。

2.4、需求矩阵Need

为n×m矩阵,表示每个进程尚需的各类资源数,Need[i,j]=K,则表示进程i还需要Rj类资源数目为K

3、银行家算法描述

3.1、银行家算法

设Request i是进程Pi的请求矢量,如果Request i[j]=K,表示进程Pi需要Rj类资源K个。当Pi发出资源请求后,系统按下述步骤进行检测:

1、如果Request i[j] ≤Need[i,j],便转向步骤2,否则认为出错,因为它所需的资源数超过了它所宣布的最大值。2、如果Request i[j] ≤Available[i,j],便转向步骤3,否则,表示尚无足够资源,Pi须等待3、系统试探着把资源分配给进程Pi,并修改下面数据结构中的数值:Available[j]=Availabe[j]-Request i[j]Allocation[i,j]=Allocation[i,j]+Request i[j]Need[i,j]=Need[i,j]-Request i[j]4、系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配;否则,将本次试探分配作废,恢复原来的资源分配状态,让进程Pi等待。

3.2、安全性算法

1.设置两个矢量。

工作矢量Work;它表示系统可提供给进程继续运行所需的各类资源数目,它含有m个元素,在执行安全算法开始时,Work=Available;Finish:它表示系统是否有足够的资源分配给进程,使之运行完成。开始时Finish[i]=false;当有足够资源分配给进程Pi时,再令Finish[i]=true;

2.从进程集合中找到一个能满足下述条件的进程:

Finish[i]=false;Need[i,j]=Work[j];

若找到,执行下一步骤,否则,执行步骤4

3.当进程Pi获得资源后,可顺利执行,直至完成,并释放分配给它的资源,共应执行:

Work[j]=Work[j]+Allocation[i,j];Finish[i]=true;go to step (2)

4.如果所有进程的Finish[i]=true满足,则表示系统处于安全状态;否则系统将处于不安全状态

4、银行家算法举例

假设系统中有5个进程{P0,P1,P2,P3,P4}和三类资源{A,B,C},各种资源的数量分别为10、5、7,在T0时刻资源分配情况见下表:

T0时刻资源分配情况

利用安全性算法对T0时刻资源分配进行分析,由下表可知,在T0时刻存在着一个安全序列{P1,P3,P4,P2,P0},故系统是安全的。

P1请求资源:P1发出请求矢量Request 1(1,0,2)系统按银行家算法检查:

Request 1(1,0,2)≤Need 1(1,2,2)Request 1(1,0,2)≤Available1(3,3,2)系统先假定可为P1分配资源,并修改Available 1、Allocation 1和Need 1矢量,由此形成的资源变化情况可见下表。再利用安全性检查此时系统是否安全。

P4请求资源:P4发出请求矢量Request 4(3,3,0),系统按银行家算法进行检查:

Request 4(3,3,0)≤Need 4(4,3,1)Request 4(3,3,0)>Available(2,3,0),让P4等待

P0请求资源:P0发出请求矢量Request 0(0,2,0),系统按银行家算法进行检查:

Request 0(0,2,0)≤Need 0(7,4,3)Request 0(0,2,0)≤Available(2,3,0)

系统暂时假定可为P0分配资源,并修改有关数据,如下表

进行安全性检查,可以资源Available(2,1,0)已不能满足任何进程需要,故系统进入不安全状态,此时系统不分配资源。

推荐DIY文章
windows rt是什么系统 Windows rt不支持的软件都有哪些
怎么安装word2010软件 希望本篇安装教程对你有所帮助|天天热门
联想g400怎么进入BIOS设置 带有NOVO按键的机型都可以怎么操作-环球微动态
w10怎么用u盘重装系统教程 重启过程中需要卸载U盘吗
Windows10系统识别不了USB设备的三种解决方法 可以重新安装USB控制器 每日短讯
电脑中运行非简体中文游戏程序显示乱码如何解决 怎么选择程序相应的语言 天天新要闻
精彩新闻

超前放送