银行家算法2013操作系统.doc

绍兴文理学院ADO.NET程序设计实验报告 计算机操作系统课程实验实验报告课程名称计算机操作系统课程实验实验名称实验四：银行家算法的模拟实现姓名学号班级实验目的（1）进一步理解利用银行家算法避免死锁的问题；（2）在了解和掌握银行家算法的基础上，编制银行家算法通用程序，将调试结果显示在计算机屏幕上，再检测和笔算的一致性。（3）理解和掌握安全序列、安全性算法。实验内容(1) 正确设置相应的数据结构;(2) 清晰画出算法流程图;(3) 准确实现教材第97-98页例题。11绍兴文理学院ADO.NET程序设计实验报告实验步骤1、 实验原理一、基本思想银行家算法的基本思想是当一个新的进程进入系统时，它将告诉系统其所需要的每种资源的最大数目，这个数目绝不应该超过系统中资源的总数。当一个用户申请一组资源时，系统需要判断这个资源的分配是否使系统处于安全状态，若是则进行分配，否则它必须等到，直到其他进程释放足够的资源。二、使用的数据结构 为实现银行家算法，系统中需要使用若干数据结构。设n是系统的进程数目，m是系统资源类数目。 1）可用资源向量Available。向量Available的长度为m， Availablej(j=1,2,.,m)为系统中资源类Rj的当前可用数。如Availablej=K表示系统中现有Rj类资源的可用个数为K。 2）最大需求矩阵Max。Max是一个n*m阶矩阵，矩阵元素Mi,j=K表示进程Pi需要Rj类资源最大数目为K。 3）资源分配矩阵Allocation。Allocation是一个n*m阶矩阵，矩阵元素Allocation i,j=K表示进程Pi当前已分得Rj类资源数为K。 4）剩余需求矩阵Need。Need是一个n*m阶矩阵，矩阵元素Nees i,j=K表示进程Pi还需要Rj类资源数为K。显然Needi,j=Maxi,j- Allocation i,j。三、银行家算法假设在进程并发执行时进程i提出请求j类资源k个后，表示为Requestij=k。系统按下述步骤进行安全检查：（1）如果RequestiNeedi则继续以下检查，否则显示需求申请超出最大需求值的错误。（2）如果RequestiAvailable则继续以下检查，否则显示系统无足够资源，Pi阻塞等待。（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Availablej=Availablej-Requestij; Allocationi,j=Allocationi,j+Requestij; Needi,j=Needi,j-Requestij;（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。四、安全性算法安全状态是指系统能按照某种顺序如(称为序列为安全序列)，为每个进程分配所需的资源，直至最大需求，使得每个进程都能顺利完成。 （1）设置两个向量： 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available; Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi=false; 当有足够资源分配给进程时， 再令Finishi=true。（2）从进程集合中找到一个能满足下述条件的进程： Finishi=false; Needi,jWorkj； 若找到， 执行步骤(3)， 否则，执行步骤(4)。（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Workj=Worki+Allocationi,j; Finishi=true; go to step 2; （4）如果所有进程的Finishi=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。2、 实验流程图Y所有finish都为true？输出安全序列NYN存在Finishi =false&Needij Needij出错返回：return(error)Requestij Availablej出错返回：(进程阻塞)return(error)Availablej = Availablej RequestijAllocationij= Allocationij + RequestijNeedij = Needij Requestij假定分配：输入初始参数（资源分配及请求情况）开始 假定分配之后，系统安全吗？申请成功。输出各种数据的变化图1-2银行家算法流程图3、 实验代码数据结构：#define False 0#define True 1int Avaliable100=0;/可用资源向量int Max100100=0;/最大需求矩阵int Allocation100100=0;/系统分配资源int Need100100=0;/剩余需求矩阵int Request100=0;/请求资源向量int Work100=0;/存放系统可提供资源int temp100=0;/存放安全序列int M=100;/作业的最大数为100int N=100;/资源的最大数为100安全性检验算法：int Safe() int i,k=0,m,apply,Finish100=0;int j;int flag=0;Work0=Avaliable0;Work1=Avaliable1;Work2=Avaliable2;for(i=0;iM;i+) apply=0;for(j=0;jN;j+)if (Finishi=False&Needij=Workj) apply+;if(apply=N)for(m=0;mN;m+)Workm=Workm+Allocationim;/变分配数Finishi=True;tempk=i;i=-1; k+;flag+;for(i=0;iM;i+)if(Finishi=False)cout系统不安全endl; /不成功系统不安全return -1; cout系统是安全的!endl; /如果安全，输出成功 cout分配的序列:;for(i=0;iM;i+) /输出运行进程数组couttempi;if(iM-1) cout;coutendl;return 0;银行家算法代码：int changdata(int i) int j;for (j=0;jM;j+)Avaliablej=Avaliablej-Requestj;Allocationij=Allocationij+Requestj;Needij=Needij-Requestj;return 1;void Share() char ch;int i=0,j=0;ch=y;cout请输入要求分配的资源进程号(0-M-1i;/输入须申请的资源号cout请输入进程 i 申请的资源:endl;for(j=0;jRequestj;/输入需要申请的资源for (j=0;jNeedij)/判断申请是否大于需求，若大于则出错 cout进程 i申请的资源大于它需要的资源;cout 分配不合理，不予分配！Avaliablej)/判断申请是否大于当前资源，若大于则 /出错cout进程i申请的资源大于系统现在可利用的资源;cout 分配出错，不予分配!endl;ch=n;break; if(ch=y) changdata(i);/根据进程需求量变换资源Showdata();/根据进程需求量显示变换后的资源Safe();/根据进程需求量进行银行家算法判断 主程序代码：int main()int i,j;int n,m,flag;cout*银行家算法的模拟实现*endl; coutn;N=n;cout请输入可用资源向量Avaliable的内容：;for(i=0;iAvaliablei;coutm;M=m; cout请输入最大需求量矩阵Max(m*n):endl;for(i=0;im;i+)for(j=0;jMaxij;doflag=0;cout请输入资源分配矩阵Allocation(m*n):endl;for(i=0;im;i+)for(j=0;jAllocationij;if(AllocationijMaxij)flag=1;Needij=Maxij-Allocationij;if(flag)cout申请的资源Allocation不能大于最大需求量Max，请重新输入!endl; /have a lookwhile(flag);Showdata();/显示各种资源Safe();/用银行家算法判定系统是否安全 while(1)coutc;if(c=0) break;Share(); /分配资源；return 0;4、 实验结果1.输入例题的提供的数据。若输入的资源分配矩阵中的数超过最大需求量2.显示资源矩阵，并检验安全性，若安全显示出安全序列3.p1请求分配资源（1,0,2）4p4请求资源（3,3,0）5.p0请求资源（0,2,0）5.退出程序实验心得体会1、操作系统的基本特征是并发与共享。系统允许多个进程并发执行，并且共享系统的软、硬件资源。为了最大限度的利用计算机系统的资源，操作系统应采用动态分配的策略，但是这样就容易因资源不足，分配不当而引起“死锁”。本次课程设计就是学会如何使用用银行家算法来避免“死锁”。2、银行家算法的核心思想是：按该法分配资源时，每次分配后总存在着一个进程，如果让它单独运行下去，必然可以获得它所需要的全部资源，也就是说，它能结束，而它结束后可以归还这类资源以满足其他申请者的需要。需满足以下要求，即一个资源每次只能由一个进程；第二个为等待条件，即一个进程请求资源不能满足时，它必须等待，但它仍继续保持已得到的所有其他资源；第三个为非剥夺条件，即在出现死锁的系统中一定有不可剥夺使用的资源；第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待它前一个进程所持有的资源。防止死锁的机构只能确保上述四个条件之一不