operatingsystem6ppt课件

1、第六章第六章 死锁死锁6.3 死锁研究的主要内容死锁研究的主要内容6.2 死锁的示例死锁的示例6.1 引论引论目目 录录死锁问题死锁问题(deadlock) OS中重点之一中重点之一一、引论一、引论 早期的操作系统对申请某种资源的进程，若该资源尚未分配时，立即将该资源分配给这个进程。后来发现，对资源不加限制地分配可能导致进程间由于竞争资源而相互制约以至于无法继续运行的局面，人们把这种局面称为死锁 (deadlock)。 死锁问题在1965年由Dijkstra 发现，并随着计算机技术的发展，逐渐成为人们关心的问题。那么，什么是死锁？其确切的定义是什么？死锁是怎么产生的？用什么方法来解决死锁？这些

2、正是今天我们要讨论的问题。二、死锁的示例二、死锁的示例例1. 日常生活中常有许多有关死锁。显然各路车队等待的事件都不会发生。 (假设它们都不改变行车方向) 这样若不采用特殊方法，它们将永远停留在这“ 井字形的路上，而处于死锁状态。 在计算机系统中，进程发生死锁与上述事例实质上是一样的。进程是因相互竞争资源而导致死锁的，与四路车队(可视为进程)竞争路口(可视为资源) 类似。计算机系统中有各种资源，如外设、数据、文件、程序等。例2. 竞争外部设备，设系统中有输入、输出设备各一台，进程A、B的代码形式如下，(争夺资源造成死锁) 进程A： 进程B： (1) 申请输入设备P(x1)(1) 申请输出设备P

3、(x2) (2) 申请输出设备P(x2)(2) 申请输入设备P(x1) (3) 释放输入设备V(x1)(3) 释放输出设备V(x2) (4) 释放输出设备V(x2)(4) 释放输入设备V(x1) 注记 A、B是并发进程，因此语句执行的先后次序是不确定的，如果某次运行是按：A(1)、 B(1)； A(2)、 B(2)秩序进行，即A进程得到了输入设备，B进程得到了输出设备，以后无论A、B按什么次序运行它们的语句，总会出现这种局面：A进程执行到语句(2)便开始等待输出设备，B进程执行到语句(2)便开始等待输入设备，形成A进程占有输入设备等待输出设备，B进程占有输出设备等待输入设备的局面。因为A进程等

4、待的前提是B进程释放输出设备，而B进程释放输出设备的前提是A进程结束等待状态。因而，A、B进程均无法继续运行而出现死锁如图示）：输入设备输出设备AB占有占有等待等待占用打印机共同进展路径1禁区禁区危险区危险区占用输入机占用打印机甲进程的进展乙进程的进展占用输入机XY 该图是对死锁现象的一种非形式的说明。X轴和Y轴分别表示甲进程和乙进程的进展用完成的指令条数来度量）。我们称这个二维空间是单处理机情况下两进程的进展空间，从该空间的原点开始的任何一条阶梯形折线为二进程的共同进展路线，这条进展路线一般情况下只能前进，因为指令的执行是不能倒退的。 当共同进展路径是按图中的路径1前进，这时不会发生死锁，因

5、为乙进程在甲进程提出对输入机的要求前，已完成了对输入机和打印机的使用，并且释放了它们。反之在乙进程对打印机提出要求前，甲进程已完成了对输入机和打印机的使用，并且释放了它们。这种共同进展路径也不会使系统成为死锁状态。但是如果二进程的共同进展路径按照这样的路径向前进时，甲进程占有了输入机，乙进程占有了打印机，从而共同进展路径进入了危险区。 危险区的右上角的顶点是死锁点。共同进展路径在危险区中前进时必定会到达危险区边缘上边、右边或死锁点），设到达了危险区的右边。这时的情况是乙进程仍然占有打印机，但尚未提出占有输入机的要求。而甲进程占有着输入机，并且提出对打印机的要求。甲进程由于资源要求不能满足而被阻

6、塞，这时只有乙进程使用处理机并取得进展，直到乙进程提出对输入机请求时也被阻塞。系统成为死锁状态。二进程的共同进展路径到达死锁点以后就无法前进了。例3. 进程通讯 (计算机通讯中)设有四个进程P、S、Q、R，用四个(buffer)缓冲区进行通讯，进程分别有如下代码：进程P：send (R.1); 通过1号缓冲区向R发信息waiter (R.answer); 等待R的回答send (Q.2); 通过2号buffer向Q发信息进程R：send (S.3); 通过3号buffer向S发信息waiter (S.answer); 等待S的回答Receive (P.1); 接收P从1号buffer送来的信息

