实验银行家算法.pdf

《实验银行家算法.pdf》由会员分享，可在线阅读，更多相关《实验银行家算法.pdf（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、 实 验 银 行 家 算 法 精品好文档，推荐学习交流 仅供学习与交流，如有侵权请联系网站删除 谢谢10 实验三 银行家算法 一、实 验目的和意义 了解掌握银行家算法，学会模拟实现资源分配，同时有要求编写和调试一个系统分配资源的简单模拟程序，观察死锁产生的条件，并使用适当的算法，有效的防止和避免死锁的发生 二、方案设计及开发过程 1.实验背景 在多道程序系统中，虽可借助与多个进程的并发执行，来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险-死琐。产生死锁的原因可归结为两点：1：竞争资源。当系统中供多个进程共享的资源如打印机、公用队列等，其数目不足以满足诸进程的需要时，会引起诸进程对

2、资源的竞争而产生死锁。2：进程间推进顺序非法。进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。最有代表性的避免死锁的算法，是 Dijkstra 的银行家算法。这是由于该算法能用与银行系统现金贷款的发放而得名的。2.算法描述 设 Requesti 是进程 Pi 的请求向量，如果 Requestij=K,表示进程 Pi 需要K 个 Rj 类型的资源，当 Pi 发出资源请求后，系统按下面步骤进行检查：（1）如果 Requestij=Needi,j，便转向步骤 2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。（2）如果 Requestij=Availablej,便转

3、向步骤 3；否则，表示尚无足够资源，Pi 须等待。（3）系统试探着把资源分配给进程 Pi，并修改下面数据结构中的数值：Availablej:=Availablej-Requestij;Allocationi,j:=Allocationi,j+Requestij;Needi,j:=Needi,j-Requestij;精品好文档，推荐学习交流 仅供学习与交流，如有侵权请联系网站删除 谢谢10（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程 Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程 Pi 等待。3.数据结构 银

4、行家算法中的数据结构：（1）可利用资源向量 Available。这是一个含有 n 个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果 Availablej=K,则表示系统中现有 Rj 类资源 K 个。（2）最大需求矩阵 Max。这是一个 m*n 的矩阵，它定义了系统中 n 个进程中每一个进程对 m 类资源的最大需求。如果 Maxi,j=K,则表示进程 i 需要 Rj 类资源的最大数目为 K。（3）分配矩阵 Allocation。这也是一个 m*n 的矩阵，它定义了系统中每一类资源当前已分配给每一

5、进程的资源数。如果 Allocationi,j=K,则表示进程i 当前已分得 Rj 类资源的数目为 K。（4）需求矩阵 Need。这也是一个 n*m 的矩阵，用以表示每一个进程尚需的各类资源数。如果 Needi,j=K,则表示进程 i 还需要 Rj 类资源 K 个，方能完成其任务。(5)工作数组 Work.。这是一个含有 n 个元素的数组，它代表可以提供分配的资源数，初始值是 Available 中的数值，随着资源的回收，它的值也会改变，公式是 Worki=Worki+Allocationi。4.主要函数说明 主要函数主要有四个：（1）Main()主函数：用来显示资源的分配情况和提示信息，同时

6、用 Main 函数来调用其它子程序。（2）Safe()函数：用来检查是否有安全序列，如果存在则返回一个 1给主函数，否则返回 0。(3)Disp()函数：用来显示随机生成的资源包括 Max、Need、Allocation、Available。精品好文档，推荐学习交流 仅供学习与交流，如有侵权请联系网站删除 谢谢10 程序初始化 随机分配资源 并显示在屏幕 检查安全序列 是否要申请资源 输入 Request RequestNeed RequestAvailable Needij=Needij-Requestj Availablej=Availablej-Requestj 报错 检查安全序列 保留

7、原始 Available、Request 恢复原始 Available、(4)Request()函数：用来进行资源请求，分为手动的和随机申请。同时对申请的资源进行判断，检查申请是否有效，如果有效则返回一个 1给主函数，否则返回 0。5.算法流程图 N Y Y N N Y 精品好文档，推荐学习交流 仅供学习与交流，如有侵权请联系网站删除 谢谢10 N Y Y 三、调试记录与分析 在调试过程中为了显示安全序列的检查状况，在检查 Available 是否满足 Need 时要检查 m*n遍，并存在表达有歧异，经过修改后，就不需要全部检查，而是 Available 只要有一个不满足 Need 就停止检查

8、。图 3.1 修改前 图 3.2 修改后 精品好文档，推荐学习交流 仅供学习与交流，如有侵权请联系网站删除 谢谢10 四、运行结果及说明 图 4.1.不存在安全序列 随机分配完资源后，进行安全检查，在检查过程中在屏幕上显示检查信息，上图为资源分配不安全时显示的信息。图 4.2.存在安全路径 存在安全路径后，在屏幕上显示变化过程和安全路径。提示是否申请资源 图 4.3.申请资源 精品好文档，推荐学习交流 仅供学习与交流，如有侵权请联系网站删除 谢谢10 提出申请后，询问进行随机分配资源还是手动分配 图 4.4 手动分配 图 4.5.随机分配 五、实验总结 附录#include#include#i

9、nclude#define M 3#define N 3 int NeedMN,AllocationMN,AvalibleN,MaxMN,finishN;/Need:进程需要的资源数 Allocation:进程已分配的资源;Avalible:进程可供分配的资源 void display(int*a,int n)/显示一维数组 int i;for(i=0;in;i+)printf(%3d,ai);void disp()/显示资源列表 int i,j,k,h,l;printf(Nnumbert Maxtt needtt allocationt avaliblen);for(i=0;iM;i+)pr

