银行家算法的模拟实现

操作系统课程设计报告题目：银行家算法的模拟实现专业计算机科学与技术学生姓名姜雯班级计算机131学号1310704112指导教师韩立毛完成日期2015.7.10信息工程学院第三篇计算机操作系统课程设计1目录1概述..............................................................................................................................................21.1设计目的...................................................................................................................................21.2设计内容...................................................................................................................................21.3设计要求...................................................................................................................................22设计原理......................................................................................................................................22.1银行家算法中的数据结构........................................................................................................22.2银行家算法应用.......................................................................................................................33设计思路......................................................................................................................................44程序运行调试结果......................................................................................................................54.1程序初始化................................................................................................................................54.2检测系统资源分配是否安全结果............................................................................................75设计小结......................................................................................................................................86参考文献......................................................................................................................................8附录源程序代码............................................................................................................................9第三篇计算机操作系统课程设计2题目：银行家算法的模拟实现1概述1.1设计目的1.进一步了解进程的并发执行。2.加强对进程死锁的理解。3.是用银行家算法完成死锁检测。1.2设计内容给出进程需求矩阵C、资源向量R以及一个进程的申请序列。使用进程启动拒绝和资源分配拒绝（银行家算法）模拟该进程组的执行情况。1.3设计要求1.初始状态没有进程启动；2.计算每次进程申请是否分配，如：计算出预分配后的状态情况（安全状态、不安全状态），如果是安全状态，输出安全序列；3.每次进程申请被允许后，输出资源分配矩阵A和可用资源向量V；4.每次申请情况应可单步查看，如：输入一个空格，继续下个申请。2设计原理2.1银行家算法中的数据结构(1)、可利用资源向量Available，这是一个含有m个元素的数组，其中的每个元素代表一类可利用资源的数目，其初始值是系统中所配置的该类全部资源的数目，其数值随该类资源的分配和回收而动态改变。如果Available[j]=K，则表示系统中现有Rj类资源K个。（2）、最大需求矩阵Max，这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。（3）、分配矩阵Allocation。这也是一个n*m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已经分得Rj类资源的数目为K。（4）、需求矩阵Need。这也是一个n*m的矩阵，用以表示每个进程尚需要的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。上第三篇计算机操作系统课程设计3述三个矩阵间存在以下关系：Need[i,j]=Max[i,j]-Allocation[i,j]2.2银行家算法应用模拟实现Dijkstra的银行家算法以避免死锁的出现，分两部分组成：一是银行家算法(扫描)；二是安全性算法。(1)银行家算法(扫描)设Requesti是进程Pi的请求向量，如果Requesti[j]=K，表示进程Pi需要K个Ri类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：①如果Requesti[j]=Need[i,j]，便转向步骤2；否则认为出错，因为它所需的资源数已经超过了它所宣布的最大值。②如果Requesti[j]=Available[j]，便转向步骤3；否则表示尚无足够资源，Pi需等待。③系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值。Available[j]=Available-Requesti[j];Allocation[i,j]=Allocation[i,j]+Requesti[j];Need[i,j]=Need[i,j]-Request[j];④系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来资源的分配状态，让进程Pi等待。(2)安全性算法系统所执行的安全性算法可描述如下：①设置两个向量：一个是工作向量Work；它表示系统可提供给进程继续运行所需要的各类资源的数目，它含有m个元素，在执行安全性算法开始时，work=Availalbe；另一个是Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]=false；当有足够资源分配给进程时，再令Finish[i]=rue；②从进程集合中找到一个能满足下述条件的进程：一是Finish[i]==false；二是Need[i,j]=Work[j]；若找到，执行步骤③，否则，执行步骤④；③当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Work[j]=Work[j]+Allocation[i,j]；Finish[i]=true；gotostep②；④如果所有进程的Finish[i]==true都满足，则表示系统处于安全状态，否则系统第三篇计算机操作系统课程设计4处于不安全状态。3设计思路1.进程一开始向系统提出最大需求量；2.进程每次提出新的需求(分期贷款)都统计是否超出它事先提出的最大需求量；3.若正常，则判断该进程所需剩余剩余量(包括本次申请)是否超出系统所掌握的剩余资源量，若不超出，则分配，否则等待。银行家算法流程如图16-4所示：提出进程i的请求向量Resquest[*]Resquest[*]=available[*]ERRORalloc[i][*]+Request[*]=claim[i][*]YesNoERRORnoavailable[*]-=Request[*]alloc[i][*]+=Request[*]yesis_safe()available[*]+=Request[*]alloc[*]-=Request[*]No同意本次分配拒绝本次分配yes图16-4银行家算法流程银行家算法安全检测流程如图16-5所示：第三篇计算机操作系统课程设计5tmp_avail[*]=available[*]寻找进程k满足Claim[k][*]-alloc[k][*]tmp_avail[*]是否存在这样的进程返回FALSEtmp_avail[*]+=alloc[*]标记进程k是否所有的进程都被标记返回TRUE图16-5银行家算法安全检测流程4程序运行调试结果4.1程序初始化第三篇计算机操作系统课程设计64.2检测系统资源分配是否安全结果第三篇计算机操作系统课程设计7第三篇计算机操作系统课程设计85设计小结“银行家算法的模拟实现”是本学期操作系统课程的课程设计。在设计此程序的过行家算法的理解，掌握了银行家算法避免死锁的过程和方法，理解了死锁产生的原因和条件以及避免死锁的方法。所编写程序基本实现了银行家算法的功能，并在其基础上考虑了输出显示格式的美观性，使界面尽可能友好。并且在编程时将主要的操作都封装在函数中，这样使程序可读性增强，使程序更加清晰明了。在算法的数据结构设计上考虑作了一些考虑。当然，在编写和调试过程中我遇到了许多的问题，通过网上查询资料、翻阅课本、向同学请教、多次调试等方法逐渐解决了大部分问题。让我收获很多，相信在今后的生活中也有一定帮助。6参考文献[1]韩立毛，李先锋.计算机操作系统实践教程[M]，南京：南京大学出版社，2011.10.[2]严蔚敏，吴伟民.数据结构[M]，北京：清华大学出版社，1997.4[3]张尧学，史美林.计算机操作系统教程[M]，北京：清华大学出版社，2000.8.[4]孙静宇.计算机操作系统课程设计指导书[M]，山西：太原理工出版社，2006.4.第三篇计算机操作系统课程设计9附录源程序代码#includestdio.h#includestdlib.h#includeconio.h#definem50intno1;//进程数intno2;//资源数intr;intallocation[m][m],need[m][m],available[m],max[m][m];charname1[m],name2[m];//定义全局变量voidmain(){voidcheck();voidprint();