操作系统课设-银行家算法

《计算机操作系统》课程设计报告题目：银行家算法设计与实现专业：软件工程班级：09级（2）班姓名：XXX学号：XXX指导老师：XXX完成时间：2012年2月20日目录课设题目要求算法设计思路主要数据结构及其说明程序流程图源程序代码结果及数据分析实验心得参考资料一、课设题目要求模拟一个银行家算法，要求如下：输入：1.系统中各类资源表2.每个进程需要各类资源总数系统分配给各个进程各类资源数输出：1.判断T0时刻的安全性

2.如果系统是安全的，任意给出某个进程的一个资源请求方式并判断系统能否接受此请求，如果可以接受，其输出全部安全序列，反之，不予分配。二、算法设计思路银行家算法是一种最具代表性的避免死锁的算法。要解释银行家算法，必须先解释操作系统的安全状态和不安全状态。安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定没有死锁发生。不安全状态：不存在一个安全序列。不安全状态不一定导致死锁。安全序列：一个进程序列{P1，…，Pn}是安全的，如果对于每个进程Pi（0≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj（j＜i）当前占有资源量之和。先对系统从源文件中读取的数据进行安全性判断，然后对用户提出的请求进行合法性检查，即检查请求的是不大于需要的，不大于系统可利用的资源。若请求合法，则进行试分配，最后对试分配状态调用安全性算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。三、主要数据结构及其说明进程数i、M资源种类数j、N最大需求矩阵intMax[i][j];分配矩阵intAllocation[i][j];需求矩阵intNeed[i][j]=Max[i][j]-Allocation[i][j];工作向量intWork[N];可利用资源矩阵intAvailable[N];进程的数目intn_pro=0;标记安全序列intflag[M]={-1};安全序列的个数intw=0;表示系统是否有足够的资源分配给进程boolfinish[M];安全性检查算法Safe（）函数只要求出了一种安全序列就可以说明系统是处于安全状态的，故：设置了两个向量：工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，在执行安全性算法开始时，Work=Available。Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时令Finish[i]=false，当有足够的资源分配给进程时，再令Finish[i]=1。在进程中查找符合以下条件的进程：条件1：Finish[i]=0;条件2：Need[i][j]<=Work[j];若找到，则执行步骤③，否则，执行步骤④当进程获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

Work[j]+=Allocation[i][j];

Finish[i]=true;