7、answer (P); 回答P进程S：Receive (Q.4); 接收Q从4号buffer送来的信息Receive (R.3); 接收R从3号buffer送来的信息answer (R); 回答R进程Q：Receive (P.2); 接收P从2号buffer送来的信息Send (S.4); 通过4号buffer向S发信息这四个进程启动后将进入死锁状态：P要收到R的回答后才向Q发送信息；R回答P之前要等待S的回答；S要收到Q送来信息后才回答R；而Q需收到P送来的信息后才向S发送信息，所以都无法再运行。P PSRQ2143满空空满buffer三、死锁的定义及性质三、死锁的定义及性质 从以上的例 2

8、 中，不难看出，所谓死锁是指进程处于等待状态，且等待事件永远不会发生。造成死锁的原因：(a) P、V操作死锁 例2(b) 推进顺序不当 例1(c) 因资源不足而争夺资源死锁 例1、2(d) 协同进程本身设计中的错误(无论按什么次序运行总免不了死锁) 例31. 死锁的定义死锁的定义 在一个进程集合中，若每个进程都在等待某些事件指：释放资源的发生，而这些事件又必须由这个进程集合中的某些进程来产生，就称该进程集合处于死锁状态。 前述车队事例中的四个车队有如一个进程集合，它们处于等待状态，等待的都是另一车队让出路，对另外几例同样可以用定义来分析。2. 死锁的四个必要条件：死锁的四个必要条件：(1) 互

9、斥：在出现死锁的系统中，必然存互斥：在出现死锁的系统中，必然存在需要互斥使用的资源，计算机系统中有存储在需要互斥使用的资源，计算机系统中有存储器、器、CPU外部设备、共享程序等各种资源，有外部设备、共享程序等各种资源，有些资源可以共享使用，有的必须独占使用，即些资源可以共享使用，有的必须独占使用，即互斥使用，若系统中所有的资源均可共享使用，互斥使用，若系统中所有的资源均可共享使用，则进程不会处于等待资源的状态，因而不会出则进程不会处于等待资源的状态，因而不会出现死锁。因而，系统出现了死锁，就说明必定现死锁。因而，系统出现了死锁，就说明必定有需要互斥使用的资源。有需要互斥使用的资源。(2) 占有

10、等待：在出现死锁的系统中，一定占有等待：在出现死锁的系统中，一定有已分配到了某些资源并且在等待另外的资源的有已分配到了某些资源并且在等待另外的资源的进程。如果这个条件不满足，则所有等待资源的进程。如果这个条件不满足，则所有等待资源的进程都不会占有任何资源，而资源的拥有者也不进程都不会占有任何资源，而资源的拥有者也不会处于等待资源的状态中。因而，拥有资源的进会处于等待资源的状态中。因而，拥有资源的进程迟早会释放出它们所拥有的资源，从而使等待程迟早会释放出它们所拥有的资源，从而使等待这些资源的进程结束等待状态，所以占有等待也这些资源的进程结束等待状态，所以占有等待也是死锁的必须满足的条件之一。是死

11、锁的必须满足的条件之一。(3) 不可剥夺：在出现死锁的系统中，不可剥夺：在出现死锁的系统中，一定有不可剥夺使用的资源。不可剥夺是指一定有不可剥夺使用的资源。不可剥夺是指在进程未主动释放资源之前不可被剥夺资源。在进程未主动释放资源之前不可被剥夺资源。若资源都可剥夺，进程就不会进入僵持状态若资源都可剥夺，进程就不会进入僵持状态而出现死锁。而出现死锁。(4) 循环等待：在出现死锁的系统中，一定存在循环等待：在出现死锁的系统中，一定存在一个处于等待状态的进程集合：一个处于等待状态的进程集合：P0, P1,，PiPn,，其中，其中Pi等待的资源被等待的资源被Pi+1占有占有(i = 0,1,n1)，Pn

12、等待的资源被等待的资源被P0占有占有(如图如图4)。P0P1P2Pn.(图4)条件4 乍看与死锁定义似乎一样，其实不然。按死锁定义构成等待所要求的条件更强，要求 Pi 等待的资源必由Pi+1 来满足。而循环等待条件则弱一些，Pi 等待的资源由Pi+1 占有，当然也有可能被另外一个进程所占有。例如：系统中有两台输出设备，Pi+1 占有一台，Pk 占有另一台，且 k0,1,n。虽然系统有一个循环等待圈，但Pk 不在圈内。若Pk 释放了输出设备，则可打破循环等待圈(如图5)。因此循环等待只是死锁的必要条件。Pi+1 Pi+2 Pi1 Pi Pk .(图5)注 上述死锁的四个必要条件不是彼此独立的，比

