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

银行家算法1操作系统实验三银行家算法姓名：杨益林学号：71115215报告日期：2017.06.07银行家算法一、实验目的通过实验，加深对多实例资源分配系统中死锁避免方法——银行家算法的理解，掌握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++和数据结构的银行家算法知识；在编程过程中虽然遇到很多困难，解决问题的过程中，同时也锻炼了我不怕困难，勇于迎接挑战的精神，为以后的工作打下了坚实的基础。八、源程序并附上注释#includeiostream#includestring.h#includestdio.h#includeiomanip#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;coutendl;coutMaxAllocationNeedAvaliableendl;cout;for(j=0;j4;j++){for(i=0;iN;i++)coutname[i];cout;}coutendl;for(i=0;iM;i++){couti;银行家算法for(j=0;jN;j++)coutMax[i][j];cout;for(j=0;jN;j++)coutAllocation[i][j];cout;for(j=0;jN;j++)coutNeed[i][j];if(i==0){cout;for(j=0;jN;j++)coutAvaliable[j];}coutendl;}}voidsave(){inti,j;for(i=0;iN;i++){ReAvaliable[i]=Avaliable[i];}for(i=0;iM;i++){for(j=0;jN;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;iN;i++){Avaliable[i]=ReAvaliable[i];}for(i=0;iM;i++){for(j=0;jN;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;jM;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;numN;num++)Work[num]=Avaliable[num];for(i=0;iM;i++){apply=0;for(j=0;jN;j++){if(Finish[i]==False&&Need[i][j]=Work[j]){apply++;if(apply==N){for(m=0;mN;m++)Work[m]=Work[m]+Allocation[i][m];//变分配数Finish[i]=True;temp[k]=i;i=-1;k++;flag++;}}}}for(i=0;iM;i++){if(Finish[i]==False){cout系统不安全,所有状态不改变！endl;//不成功系统不安全return1;}}cout系统是安全的!endl;//如果安全，输出成功save();//进行保存cout安全序列:;银行家算法for(i=0;iM;i++){//输出运行进程数组couttemp[i];if(iM-1)cout-;}coutendlendl;return0;}voidshare()//利用银行家算法对申请资源对进行判定{boolch=true;inti=0,j=0;//ch='y';cout请输入请求分配资源的进程号(0-M-1):;cini;//输入须申请的资源号cout请输入进程i申请的资源数量:endl;for(j=0;jN;j++){coutname[j]:;cinRequest[j];//输入需要申请的资源}for(j=0;jN;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;iN;i++)coutname[i]:Avaliable[i];coutendl输入修改值:endl;for(inti=0;iN;i++){coutname[i]:;cinAvaliable[i];}cout修改后的[Avaliable]:endl;for(intk=0;kN;k++)coutname[k]:Avaliable[k]endl;showdata();safe();}intmain()//主函数{inti,j,number,m,n,flag;intchoice=1;charming;cout请输入系统资源的种类数:;cinn;N=n;cout请依次输入系统资源的名称与数量：endl;for(i=0;in;i++){//cout资源i+1的名称:;cinmingnumber;name[i]=ming;//cout资源i+1的数量:;//cinnumber;Avaliable[i]=number;}coutendl;cout请输入进程的数量:;c