《工作计划总结与计划_西安交通大学计算机教学试验中心》由会员分享，可在线阅读，更多相关《工作计划总结与计划_西安交通大学计算机教学试验中心（27页珍藏版）》请在金锄头文库上搜索。
1、HPM&S活动10TheOrangeGame网络中的路由和死锁西安交通大学高效能建模与仿真研究小组2011年10本PPT的材料改编自csunplugged.org项目Puttingcomputerstowork-AlgorithmsHPM&S主要内容l橙子问题的描述l死锁概念l一般解决方案l网络路由l路由和死锁l存储转发死锁l重装死锁l结论及参考文献HPM&S活动背景l曲水流觞是中国古代很多文人雅士热衷的一种游戏。大家坐在河渠两旁，在上流放置酒杯，酒杯顺流而下，停在谁的面前，谁就取杯饮酒并作诗一首，被大家所熟知的著名典故为：永和九年，晋代有名的大书法家、会稽内史王羲之偕亲朋谢安、孙绰等42人，
2、在兰亭修禊后，举行饮酒赋诗的“曲水流觞”活动，引为千古佳话。l死锁的根本原因是资源的竞争。在这个游戏里，酒杯和酒都可以看做资源。随着游戏的进行，酒杯会逐渐聚到下游，上游人有酒没酒杯，下游人有酒杯没酒，如果都不释放资源就形成死锁。HPM&S1.橙子问题的描述l游戏右图是6小孩坐成一个圆圈，他们拥有11个橙子。将孩子和橙子做标记，一个字母对应一个孩子、两个橙子。初始小孩不能持有他们对应的橙子。l目标孩子们通过传递橙子，使每个孩子最终持有他们相应的橙子HPM&S1.橙子问题的描述l橙子传递规则小孩一只手只能拿一个橙子橙子只能经由空手传递给邻居l问题小孩们很快就会发现，如果他们“贪婪”(一旦得到自己的
3、橙子就不放手)，那么该组可能永远无法实现其目标。在该游戏中，只有当每个人都有自己的橙子，这个问题才被真正解决。HPM&S2.死锁概念l死锁多个进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去HPM&S2.死锁概念多个进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去HPM&S2.死锁概念l死锁产生的原因系统资源不足进程运行推进的顺序不合适资源分配不当l死锁产生的四个必要条件资源互斥：一个资源每次只能被一个进程使用请求与保持：一个进程因请求资源而阻塞时，对已获得的资源保持不释放不可剥夺（不可抢占）：进程已获得的资源
4、，在未使用完之前，不能强行剥夺循环等待：若干进程之间形成一种头尾相接的循环等待资源关系HPM&S3.一般解决方案l预防摒弃“请求和保持”条件进程一次性地申请在整个运行过程所需的全部资源，若系统没有足够资源，则全部不分配给进程摒弃“不可剥夺”条件已经保持某些资源的进程，当提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所有资源HPM&S3.一般解决方案l预防摒弃“环路等待”条件资源按某种规则系统中的所有资源统一编号，申请时必须以上升的次序。系统要求申请进程：对它所必须使用的且属于同一类的所有资源，必须一次申请完在申请不同类资源时，必须按各类设备的编号依次申请HPM&S3.一般解决方案l
5、银行家算法（避免）基本思想分配资源之前判断系统是否是安全的若是才分配。它是最具有代表性的避免死锁的算法。数据结构可利用资源向量Available最大需求矩阵Max分配矩阵Allocation需求矩阵NeedHPM&S3.一般解决方案l银行家算法（避免）算法描述设进程cusNeed提出请求REQUESTi，则银行家算法按如下规则进行判断：(1)如果REQUESTcusNeedi=NEEDcusNeedi，则转(2)；否则，出错。(2)如果REQUESTcusNeedi=AVAILABLEcusNeedi。则转(3)；否则，出错。(3)系统试探分配资源，修改相关数据：AVAILABLEi-=REQ
6、UESTcusNeediALLOCATIONcusNeedi+=REQUESTcusNeediNEEDcusNeedi-=REQUESTcusNeedi(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。HPM&S3.一般解决方案l银行家算法（避免）安全性检查算法(1)设置两个工作向量Work=AVAILABLEFINISH(2)从进程集合中找到一个满足下述条件的进程，FINISH=falseNEED=Work如找到，执行(3)；否则，执行(4)(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。Work+=ALLOCATIONFinish=tru
7、eGOTO(2)(4)如所有的进程Finish=true，则表示安全；否则系统不安全。HPM&S3.一般解决方案l鸵鸟算法概念当你对某一件事情没有一个很好的解决方法时，那就忽略它，这样的算法称为“鸵鸟算法“（Ostrichalgorithm）。当系统发生死锁时不会对用户造成多大影响，或系统很少发生死锁的场合采用允许死锁发生的鸵鸟算法，这样一来可能开销比不允许发生死锁及检测和解除死锁的小。大多数操作系统，包括UNIX，MINUX和windows，处理死锁问题的办法仅仅是忽略它。其假设前提是大多数用户宁可在极偶然的情况下发生死锁也不愿接受性能的损失。所以鸵鸟算法，是平衡性能和复杂性而选择的一种方法
8、。HPM&S3.一般解决方案l解除撤销进程撤销陷于死锁的全部进程逐个撤销陷于死锁的进程，直到死锁解除剥夺资源从陷于死锁的进程中逐个强迫放弃所占用的资源，直至死锁消失；从另外一些进程那里强行剥夺足够数量的资源分配给死锁进程，以解除死锁状态HPM&S4.网络路由l概念确定分组从发送发到接收方传送过程中所经历的路径或者路由器l常见路由算法静态路由算法动态路由算法：链路状态算法、距离向量路由算法HPM&S4.网络路由l链路状态算法HPM&S5.路由和死锁死锁是网络中最容易发生的故障之一即使在网络负荷不很重时也会发生。死锁发生时一组节点由于没有空闲缓冲区而无法接收和转发分组节点之间相互等待并一直保持这一
9、僵局。此时只能靠人工干预来重新启动网络解除死锁。HPM&S6.存储转发死锁l直接存储转发死锁两个节点彼此的所有缓冲区都装满了等待输出到对方的分组，造成两节点既不能接收也不能发送分组的现象。l间接存储转发死锁在一组节点之间，某节点的所有缓冲区都装满了等待输出到下一节点的分组，这种情况依次传递构成循环，造成多节点间的死锁。HPM&S6.存储转发死锁l防止方法每个节点设置M+1个缓冲区并以0到M编号。M为通信子网的直径即从任一源节点到任一目的节点间的最大链路段数。每个分组都是按照编号递增规则分配缓冲区。节点之间不会相互等待空闲缓冲区而发生死锁现象。使每个分组上都携带一个全局性的惟一的时间戳每个节点要
10、为每条输入链路保留一个特殊的接收缓冲区而其它缓冲区均可用于存放中转分组。HPM&S7.重装死锁假设发给一个端系统的报文很长被源节点拆成若干个分组发送目的节点要将分组重新装配成报文递交给目的端系统若目的节点用于重装报文的缓冲区空间有限而且它无法知道正在接收的报文究竟被拆成多少个分组此时就可能发生严重的问题:该目的节点用完了它的缓冲空间但它又不能将尚未拼装完整的报文递送给目的端系统而邻节点仍在不断地向它传送分组但它却无法接收。HPM&S7.重装死锁HPM&S7.重装死锁l避免方法允许目的节点将不完整的报文递交给目的端系统一个不能完整重装的报文能被检测出来并要求发送该报文的源端系统重新传送为每个节点
11、配备一个后备缓冲空间用以暂存不完整的报文HPM&S8.结论l主要结论当对资源的需求有依赖关系时，有可能出现“死锁”的情况一个在任何人继续下去之前，死锁都一直存在，因此，有些人总是必须返回的需要相互协作解决问题，个人胜利不代表团队成功HPM&S9.参考文献(1)汤子瀛，哲凤萍，汤小丹，计算机操作系统，西安电子科技大学出版社(2)刘东飞，李春林，计算机网络，清华大学出版社(3)AndrewS.Tanenbaum著，陈向群马洪兵等译，现代操作系统，机械工业出版社(4)AndrewS.Tanenbaum著，潘爱民译，计算机网络，清华大学出版社(5)陆松年主编，潘理翁亮薛质等著，操作系统教程，电子工业出版社HPM&S谢谢HPM&S知识回顾知识回顾KnowledgeKnowledgeReviewReview
