实验二银行家算法

实验报告实验报告课程名称操作系统班级实验日期姓名学号实验成绩实验名称银行家算法实验目的及要求了解掌握银行家算法，学会模拟实现资源分配，同时有要求编写和调试一个系统分配资源的简单模拟程序，观察死锁产生的条件，并使用适当的算法，有效的防止和避免死锁的发生实验环境MicrosoftVisualStudio实验内容1、模拟操作系统对于资源动态分配的过程2、模拟的程序，首先可以由用户进行自由的输入当前系统中进程的数目和资源的分配状态，可以进行对于当前资源分配的状态情况进行安全检验。第二，程序可以满足进程对于资源的请求，并且进行分配。分配结束之后检验是否处于安全的状态。并且可以报告出现的情况。算法描述及实验步骤MMain()安全性算法资源请求算法银行家算法：设Request[i]是进程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）可利用资源向量Available。这是一个含有n个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K,则表示系统中现有Rj类资源K个。（2）最大需求矩阵Max。这是一个m*n的矩阵，它定义了系统中n个进程中每一个进程对m类资源的最大需求。如果Max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K。（3）分配矩阵Allocation。这也是一个m*n的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K,则表示进程i当前已分得Rj类资源的数目为K。（4）需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K,则表示进程i还需要Rj类资源K个，方能完成其任务。（5）工作数组Work.。这是一个含有n个元素的数组，它代表可以提供分配的资源数，初始值是Available中的数值，随着资源的回收，它的值也会改变，公式是Work[i]=Work[i]+Allocation[i]。Safety功能：检验当前系统对于进程分配的资源之后是否存在死锁，是否处于安全状态。进程数，资源数，分配状态都需要用户自行进行输入。算法：voidSafety(int*Available,int*Finish,int**Max,int**Allocation,int**Need,intm,intn)//安全算法实现代码Request功能：对于用户输入的资源请求进行模拟，看是否可以进行资源的分配。满足请求后，进行检验，看系统是否处于安全状态。算法：voidRequesta(int*Request,int*Available,int*Finish,int**Max,int**Allocation,int**Need,intm,intn)//资源请求算法的实现二维数组某一行和一维数组：intCompare1(int**Need,int*Available,intn,inti)比较一维数组：intCompare2(int*Request,int*Available,intn)二维数组某一行和一维数组：intCompare3(int**Need,int*Request,intn,inti)在Safety算法中调用Compare1，在Requesta算法中调用Compare2、Compare3。在主函数中调用Safety算法和Requesta算法来实现。调试过程及实验结果1、安全性算法2、资源请求算法总结优点：程序中的数组采用了动态开辟的方法，有效地减少了对于空间的占用。提高了空间的利用率。输出的界面比较的简洁，直接给出了分配资源的顺序。资源请求算法则直接给出了请求后造成的情况，比较的明了。缺点：程序仍然存在很多地方可以改进。比如输出界面，可以做的更漂亮。部分地方可以采用其他的方法。通过本次试验，加深了对银行家算法的了解，掌握了如何利用银行家算法避免死锁。通脱这次试验，使我的理论知识更加牢固，是自己在学习以后的知识及编程语言更有信心。银行家算法是为了是系统保持安全状态。附录#include<stdio.h>#include<stdlib.h>#include<math.h>#defineTRUE1#defineFALSE0intCompare1(int**Need,int*Available,intn,inti)//二维数组某一行和一维数组{ intj=0; intflage=0;//标记做了多少次成功比较 for(j=0;j<n;j++) {if(Need[i][j]<=Available[j]) flage++; } if(flage==n) return1; else return0;}//成功了返回1；失败了返回0intCompare2(int*Request,int*Available,intn)//比较一维数组{ intj=0; intflage=0;//标记做了多少次成功比较 for(j=0;j<n;j++) {if(Request[j]<=Available[j]) flage++; } if(flage==n) return1; else return0;}//成功了返回1；失败了返回0intCompare3(int**Need,int*Request,intn,inti)//二维数组某一行和一维数组{ intj=0; intflage=0;//标记做了多少次成功比较 for(j=0;j<n;j++) {if(Need[i][j]>=Request[j]) flage++; } if(flage==n) return1; else return0;}//成功了返回1；失败了返回0voidSafety(int*Available,int*Finish,int**Max,int**Allocation,int**Need,intm,intn)//安全算法实现代码{int*a; inti,s,h=0,p,q,flag=0,b=0,c=0; a=(int*)malloc(sizeof(int)*n); for(i=0;i<n;i++) { a[i]=0; }//用来记录进程执行的顺序 printf("执行过程为：");printf("\n"); for(p=0;p<m;p++)//每次只处理一个未被标记的数组进程 { for(i=0;i<m;i++) { if(Finish[i]==0) { c=Compare1(Need,Available,n,i);//检测第i进程是否可以执行，可以执行则返回1，不可以执行返回0 if(c==1) { printf("第%d个进程被执行后Available数组：\n",i); for(s=0;s<n;s++) { Available[s]=Available[s]+Allocation[i][s]; printf("%d",Available[s]); Finish[i]=1; }//刷新Available数组 a[p]=i; printf("\n"); break; } } } } for(q=0;q<m;q++) { if(Finish[q]==1) { b++; } } if(b==m) { printf("\n"); printf("可以安全完成，完成的顺序为：<"); for(q=0;q<m;q++) { printf("%d",a[q]); } printf(">"); } else { printf("不能安全完成\n"); }}voidRequesta(int*Request,int*Available,int*Finish,int**Max,int**Allocation,int**Need,intm,intn)//资源请求算法的实现 { inti,j,s; printf("请输入为哪个进程申请资源（进程从第0个开始）\n"); scanf("%d",&j); printf("请输入Request数组：\n"); for(i=0;i<n;i++) { scanf("%d",&Request[i]); } if(Compare3(Need,Request,n,j)) { if(Compare2(Request,Available,n)) { printf("可以安全的分配给其资源\n"); printf("分配给其资源后刷新数据：\n");printf("Available数组更新为\n"); for(s=0;s<n;s++) { Available[s]=Available[s]-Request[s]; printf("%d",Available[s]); } printf("\n"); printf("Need数组第%d行更新为：\n",j+1); for(s=0;s<n;s++) { Need[j][s]=Need[j][s]-Request[s]; printf("%d",Need[j][s]); }printf("\n");printf("Allocation数组第%d行更新为：\n",j+1);for(s=0;s<n;s++) { Allocation[j][s]=Allocation[j][s]+Request[s]; printf("%d",Allocation[j][s]); } printf("\n"); printf("调用安全性检测算法;\n"); Safety(Available,Finish,Max,Allocation,Need,m,n);//调用安全性检测算法 }//刷新各个数组 else { printf("超过了Available的资源数目\n"); } } else { printf("输入的数值错误，超过了需要的资源数目\n"); }}voidmain(){ int*Available;//可用资源数组 int*Request;//请求预先分配的资源数组 int*Finish;//标记已经访问的数组 int**Max; int**Allocation; int**Need; intn,m,i,j,p;//m是进程数目。n是资源数目,s是选择算法的参数 printf("|------------------------------------------------------------------------------|"); printf("|银行家算法|"); printf("|------------------------------------------------------------------------------|"); printf("\n"); printf("\t\t\t|----选项--------------------|\n"); printf("\t\t\t|1.安全性算法|\n"); printf("\t\t\t|----------------------------|\n"); printf("\t\t\t|2.资源请求算法|\n"); printf("\t\t\t|----------------------------|\n"); printf("\t\t\t|3.退出|\n"); printf("\t\t\t|----------------------------|\n"); printf("\n"); printf("请输入资源种类数:");scanf("%d",&n);printf("\n");printf("请输入进程的数量:"); scanf("%d",&m);//动态开辟一维数组的代码 Available=(int*)malloc(sizeof(int)*n);printf("\n"); printf("请输入Available数组："); for(i=0;i<n;i++) { scanf("%d",&Available[i]); }Finish=(int*)malloc(sizeof(int)*n); for(i=0;i<m;i++) { Finish[i]=0; } Request=(int*)malloc(sizeof(int)*n); for(i=0;i<m;i++) { Request[i]=0; }//预先创建需求数组 //动态开辟二维数组的代码 Max=(int**)malloc(sizeof(int*)*m);for(i=0;i<m;i++) { Max[i]=(int*)malloc(sizeof(int)*n); }printf("\n"); printf("请输入Max矩阵：\n"); for(i=0;i<m;i++) {for(j=0;j<n;j++) { scanf("%d",&Max[i][j]); } } //MAX矩阵完成Allocation=(int**)malloc(sizeof(int*)*m);for(i=0;i<m;i++) { Allocation[i]=(int*)malloc(sizeof(int)*n); }printf("\n"); printf("请输入Allocation矩阵：\n"); for(i=0;i<m;i++) {for(j=0;j<n;j++) { scanf("%d",&Allocation[i][j]); }