admin 管理员组文章数量: 887019
银行家算法
一、实验目的
加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。要求编写和调试一个系统动态分配资源的简单模拟程序，观察死锁产生的条件，并采用银行家算法，有效的防止和避免死锁的发生。
二、实验原理
银行家算法中的数据结构
(1)可利用资源向量Available：是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available［j］=K，则表示系统中现有Rj类资源K个。
(2)最大需求矩阵Max：是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max［i,j］=K，则表示进程i需要Rj类资源的最大数目为K。
(3) 分配矩阵Allocation：也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation［i,j］=K，则表示进程i当前已分得Rj类资源的数目为K。
(4)需求矩阵Need：也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need［i,j］=K，则表示进程i还需要Rj类资源K个，方能完成其任务。
Need［i,j］=Max［i,j］-Allocation［i,j］
算法描述：
设Requesti是进程Pi的请求向量，如果Requesti［j］=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：
(1)如果Requesti［j］≤Need［i,j］，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
(2)如果Requesti［j］≤Available［j］，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。
(3)系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：
Available［j］∶=Available［j］-Requesti［j］;
Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;
Need［i,j］∶=Need［i,j］-Requesti［j］;
(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。
安全性检查 :
(1)设置两个向量：
① 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work∶=Available;
② Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish［i］∶=false; 当有足够资源分配给进程时， 再令Finish［i］∶=true。
(2)从进程集合中找到一个能满足下述条件的进程：
① Finish［i］=false;
② Need［i,j］≤Work［j］； 若找到， 执行步骤(3)， 否则，执行步骤(4)。(3)当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
Work［j］∶=Work［i］+Allocation［i,j］;
Finish［i］∶=true;
go to step 2;
(4)如果所有进程的Finish［i］=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。
三、实验操作方法和步骤
本实验要求通过编写和调试一个系统动态分配资源的简单模拟程序，观察死锁产生的条件，并采用适当的算法，有效地防止和避免死锁地发生。具体要求如下：
（1）模拟一个银行家算法，判断是否处于安全状态；
（2）初始化时让系统拥有一定的资源；
（3）用键盘输入的方式申请资源；
（4）如果预分配后，系统处于安全状态，则修改系统的资源分配情况，判断其安全序列；
（5）如果预分配后，系统处于不安全状态，则提示不能满足请求；
设计的主要内容是模拟实现动态资源分配，观察死锁产生的条件，并使用适当的算法，有效的防止和避免死锁的发生。
四、实验结果与分析
1、对安全性检测部分代码进行截图，并进行简要说明
(1)设置两个向量:①工作向量Work,它表示系统可提供给进程继续运行所需的各类
资源数目,它含有m个元素,在执行安全算法开始时,Work= Available;② Finish:它表
示系统是否有足够的资源分配给进程,使之运行完成。开始时先做 Finish]= false;当有足
够资源分配给进程时,再令 Finish[i]=tnue
(2)从进程集合中找到一个能满足下述条件的进程
① Finish[il= false;
② Needi, i]s Work]
若找到,执行步骤(3),否则,执行步骤(4)。
(3)当进程P获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应
执行:
Work[il= Work[]+ Allocation[i,j
Finishi=true,
go to step 2,
(4)如果所有进程的 Finish[]=tne都满足,则表示系统处于安全状态;否则,系统处于不安全状态。
2、对最终的银行家算法部分代码进行截图，并进行简要说明
3、对运行结果进行截图，并进行简要说明
假定系统中有4个进程{pr1,pr2,pr3,pr4}和三类资源{A，B，C}各种资源的数量为3，3，2，t0时刻的资源分配情况如下图所示：
（1） TO时刻的安全性：利用安全性算法队T0时刻的资源分配情况进行分析，在T0时刻存放着一个安全序列{P1,P2,P3,P4,P0}，故系统时安全的。
（2） P1请求资源：P1发出请求向量Request(1,0,2),系统按银行家算法进行检查：
① Request(1,0,2)<=Need（1,2,2）
② Request(1,0,2)<=Available1（3,3,2）
③ 系统先设定为P1分配资源，并修改Available，Allocation和Need向量。
④ 再利用安全性算法检查此时系统是否安全。
（3） P4请求资源：P4发出请求向量Request（3,3,0）系统按银行家算法进行检查：
① Request（3,3,0）<=Need(4,3,1);
② Request（3,3,0）> Available1 (2,3,0);
（4）P0请求资源：P0发出请求向量Request（0,2,0）系统按银行家算法进行检查：
① Request（0,2,0）<=Need(7,4,0);
② Request（0,2,0）<= Available1 (2,3,0);
③ 系统暂时先设定为P0分配资源，并修改相关数据
版权声明：本文标题：银行家算法实验 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1727379202h1111353.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论