网络中的路由和死锁

1、HPM&S活动活动10 The Orange Game网络中的路由和死锁网络中的路由和死锁西安交通大学高效能建模与仿真研究小组2011年10本PPT的材料改编自项目Putting computers to work-AlgorithmsHPM&S 主要内容主要内容l橙子问题的描述l死锁概念l一般解决方案l网络路由l路由和死锁l存储转发死锁l重装死锁l结论及参考文献HPM&S活动背景活动背景l曲水流觞是中国古代很多文人雅士热衷的一种游戏。大家坐在河渠两旁，在上流放置酒杯，酒杯顺流而下，停在谁的面前，谁就取杯饮酒并作诗一首，被大家所熟知的著名典

2、故为：永和九年，晋代有名的大书法家、会稽内史王羲之偕亲朋谢安、孙绰等42人，在兰亭修禊后，举行饮酒赋诗的“曲水流觞”活动，引为千古佳话。l死锁的根本原因是资源的竞争。在这个游戏里，酒杯和酒都可以看做资源。随着游戏的进行，酒杯会逐渐聚到下游，上游人有酒没酒杯，下游人有酒杯没酒，如果都不释放资源就形成死锁。HPM&S1. 1. 橙子问题的描述橙子问题的描述l游戏右图是6小孩坐成一个圆圈，他们拥有11个橙子。将孩子和橙子做标记，一个字母对应一个孩子、两个橙子。初始小孩不能持有他们对应的橙子。l目标孩子们通过传递橙子，使每个孩子最终持有他们相应的橙子HPM&S1. 1. 橙子问题的描述

3、橙子问题的描述l橙子传递规则小孩一只手只能拿一个橙子橙子只能经由空手传递给邻居l问题小孩们很快就会发现，如果他们“贪婪”(一旦得到自己的橙子就不放手)，那么该组可能永远无法实现其目标。在该游戏中，只有当每个人都有自己的橙子，这个问题才被真正解决。HPM&S2. 2. 死锁概念死锁概念l死锁多个进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去HPM&S2. 2. 死锁概念死锁概念多个进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去HPM&S2. 2. 死锁概念死锁概念l死锁产生的原因系统资

4、源不足进程运行推进的顺序不合适资源分配不当l死锁产生的四个必要条件资源互斥：一个资源每次只能被一个进程使用请求与保持：一个进程因请求资源而阻塞时，对已获得的资源 保持不释放不可剥夺（不可抢占）：进程已获得的资源，在未使用完之前，不能强行剥夺循环等待：若干进程之间形成一种头尾相接的循环等待资源关系HPM&S3. 3. 一般解决方案一般解决方案l预防摒弃“请求和保持”条件进程一次性地申请在整个运行过程所需的全部资源，若系统没有足够资源，则全部不分配给进程摒弃“不可剥夺”条件已经保持某些资源的进程，当提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所有资源 HPM&S3.

5、3. 一般解决方案一般解决方案l预防摒弃“环路等待”条件资源按某种规则系统中的所有资源统一编号，申请时必须以上升的次序。系统要求申请进程： 对它所必须使用的且属于同一类的所有资源，必须一次申请完在申请不同类资源时，必须按各类设备的编号依次申请HPM&S3. 3. 一般解决方案一般解决方案l银行家算法（避免）基本思想分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。数据结构可利用资源向量Available 最大需求矩阵Max分配矩阵Allocation需求矩阵NeedHPM&S3. 3. 一般解决方案一般解决方案l银行家算法（避免）算法描述设进程

