《银行家算法实验报告.doc》由会员分享，可在线阅读，更多相关《银行家算法实验报告.doc（13页珍藏版）》请在三一文库上搜索。
1、银行家算法实验报告一、 设计目的银行家算法是是最具有代表性的避免死锁的算法，由于该算法能用于银行系统现金贷款而得名。该算法能够进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念。二、 设计要求根据银行家算法的基本思想，编写和调试一个动态分配的模拟程序，并能够有效的防止和避免死锁的发生。三、 设计思想银行家算法：我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分
2、配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。1、 银行家算法中的数据结构1）可利用资源向量Available 是个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果Availablej=K，则表示系统中现有Rj类资源K个。 2）最大需求矩阵Max 这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi,j=K，则表
3、示进程i需要Rj类资源的最大数目为K。 3）分配矩阵Allocation 这也是一个nm的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi,j=K，则表示进程i当前已分得Rj类资源的 数目为K。 4）需求矩阵Need 这也是一个nm的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j=K，则表示进程i还需要Rj类资源K个，方能完成其任务。 Needi,j=Maxi,j-Allocationi,j2、 银行家算法设进程Pi提出请求Request(i) j，如果Request(i)j=k,表示进程Pi需要K个R(j)类型的资源。当Pi发出请求后，系统
4、按下述步骤进行判断： (1)如果Request (i) j= Needij，则转(2)；否则，出错。 (2)如果Request (i) j= Availablej，则转(3)；否则，出错。 (3)系统试探分配资源，修改相关数据： Available j= Available j-Request (i) j;Allocationij= Allocationij+Request (i) j; Needij= Needij-Request (i) j; (4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。3、安全算法1)设置两个工作向量Work:=Availa
5、ble;Finish (2)从进程集合中找到一个满足下述条件的进程， Finishi=false; Needij=Workj; 如找到，执行(3)；否则，执行(4) (3)设进程获得资源，可顺利执行，直至完成，从而释放资源。 Workj= Workj+Allocationi,j; Finishi=true; Go to 2 (4)如所有的进程Finishi= true，则表示安全；否则系统不安全。四、流程图初始化函数input()开始 输入资源种类数 输入进程的数量输入可利用的资源数输入最大需求Max所需要的Need0Error;初始化函数input（）结束，银行家函数Resquest()提出
6、请求RequestiError;Requesti=NeediRequestTi=AvailableiError;分配错误！ IsSafe();分配成功！Availablei-=Requesti；Allocationi-=Requesti;Needi+=Requesti；Availablei-=Requesti;Allocationi+=Requesti;Needi-=Requesti;是否进行再次分配退出程序银行家算法Resquest()结束;安全性算法IsSafe()开始Work=Available;Finish=false；Needi=Work&Finishi=false;Work+=Al
7、locationi;Finishi=ture;所有进程的FINISH=ture；输出提示：系统是不安全的安全，输出安全序列Return ture；安全算法IsSafe()结束五、源代码package com.huyanmin;import java.util.Scanner;public class Data public int available = new int50;public int max =new int5050;public int need = new int5050;public int allocation=new int5050;public int m,n;publ
8、ic void Input()Scanner input = new Scanner(System.in);System.out.println(请输入资源个数：);m = input.nextInt();System.out.println(请输入进程数：);n = input.nextInt();System.out.print(请输入可利用资源的数目：);for(int i=0;im;i+)int s = input.nextInt();availablei=s;System.out.print(请输入每个进程每类资源的最大需求量：);for(int i =0;in;i+)for(int
9、 j =0;jm;j+)maxij = input.nextInt();System.out.print(请输入每个进程的已分配的资源数：);for(int i =0;in;i+)for(int j =0;jm;j+)allocationij = input.nextInt();for(int i =0;in;i+)for(int j =0;jm;j+)needij = maxij-allocationij;if(needij0)System.out.println(资源不足，请重新输入已分配资源：);for( i =0;in;i+)for(j =0;jm;j+)allocationij =
10、input.nextInt();needij = maxij-allocationij;public void Output()System.out.println(进程 Max Need Allocation Available );for(int i=0;in;i+)System.out.print(i+ );for(int j=0;jm;j+)System.out.print( +maxij);System.out.print( );for(int j=0;jm;j+)System.out.print( +needij);System.out.print( );for(int j=0;j
11、m;j+)System.out.print( +allocationij);System.out.print( );for(int j=0;jm;j+)System.out.print( +availablej);System.out.println();package com.huyanmin;public class IsSafe public int work = new int50;public boolean finish=new boolean50;public int index=0;public void isSafe(Data data)for(int i=0;idata.m
12、;i+)worki = data.availablei;for(int i=0;idata.n;i+)finishi=false;for(int f=0;fdata.n;f+)for(int i=0;idata.n;i+)if(bj(i,data)=true & finishi=false)finishi=true;for(int c=0;cdata.m;c+)workc=workc+data.allocationindexc;index=i;break;int ss =0;for(int i=0;idata.n;i+)if(finishi=true)ss+;if(ss=data.n)show
13、(data);elseSystem.out.println(系统不安全,没有安全序列);data.Output();public void show(Data data)for(int i=0;idata.m;i+)worki = data.availablei;for(int i=0;idata.n;i+)finishi=false;System.out.println(安全序列表：);System.out.println(进程 work need allocatin work+allocation finish);for(int f=0;fdata.n;f+)for(int i=0;ida
14、ta.n;i+)if(bj(i,data)=true & finishi=false)finishi=true;index=i;System.out.print(index+ );for(int s=0;sdata.m;s+)System.out.print( +works);System.out.print( );for(int s=0;sdata.m;s+)System.out.print( +data.needindexs);System.out.print( );for(int s=0;sdata.m;s+)System.out.print( +data.allocationindex
15、s);System.out.print( );for(int s=0;sdata.m;s+)System.out.print( +(works+data.allocationindexs);System.out.print( );System.out.println(finishindex);for(int c=0;cdata.m;c+)workc=workc+data.allocationindexc;break;public boolean bj(int i,Data data)int a =0;for(int l=0;l3;l+)if(data.needil=0)a+;if(a=3)re
16、turn true;return false ;package com.huyanmin;import java.util.Scanner;public class Resquest public int request=new int50;IsSafe is = new IsSafe();public void request(Data data)System.out.println(请输入第几个进程请求：);Scanner input =new Scanner(System.in);int num = input.nextInt();System.out.print(各资源请求数量：);f
17、or(int i=0;idata.m;i+)int s = input.nextInt();requesti=s;if(Compare(num,data)=true & Compare1(data)=true )for(int j=0;jdata.m;j+)data.availablej=data.availablej-requestj; data.allocationnumj=data.allocationnumj+requestj;data.neednumj=data.neednumj-requestj;is.show(data);if(Compare3(num,data)=true )f
18、or(int j=0;jdata.m;j+)data.availablej=data.availablej+data.allocationnumj;data.allocationnumj=0;data.maxnumj=0;data.Output();for(int j=0;jdata.m;j+)if(is.workj!=0) request(data);elsebreak;elseSystem.out.println(系统资源不足，请等待.);request(data);public boolean Compare(int i,Data data)int a=0;for(int j=0;jda
19、ta.m;j+)if(requestj=data.needij)a+;if(a=data.m)return true;return false;public boolean Compare1(Data data)int a=0;for(int j=0;jdata.m;j+)if(requestj=data.availablej)a+;if(a=data.m)return true;return false;public boolean Compare3(int i,Data data)int a=0;for(int j=0;jdata.m;j+)if(data.needij=0)a+;if(a
20、=data.m)return true;return false;package com.huyanmin;public class Test public static void main(String args) Data data = new Data();data.Input();data.Output();IsSafe is = new IsSafe();is.isSafe(data);Resquest re = new Resquest();re.request(data);运行结果：请输入资源个数：2请输入进程数：3请输入可利用资源的数目：2 2请输入每个进程每类资源的最大需求量
21、：4 33 35 2请输入每个进程的已分配的资源数：1 12 22 1进程 Max Need Allocation Available 0 4 3 3 2 1 1 2 21 3 3 1 1 2 2 2 22 5 2 3 1 2 1 2 2安全序列表：进程 work need allocatin work+allocation finish1 2 2 1 1 2 2 4 4 true0 4 4 3 2 1 1 5 5 true2 5 5 3 1 2 1 7 6 true请输入第几个进程请求：1各资源请求数量：1 1安全序列表：进程 work need allocatin work+allocat
22、ion finish1 1 1 0 0 3 3 4 4 true0 4 4 3 2 1 1 5 5 true2 5 5 3 1 2 1 7 6 true进程 Max Need Allocation Available 0 4 3 3 2 1 1 4 41 0 0 0 0 0 0 4 42 5 2 3 1 2 1 4 4请输入第几个进程请求：2各资源请求数量：3 1安全序列表：进程 work need allocatin work+allocation finish1 1 3 0 0 0 0 1 3 true2 1 3 0 0 5 2 6 5 true0 6 5 3 2 1 1 7 6 true
23、进程 Max Need Allocation Available 0 4 3 3 2 1 1 6 51 0 0 0 0 0 0 6 52 0 0 0 0 0 0 6 5请输入第几个进程请求：0各资源请求数量：3 2安全序列表：进程 work need allocatin work+allocation finish0 3 3 0 0 4 3 7 6 true1 7 6 0 0 0 0 7 6 true2 7 6 0 0 0 0 7 6 true进程 Max Need Allocation Available 0 0 0 0 0 0 0 7 61 0 0 0 0 0 0 7 62 0 0 0 0
24、 0 0 7 6六、课程设计的总结 在多道程序系统中，多个进程的并发执行来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险死锁。所谓死锁(Deadlock)，是指多个进程在运行过程中因争夺资源而造成的一种僵局（DeadlyEmbrace），当进程处于这种状态时，若无外力作用，他们都无法在向前推进。要预防死锁，有摒弃“请求和保持”条件，摒弃“不剥夺”条件，摒弃“环路等待”条件等方法。但是，在预防死锁的几种方法之中，都施加了较强的限制条件；而在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统状态分为安全状态和不安全状态，便可避免死锁的发生。而最具代表性的避免死锁的算法，便是Dijkstra的银行家算法。利用银行家算法，我们可以来检测CPU为进程分配资源的情况，决定CPU是否响应某进程的的请求并为其分配资源，从而很好避免了死锁的产生。 操作系统课程设计-课程设计题目：银行家算法学院:计算机科学与工程专业:计算机科学与技术班级：090602学号：090602126姓名：胡艳敏