10、intf(p%dt,i);display(Maxi,N);printf(t);display(Needi,N);printf(t);display(Allocationi,N);printf(t);if(i=0)display(Avalible,N);printf(n);精品好文档，推荐学习交流 仅供学习与交流，如有侵权请联系网站删除 谢谢10 int grand(int*a,int*b,int n)/分配资源 int i;for(i=0;in;i+)ai=bi;int check(int*a,int*b,int n)/检查 Allocation 是否与 Max相等 int i;for(i=0

11、;in;i+)if(aibi)return 0;return 1;int compare(int*a,int*b,int n)/比较数组的大小 int i;char flag;for(i=0;in;i+)if(aibi)return 0;return 1;int comp(int*a,int*b,int n,int m)/比较数组 int i;for(i=0;ibi)if(m=1)printf(request Number%d resouce have an error request overflow avalible%dn,i+1,i);if(m=2)printf(request Numb

12、er%d resouce have an error request overflow Need%dn,i+1,i);return 0;return 1;void dec(int*a,int*b,int n)/数组相减 int i;for(i=0;in;i+)ai-=bi;char input()/输入数据 char c;c=getchar()-0 x30;return c;void add(int*a,int*b,int n,int m)/数组相加 int i;for(i=0;in;i+)ai+=bi;for(i=0;in;i+)if(m=0)printf(Avalible%d=%d,i,a

13、i);if(m=3)printf(n);if(m=1)printf(work valuese changed work%d=%dn,i,ai);printf(n);/检查安全序列 int safe()int i,count=0,n,j,r1=1;int workN,srM,flag;精品好文档，推荐学习交流 仅供学习与交流，如有侵权请联系网站删除 谢谢10 int finish1N;grand(work,Avalible,N);printf(check safe list.n);for(i=0;iN;i+)finish1i=-1;for(n=0;nM;n+)for(i=0;ineed%d,n,

14、i);break;if(finish1i=-1&flag=1&finishi=-1)printf(find a right need-process%d-need%dn,n,i);add(work,Allocationi,N,r1);finish1i=1;srcount=i;count+;/记录安全序列 if(count=M)printf(-have an safe list-n);for(i=0;i,sri);else printf(p%dn,sri);return 1;else printf(after check there no safe list.n);printf(cant app

15、ly resoucen);return 0;/随机请求资源 int ran_request()int i,flag1,flag2,r1=1,r2=2,r3=3;int requestN,pn;pn=rand()%2;printf(Process%d call for resoucen,pn);for(i=0;iN;i+)requesti=rand()%5;for(i=0;iM;i+)finishi=-1;printf(random produce request%d:,N);display(request,N);printf(n);if(finishpn=-1)/finish 记录进程是否分配

16、完成 flag1=comp(request,Avalible,N,r1);flag2=comp(request,Needpn,N,r2);if(flag1=1&flag2=1)printf(call for request avalible);dec(Avalible,request,N);dec(Needpn,request,N);add(Allocationpn,request,N,r3);disp();if(safe()=1)if(check(Allocationpn,Maxpn,N)=1)add(Avalible,Allocationpn,N,0);finishpn=1;return

17、1;else return 0;else printf(the resouce have assingnedn);精品好文档，推荐学习交流 仅供学习与交流，如有侵权请联系网站删除 谢谢10 int request()/手动申请资源 int i,j,pn,c,flag1,flag2,r1=1,r2=2,r3=3,k=0;int rtN;printf(please input the process number which you want:);scanf(%d,&pn);if(pnM-1)printf(input error!);else printf(nplease input the re

18、quest number:n);for(i=0;iN;i+)getchar();printf(The%d rquest:n,i);rti=input();printf(Your request is 锛歕 n);display(rt,N);if(finishpn=-1)flag1=comp(rt,Avalible,N,r1);flag2=comp(rt,Needpn,N,r2);if(flag1=1&flag2=1)printf(call for request avalible);dec(Avalible,rt,N);dec(Needpn,rt,N);add(Allocationpn,rt,

19、N,r3);disp();if(safe()=1)if(check(Allocationpn,Maxpn,N)=1)add(Avalible,Allocationpn,N,0);finishpn=1;k+;return 1;else return 0;else printf(The resouce have assignedn);int main()int i,j,s_flag;char c,s;int avN,s_llMN;for(i=0;iM;i+)finishi=-1;srand(time(NULL);for(i=0;iM;i+)for(j=0;jN;j+)Allocationij=ra

20、nd()%10;Needij=rand()%10;Maxij=Allocationij+Needij;for(i=0;iN;i+)Avaliblei=rand()%12;disp();s_flag=safe();if(s_flag=1)printf(是否申请资源-(Y/N)n);c=getchar();if(c=Y|c=y)N1:printf(1-random request resoucen);printf(2-request resouce by mann);grand(av,Avalible,N);/保存原始的 available 的值 for(i=0;iM;i+)精品好文档，推荐学习交

21、流 仅供学习与交流，如有侵权请联系网站删除 谢谢10 grand(s_lli,Allocationi,N);getchar();Mnu:s=getchar();switch(s)case 1:if(ran_request()=1)printf(continue request(Y/N)n);getchar();c=getchar();if(c=Y|c=y)goto N1;else grand(Avalible,av,N);for(i=0;iM;i+)grand(Allocationi,s_lli,N);break;case 2:if(request()=1)printf(continue request(Y/N)n);getchar();c=getchar();if(c=Y|c=y)goto N1;else grand(Avalible,av,N);for(i=0;iM;i+)grand(Allocationi,s_lli,N);break;default:printf(input error,please input agin.n);goto Mnu;if(c=N|c=n)printf(Thank for your use.n);return 0;精品好文档，推荐学习交流 仅供学习与交流，如有侵权请联系网站删除 谢谢10