移动通信操作系统综述 第三章.ppt

第三章 死锁 移动通信操作系统综述 回顾 进程 Process 的概念线程的概念进程的通信方式经典的IPC问题进程调度有关进程与线程的研究 目标 掌握资源与死锁的概念了解鸵鸟算法理解死锁的检测和恢复死锁的避免 资源 可剥夺的 可从拥有它的进程中剥夺而不会有副作用 不可剥夺的 从拥有它的进程中剥夺不会产生错误 存储器打印机 资源分类 资源定义 任何时候都只能被一个进程使用的任何对象 排它性使用的这类对象例如打印机等 资源的使用顺序 申请资源使用资源释放资源 产生死锁的原因 竞争资源引起死锁 进程推进顺序不当引发死锁 例系统中只有一台打印机和一台磁带机 进程p1和p2都要进行打印 Request 打印机 Request 磁带机 使用Release 打印机 Release 磁带机 死锁定义 死锁的条件 互斥条件部分分配 保持和等待条件 非剥夺条件循环等待的条件 死锁的定义 假若在一个进程集合中的每个进程都在等待由该集合中的其他进程所占用的资源 因而无法得到该资源 那么这种状态被称之为死锁 死锁定义 死锁示意图 死锁定义 死锁表现 多数情况下 进程是在等待集合中的另一个进程正占有的资源 但由于所有进程都在等待都不能运行 因而无法释放任何资源 于是该集合中的任何进程都不能被唤醒 产生死锁的必要条件 互斥条件每个资源要么分配给一个进程 要么空闲 请求和保持条件已经得到资源的进程可以申请新的资源 申请失败时变为阻塞状态 此时他人然保持着原有资源不放 不可剥夺条件已经分配给一个进程的资源不能被剥夺 只能由占有他的进程主动释放 环路等待条件系统一定有两个或两个以上进程组成一条环路 该环路的每个进程都在等待着相邻进程正占用着的资源 处理死锁的四种策略 忽略该问题假装死锁永不发生 鸵鸟算法 检测与解除死锁检测系统是否出现死锁 如果出现解除它 预防死锁通过破除死锁产生的四个必要条件之一来防止死锁产生 避免死锁仔细的对资源进行动态分配 以避免死锁发生 鸵鸟算法 对可能发生的死锁视而不见 含义 理由 死锁避免的代价高 死锁恢复困难 死锁发生的概率低 鸵鸟算法举例 假设一个unix系统的进程表有100项 有10个进程在执行 每一个都要创建12个子进程 在每个进程创建9个进程后 原来的10个进程和新创建的90个进程将进程表项全部用完 这10个进程将无休止的进入fork失败的循环 这种事件概率很小 但却是存在 我们会因为这个原因而放弃进程 fork等概念吗 死锁检测和恢复 进程节点子集资源节点子集请求边 进程请求一个单位的资源并正在等待 分配边 一个单位的资源已分配给进程 资源分配图 ResourceAllocationGraph 死锁检测 死锁检测示意图 死锁的检测 死锁定理S为死锁状态的充分条件是 当且仅当S状态的资源分配图是不可完全简化的 资源分配图的简化过程找只有分配边没有请求边相连的进程节点 将其分配边删掉 找虽有请求边 但请求边可立即全部转化为分配边的节点 将其请求边转化为分配边 再将分配边删掉 经过1 2后 如果进程节点和资源节点全部成为孤立节点 即没有边相连 则该RAG是可完全转化的 否则图中必定存在环路 说明此RAG是不可完全简化的 死锁的避免 死锁的避免 银行家算法 思路允许进程动态申请资源 将系统分为安全状态 不会发生死锁 不安全状态 可能发生死锁 避免系统进入不安全状态做法每次进行资源分配时 首先检测一下资源分配后系统处于何种状态 若处于安全状态 则正是实施本次分配 否则不予分配 申请资源的进程阻塞 死锁的预防 预防死锁的策略 打破互斥条件 打破保持和请求条件 规定进程在运行前要一次性申请运行所需全部资源 只有资源全部到手方可运行 否则进程等待 死锁的预防 预防死锁的策略 打破循环等待条件 1 保证每个进程在时候只能占用一个资源 要用第二个必须先释放第一个 2 将系统中所有资源赋予一个全局编号 进程申请资源时 必须按编号递增顺序进行 打破非剥夺条件 保持资源的进程申请新资源失败时 在转为阻塞状态之前 必须释放其占用的全部资源 而该进程自身则必须等到重新获得原有资源和新资源后 才能重新运行 死锁的恢复 将资源从一个进程抢占过来给另