银行家算法实验报告

1、一. 绪论这次课程设计要求完成一个资源管理系统，该系统必须包括资源的添加、删除和 修改等功能，并且允许其它进程来申请这里的资源，任何一个进程来申请资源时， 必须先登记该进程对资源的申请要求， 然后由系统检查当前资源的状况，并用银 行家算法和安全性算法来检查是否允许分配资源给进程。通过课程设计，加深我们对利用银行家算法避免死锁的理解。在设计中主要的难点是用语言编写银行家 算法和安全性算法，使系统资源分配能安全进行，避免系统死锁。二. 设计目的在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用提 高吞吐量，但可能发生一种危险一一死锁。 所谓死锁，是指多个进程运行中因争 夺资源而造

2、成的一种僵局，当进程处于这种僵持状态时，若无外力作用，他们都 无法再向前推进。虽然进程在运行过程中，可能发生死锁，但死锁的发生必须同时具备四个条件： 互斥条件、请求和保持条件、不剥夺条件、环路等待条件；防止死锁的机构只须 确保上述四个条件之一不出现，则系统不会发生死锁。系统的状态分为安全状态和不安全状态， 只要能使系统都处于安全状态，便可避 免死锁。所谓安全状态，是指系统能按某种进程顺序（ Pl, P2,，Pn）,来为 每个进程P分配其所需分配，直至满足每个进程对资源的最大需求，使每个进 程都可顺利地完成。如果系统无法找到一个这样地安全系列，则称系统处于不安 全状态。在操作系统中研究资源分配策

3、略时也有类似的问题，系统中有限的资源要供多个 进程使用，必须保证得到资源的进程能在有限的时间内归还资源，以供它进程使用资源。如果资源分配不得当就会发生进程循环等待资源， 各进程都无法继续执 行下去的死锁现象。而最有代表性的避免死锁的算法，是Dijkstra 的银行家算法。银行家算法是避免死锁的一种重要方法， 在课程设计中用c语言编写一个资源管理系统，并要用 银行家算法和安全性算法 检查是否允许分配资源给进程，避免死锁。通过课程设计，加 深我们对了解有关资源申请、避免死锁等概念，并加深我们对银行家算法理解。提高了我们分析、解决问题的能力。三. 设计要求用所学过的语言编程实现一个资源管理系统，该系

4、统必须包括资源的添加、删除 和修改等功能，并且允许其它进程来申请这里的资源， 任何一个进程来申请资源 时，必须先登记该进程对资源的申请要求， 然后由系统检查当前资源的状况， 并 用银行家算法和安全性算法来检查是否允许分配资源给进程。四. 原理分析在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。银行家算法是避免死锁的一种重要方法，为实现银行家算法，系统必须设置若干数据结构。4.1、银行家算法中的数据结构1）可利用资源向量Available是个含有m个元素的数组，其中的每一个元素代表一类可利用的资源

5、数目。如果Available j =K，则表示系统中现有Rj类资源K个。2）最大需求矩阵Max这是一个nx m的矩阵，它定义了系统中n个进程中的每一个进程对 m类资源的 最大需求。如果Max i,j =K，则表示进程i需要Rj类资源的最大数目为K。3）分配矩阵Allocation这也是一个nxm的矩阵，它定义了系统中每一类资源当前已分配给每一进程的 资源数。如果Allocation i,j =K，则表示进程i当前已分得Rj类资源的数目为K。4）需求矩阵Need。这也是一个nx m的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j =K，则表示进程i还需要Rj类资源K个，方能完成其任

6、务。Need i,j =Max i,j -Allocation i,j 4.2、银行家算法设Requesti是进程Pi的请求向量，如果 Requesti j =K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：如果Requesti j Need i,j ，便转向步骤2；否则认为出错，因为它所需要 的资源数已超过它所宣布最大值。1）如果Requesti j Available j，便转向步骤 ；否则，表示尚无足够资源，Pi须等待。2）系统试探着把资源分配给进程 Pi，并修改下面数据结构中的数值：Available j ： =Available j -Reque

