linux处理机调度与死锁PPT课件.ppt

1 7 3死锁的概念 7 3 1死锁的定义可重用资源 reusableresource 各个进程可以轮流使用 如处理机 内存 I 0外设 文件等都是可重用资源 在使用可重用资源时可能出现的死锁 Deadlock 通常是由于各进程巳拥有部分资源 同时请求其他进程已占有的资源 从而造成永远等待 可消耗资源 consumableresource 是指可以动态生成和动态消耗的资源 一般不限制数量 如中断 信号量 消息 缓冲区等都是可消耗资源 由于可消耗资源的生成和消耗存在依赖关系 因此他们的使用也可能因为双方都等待对方生成资源而形成死锁 2 图7 1进程之间通信时的死锁 3 死锁的定义 死锁是一组并发进程 它们共享系统的某些资源 该组进程中每个进程都已经占有了部分资源 但都在不释放自己占有资源的情况下要求获得被其它进程已经占有的资源 从而造成它们相互等待 永远不能继续推进的状态 说明 参与死锁的进程最少是两个 两个以上进程才会出现死锁 参与死锁的进程至少有两个已经占有资源 参与死锁的所有进程都在等待事件 参与死锁的进程是当前系统中所有进程的子集 4 7 3 2资源分配图 2 凡属于E中的一个边e E 都连接着P中的一个结点和R中的一个结点 e pi rj 是资源请求边 由进程pi指向资源rj 它表示进程pi请求一个单位的rj资源 e rj pi 是资源分配边 由资源rj指向进程pi 它表示把一个单位的资源rj分配给进程pi 该图是由一组结点V和一组边E所组成的 G V E 具有以下形式的定义和限制 1 V被分为两个互斥的子集 一组进程结点P p1 p2 pn 一组资源结点R r1 r2 rn 5 7 3 3产生死锁的原因 产生死锁的根本原因是 资源不足 引起资源竞争 进程推进顺序不合理 6 例 设有两个进程Pa和Pb 它们都需要使用系统内的打印机和输入机 它们的算法设计如下 设信号量s1代表输入机资源可用数量 s1 1设信号量s2代表打印机资源可用数量 s2 1 Pa P s2 P s1 V s2 V s1 Pb P s1 P s2 V s1 V s2 7 7 3 4死锁产生的必要条件 互斥条件 进程要求对所分配的资源进行排他性使用 即在一段时间内某资源仅为一个进程所占用 不剥夺条件 进程所获得的资源在未使用完毕之前 不能被其他进程强行夺走 即只能由获得该资源的进程自己来释放 请求和保持条件 进程每次申请所需要的一部分资源 在等待新资源的同时 进程继续占有已分配到的资源 循环等待条件 存在进程资源的循环等待链 链中的每一个进程已获得资源 同时被链中的下一个进程所请求 8 7 4预防死锁 解决死锁问题的基本方法有 预防死锁 避免死锁 检测死锁和解除死锁 除此之外还有鸵鸟算法和综合措施 预防死锁是指通过某种策略来限制并发进程对资源的请求 使系统在任何时刻都不满足死锁的必要条件 就是在设计操作系统时 通过设置某些限制条件 去破坏死锁四个必要条件中的一个或多个 来防止死锁 使系统能预先排除死锁的可能性 9 7 4 1摒弃请求和保持条件 采用设备的静态预先分配办法 具体作法 作业调度程序在选择作业时 只选择那些系统能满足其运行时所需的全部资源的作业投入运行 并且在作业运行前 将其所需的全部资源一次性地分配给该作业 该方法的优点和缺点如下 简单 安全 易于实现 程序在运行之前很难提出将要使用的全部设备 直到所有资源满足才能运行 实际上某些资源可能要到运行后期才会用到 一个进程运行期间 对某些设备的使用时间很短 甚至不会用到 作业的周转时间被加长 系统资源的使用率被降低 10 7 4 2摒弃不剥夺条件 为了破坏不可剥夺条件 我们采用这样的策略 一个已拥有资源的进程 若它再提出新资源要求而不能立即得到满足时 它必须释放已经拥有的所有资源 以后需要时再重新申请 拥有资源的进程在运行过程中其资源可能被剥夺 从而破坏了不可剥夺条件 该方法实现复杂 被剥夺资源的进程前期工作失效 重复申请和释放资源给系统增加了开销 系统要付出很大的代价 11 7 4 3摒弃环路等待条件 为了破坏环路等待条件 采用有序资源分配策略 对申请资源的进程规定 同类资源需一次申请 在获得资源后 只能申请较高级号的资源 无权申请低级号资源和同类资源 对于低级号资源和同类资源申请 必须先释放所有高级号的资源 然后再申请 否则不予分配 优点 同前两法相比 其资源利用率和系统吞吐量有较明显的改善 缺点 进程实际需要资源的顺序不一定与资源的编号一致 因此仍会造成资源浪费 系统增加新设备较困难 12 7 4 4摒弃互斥条件 互斥条件是由于设备本身特性所决定的 不能简单的把其打破 只有通过改造设备特性实现 具体办法采用Spooling技术 把独占设备改造成共享设备来实现 13 7 5避免死锁 死锁的避免是动态的预防措施 系统允许进程动态地申请资源 如果措施得当 可以使系统获得较为满意的系统性能 具体的办法是 系统为进程分配资源之前 首先对系统的安全性进行计算 如果为进程分配了所需资源后 系统仍处于安全状态 那么就把资源分配给该进程 反之则不为该进程分配资源 银行家算法 该问题是研究一个银行家如何将其总数一定的现金 安全的借给若干个顾客 使这些顾客既能满足对资金的要求又能完成其交易 也使银行家可以收回自己的资金不至于破产 14 7 5 1系统的安全状态和不安全状态安全状态 是指系统能按某种进程推进顺序 p1 p2 pn 来为每个进程分配其所需资源 直至最大需求 使每个进程都能顺利完成其任务 只要系统存在这样的安全序列 则系统处于安全状态 7 5 2安全状态的例子假定系统有三个进程p1 p2和p3 共有12台磁带机 进程p1 p2 p3分别要求10台 4台和9台 设在T0时刻p1 p2 p3已分别获得5台 2台和2台 尚有3台空闲磁带机未分配出去 分配情况如下所示 15 经分析 在T0时刻系统是安全的 因为存在一个安全序列向不安全状态的转换若在T0时刻 p3请求1台磁带机 若满足其要求 则系统进入不安全状态 16 7 5 3利用银行家算法避免死锁 银行家算法中的数据结构 可利用资源向量Available R1 R2 Rm 它是一个含有m个元素的数组 其中的每一个元素代表一类可利用的资源数目 其初始值是系统中所配置的该类全部可用资源数目 其数值随该类资源的分配和回收而动态地改变 最大需求矩阵Max 这是 个n m的矩阵 它定义了系统中n个进程中的每一个进程对m类资源的最大需求 如果Max i j k 表示进程Pi需要Rj类资源的最大数目为k 分配矩阵Allocation 这是一个n m的矩阵 它定义了系统中每一类资源当前已分配给每个进程的资源数 如果Allocation i j k 表示进程Pi当前已分得Rj类资源的数目为k 需求矩阵 Need 它是一个n m的矩阵 用以表示每一个进程尚需的各类资源数 如果Need i j k 表示进程Pi还需要Rj类资源k个 方能完成其任务 上述三个矩阵间存在下述关系 Need i j Max i j Allocation i j 17 银行家算法设Requesti r1 r2 rm 是进程Pi的请求向量 如果Requesti j k 表示进程Pi只需要k个Rj类型的资源 当Pi发出资源请求后 系统按下述步骤进行检查 如果Requesti Needi 则执行步骤 否则 认为出错 因为它所需要的资源数已超过它所宣布的最大值 如果Requesti Availablei 则执行步骤 否则 表示系统中尚无足够的资源 Pi等待 系统试探把要求的资源分配给进程Pi 并修改下面数据结构中的数值 Available j Available j Requesti j Allocation i j Allocation i j Requesti j Need i j Need i j Requesti j 系统执行安全性算法 检查此次资源分配后 系统是否处于安全状态 若安全 才正式将资源分配给进程Pi 以完成本次分配 否则 将试探分配作废 恢复原来的资源分配状态 让进程Pi等待 18 安全性算法系统所执行的安全性算法可描述如下 设置两个工作向量 工作向量Work 它含有m个元素 它表示系统可提供给进程继续运行所需要的各类资源数目 初值Work Available 完成标志工作向量Finish 它含有n个元素 它表示系统是否有足够的资源分配给进程 使之运行完成 当有足够资源分配给进程时 Finish i true 初值Finish i false 从进程集合中找到一个能满足下述条件的进程 Finish i false Needi Work 如找到 执行步骤 否则 执行步骤 当进程Pi获得资源后 可顺利执行 直至完成 并释放出分配给它的资源 系统回收这些资源 故修改下面数据结构中的数值 Work j Work j Allocation i j Finish i true 转步骤 如果所有进程的Finish i true 则表示存在这样一个安全序列 系统处于安全状态 否则 系统处于不安全状态 2020 2 4 19 20 银行家算法之例 如表7 4所示T0时刻的资源分配表 假定系统中有五个进程 P0 P1 P2 P3 P4 和三种类型的资源 A B C 每一种资源的数量分别为10 5 7 21 如表7 5所示 对T0时刻进行安全性检查 可以找到一个安全序列 P1 P3 P4 P2 P0 系统是安全的 22 P1发出请求Request 1 0 2 执行银行家算法 如表7 6所示 进行安全性检查 通过第一步和第二步检查 并找到一个安全序列 P1 P3 P4 P2 P0 系统是安全的 可以分配P1的请求 23 24 P4发出请求Request 3 3 0 执行银行家算法 Available 2 3 0 不能通过第二步检查 Request i Available 所以P4等待 P0请求资源 Request 0 2 0 执行银行家算法 进行安全性检查 通过第一步和第二步检查 如表7 7所示 Available 2 1 0 已不能满足任何进程需要 所以系统进入不安全状态 P0的请求不能分配 25 7 6检测死锁并解除死锁7 6 1检测死锁 这是一种事后处理的措施 具体方法是 1 判断是否构成环路条件采用有限状态转移图法 2 周期性检测方法 类似银行家算法 26 死锁定理 1 死锁定理 S为死锁状态的充分必要条件是当且仅当S状态的资源分配图是不可化简的 2 资源分配图的化简原则 1 在资源分配图中 找出一个既不阻塞又非独立的进程结点pi 在顺利情况下 pi可获得所需资源而继续执行 直至运行完毕 再释放其所占有的全部资源 这相当于消去pi所有的请求边和分配边 使之成为孤立的结点 27 2 p1释放资源后 便可使p2获得资源而继续运行 直到p2完成后又释放出它所占有的全部资源 而形成图 c 所示的情况 3 在进行一系列简化后 若能消去图中所有边 使所有进程都成为孤立结点 则称该图是可完全简化的 若不能通过任何过程使该图完全简化 则称该图是不可完全简化的 28 假定某系统当时的资源分配图如下所示 1 分析当时系统是否存在死锁 2 若进程P3再申请R3时 系统将发生什么变化 说明原因 29 3 死锁检测中的数据结构 1 可利用资源向量Available 它表示了m类资源中每一类资源的可用数目 2 把不占用资源的进程 向量Allocation 0 记入L表中 即Li L 3 从进程集合中找到一个Requesti Work的进程 做如下处理 将其资源分配图简化 释放出资源 增加工作向量Work Work Allocationi 将它记入L表中 30 4 若不能把所有进程都记入L表中 便表明系统状态S的资源分配图是不可完全简化的 因此 该系统状态将发生死锁 Work Available L Li Allocationi 0 Requesti 0 forallLiLdo begin forallRequesti Workdo begin Work Work Allocationi Li L end end deadlock L p1 p2 pn 31 7 6 3解除死锁 方法如下 系统重新启动 撤消所有死锁进程 退回到前一检查点并从此点重新启动进程 逐个撤消死锁进程 直到死锁不存在 逐个抢占死锁进程资源直到死锁不存在 32 7 6 4处理死锁的综合措施 较理想的处理死锁综合措施如下 内部资源 系统本身使用的资源 如I O通道 进程控制块 设备控制块 系统保留区等 对内部资源通过破坏循环等待条件 即对此类资源使用有序资源分配法预防死锁 内存资源 可以按帧或段分配给进程的存储空间 对内存实行可剥夺式方法预防死锁是最适合的策略 当一个进程被剥夺后 它仅仅被换到外存 释放空间以解决死锁 进程资源 用于进程的可分配设备 如打印机 文件等 对这类资源 死锁避免策略常常是很有效的 这是因为进程可以事先声明他们将需要的这类资源 也可以采用有序资源分配法预防策略 交换空间 进程交换所使用的外存交换区 通过要求一次性分配所有请求的资源来预防死锁 也可以采用死锁避免措施 33 复习思考题一选择题1 银行家算法是一种 算法 A 死锁解除B 死锁避免C 死锁预防D 死锁检测2 在下列解决死锁的方法中 属于死锁预防策略的是 A 银行家算法B 资源有序分配法C 死锁检测法D 资源分配图化简法3 在为多道程序所提供的可共享的系统资源不足时 可能出现死锁 但是 不适当的 也可能产生死锁 A 进程优先权B 资源的线性分配C 进程推进顺序D 分配队列优先权4 采用资源剥夺法可解除死锁 还可以采用 方法解除死锁 A 执行并行操作B 撤消进程C 拒绝分配新资源D 修改信号量5 资源的按序分配可以破坏 条件 A 互斥使用资源B 占有且等待资源C 非抢夺资源D 循环等待资源 34 6 在 的情况下 系统出现死锁 A 计算机系统发生了重大故障B 有多个封锁的进程同进存在C 若干进程因竞争资源而无休止地相互等待他方释放已占有的资源D 资源数大大小于进程数或进程同时申请的资源大大超过资源总数7 产生死锁的四个必要条件是 互斥 循环等待和不剥夺 A 请求与阻塞B 请求与保持C 请求与释放D 释放与阻塞8 在分时操作系统中 进程调度经常采用 算法 A 先来先服务B 最高优先权C 时间片轮转D