死锁避免-Read.ppt

第四章 死锁 本章的主要内容 死锁的现象及其概念 哲学家就餐问题 死锁的必要条件 死锁的处理 死锁的预防 死锁的避免 死锁的检测 死锁的恢复 死锁的现象 现象1： 独木桥上的双向死锁 死锁的现象 现象2： 四方街区的交通死锁 死锁的现象 现象3： 十字路口的交通死锁 死锁的概念 死锁的概念 计算机系统由有限的资源组成，这些资源在进程之间分配 资源被划分成不同的类型, 每一种类型都有一些实例 比如, 当前系统有两个CPU, 那么CPU这种类型的资源有两个实例 如系统有一个打印机，则对应资源就有一个实例 死锁的概念 在通常的操作模式下, 进程按如下的步骤使用资源: 申请– 如果申请不能马上得到批准，该进程必须等待，直到他获得资源 使用– 该进程可以对资源进行操作 释放– 该进程释放资源 死锁的概念 申请和释放资源是由系统调用, 例子如下: 申请和释放设备资源 打开和关闭文件 分配和释放内存空间 申请 和释放资源 可以通过 在信号量上操作wait and signal来完成 （相当理解我们的P、V操作） 死锁的概念 在多程序系统中, 进程竞争有限的资源 CPU, 内存, 文件, 外设 (磁带, 打印机等 …) 如果一个进程申请一个资源， 但资源不可用， 这个进程可以进入睡眠状态 如果被等待的资源永远不被释放, 那么该进程就永远无法重新运行 死锁的概念 当一个集合中的每一个进程都在等待一个可能由该集合中另一个进程导致的事件时，称该进程集合陷入死锁 状态 ， 比如, 进程1持有磁带驱动器， 进程2持有打印机. 如果这时进程1申请打印机，进程2申请磁带驱动器, 一个死锁就发生了 … 死锁的概念 死锁的定义 若系统中存在一组进程（两个或多个进程），它们中的每一个进程都占用了某种资源而又都在等待该组进程中另一个进程所占用的资源，这种等待永远不能结束，则说系统出现了“死锁”，或说这组进程处于“死锁”状态。 哲学家用餐问题 经典问题——哲学家用餐问题 经典问题——哲学家用餐问题 经典问题——哲学家用餐问题 经典问题——哲学家用餐问题 死锁的必要条件 死锁的必要条件 互斥 占有并等待 非抢占 循环等待 死锁的必要条件 如果一个系统中下面四个条件同时满足时，那么会引起死锁。 互斥：至少有一个资源是处于非共享模式，即一次只有一个进程可以使用。如果另一个申请只能等待到其释放，比如：只有一个CPU。 占有并等待：一个进程占有一些资源，并等待另一个资源，而该资源已被其他进程所占有。 死锁的必要条件 非抢占：资源不能被抢占，即只能由占用该资源的进程完成任务后而释放。 循环等待： 存在一组进程，其中每个进程分别等待另一个进程所占有的资源 如：进程P1在等待 x， x 被进程 P2持有, P2 在等待 y， y 被 P1持有。 如：哲学家进餐问题等 死锁的必要条件 说明：这四个条件不是充分条件而是必要条件，即只要死锁发生则这四个条件同时成立，但是反之则不然。 这四个条件也不是完全相互独立的 “循环等待条件”就包含了“占有并等待”的条件，但是“占有并等待条件”存在时并不一定存在“循环等待条件”，两者既不完全独立也不是等价的。 但是对每个条件分开考虑是很有用的 (见后面死锁的预防) 死锁产生的原因 因为系统资源不足 进程运行推进的顺序不合理 资源分配不当等 资源分配图 资源分配图 死锁可以由系统资源分配图来精确描述, 系统资源分配图是一个有向图，它描述了资源分配的情况 可以以文本方式或图形的方式来描述 由进程集 P， 资源集 R 和边集 E 组成 边可以是分配边或请求边 资源分配图 文本表示方式 进程集 P = {P1, P2, P3, …} 资源集 R = {R1, R2, R3, …} 边集 E = {P1?R1, P2 ? R3, R1 ? P2, R2 ? P3, …} 资源实例说明 进程状态说明 说明：类似数据结构所学的图的表示方法 资源分配图 图形表示方式 进程集 资源集 边集 申请边 分配边 资源分配图 资源分配图 单个实例 资源分配图 单个实例 资源分配图 多个实例 资源分配图 资源分配图 如果资源分配图中有回路 如果每种资源只有一个实例，那么有环就意味着会出现死锁，在这种情况下，图中的环就是死锁存在的充分必要条件。 如果每个资源有多个实例，那么有环并不意味着已经出现死锁，在这种情况下，图中的环就是死锁存在的必要条件而不是充分条件了。 如果图中没有回路，就没有死锁。 死锁的处理 死锁的处理 从原理上来说，有三种方式可以处理死锁问题确保系统决不会进入死锁状态 使用协议进行死锁的预防 使用协议以避免死锁 允许系统进入死锁, 但是要检测它并加以恢复 鸵鸟算法 假装它不会发生（认为死锁不可能在系统内产生） 这种技术被多种操作系统所采用，包括