1、HPM&S活动 10 The Orange Game 网络中的路由和死锁西安交通大学高效能建模与仿真研究小组2011年 10本 PPT的材料改编自 csunplugged.org项目Putting computers to work-AlgorithmsHPM&S主要内容l橙子问题的描述l死锁概念l一般解决方案l网络路由l路由和死锁l存储转发死锁l重装死锁l结论及参考文献HPM&S活动背景l曲水流觞是中国古代很多文人雅士热衷的一种游戏。大家坐在河渠两旁，在上流放置酒杯，酒杯顺流而下，停在谁的面前，谁就取杯饮酒并作诗一首，被大家所熟知的著名典故为：永和九年，晋代有名的大书法家、会稽内史王羲之偕亲
2、朋谢安、孙绰等 42人，在兰亭修禊后，举行饮酒赋诗的 “ 曲水流觞 ” 活动，引为千古佳话。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预防摒弃 “ 环路等待 ” 条件资源按某种规则系统中的所有资源统一编号，申请时必须以上升的次序。系统要求申请进程： 对它所必须使用的且属于同一类的所有资源，必须一次申请完 在申请不同类资源时，必须按各类设备的编号依次申请