7、sti j ;Allocation i,j ： =Allocation i,j +Requesti j ;Need i,j ： =Need i,j -Requesti j;3）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安 全，才正式将资源分配给进程 Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。4.3、安全性算法1) 设置两个向量:工作向量Work:它表示系统可提供给进程继续运行所需的各类资源数目，它含 有m个元素，在执行安全算法开始时，Work : =Available;工作向量Finish:它表示系统是否有足够的资源分配给进

8、程，使之运行完成。开 始时先做Finish i ： =false;当有足够资源分配给进程时，再令Finish i =true。2) 从进程集合中找到一个能满足下述条件的进程：Finish i =false;Need i,j Work j;若找到，执行(3),否则，执行(4)3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源, 故应执行：Work j ： = Work i +Allocation i,j Finish i ： = true;go to step 2;4) 如果所有进程的Finish i =true都满足，则表示系统处于安全状态；否则， 系统处于不安全状态五.

9、 具体设计和程序流程图在程序中设计五个进程，分别为 pr0,pr1,pr2,pr3,pr4 。共享三类资源。在这个资源管理系统中对进程的所需最大资源(Max)、已分配给当前进程资源(Allocation)和系统可用资源(Available)分别进行了初始化了值。进程可动态地申请资源和释放资源，系统按各进程的申请动态地分配资源。要求程序具有显示和打印各进程的某一时刻的资源分配表和安全序列，若分配不安全，则释放分配的资源，防止使系统进入不安全状态。显示和打印各进程依次要求申请的资源 号以及为某进程分配资源后的有关资源数据。程序还可以实现对系统的修改。如果修改系统可用资源(Available)，和进

10、程分配资源。程序具体的设计是：函数void showdata()用来显示资源矩阵，包括系统可用资源 数目，进程对资源最大需求数，系统已分配给进程的资源数，进程还需求资源。 通过以上显示，很直观的观察到资源分配和修改的过程。函数share()用来利用银行家算法对某个进程申请资源对进行判定。函数in t cha ngdata(i nt i)用来实现资源试探分配。主要执行的步骤是Avaliablej=Avaliablej-Requestj，Allocationij =Allocationij+Requestj , Needij=Needij-Requestj。函数safe()用来实现安全性算法，对分

11、配后的资源进行计算，若分配资源后，系统是安全的，则资源完成本次分配。若不安全将本次的试探分配作废，调用shifang()函数恢复原来的资源分配状态。资源修改功能用 Revision()来实现。六. 程序源代码#in clude#defi ne MM 50#defi ne true 1#defi ne false 0int avMM;int maxMMMM;int alMMMM;int needMMMM;int pMM;/* 进程 */int N,M; /* 进程数和资源数*/int s(int avMM,int needMM,int alMM) /*安全性检查 */int i,j,t=O,x,

12、y=O, workMM,finishMM,ppMM;for(i=0;iN;i+)fini shi=false;for(j=0;jM;j+)workj=avj;for(x=0;xN-t;)for(i=0;iN;i+)for(j=0;j=needij)y+; /*y表示符合的资源个数*/else y=0;if(y=M) /* 如果第i个进程的所有资源都满足，分配并回收资源*/for(j=0;jM;j+)workj=workj+alij;fini shi=true;ppt=i;t+；y=0;/*第三个for*/*第二个 for*/ /*第一个 for*/if(t=N) /*被分配的资源为N,安全*/

