补充课件4：死锁概念引入解析.pptVIP

2.8 死 锁 在多道程序系统中，并发进程改善了系统资源利用率和提高系统的吞吐量，但可能死锁。 [例]一个计算机系统，它有4台磁带机和2个并发执行的进程。某一时刻，每一进程都已占有2台磁带机，还要再请求一台磁带机才能完成它们的任务。这时，由于系统再无空闲的磁带机，两个进程就处于永远的等待状态，我们就说系统产生了死锁。 2.8.1 死锁的定义和死锁产生的必要条件 1. 资源的特性 硬件资源：如打印机、磁带机、主存等。 软件资源：如共享变量、数据库中的加锁记录。 可抢占资源：是这样一类资源，当资源从占用进程剥夺走时，对进程不产生什么破坏性的影响。如主存、CPU。 不可抢占资源：一旦分配，不能强收回，只能由其自动释放。如打印机、磁带机。通常情况下，死锁涉及的是不可抢占资源。 一个进程必须按下述三个顺序事件使用资源。 （1）请求资源：若请求不能立即满足，则申请者等待。 （2）使用资源：获得资源后，可使用它。 （3）释放资源：使用完毕，将资源归还系统。 2. 死锁的定义 死锁：是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能向前推进。 资源互斥使用：任一时刻只允许一个进程使用资源 部分分配：进程在请求其余资源时，不主动释放已经占用的资源 不可剥夺性：进程已经占用的资源，不会被强制剥夺 环路等待：环路中的每一条边是进程在请求另一进程已经占有的资源。 2.8.2 解决死锁的方法 用有向图研究解决死锁的方法。 图中圆圈代表进程，方块代表资源。 资源已经分配给进程用从资源 (方块)到进程 (圆圈)的有向弧表示； 进程请求该资源用从进程到资源的有向弧表示。 图2.10给出进程对资源的可能情况。 处理死锁的基本方法 鸵鸟算法。忽略死锁。 预防死锁。通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来防止发生死锁。 避免死锁。是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。 检测和恢复死锁。允许死锁发生，通过设置检测机构，及时检测出死锁的发生，然后采取适当措施清除死锁。 1 鸵鸟算法（置之不理） 是解决死锁的最简单方法。即像鸵鸟一样，当遇到危险时，将头埋进沙子里，假装毫无问题。 当死锁在计算机中很少出现时，比如说每五年或更长时间才出现一次时，人们就不必花费更多的精力去解决它，而是采用类似鸵鸟一样的办法忽略它。 [例] UNIX系统，它潜在地存在死锁，但它并不花功夫去检测和解除死锁，而是忽略不去理它。 2 死锁的检测和恢复 死锁的检测和恢复技术：是指定期启动一个软 件检测系统的状态，若发现有死锁存在，则采取措 施恢复之。 (1)死锁的检测 [方法]：由软件检查系统中由进程和资源构成的 有向图是否构成一个或多个环路，若是，则存在死 锁，否则不存在。 [例]假定系统有七个进程:A～G;六个资源:R～W。资源 的使用情况如下: 进程A保持资源R，请求资源S。 进程B没有保持资源，请求资源T。 进程C也没有保持资源，请求S资源。 进程D保持资源U，请求S和T资源。 进程E保持T，请求V资源。 进程F保持W，请求S资源。 进程G保持V，请求U资源。 进程资源图如图2.11 一个简单的死锁检测算法 需要一个数据结构L，用来记录系统中各节点的情况。执行过程中，标记已检测过的弧。 类似于有向图的遍历。 ①对于图中的每个节点N，以N为起始节点，执行以下5步。 ②将L初始化为空表，以表示所有弧都未标记过。 ③将当前节点加到L的末端，检查这个节点在表中是否出现过。如果是，这个图包含一个环路，算法终止。如果没有，转④。 ④由这个节点再看，是否有未标记的引出弧。如果有，转⑤；若没有，转⑥。 ⑤任意选择一个未标记的引出弧并标记它。然后，将引出弧所到节点作为新的当前节点，转③。 ⑥若所有从这个节点引出的弧都已标记，则返回到前一个节点，如果这个节点是最初开始的节点，这个图没有包含环路，算法终止；若不是初始节点，再以该节点作为当前节点，转③。 以图2.11为例： 假定从上到下，从左到右。从R开始，然后依次为A，B，C，S，D，T，E，F等。若找到了一个环路，该算法终止。 以R为起始节点并将L初始化为空表。将R加入表中，从R出发，只有一个未标记的弧，标记它，随后它指向A，将A加入L中，此时 L=［R,A］。由A到S也只有一个未标记弧，标记它，将S加入表中，L=［R,A,S］。由于S没有引出弧，S为终结节点，由S回退到A。由于A没有未标记的弧，再回退到R，完成了对R的检测。 以A为起始节点开始这个算法,重置L为空。这次检索很快停止(因为A又指向S)。 再从B开始。由B跟踪引出弧一直到D,得L=[B,T,E,V,G,U,D]。此时D有两条引