gotostep2;如果所有的Finish[i]=true，则表示系统处于安全状态，否则，处于不安全状态。Safe1（intflag[],intn,intt）函数用于输出所有的安全序列，使用了回溯法。Request（）函数用于进程请求资源。输入发出请求的进程号i，请求的资源数Request[i][j]，系统按银行家算法进行检查：①所请求的资源小于等于所需要的资源，否则分配不合理，不予分配；②所请求的资源小于等于系统可利用资源，否则分配不合理，不予分配；③假设可为该进程分配资源，安全性检查，若有安全序列，分配资源，否则系统处于不安全状态，不予分配四、程序流程图整体流程图判断系统的安全性Safe（）五、源程序代码#include<fstream.h>#include<stdio.h>#include<stdlib.h>#defineM10//最大进程数#defineN3//系统所拥有的资源类型intMax[M][N];//进程对各类资源的最大需求intAllocation[M][N];//系统已为进程所分配的各类资源数intNeed[M][N];//运行进程尚需的各类资源数intWork[N];//运行进程时系统所拥有的资源数boolfinish[M];//表示系统是否有足够的资源分配给进程intAvailable[N];//系统可利用的资源数intn_pro=0;//进程的数目intflag[M]={-1};//用于标记安全序列intReadfile();//从磁盘读文件intSafe1(intflag[],intn,intt);//输出所有安全状态voidshow();intSafe();//判断系统是否处于安全状态intRequest();//请求资源分配函数voidshow(){ printf("\t%-9s\t%-9s\t%-9s\n","MAX","Allocation","Need"); printf("\tABC\tABC\tABC\n"); for(inti=0;i<n_pro;i++) { printf("p%d\t%d%4d%4d\t",i,Max[i][0],Max[i][1],Max[i][2]); printf("%d%4d%4d\t",Allocation[i][0],Allocation[i][1],Allocation[i][2]); printf("%d%4d%4d\n",Need[i][0],Need[i][1],Need[i][2]); } printf("系统可利用资源数:\n"); printf("\tA\tB\tC\n"); printf("\t%d\t%d\t%d\n",Available[0],Available[1],Available[2]);}intReadfile()//从磁盘读文件{ inti=0,j=0;//i表进程，j表资源 ifstreaminFile;//文件 inFile.open("test.txt");//打开输入文件，按照规定的格式提取线程等信息 for(j=0;j<N;j++) inFile>>Available[j]; inFile.get(); printf("系统最大资源数:\n"); printf("\tA\tB\tC\n"); printf("\t%d\t%d\t%d\n",Available[0],Available[1],Available[2]); inFile>>n_pro; inFile.get(); printf("当前进程的数目:%d\n",n_pro); while(i<n_pro)//提取进程的相关资源信息 { for(j=0;j<N;j++) inFile>>Max[i][j]; for(j=0;j<N;j++) inFile>>Allocation[i][j]; for(j=0;j<N;j++) { Need[i][j]=Max[i][j]-Allocation[i][j]; Available[j]-=Allocation[i][j]; } i++; } for(j=0;j<N;j++) Work[j]=Available[j]; printf("显示初始化资源分配表:\n"); show(); printf("\n"); return0;}intSafe()//判断系统是否是安全的{ inttempn=n_pro; inti=0,j=0,t=0; for(i=0;i<n_pro;i++) finish[i]=false; while(tempn) { for(i=0;i<n_pro;i++) { if(!finish[i]) { inttp=0;//注释部分用于调试程序// printf("%d\t%d%4d%4d\t",i,Work[0],Work[1],Work[2]);// printf("%d%4d%4d\n",Need[i][0],Need[i][1],Need[i][2]); tp=(Work[0]>=Need[i][0])&&(Work[1]>=Need[i][1])&&(Work[2]>=Need[i][2]); if(tp) { finish[i]=true; for(intj=0;j<N;j++) Work[j]+=Allocation[i][j]; flag[t]=i;// printf("%d\tflag[%d]=%d",i,t,flag[t]);system("pause");printf("\n");t++; break; } } } tempn--; } for(i=0;i<n_pro;i++) if(finish[i]==false){printf("系统不安全,不存在安全序列\n");return-1;} printf("系统是安全的,存在安全序列:\n"); for(j=0;j<N;j++) Work[j]=Available[j]; Safe1(flag,n_pro,0); printf("\n"); return0;}intSafe1(intflag[],intn,intt){ intp,i,j;//p为标记 inttemp[N];//临时数组 for(i=0;i<n;i++) { inttp=0; tp=(Work[0]>=Need[i][0])&&(Work[1]>=Need[i][1])&&(Work[2]>=Need[i][2]); if(tp) { for(j=0;j<N;j++) Work[j]+=Allocation[i][j]; flag[t]=i; p=1; } elsecontinue; for(intj=0;j<t;j++) if(flag[t]==flag[j]) { for(j=0;j<N;j++) Work[j]-=Allocation[i][j]; p=0;break; } if(p==1) { if(t==n-1) { for(j=0;j<n;j++) printf("p%-5d",flag[j]); printf("\n"); } else { for(j=0;j<N;j++) temp[j]=Work[j]-Allocation[i][j]; Safe1(flag,n,t+1); for(j=0;j<N;j++) Work[j]=temp[j]; } } } return0;}intRequest()//进程提出请求后，判断系统能否将资源分配给它{ intrq;//下标 intRequest[N]; printf("请输入需要请求的进程号(0~4):"); scanf("%d",&rq); printf("请输入需要请求的资源数(ABC):"); scanf("%d%d%d",&Request[0],&Request[1],&Request[2]); if(Need[rq][0]<Request[0]||Need[rq][1]<Request[1]||Need[rq][2]<Request[2]) { printf("进程p%d申请的资源大于它所需要的资源\n分配不合理，不予分配\n\n",rq); return-1; } if(Available[0]<Request[0]||Available[1]<Request[1]||Available[2]<Request[2]) { printf("进程p%d申请的资源大于系统现在可利用的资源\n分配不合理，不予分配\n\n",rq); return-1; } for(intj=0;j<N;j++) { Available[j]-=Request[j]; Allocation[rq][j]+=Request[j]; Need[rq][j]-=Request[j]; } printf("假定系统可为p%d分配，分配后的资源分配表:\n",rq); show(); printf("\n"); for(j=0;j<N;j++) Work[j]=Available[j]; if(Safe()) { printf("系统进入不安全状态，不予分配\n\n"); for(intj=0;j<N;j++) { Available[j]+=Request[j]; Allocation[rq][j]-=Request[j]; Need[rq][j]+=Request[j]; } printf("此刻的资源分配表为:\n"); show(); printf("\n"); } else { printf("系统是安全的，以上序列是此刻所存在的安全序列!\n"); printf("系统已分配p%d所申请的资源!\n\n",rq); } return0;}intmain(){ printf("从磁盘读取源文件…\n"); Readfile(); printf("T0时刻的安全性:\n"); if(Safe())return-1; while(1) { Request(); } return0;}六、结果及数据分析①、本程序按下图建立.txt源文件，作为程序的初始化输入。②、执行程序，读取源文件，并判断T0时刻所得结果:③、T0时刻的安全序列以及输入P2进程Request（222）所得请求结果：④、调用Request（）函数，测试该函数的可行性，如输入P1进程Request（102），所得结果：输入P0进程Request（020），所得结果:七、心得体会在程序进行编写之前，先对程序的要求进行分析，弄清楚程序所需要的功能，然后将每个功能分