13、prin tf(nit is safe!n);printf(the safe line:n); /*寻找安全序列 */for(i=0;iN;i+)prin tf(P%d,ppi);return true;elseif(t=N|i0)prin tf(the process does not exist! n);con ti nue;prin tf(i nput the nu mber of request; n);for(j=0;jM;j+)scan f(%d,&requestj);for(j=0;jM;j+)if(requestj=needij&requestj=avj)/*试探着分配资源 *

14、/k+; /*对满足条件的资源计数*/elseprintf(nthe process should wait.n); /*否则等待 */if(k=M) /*/for(j=0;jM;j+)avj=avj-requestj;alij=alij+requestj;n eedij=n eedij-requestj;r=s(av, need,al);if(r=false)/*不安全，回收资源*/for(j=0;jM;j+)avj=avj+requestj; alij=alij-requestj;n eedij=n eedij+requestj;else安全,继续*/prin tf(nls there a

15、 process request?n); /*scan f(%d, &flag);if(flag) /*判断有无请求*/f(flag); /*如有，分配 */ elseprin tf(nshi fou jin xing qi ta jia n ce?(y=1,c on ti nu e.y=0,stop)n); /* 进行另一组检测*/scan f(%d, &y);if(y)c(); /*/else否则等待*/prin tf(the process should wait.n); /*int c()int i,j,r,flag; /*flag为1,有请求,否则,无请求*/prin tf(i np

16、ut the mumber of sources: n);sca nf(%d,&M);prin tf(i nput the mumber of processes: n);sca nf(%d,&N);prin tf(please in put av:n); /*输入现有资源数*/for(i=0;iM;i+)sca nf(%d,&avi);prin tf(please in put every processs max: n); /*/输入每个进程需要资源最大值for(i=0;iN;i+) for(j=0;jM;j+)scan f(%d,&maxij);prin tf(please in put

17、 every processs al:n); /* for(i=0;iN;i+) for(j=0;jM;j+)sca nf(%d,&alij);prin tf(i nput every processs n eed:n); /* for(i=0;iN;i+)for(j=0;jM;j+)输入每个进程已分配资源数*/显示还需资源数*/n eedij=maxij-alij;prin tf(%d , n eedij);r=s(av,need,al); /*安全检测 */if(r)prin tf(nls there a process request? n);scan f(%d, &flag);if(f

18、lag) /*判断有无请求*/f(flag); /*如有，分配 */main ()c(); /* 初始化*/getch();七. 设计小结一周的操作系统课程设计终于结束了，虽然很忙碌很疲劳，但感觉收获还是蛮 大的。我几乎每天的专注和辛劳，唤回了我对操作系统的重新的认识，在编写 程序不断出现错误和改正的过程序中加深了我对银行家算法的理解。这个系统 的功能基本能满足要求，完成了对资源的修改还有用银行家算法和安全性算法 来检查是否允许分配资源给进程。在课程设计的过程中，通过与同组人的相互 讨论，很多问题迎刃而解。让我从中体会到是小组合作的力量。设计主要由两部分组成。第一部分：银行家算法（扫描）1.如

19、果Request=Need,则转向2;否则,出错2.如果Request=Available,则转向3,否则等待3.系统试探分配请求的资源给进程4.系统执行安全性算法安全性算法1.设置两个向量（1）.工作向量:Work=Available（表示系统可提供给进程继续运行所需要的各类资源数目）（2）.Finish:表示系统是否有足够资源分配给进程（True:有;False:没有）.初始化为 False2.若Finishi=False&NeedNeedi ，n，则报错返回。如果RequestnAvailable ，则进程i进入等待资源状态，返回。(3) 假设进程i的申请已获批准，于是修改系统状态：Av

20、ailable=Available-RequestAllocation=Allocation+RequestNeed=Need-Request(4) 系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。2.安全性检查(1) 设置两个工作向量 Work=Available ； Finish =False(2) 从进程集合中找到一个满足下述条件的进程，Finish =FalseNeed=Work如找到，执行；否则，执行(4)(3) 设进程获得资源，可顺利执行，直至完成，从而释放资源。Work=Work+AllocationFinish=TrueGO TO 2如所有

21、的进程Finish =true，则表示安全；否则系统不安全3 数据结构假设有M个进程N类资源，则有如下数据结构：#define W 10#define R 20int A ;/总进程数int B ;/资源种类int ALL_RESOURCEW; / 各种资源的数目总和int MAXW ;M 个进程对N类资源最大资源需求量int AVAILABLE ;/系统可用资源数int ALLOCATIONW ;M个进程已经得到 N类资源的资源量int NEEDW ;M个进程还需要N类资源的资源量int Request ;/ 请求资源个数5.4主要函数说明void showdata(); /主要用来输出资源