13、如条件 4 包含了前三个条件。而将它们分别列出是为了方便我们研究各种防止死锁的方法。3. 资源与死锁资源与死锁(1) 死锁与设备、文件等实体的互斥访问有关，为叙述方便我们称它们为资源。 资源既可以指硬件设备，也可能指软件信息。计算机有许多可供进程使用的资源，而对于某种资源，它在数目上可能不止一个。进程申请这类资源时，可分配其中任何一个给它。(2) 一个进程获取资源的步骤如下：a. 申请资源b. 使用资源c. 释放资源(3) 当进程申请资源，而资源当前又无剩余时，进程必须等待。在一些操作系统中，进程申请失败后便自动阻塞。当资源可用时，再把进程唤醒。另一些OS则是在进程申请失败后，给出一个错误码，

14、因此是由进程本身决定等待时间，然后重新申请。例：三个进程A、B、C，三类资源R、S、TA进程，请求R，请求S，释放R，释放S；B进程，请求S，请求T，释放S，释放T；C进程，请求T，请求R，释放T，释放R；1) 假设：ABC，不会死锁，进程间不存在资源竞争，但这种运行顺序的并行度很低，某一进程做I/O时，CPU的时间浪费掉了。A B C A B CABCRST2) 为取得较高的并行度，可采用轮转法调度，在这种调度方案下，有可能出现下列执行顺序。 从上面的分析可知会出现死锁，若上例中暂不调度B进程运行，而只运行A和C，那么：A C A C A C系统不会死锁。最后再运行B，也可完成。四、死锁研究

15、的主要内容四、死锁研究的主要内容1. 死锁问题有许多内容有待研究，这里主要介绍死锁问题有许多内容有待研究，这里主要介绍解决死锁所采用的方法：解决死锁所采用的方法：忽略此问题不做任何实际处理 (鸵鸟策略)设计无死锁的系统允许系统出现死锁后排除之死锁防止 (deadlock prevention)死锁避免 (deadlock avoidance)死锁检测 (deadlock detection)死锁恢复 (deadlock recovery)2. 死锁的防止死锁的防止 通过破坏死锁存在的(4个)必要条件来防止死锁发生。我们不妨把死锁的四个必要条件记做C1， C2， C3， C4，把死锁记做D，则有

16、逻辑公式：D C1C2 C3 C4，由离散数学公式推导得： C1 C2 C3 C4D(2)式中的“ ”表示“ 蕴含”；“ ”表示“ 与”；“ ”表示“ 或”；“ ”表示“ 非”。由(2) 式可知，只要系统中有一个必要条件不成立就能不出现死锁，此即死锁防止的思想基础。(1) 破坏互斥条件破坏互斥条件 如果允许系统资源都能共享使用，则系统不会进入死锁状态。但这种方法不是切实可行的。因为有些资源若是共享使用。例如：打印机在多进程打印，不能每个进程打印一行，则无法保证其正确性。又如，对临界资源的访问就必须互斥进行。(2) 破坏占有等待破坏占有等待 (二个方法二个方法) 方法一：进程申请到它所需要的所有

17、资源后，才能开始运行，又称预先静态分配法。例如，一个制表打印进程，需占有打印机，才能运行。此方法虽可保证无死锁，但是 资源的利用率低 (在程序运行中，打印机空闲)； 由于所需资源不能在一次中得到全部满足，而使作业无限期延长。 方法二：进程提出申请资源前必须释放已占有的一切资源。这些虽然能提高资源利用率，但要仔细进行程序设计，有时仍需提前申请资源才能保证正确性。这使用户倍感不便。 注要考虑无限等待现象 (其实质与死锁一样)。例：P1申请r1, r2, r3，而仅有r3。这时P2申请r3；则把r3给P2，某一进程Pi又释放了r1, r2，而 P1又因无r3，仍需等待直到饿死P1。 我们应有相应的防

18、止措施。比如按申请资源的先后秩序给进程赋优先级。这种资源预先分配的方法，适于对外存空间的分配。因为作业运行期间所需外存变化不大。(3) 破坏非剥夺性条件破坏非剥夺性条件 在进程主动释放占有的资源前即予以剥夺，也能保证系统不出现死锁。 方法一：当进程Pi申请rj类资源时，检查rj中有无可分配的资源，有则分配给Pi；否则将Pi占有的资源全部释放进入等待状态。 方法二：当Pi申请rj时，检查rj中有无可分配的资源，有则分配；否则检查占有rj类资源的进程Pk。若Pk处于等待资源状态，则剥夺Pk的rj分给Pi；若Pk处于不等待资源状态，则置Pi于等待资源状态 (此时Pi原占有的资源可能被剥夺。)注剥夺资源时，需保存中间信息。因使用资源的进程尚未主动释放资源，这样开销很大。故只宜在CPU和主存这类重要资源的管理上使用。不宜剥夺临介资源等类型资源。(4) 破坏循环等待条件破坏循环等待条件 采用资源顺序分配法，可以破坏循环等待条件。该方法首先给系统中的资源编号 (唯一)，即寻找一个函数F：RN (R：表资源类集合) 即r1, r2, ri12iF(ri) = i每个进程只能按序号由小到大的顺序申请资源，而且对它所必须使用的且属于某