第9章-死锁.ppt

银行家算法的实质： 设法保证系统动态分配资源后不进入不安全状态，以避免可能产生的死锁。 每当进程提出资源请求且系统的资源能够满足该请求时，系统将判断如果满足此次资源请求系统状态是否安全，如果判断结果为安全，则给该进程分配资源，否则不分配资源，申请资源的进程将阻塞。 【例】已知4个进程：A、B、C、D，总资源数 = 10，进程对资源的最大需求量分别为6、5、4、7。 银行家算法中所用的主要数据结构： (1)可用资源向量Available 记录资源的当前可用数量。如果Available[j]=k，表示现有Rj类资源k个。 (2) 最大需求矩阵Max 每个进程对各类资源的最大需求量 (3)分配矩阵Allocation 已分配给每个进程的各类资源的数量 (4)需求矩阵Need 进程对各类资源尚需要的数量 Need = Max－Allocation (5)请求向量Request 记录某个进程当前对各类资源的申请量 当Pi发出资源请求后，系统按下述步骤进行检查： (1)如果Request Need[i],则出错。 (2)如果Request Available,则Pi阻塞。 (3)假设把要求的资源分配给进程Pi，则有 Available = Available – Request; Allocation[i] = Allocation[i] + Request; Need[i] = Need[i] - Request; 检查此次资源分配后，系统是否处于安全状态。若安全，正式将资源分配给进程Pi，以完成本次分配；否则，恢复原来的资源分配状态，让进程Pi等待。 为进行安全性检查，定义数据结构： ① 工作向量Work 表示系统可提供给进程的各类资源的数量 开始时，Work = Available ② 向量Finish 标记进程是否可运行结束。开始时先做Finish[i] = false；当有足够的资源分配给进程时，令Finish[i] = true. 安全性检查的步骤： (1) Work = Available; 对于每个i，置Finish[i] = false; (2) 寻找满足条件的i： Finish[i] = false，且 Need[i]≤Work; 如果不存在，则转(4) (3) 假设把资源分配给进程Pi，Pi可以运行到结束并释放资源 Work = Work + Allocation[i]; Finish[i] = true; 转(2) (4) 若对所有i，Finish[i]都等于true，则系统处于安全状态，否则处于不安全状态。 银行家算法虽然可以避免死锁，但缺乏实用价值，因为需要实现知道每个进程对每种资源的最大需求。 很少有进程能够在运行前就知道其所需资源的最大值，而且进程数也不是固定的，往往在不断地变化（如新用户登录或退出），况且原本可用的资源也可能突然间变成不可用（如磁带机可能坏掉）。因此，在实际中，如果有，也只有极少的系统使用银行家算法来避免死锁。 * 第9章 死锁 9.1 死锁的基本概念 9.2 死锁的检测与恢复 9.3 死锁避免 9.4 死锁预防 9.1 死锁的基本概念 一、什么是死锁（Deadlock）？ 一个进程集合中的每个进程都在等待只能由该集合中的其它进程才能引发的事件，这种状态称作死锁。 一组竞争系统资源的进程由于相互等待而出现“永久”阻塞。 9.1 死锁的基本概念 为什么会出现死锁？ 竞争资源，而资源有限。 例如，2个进程A、B，都需要资源R1、R2 若A：拥有R1，申请R2 若B：拥有R2，申请R1 如何？ 9.1 死锁的基本概念 二、什么情况下会产生死锁？ 4个 必要条件：coffman(1971)年提出 1）互斥条件 每个资源要么被分配给了1个进程，要么空闲 2）占有及等待（部分分配）条件 已经得到了资源的进程要申请新的资源 3）不可剥夺条件 已经分配给一个进程的资源不能被剥夺，只能由占有者显式释放 4）环路等待条件 存在由2个或多个进程组成的一条环路，该环路中的每个进程都在等待相邻进程占有的资源 9.1 死锁的基本概念 三、如何处理死锁？ 1、由OS处理 检测死锁并恢复 分配资源时避免死锁 假装没看见（鸵鸟策略）：多数OS对待死锁的策略 2、由应用程序本身预防死锁 9.2 死锁的检测与恢复 一、死锁的检测方法 1.每种资源只有1个 借助于资源分配图 方法：构造资源分配图，若存在环，则环中进程死锁。 死锁的检测方法 资源分配图： ：进程 ：资源 ：进程已占有资源 ：进程申请资源，处于等待状态 死锁的检测方法 【例】设系