22、分配情况void changdata(int); /主要用来输出资源分配后后的情况void rstordata(int); /用来恢复资源分配情况，如:银行家算法时，由于分配不安全则要恢复资源分配情况int chkerr(int); /银行家分配算法的安全检查void bank() ;/ 银行家算法银行家算法的课程设计(二 )VC+6.02008-01-28 15:29 源程序数据结构分析：假设有M个进程N类资源，则有如下数据结构：#define W 10#define R 20int A ;/总进程数int B ;/资源种类int ALL_RESOURCEW; / 各种资源的数目总和int

23、MAXW ;M 个进程对N类资源最大资源需求量int AVAILABLE ;/系统可用资源数int ALLOCATIONW ;M个进程已经得到 N类资源的资源量int NEEDW ;M个进程还需要N类资源的资源量int Request ;/ 请求资源个数第 3 章 程序清单 #include using namespace std;#define MAXPROCESS 50/*最大进程数*/#define MAXRESOURCE 100/*最大资源数*/int AVAILABLEMAXRESOURCE;/*可用资源数组*/int MAXMAXPROCESSMAXRESOURCE;/*最大需求矩

24、阵 */int ALLOCATIONMAXPROCESSMAXRESOURCE; /*分配矩阵 */int NEEDMAXPROCESSMAXRESOURCE;/*需求矩阵 */int REQUESTMAXPROCESSMAXRESOURCE; /*进程需要资源数 */bool FINISHMAXPROCESS;/* 系统是否有足够的资源分配 */int pMAXPROCESS;/* 记录序列 */int m,n;/*m 个进程,n个资源*/void Init();bool Safe(); void Bank(); int main()Init();Safe();Bank();void Ini

25、t()/*初始化算法*/int i,j;couttvvendl;coutt|vvendl;coutt|银行家算法vvendl;coutm;coutvv请输入资源的种类:;cinn;coutvv请输入每个进程最多所需的各资源数，按照vvmvvxvvnvv矩阵输入vvendl;for(i=0;ivm;i+)for(j=0;jvn;j+)cinMAXj;coutvv请输入每个进程已分配的各资源数，也按照vvmvvxvvnvv矩阵输入vvendl;for(i=0;ivm;i+)for(j=0;jvn;j+)cinALLOCATIONj;NEEDj=MAXj-ALLOCATIONj;if(NEEDjv0

26、)coutvv您输入的第vvi+1vv个进程所拥有的第vvj+1vv个资源数错误，请重新输入:vvendl;j-;continue;coutvv请输入各个资源现有的数目:vvendl;for(i=0;ivn;i+)cinAVAILABLE;void Bank()/*银行家算法*/int i,cusneed;char again;while(1)coutvv请输入要申请资源的进程号(注:第1个进程号为0,依次类推)endl;cincusneed;coutvv请输入进程所请求的各资源的数量vvendl;for(i=O;in;i+)cinREQUESTcusneed;for(i=O;iNEEDcus

27、need)coutvv您输入的请求数超过进程的需求量！请重新输入!AVAILABLE)coutvv您输入的请求数超过系统有的资源数！请重新输入!vvendl;continue;for(i=0;ivn;i+)AVAILABLE-=REQUESTcusneed;ALLOCATIONcusneed+=REQUESTcusneed;NEEDcusneed-=REQUESTcusneed;if(Safe()coutvv同意分配请求!vvendl;elsecoutvv您的请求被拒绝!vvendl;for(i=O;ivn;i+)AVAILABLE+=REQUESTcusneed;ALLOCATIONcusn

28、eed-=REQUESTcusneed;NEEDcusneed+=REQUESTcusneed;for(i=0;im;i+)FINISH=false;coutvv您还想再次请求分配吗cinagain;if(agai n=y|agai n=Y)continue;break;bool Safe()/*int i,j,k,l=0;int WorkMAXRESOURCE;for(i=0;in;i+)Work=AVAILABLE;for(i=0;im;i+)FINISH=false;for(i=0;im;i+)if(FINISH=true)continue;elsefor(j=0;jWorkj)break;?是请按y/Y,否请按其它键endl;安全性算法*/* 工作数组*/if(j=n)FINISH=true; for(k=