操作系统实验报告三-银行家算法

..-..-可修遍-操作系统实验三银行家算法：益林学号：71115215报告日期：一、实验目的通过实验，加深对多实例资源分配系统中死锁防止方法——银行家算法的理解，掌握Windows环境下银行家算法的实现方法，同时稳固利用WindowsAPI进展共享数据互斥访问和多线程编程的方法。二、实验容1.在Windows操作系统上，利用Win32API编写多线程应用程序实现银行家算法。2.创立n个线程来申请或释放资源，只有保证系统平安，才会批准资源申请。3.通过Win32API提供的信号量机制，实现共享数据的并发访问。三、实验步骤〔一〕设计思路：银行家算法可分为个主要的功能模块，其描述如下：1.初始化由用户输入数据，分别对运行的进程数、总的资源种类数、总资源数、各进程所需要的最大资源数量〔Max〕，已分配的资源数量赋值。2.平安性检查算法(1)设置两个工作向量Work=AVAILABLE;FINISH=false;(2)从进程集合中找到一个满足下述条件的进程，FINISH==false;NEED<=Work;如找到，执行(3)；否那么，执行(4)(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。Work+=ALLOCATION;Finish=true;(4).如所有的进程Finish=true，那么表示平安；否那么系统不平安。3.银行家算法在防止死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为平安状态和不平安状态，只要能使系统始终都处于平安状态，便可以防止发生死锁。银行家算法的根本思想是分配资源之前,判断系统是否是平安的;假设是,才分配。它是最具有代表性的防止死锁的算法。设进程j提出请求REQUEST[i]，那么银行家算法按如下规那么进展判断。(1).如果REQUEST[j][i]<=NEED[j][i]，那么转(2)；否那么，出错。(2).如果REQUEST[j][i]<=AVAILABLE[j][i]，那么转(3)；否那么，出错。(3).系统试探分配资源，修改相关数据：AVAILABLE[i]-=REQUEST[j][i];ALLOCATION[j][i]+=REQUEST[j][i];NEED[j][i]-=REQUEST[j][i];用到的数据构造：实现银行家算法要有假设干数据构造，它们用来表示资源分配系统的状态。令n表示系统中进程的数目，m表示资源的分类数。还需要以下数据构造：1).Available是一个长度为m的向量，它表示每类资源可用的数量。Available[j]=k，表示j类资源可用的数量为k。2).Max是一个n×m矩阵，它表示每个进程对资源的最大需求。Max[i，j]=k，表示进程pi至多可以申请k个j类资源单位。3).Allocation是一个n×m矩阵，它表示当前分给每个进程的资源数目。Allocation[i，j]=k，表示进程i当前分到k个j类资源。4).Need是一个n×m矩阵，它表示每个进程还缺少多少资源。Need[i，j]=k，表示进程pi尚需k个j类资源才能完成其任务。显然Need[i，j]=Max[i，j]-Allocation[i，j]。〔二〕流程图四、运行结果例如这里以书上的例子为例，初值如下表：AllocationMaxAvailableABCABCABCP0010753332P1200322P2301900P3211222P4002433现在让进程P1再申请A:1B:0C:2个资源，首先调用平安算法测试如果分配后系统是否平安，然后给出了分配序列，如下列图：如果再让P4申请A:0B:2C:0个资源，首先调用平安算法测试如果分配后系统是否平安，发现分配后系统不平安，于是报分配错误，不予分配，结果如下列图：七、实验体会银行家算法的具体实现，我学到了很多课本上没有的知识。想要完成模拟银行家算法的C++程序，首先就是要彻底熟悉算法，了解算法的根本原理，才能开场着手程序设计在程序设计设计过程中，遇到了一些困难，通过向同学询问，翻阅资料等，问题被一一解决了。首先就是在知识层面上了解了银行家算法这种进程调度和防止死锁的算法，并用C++程序真正模拟出平安性检查和银行家算法过程，复习了之前所学C++和数据构造的知识；在编程过程中虽然遇到很多困难，解决问题的过程中，同时也锻炼了我不怕困难，勇于迎接挑战的精神，为以后的工作打下了坚实的根底。八、源程序并附上注释#include<iostream>#include<string.h>#include<stdio.h>#include<iomanip>#defineFalse0#defineTrue1usingnamespacestd;intMax[100][100]={0};//各进程所需各类资源的最大需求intReMax[100][100]={0};intAvaliable[100]={0};//系统可用资源intReAvaliable[100]={0};charname[100]={0};//资源的名称intAllocation[100][100]={0};//系统已分配资源intReAllocation[100][100]={0};intNeed[100][100]={0};//还需要资源intReNeed[100][100]={0};intRequest[100]={0};//请求资源向量inttemp[100]={0};//存放平安序列intWork[100]={0};//存放系统可提供资源intM=100;//进程的最大数量为100intN=100;//资源的最大数量为100voidshowdata()//显示资源矩阵{inti,j; cout<<endl; cout<<"MaxAllocationNeedAvaliable"<<endl; cout<<"";for(j=0;j<4;j++){for(i=0;i<N;i++) cout<<name[i]<<""; cout<<""; } cout<<endl;for(i=0;i<M;i++){ cout<<""<<i<<"";for(j=0;j<N;j++) cout<<Max[i][j]<<""; cout<<"";for(j=0;j<N;j++) cout<<Allocation[i][j]<<""; cout<<"";for(j=0;j<N;j++) cout<<Need[i][j]<<"";if(i==0){ cout<<"";for(j=0;j<N;j++) cout<<Avaliable[j]<<""; } cout<<endl; }}voidsave(){inti,j;for(i=0;i<N;i++) { ReAvaliable[i]=Avaliable[i]; }for(i=0;i<M;i++){for(j=0;j<N;j++){ ReMax[i][j]=Max[i][j]; ReAllocation[i][j]=Allocation[i][j]; ReNeed[i][j]=Need[i][j]; } }}voidrestore(){inti,j;for(i=0;i<N;i++) { Avaliable[i]=ReAvaliable[i]; }for(i=0;i<M;i++){for(j=0;j<N;j++){ Max[i][j]=ReMax[i][j]; Allocation[i][j]=ReAllocation[i][j]; Need[i][j]=ReNeed[i][j]; } }}intchangdata(inti)//进展资源分配{intj;for(j=0;j<M;j++){ Avaliable[j]=Avaliable[j]-Request[j]; Allocation[i][j]=Allocation[i][j]+Request[j]; Need[i][j]=Need[i][j]-Request[j]; }return1;}intsafe()//平安性算法{inti,k=0,m,apply,Finish[100]={0};intj;intflag=0;for(intnum=0;num<N;num++) Work[num]=Avaliable[num];for(i=0;i<M;i++){ apply=0;for(j=0;j<N;j++){if(Finish[i]==False&&Need[i][j]<=Work[j]){ apply++;if(apply==N){for(m=0;m<N;m++) Work[m]=Work[m]+Allocation[i][m];//变分配数Finish[i]=True; temp[k]=i; i=-1; k++; flag++; } } } }for(i=0;i<M;i++){if(Finish[i]==False){ cout<<"系统不平安,所有状态不改变！"<<endl;//不成功系统不平安return1; } } cout<<"系统是平安的!"<<endl;//如果平安，输出成功save();//进展保存cout<<"平安序列:";for(i=0;i<M;i++){//输出运行进程数组cout<<temp[i];if(i<M-1)cout<<"->"; } cout<<endl<<endl;return0;}voidshare()//利用银行家算法对申请资源对进展判定{boolch=true;inti=0,j=0;//ch='y';cout<<"请输入请求分配资源的进程号(0-"<<M-1<<"):"; cin>>i;//输入须申请的资源号cout<<"请输入进程"<<i<<"申请的资源数量:"<<endl;for(j=0;j<N;j++) { cout<<name[j]<<":"; cin>>Request[j];//输入需要申请的资源 }for(j=0;j<N;j++){if(Request[j]>Need[i][j])//判断申请是否大于需求，假设大于那么出错 {cout<<"进程"<<i<<"申请的资源大于它需要的资源"; cout<<"分配不合理，不予分配！"<<endl; ch=false;break; }else{if(Request[j]>Avaliable[j])//判断申请是否大于当前资源，假设大于那么 {//出错cout<<"进程"<<i<<"申请的资源大于系统现在可利用的资源"; cout<<"分配出错，不予分配!"<<endl; ch=false;break; } } }if(ch){ changdata(i);//根据进程需求量变换资源if(safe()){ restore(); }//根据进程需求量进展银行家算法判断showdata();//根据进程需求量显示变换后的资源 }}voidchangeresources(){//修改资源函数cout<<"当前的[Avaliable]:"<<endl;for(inti=0;i<N;i++) cout<<name[i]<<":"<<Avaliable[i]<<""; cout<<endl<<"输入修改值:"<<endl;for(inti=0;i<N;i++){ cout<<name[i]<<":"; cin>>Avaliable[i]; } cout<<"修改后的[Avaliable]:"<<endl;for(intk=0;k<N;k++) cout<<name[k]<<":"<<Avaliable[k]<<endl; showdata(); safe();}intmain()//主函数{inti,j,number,m,n,flag;intchoice=1;charming; cout<<"请输入系统资源的种类数:"; cin>>n; N=n; cout<<"请依次输入系统资源的名称与数量："<<endl;for(i=0;i<n;i++) {//cout<<"资源"<<i+1<<"的名称:";cin>>ming>>number; name[i]=ming;//cout<<"资源"<<i+1<<"的数量:";//cin>>number;Avaliable[i]=number; } cout<<endl; cout<<"请输入进程的数量:"; cin>>m; M=m; cout<<"请输入各进程的最大需求量("<<m<<"*"<<n<<"矩阵)[Max]:"<<endl;for(i=0;i<m;i++)for(j=0;j<n;j++){ cin>>Max[i][j]; }do{flag=0; cout<<"请输入各进程已经申请的资源量("<<m<<"*"<<n<<"矩阵)[Allocation]:"<<endl;for(i=0;i<m;i++)for(j=0;j<n;j++){ cin>>Allocation[i][j];if(Allocation[i][j]>Max[i][j]) flag=1; Need[i][j]=Max[i][j]-Allocation[i][j]; Avaliable[j]=Avaliable