模拟银行家算法实现死锁避免

1《操作系统》课程设计报告院系：计算机与信息工程学院题目：模拟银行家算法实现死锁避免学生姓名：学生学号：专业班级：指导教师：完成时间：2012年9月6日2评分表：课题名称指导教师评语成绩评定姓名成绩学号日期年月日3目录题目：模拟银行家算法实现死锁避免...................................1评分表：...........................................................................................2一课程设计目的....................................................................................5二课程设计内容....................................................................................5三课程设计环境....................................................................................6四课程设计步骤....................................................................................641.需求分析................................................................................64.1.1问题的提出.........................................................................64.1.2银行家算法原理................................................................64.1.3银行家算法详细解析.........................................................74.1.4银行安全性算法目的........................................................84.2概要设计.....................................................................................84.2.1功能模块设计如下：........................................................84.2.2功能模块描述....................................................................94.3详细设计.....................................................................................94.3.1基本数据结构的设计.........................................................94.3.2算法的设计.......................................................................104五课程设计结果..................................................................................115.1运行结果...................................................................................115.2测试分析...................................................................................14六课程设计心得与体会......................................................................14总结.......................................................................................................14七参考文献.........................................................................................15八程序清单.........................................................................................168.1操作主界面代码：...................................................................168.2功能实现代码：........................................................................195一课程设计目的在熟练掌握死锁发生原理和解决死锁问题的基础上，利用一种程序设计语言模拟实现利用银行家算法实现死锁避免，一方面加深对原理的理解，另一方面提高学生通过编程根据已有原理解决实际问题的能力，为学生将来进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。二课程设计内容模拟实现银行家算法对系统资源进行分配，以防止死锁的出现。本课题肯定不可能实现对实际操作系统的资源管理，而是通过对模拟资源数据的处理，检测银行家算法在防止死锁出现的作用。银行家算法描述：第一部分:银行家算法(扫描)1．如果Request=Need,则转向2;否则,出错2．如果Request=Available,则转向3,否则等待3．系统试探分配请求的资源给进程4．系统执行安全性算法第二部分:安全性算法1.设置两个向量(1).工作向量:Work=Available(表示系统可提供给进程继续运行所需要的各类资源数目)(2).Finish:表示系统是否有足够资源分配给进程(True:有;False:没有).初始化为False2.若Finish[i]=False&&Need=Work,则执行3;否则执行4(i为资源类别)63.进程P获得第i类资源,则顺利执行直至完成，并释放资源:Work=Work+Allocation;Finish[i]=true;转2请充分理解以上银行家算法描述的核心思想。（详细银行家算法描述见p95）三课程设计环境Windows操作系统java语言eclipse编程工具四课程设计步骤41.需求分析4.1.1问题的提出银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系银行家算法统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。要解释银行家算法，必须先解释操作系统安全状态和不安全状态。4.1.2银行家算法原理我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管7理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。为保证资金的安全，银行家规定：(1)当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客；(2)顾客可以分期贷款，但贷款的总数不能超过最大需求量；(3)当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款；(4)当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金.操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。4.1.3银行家算法详细解析1、安全性算法：确定计算机系统是否处于安全状态的算法分为如下几步：（1)设置两个工作向量Work=AVAILABLE;FINISH(2)从进程集合中找到一个满足下述条件的进程，FINISH==false;NEED=Work;如找到，执行(3)；否则，执行(4)(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。Work+=ALLOCATION;Finish=true;GOTO2(4)如所有的进程Finish=true，则表示安全；否则系统不安全。2、资源请求算法：设进程k提出请求request[i]，则银行家算法按如下规则进行判断。(1)如果request[k][i]=need[k][i]，则转(2)；否则，出错。(2)如果request[k][i]=avaliable[k][i]，则转(3)；否则，出错。(3)系统试探分配资源，修改相关数据：8avaliable[i]-=request[k][i];avaliable[k][i]+=request[k][i];need[k][i]-=request[k][i];(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。4.1.4银行安全性算法目的银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。4.2概要设计4.2.1功能模块设计如下：图4.2.1：程序功能模块设计图输入系统总资源数输入max(最大资源数)安全性检测操作主界面输入系统进程数输入资源类型数进入操作界面输入allocation资源请求检测94.2.2功能模块描述第一部分:银行家算法1．如果Request=Need,则转向2;否则,出错2．如果Request=Available,则转向3,否则等待3．系统试探分配请求的资源给进程4．系统执行安全性算法第二部分:安全性算法1.设置两个向量(1).工作向量:Work=Available(表示系统可提供给进程继续运行所需要的各类资源数目)(2).Finish:表示系统是否有足够资源分配给进程(True:有;False:没有).初始化为False2.若Finish[i]=False&&Need=Work,则执行3;否则执行4(i为资源类别)3.进程P获得第i类资源,则顺利执行直至完成，并释放资源:Work=Work+Allocation;Finish[i]=true;转24.3详细设计4.3.1基本数据结构的设计staticinttatoal[n];//总资源数staticintavaliable[];//可利用资源数staticintallocation[][];//已用资源数staticintmax[][];//最大资源需求staticintneed[][];//还需的各种资源数staticintrequest[][];//请求资源数104.3.2算法的设计银行家安全性算法思路：图4.3.2：银行家安全性算法流程图对各进程、资源初始化开始进程Pi申请资源是否满足申请条件NO系统安全性检测正式分配资源YES安全不安全11五课程设计结果5.1运行结果(1)主界面图5.1-1:操作主界面(2)输入系统进程数为5、系统资源类型数为3银行家算法算法演