windows操作系统概述.ppt

第十讲死锁 目的与要求 了解死锁的定义 掌握死锁预防 了解死锁避免 死锁检测 死锁恢复的方法 重点与难点 死锁预防法则的使用 作业 21 22 4 4死锁4 4 1死锁示例 日常生活中的例子进程死锁的例子竞争外部设备竞争辅存空间编程错的例子 4 4 2死锁定义及性质 死锁定义在一个进程集合中 若每个进程都在等待某些事件 指 释放资源 的发生 而这些事件又必须由这个进程集合中的某些进程来产生 就称该进程集合处于死锁状态 死锁定义及性质 出现死锁的系统必须同时满足下列四个必要条件互斥 必须存在需要互斥使用的资源占有等待 一定有占有资源而又等待其它资源的进程非剥夺 系统中进程占有的资源未主动释放时不可以剥夺循环等待 进程集合 P0 P1 Pn Pi等待Pi 1 Pn等待P0 死锁定义及性质 资源分配图定义资源分配图由如下部件组成 如果各类资源数为1 则系统出现死锁的充要条件是资源分配图含圈 Pi 死锁研究的主要内容 死锁防止死锁避免死锁检测死锁恢复 无死锁系统 允许死锁 出现排除 4 4 3死锁防止 逻辑公式 D C1 C2 C3 C4 C1 C2 C3 C4 D 破坏互斥占用条件让资源都能共享使用 但有些资源必须互斥使用 破坏占有等待条件将进程所要资源一次性分给进程 要么没分到一个资源 要么全部满足 适合廉价资源的分配 如外存空间分配 进程在下一轮申请资源时 释放所占的所有资源 用完一个再用下一个 破坏非剥夺条件 用于内存管理 CPU管理等 当进程Pi申请ri类资源时 若有则分配 若没有则剥夺 释放 Pi占有的所有资源 当进程Pi申请ri类资源时 若有则分配 若无则剥夺 淘汰 占有ri类资源进程所占的ri类资源分配给Pi 或看占用ri类资源的Pk处于什么状态 若处于等资源状态 则剥夺其资源 否则让Pi等待 等于剥夺Pi的资源 破坏循环等待条件采用资源顺序分配方法 给每类资源编号 进程只能按序号由小到大的顺序申请资源 若不满足则拒绝分配 反证 若出现循环等待 则必会有小序号资源序号 大序号资源序号 4 4 4死锁避免 银行家算法 在系统处理资源申请时 判断在满足申请时 系统是否还处于安全状态 是则满足本次资源申请 否则拒绝 依此引导进程运行次序 单类资源系统安全状态定义 设系统中有n个进程 若存在一个序列 P1 2 n 使得Pi i 1 2 n 以后还需要的资源可以通过系统现有资源加上所有Pj j i 占有的资源来满足 则称这个系统处于安全状态 序列 n 称为安全序列 举例 设银行家有10万贷款 P Q R分别需要8 3 9万元搞项目 假设任何人满足资金总额后都会归还所有贷款 如果P已申请到了4万 Q要申请2万 显然 如果满足Q的申请 有安全序列 但如果R要申请4万 显然 如果满足R的申请 则不存在安全序列 扩展的银行家算法描述n 系统中的进程个数 m 系统中的资源类型数 Available 1 m 现有资源向量 Available j k表示有k个未分配的j类资源 Max 1 n 1 m 资源最大申请量矩阵 Max i j k表示第i个进程对第j类资源的最大申请量为k Allocation 1 n 1 m 资源分配矩阵 Allocation i j k表示进程i已占有k个j类资源 Need 1 n 1 m 进程以后还需要的资源矩阵 Need i j k表示第i个进程以后还需要k个第j类资源 显然Need Max Allocation Request 1 n 1 m 进程申请资源矩阵 Request i j k表示进程i申请k个第j类资源 资源分配程序的工作过程 当进程提出资源申请时 系统首先检查该进程对资源的申请量是否超过其最大需求量及系统现有资源能否满足进程需要 若能则进一步检查 若把资源分给该进程系统能否处于安全状态 若安全则分配 否则置该进程为等待资源状态 为简单起见 记Ai为A i 1 A i 2 A i m 其中A为n m矩阵 定义长度为m的向量X Y间的关系为 X Y当且仅当X i Y i i 1 2 m 1 如果Requesti Needi则报错返回 2 如果Requesti Available 则进程i进入等待资源状态 返回 3 假设进程i的申请已获准 于是修改系统状态 Available Available RequestiAllocationi Allocationi RequestiNeedi Needi Requesti4 调用安全状态检查算法 设进程i申请资源 申请资源向量为Requesti 则有如下的资源分配过程 续 5 若系统处于安全状态 则将进程i申请的资源分配给进程i 返回 6 若系统处于不安全状态 则进程i进入等待资源状态 并恢复系统状态后返回 Available Available RequestiAllocationi Allocationi RequestiNeedi Needi Requesti 安全状态检查算法 设Work 1 m 为临时工作向量 初始时Work Available 令N 1 2 n 1 寻找j N使其满足Needj Work 若不存在这样的j则转 3 2 Work Work AllocationjN N j 转 1 3 如果N为空则返回 系统安全 如果N不为空则返回 系统不安全 举例 AllocationMaxRequestavailableP1124258121133P2033444300P3411544122如果p1先申请 无安全序列 如果p3申请 可有安全序列或 4 4 5死锁检测 资源分配图的简化过程 1 在图中找一个进程顶点 i Pi的请求边均能立即满足 2 若找到这样的Pi则将与 i相连的边全部删去 转 1 否则化简过程结束 采用化简资源分配图的方法可以检测系统中有无进程处于死锁状态 如果化简后所有的进程顶点都成了孤立点 则称该图可完全化简 否则称该图是不可完全化简的 系统中有死锁的充分必要条件是资源分配图不可完全化简 死锁检测算法设Work 1 m 为临时工作向量 初始时Work Available 令N 1 2 n 寻找j N使其满足Requestj Work 若不存在这样的j则转 3 Work Work AllocationjN N j 转 1 如果N为空则无死锁 如果N不为空则有死锁 N就是处于死锁状态的进程集合 4 4 6死锁恢复 检测出死锁后的处理破坏循环等待 杀掉有关进程 4 4 7死锁的综合处理 把系统中的资源分成几大类 整体上采用资源顺序分配法 再对每类资源根据其特点选择最适合的方法 例如 1 主存 处理机 剥夺法 2 辅存 预分配法 3 其他 死锁检测 交通死锁的示例 进程A进程B 申请输入设备 申请输出设备 申请输出设备 申请输入设备 释放输入设备 释放输出设备 释放输出设备 释放输入设备如果执行次序为 进程A 进程B 则发生死锁 A在干什么 B在干什么 竞争外设死锁示例 A B C D E L M N O P Q F G H I J K SPOOLing系统死锁示例 输出井 进程B 进程C 满啦 不够 不够 不够 进程A