6、cusNeed提出请求REQUESTi，则银行家算法按如下规则进行判断：(1)如果REQUESTcusNeedi=NEEDcusNeedi，则转(2)；否则，出错。(2)如果REQUESTcusNeedi=AVAILABLEcusNeedi。则转(3)；否则，出错。(3)系统试探分配资源，修改相关数据： AVAILABLEi-=REQUESTcusNeedi; ALLOCATIONcusNeedi+=REQUESTcusNeedi; NEEDcusNeedi-=REQUESTcusNeedi; (4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。 HPM

7、&S3. 3. 一般解决方案一般解决方案l银行家算法（避免）安全性检查算法(1)设置两个工作向量Work=AVAILABLE;FINISH (2)从进程集合中找到一个满足下述条件的进程， FINISH=false; NEED=Work; 如找到，执行(3)；否则，执行(4) (3)设进程获得资源，可顺利执行，直至完成，从而释放资源。 Work+=ALLOCATION; Finish=true; GOTO (2) (4)如所有的进程Finish= true，则表示安全；否则系统不安全。 HPM&S3. 3. 一般解决方案一般解决方案l鸵鸟算法概念当你对某一件事情没有一个很好的解决

8、方法时，那就忽略 它 ， 这 样 的 算 法 称 为 “ 鸵 鸟 算 法 “ （ O s t r i c h algorithm）。当系统发生死锁时不会对用户造成多大影响，或系统很少发生死锁的场合采用允许死锁发生的鸵鸟算法，这样一来可能开销比不允许发生死锁及检测和解除死锁的小。大多数操作系统，包括UNIX，MINUX和windows，处理死锁问题的办法仅仅是忽略它。其假设前提是大多数用户宁可在极偶然的情况下发生死锁也不愿接受性能的损失。所以鸵鸟算法，是平衡性能和复杂性而选择的一种方法。 HPM&S3. 3. 一般解决方案一般解决方案l解除撤销进程撤销陷于死锁的全部进程逐个撤销陷于死锁的

9、进程，直到死锁解除剥夺资源从陷于死锁的进程中逐个强迫放弃所占用的资源，直至死锁消失； 从另外一些进程那里强行剥夺足够数量的资源分配给死锁进程，以解除死锁状态HPM&S4. 4. 网络路由网络路由l概念确定分组从发送发到接收方传送过程中所经历的路径或者路由器l常见路由算法静态路由算法动态路由算法：链路状态算法、距离向量路由算法HPM&S4. 4. 网络路由网络路由l链路状态算法HPM&S5. 5. 路由和死锁路由和死锁死锁是网络中最容易发生的故障之一,即使在网络负荷不很重时也会发生。死锁发生时,一组节点由于没有空闲缓冲区而无法接收和转发分组,节点之间相互等待,并一直保持这

10、一僵局。此时,只能靠人工干预来重新启动网络,解除死锁。HPM&S6. 6. 存储转发死锁存储转发死锁l直接存储转发死锁两个节点彼此的所有缓冲区都装满了等待输出到对方的分组，造成两节点既不能接收也不能发送分组的现象。l间接存储转发死锁在一组节点之间，某节点的所有缓冲区都装满了等待输出到下一节点的分组，这种情况依次传递构成循环，造成多节点间的死锁。HPM&S6. 6. 存储转发死锁存储转发死锁l防止方法每个节点设置M+1个缓冲区,并以0到M编号。 M为通信子网的直径,即从任一源节点到任一目的节点间的最大链路段数。每个分组都是按照编号递增规则分配缓冲区。节点之间不会相互等待空闲缓冲区

11、而发生死锁现象。使每个分组上都携带一个全局性的惟一的时间戳,每个节点要为每条输入链路保留一个特殊的接收缓冲区,而其它缓冲区均可用于存放中转分组。 HPM&S7. 7. 重装死锁重装死锁假设发给一个端系统的报文很长,被源节点拆成若干个分组发送,目的节点要将分组重新装配成报文递交给目的端系统若目的节点用于重装报文的缓冲区空间有限,而且它无法知道正在接收的报文究竟被拆成多少个分组此时,就可能发生严重的问题:该目的节点用完了它的缓冲空间,但它又不能将尚未拼装完整的报文递送给目的端系统,而邻节点仍在不断地向它传送分组,但它却无法接收。 HPM&S7. 7. 重装死锁重装死锁HPM&

12、;S7. 7. 重装死锁重装死锁l避免方法允许目的节点将不完整的报文递交给目的端系统一个不能完整重装的报文能被检测出来,并要求发送该报文的源端系统重新传送为每个节点配备一个后备缓冲空间,用以暂存不完整的报文HPM&S8. 8. 结论结论l主要结论当对资源的需求有依赖关系时，有可能出现当对资源的需求有依赖关系时，有可能出现“死锁死锁”的情况的情况一个在任何人继续下去之前，死锁都一直存在任何人继续下去之前，死锁都一直存在，因此，有些人总是必须返回的在，因此，有些人总是必须返回的 需要相互协作解决问题，个人胜利不代表团需要相互协作解决问题，个人胜利不代表团队成功队成功HPM&S9. 9. 参考文献参考文献