操作系统原理课程设计实践报告题目: 仿真多进程并发环境中死锁的预防、避免、检测与解除姓名:学院: 信息科技学院专业: 计算机科学技术系班级:学号:指导教师: 职称:20010年4月8日仿真多进程并发环境中死锁的预防、避免、检测与解除摘要:在多道程序系统中,多个程序并发执行时可能造成死锁。
所谓死锁是指多个进程在运行过程中因争夺资源而造成的一种僵局。
当进程处于这种僵局状态时若无外力作用,它们都将无法再向前推进,造成资源的浪费。
该程序将模拟多进程并发时死锁现象的产生、避免、检测与解除。
死锁避免用最著名的银行家算法,用银行家安全性算法类似的死锁检测算法来检测进程状况,又用资源剥夺法来实现死锁的解除。
该程序实现操作简易,表示清晰并且形象描述多进程并发环境中死锁的预防、避免、检测与解除。
关键字:死锁;避免死锁;安全状态;银行家算法引言:在操作系统、数据库系统以及网络通信中,由于进程并发和资源共享,当系统中资源分配顺序或者进程推进顺序不当就会造成系统死锁[1]。
处于死锁状态的系统中,进程之间互相等待资源而永远不能继续向前推进,严重地影响了系统的可靠性。
因而有时需要合理的对资源进行分配必要的时候加以限制保证系统安全、高效、稳定的运行。
1理论分析1.1 死锁的概念如果一个进程集合中的每个进程都在等待只能由此集合中的其他进程才能引发的事件,而无限期陷入僵持的局面称为死锁[2]。
1.2 产生死锁的条件:1、互斥使用(资源独占):一个资源每次只能给一个进程使用。
2、不可强占(不可剥夺):资源申请者不能强行的从资源占有者手中夺取资源,资源只能由占有者自愿释放。
3、请求和保持(部分分配,占有申请):一个进程在申请新的资源的同时保持对原有资源的占有(只有这样才是动态申请,动态分配)。
4、循环等待:存在一个进程等待队列{P1,P2,…,Pn},其中P1等待P2占有的资源,P2等待P3占有的资源,…,Pn等待P1占有的资源,形成一个进程等待环路[3]。
1.3死锁的预防在系统设计时确定资源分配算法,保证不发生死锁。
具体的做法是破坏产生死锁的四个必要条件之一。
①破坏“不可剥夺”条件在允许进程动态申请资源前提下规定,一个进程在申请新的资源不能立即得到满足而变为等待状态之前,必须释放已占有的全部资源,若需要再重新申请。
②破坏“请求和保持”条件要求每个进程在运行前必须一次性申请它所要求的所有资源,且仅当该进程所要资源均可满足时才给予一次性分配。
③破坏“循环等待”条件采用资源有序分配法:把系统中所有资源编号,进程在申请资源时必须严格按资源编号的递增次序进行,否则操作系统不予分配。
1.4安全状态与不安全状态所谓安全状态,是指进程能按某种进程次序(p1,p2,⋯,pn),来为每个进程pi 分配其所需资源,直至满足进程pi对资源的最大需求量,使每个进程pi可顺利地完成,则此时系统处于安全状态,称序列(p1,p2,⋯,pn)为安全序列.如果系统无法找到这样一个安全序列,则称系统处于不安全状态[4]。
2 功能设计及其数据结构设计2.1功能设计程序主要提供并发环境的仿真,死锁的检测,银行家算法解决,死锁的解除等功能。
2.2数据结构设计主要数据结构:进程类 Struction_pro 属性:ID,P1,P2,P3,State 类 Struction 属性:P1,P2,P3Struction Resource = new Struction(10,5,7);用于存放每种资源最大值 Struction Available = new Struction(10,5,7); 用于存放每种资源可用值 Struction_pro [] Claim =new Struction_pro[5]; 用于存放进程集合信息Struction_pro[] Allocation = new Struction_pro[5];用于存放进程集合已非配资源信息3 核心算法 3.1银行家算法死锁的避免主要采用银行家算法,流程图如下:银行家算法的基本思想:Y Y Y进程到达 试探分配资源分配给进程 申请资源≤进程需求申请资源≤可用资源 执行安全性算法 资源分配给进程N N N在避免死锁的方法中,所施加的限制条件较弱,有可能获得令人满意的系统性能。
在该方法中把系统的状态分为安全状态和不安全状态,只要能使系统始终都处于安全状态,便可以避免发生死锁。
银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。
它是最具有代表性的避免死锁的算法。
设进程cusneed提出请求REQUEST [i],则银行家算法按如下规则进行判断。
(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i],则转(2);否则,出错。
(2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i],则转(3);否则,出错。
(3)系统试探分配资源,修改相关数据:AVAILABLE[i]-=REQUEST[cusneed][i];ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];NEED[cusneed][i]-=REQUEST[cusneed][i];(4)系统执行安全性检查,如安全,则分配成立;否则试探险性分配作废,系统恢复原状,进程等待。
安全性算法流程图:死锁检测:允许死锁发生,操作系统不断监视系统进展情况,判断死锁是否发生一旦死锁发生则采取专门的措施,解除死锁并以最小的代价恢复操作系统运行死锁检测算法与银行家安全性算法类似。
死锁检测时机有:当进程等待时检测死锁、定时检测、系统资源利用率下降时检测死锁。
该程序才用定时检测。
死锁解除有:重新启动、撤消进程、剥夺资源、进程回退。
该程序中可使用重新启动或者剥夺资源两中方法。
死锁检测与解除往往配套使用,当死锁被检测到之后,采用各种方法解除系统的死锁。
4调试分析4.1无措施运行:进程0请求1个P2失败…进程2请求6个P1失败进程1请求2个P3成功并且分配进程0请求1个P3成功并且分配进程0请求2个P2失败进程0请求1个P1成功并且分配进程4请求1个P3成功并且分配进程4请求2个P2成功并且分配进程4请求1个P1成功并且分配进程2请求1个P3成功并且分配进程2请求7个P1失败进程1请求3个P1成功并且分配进程0请求2个P3成功并且分配进程0请求3个P2成功并且分配进程0请求5个P1成功并且分配运行无措施方案系统完成初始化选择无措施方案,点击运行各进程资源进行申请资源分配资源,出现资源不足情况,造成死锁。
4.2银行家算法:进程4完成并且释放资源进程4需求资源达到要求进程开始运行确定为进程4分配2块P1资源此次请求后存在安全序列: 4尝试为进程4分配2块P1资源…进程2完成并且释放资源进程2需求资源达到要求进程开始运行确定为进程2分配2块P1资源此次请求后存在安全序列: 2 4尝试为进程2分配2块P1资源此次资源请求后不存在安全序列,系统拒接此次资源请求…尝试为进程4分配3块P3资源此次请求后存在安全序列: 1 4 2尝试为进程4分配3块P2资源进程3完成并且释放资源进程3需求资源达到要求进程开始运行尝试为进程3分配0块P2资源此次请求后存在安全序列: 3 1 4 2尝试为进程3分配0块P2资源此次资源请求后不存在安全序列,系统拒接此次资源请求尝试为进程4分配4块P2资源…确定为进程1分配2块P1资源此次请求后存在安全序列: 1 3 2 4尝试为进程1分配2块P1资源进程0完成并且释放资源进程0需求资源达到要求进程开始运行确定为进程0分配1块P1资源此次请求后存在安全序列: 0 3 1 4 2尝试为进程0分配1块P1资源此次资源请求后不存在安全序列,系统拒接此次资源请求尝试为进程4分配1块P1资源尝试为进程0分配2块P3资源此次请求后存在安全序列: 0 3 1 4 2…尝试为进程4分配3块P3资源此次请求后存在安全序列: 0 3 1 4 2尝试为进程4分配3块P2资源此次资源请求后不存在安全序列,系统拒接此次资源请求尝试为进程4分配3块P2资源此次资源请求后不存在安全序列,系统拒接此次资源请求尝试为进程4分配3块P1资源…确定为进程3分配2块P1资源此次请求后存在安全序列: 0 3 1 4 2尝试为进程3分配2块P1资源确定为进程2分配1块P1资源…确定为进程0分配4块P1资源此次请求后存在安全序列: 0 2 4 1 3尝试为进程0分配4块P1资源运行银行家算法系统初始化完成进程0完成并且释放资源进程0需求资源达到要求进程开始运行运行银行家算法,日志显示每次进程申请资源都会进行尝试分配然后计算安全性算法,存在的话则进行分配否则恢复操作。
资源达到条件后则运行,不会出现死锁状况。
4.2自动检测解除:进程0请求1个P2成功并且分配不存在死锁检测死锁程序启动不存在死锁检测死锁程序启动进程0请求1个P2成功并且分配进程0请求1个P1成功并且分配不存在死锁检测死锁程序启动进程0请求2个P1成功并且分配不存在死锁检测死锁程序启动进程0请求3个P3成功并且分配进程0请求1个P2成功并且分配进程0请求4个P1成功并且分配不存在死锁检测死锁程序启动不存在死锁检测死锁程序启动进程4已挂起并且释放已占有资源进程3已挂起并且释放已占有资源进程2已挂起并且释放已占有资源进程1已挂起并且释放已占有资源进程0已挂起并且释放已占有资源产生死锁的进程为: 0 1 2 3 4 检测死锁程序启动进程4请求1个P3成功并且分配进程4请求3个P2失败进程4请求1个P1成功并且分配…进程0请求3个P1成功并且分配运行自动检测与解除系统初始化完成选择自动检测运行,系统自然运行,没隔一段时间会自动检测是否会造成死锁。
如果会造成死锁则将会造成死锁的进程挂起,否则不触发任何事件。
5 计划安排1.进度安排:寒假期间加深对该主题的了解、构思框架、分配任务、学习该掌握的内容并且完成部分功能。
3月8日:确定界面3月9日-3月11:完善程序3月12日-3月13:修改不足,准备答辩2.人员安排:***:数据结构的构建、框架构建、界面设计、分配监督***:银行家算法设计及实现***:死锁检测算法设计及实现3.执行情况:我们小组各成员相互协作,都在规定的时间内完成了事先的计划,并将各自的模块有效地整合到一起,基本实现了题目要求的内容。
6创新及特点1.界面设计直观、人性化,令用户容易入手该软件的使用。
2.每个进程的资源请求都为系统自动分配,实现一键完成调度算法。
3.系统日志,系统自动显示出进程和资源的调度状态7存在问题及提高1.整个系统的资源,及其资源请求都是固定的,可以进一步做到自定义。