现代操作系统第六章死的锁PPT.ppt

* 从死锁中恢复 杀死进程来恢复 最粗鲁也是最简单的解决死锁的方法就是杀死一个或多个进程。 杀掉环路中的一个进程。 另外，也可以是将环路外的进程作为牺牲品，以释放资源。 最好杀死可以从头再运行而不会产生副作用的进程。 * 死锁避免 在讨论死锁检测时，我们假设，当进程申请资源时，它一次性申请所有的资源。 不过，在大多数系统中一次只申请一个资源。系统必须能够判断授权某个资源是否安全，并且只在安全的情况下分配资源。 这就引出了一个问题：是否存在一种算法总能作出正确的选择从而避免死锁？答案是肯定的，但是必须预知某些特定的信息。 * 资源轨迹图 避免死锁的主要算法基于安全状态的概念。在描述该算法之前，先了解安全的概念。通过图示的方式，更容易理解。尽管该图的方法不能直接转换成可用的算法，但它给出了一个解决问题的直觉。 在下图中，可以看到处理两个进程和两种资源(打印机和绘图仪)的模型。 * 两个进程的资源轨迹 资源轨迹图 * 安全和不安全状态 在任何时刻，当前状态都包括E, A, C和R。如果没有死锁，而且存在某种调度次序能够满足所有进程最大的资源请求并且完成它们，那么此状态就是安全(safe)的。 不安全状态没有任何序列可以保证完成工作。 安全状态和不安全状态的区别是：从安全状态出发，系统能够确保所有进程都能完成；而从不安全状态出发，不存在这样的保证。 * 安全和不安全状态 上图中状态(a)是安全的 从状态(a)出发，存在一个分配序列B、C、A使得所有进程都可以完成 * 安全和不安全状态 上图中状态(b)是不安全的 从状态(b)出发，不存在任何一个分配序列可以使得所有进程都完成 * 单资源的银行家算法 Dijkstra(1965)提出了一种能够避免死锁的调度算法，称为银行家算法(banker’s algorithm)，该算法是死锁检测算法的扩展。 它是一个小镇的银行家为模型设计的，银行家向一群客户分别承诺了一定的贷款额度。 该算法所作的就是检查请求获准是否会导致不安全状态。如果会，请求即被拒绝；否则，批准其请求。 * 资源分配状态 (a) 安全 (b) 安全 (c) 不安全 单资源的银行家算法 * 算法： 对每个资源请求检查满足它会否引起不安全状态，如果是不安全状态，则不满足此请求。 检测状态是否安全：此状态下是否有足够的资源满足一个距最大需求最近的客户，如果有，将此客户标记，（设客户运行结束）资源释放后，继续检查其他客户，直至所有客户都被标记则是安全状态，否则是不安全状态。 单资源的银行家算法 * 多资源的银行家算法 银行家算法可以进行推广到处理多种资源。 检查一个状态是否安全的步骤如下： 查找矩阵R，有没有某行Ri=向量A。如果找不到，那么系统最终将会死锁，因为任何进程都无法运行完成。 若有,假设被选择的进程i申请其所需的所有资源(已经确保有可能满足)并且完成，将该进程标记为终止，并将其所有资源加到向量A上，即A?A+Ci。 重复以上两步，直到所有的进程都标记为终止。如果所有进程都可以终止，那么初始状态是安全的；否则，就会产生死锁。 * 多资源的银行家算法范例 多资源的银行家算法 * 银行家算法中，若出现下述的资源分配情况 Allocated Need Available P0 0 0 3 2 0 0 1 2 1 6 2 2 P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6 P3 0 3 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6 问：①该状态是否安全,为什么？ ② 如P2提出资源分配请求（0 0 0 1），系统能否将资源分配给它？ 多资源的银行家算法实例 * 解：①该状态安全，因为存在分配序列使的所有的进程都可以运行完成： P0 (0 0 1 2)(1 6 2 2)?A=(1 6 5 4) P3 (0 6 5 2)(1 6 5 4)?A=(1 9 8 6) P1 (1 7 5 0)(1 9 8 6)?A=(2 9 8 6) P4 (0 6 5 6)(2 9 8 6)?A=(2 9 9 10) P2 (2 3 5 6)(2 9 9 10) ?A=(3 12 14 14) ②不能分配，因为如果分配给P2 （0 0 0 1），则系统还剩资源（1 6 2 1），在系统中找不到一个进程可以满足NeedAvailable，进程将处于死锁状态。 多资源的银