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

第3章处理机调度与死锁 3 1处理机调度的基本概念3 2调度算法3 3实时调度3 4多处理机系统中的调度3 5产生死锁的原因和必要条件3 6预防死锁的方法3 7死锁的检测和解除 开始 1 本章学习目标 处理机调度的基本概念处理机调度算法实时调度和多处理机调度死锁问题及解决对策 返回本章首页 2 3 1处理机调度的基本概念 3 1 1高级 中级和低级调度3 1 2调度队列模型3 1 3选择调度方式和算法的准则 返回本章首页 3 3 1 1调度的类型 一 调度的职能 1 记录系统中所有进程的有关情况 2 确定分配处理机的原则 3 分配处理机给进程 4 从进程收回处理机 返回本节目录 4 二 高级 中级和低级调度 1 高级调度 作业调度 1 接纳多少作业 2 接纳哪些作业 取决于调度算法 返回本节目录 5 2 低级调度 进程调度 1 非抢占方式 CPU不能被动剥夺引起调度的因素 进程执行完毕 或发生某事件进程不能继续运行 进程因I O请求而停止 进程通信或同步过程中执行了某种原语 返回本节目录 6 2 抢占方式 PreemptiveMode 抢占的原则 优先权原则 短作业优先原则 时间片原则 返回本节目录 7 3 中级调度 对换暂时不能运行的进程 中级调度的任务是挂起暂时不能运行的进程 以提高内存的利用率和系统的吞吐量 返回本节目录 8 3 1 2调度队列模型 一 仅有进程调度的调度队列模型 返回本节目录 9 二 具有高级和低级调度的调度队列模型 1 调度队列模型 10 2 与进程调度队列模型的区别 1 就绪队列的形式 优先权队列 无序链表 2 设置多个阻塞队列 11 三 同时具有三级调度的调度队列模型 12 3 1 3选择调度方式和算法的准则 一 面向用户的准则1 周转时间短作业周转时间 外存等待时间 就绪队列等待时间 CPU执行时间 I O操作时间平均周转时间 平均带权周转时间2 响应时间快 提交请求开始到首次响应止3 截止时间的保证 任务必须开始执行的最迟时间4 优先权准则 紧急任务优先执行 返回本节目录 13 二 面向系统的准则 1 系统吞吐率高 单位时间内完成的作业多2 处理机利用高 40 90 3 各类资源平衡利用 14 3 2调度算法 3 2 1先来先服务和短作业优先调度算法3 2 2优先权调度算法3 2 3基于时间片的调度算法 下一页 15 3 2 1先来先服务和短作业优先调度算法 一 先来先服务调度算法 FCFS按照进程进入就绪队列的先后顺序调度进程 到达得越早 其优先数越高 未遇到其他情况时 获得处理机的进程就一直运行下去 16 二 运行时间 短作业优先调度算法 1 基本原理2 算法的缺点 1 对长作业不利 2 未考虑作业的紧迫性 3 时间是估计的 不一定真的最短 17 3 2 2优先权调度算法 一 优先权调度算法的类型1 非抢占式优先权算法最高优先级的就绪进程获得处理机之后 就一直运行下去 除非因自身的原因被阻塞 如要求I O操作 直至运行结束 2 抢占式优先权算法就绪队列中优先级高的进程可以随时取代正在运行的进程 投入运行 18 二 优先权的类型 1 静态优先权 进程创建时确定 1 进程的类型 I O进程 对换进程等 2 进程的资源需求 内存 执行时间等 3 用户要求 紧迫程度 支付费用等 2 动态优先权 进程创建时确定 19 三 高响应比优先调度算法 1 优先权的定义2 响应比3 算法特点 1 对短作业有利 2 服务时间相同 等待时间越长 优先权越高 3 随着时间增加 长作业得到照顾 20 3 2 3基于时间片的调度算法 一 时间片轮转法所有就绪进程按先后次序排队 处理机总是优先分配给就绪队列中的第一个进程 并分配它一个固定的时间片 如100毫秒 时间片时间到 同时未遇到任何阻塞时 进程就回到就绪队列的尾部 21 二 多级反馈队列调度算法 根据进程的优先级设置多个就绪队列 第一个队列的优先级最高 队列之间的优先级依次降低 高优先级队列中的进程执行时间片短当一个进程进入内存时 首先把它放到第一个队列的末尾 按FCFS原则等待调度 若在时间片内未执行完 将被放到第二个队列的末尾 然后依次类推仅当前面的队列为空时 才调度后面队列中的进程 22 三 多级反馈队列调度算法的性能 1 终端型作业此类作业较短 只要在第一队列的时间片内完成 即可获得较好的满意度2 短批处理作业用较短的时间即可完成3 长批处理作业将依次在不同的队列中运行 不必担心长期得不到处理 23 3 3实时调度 3 3 1实现实时调度的基本条件3 3 2实时调度算法的分类3 3 3常用的几种实时调度算法 24 3 3 1实现实时调度的基本条件 一 提供必要的调度信息1 就绪时间2 开始截止时间和完成截止时间3 处理时间4 资源要求5 优先级 25 二 系统的处理能力强 二 系统的处理能力强1 单机系统m个周期性任务 Pi为周期时间 Ci为执行时间2 多处理机系统 处理机数为N 三 采用抢占式调度机制四 具有快速切换机制1 对外部中断的快速响应能力2 快速的任务切换能力 26 3 3 2实时调度算法的分类 一 非抢占式调度算法1 非抢占式轮转调度算法响应时间 几秒 几十秒2 非抢占式优先调度算法响应时间 几百毫秒 27 二 抢占式调度算法 响应时间几十毫秒以下 1 基于时钟中断的抢占式优先权调度算法优先级高于当前任务的实时任务到达 但是在发生时钟中断时才剥夺当前任务的执行2 立即抢占的优先权调度算法一旦出现外部中断 只要当前任务未处于临界区 就立即剥夺当前任务的执行 把处理机分配给请求中断的紧迫任务 28 3 3 3常用的几种实时调度算法 一 最早截止时间优先算法EDF EarliestDeadlineFirst 算法该算法根据任务的开始截止时间确定任务的优先级 截止时间越早 优先级越高 系统中保持一个就绪队列 队列中的各任务按截止时间的早晚排序 该算法既可用于抢占式调度 也可用于非抢占式调度 29 二 最低松弛度优先调度算法 1 基本原理该算法根据任务的紧急 或松弛 程度确定任务的优先级 任务的紧急程度越高 优先级也就越高系统中保持一个就绪队列 队列中的各任务按松弛度排序 松弛度最低的任务排在队列的最前面 该算法既主要应用于抢占式调度 30 2 松弛度的计算 松弛度的定义松弛度的计算任务A要求每20ms执行一次 执行时间10ms任务B要求每50ms执行一次 执行时间25ms图P84 31 3 4多处理机系统中的调度 3 4 1多处理器系统的类型3 4 2进程分配方式3 4 3进程 线程 调度方式 32 3 4 1多处理器系统 MPS 的类型 MPS MultiProcessorSystem一 紧密耦合MPS和松弛耦合MPS1 紧密耦合MPS通过高速总线或高速交叉开关连接多个处理器 多个CPU共享主存储器和I O设备 系统中的所有资源和进程由操作系统统一控制和管理2 松弛耦合MPS通过通道或通信线路连接多个计算机 每个计算机都有自己的存储器和I O设备 都有自己的操作系统控制和管理本地资源和进程的运行 计算机网络 33 二 对称MPS和非对称MPS 根据处理器是否相同来划分 1 对称MPS SMPS系统中的处理器在结构和功能上都相同2 非对称MPS系统中有多种类型的处理器 它们的结构和功能各不相同 其中一个是主处理器 其余都是从处理器 34 3 4 2进程分配方式 一 对称多处理器系统中的进程分配方式1 静态分配方式进程从开始执行到执行结束 都被固定地分配到一个处理器 每个处理器有一个专用的就绪队列 被阻塞的进程再次就绪时 仍回到该队列的末尾 2 动态分配方式系统中可以只设置一个公共的就绪队列 其中的进程可以分配到系统中的任何一个处理器 35 2020 1 7 36 二 非对称MPS中的进程分配方式 此类系统一般采用主从式操作系统 即OS的核心驻留于主处理器中 而用户程序则在从处理器上 进程调度由主处理器执行 每当从处理器空闲时 就小向主处理器发送一个索求进程的信号 主处理器从公用就绪队列中进行进程调度 37 3 4 3进程 线程 调度方式 一 自调度方式1 自调度机制在系统中设置一个公共的进程 线程 就绪队列 所有的处理器空闲时 都可以自己到该队列中取得一个进程 线程 投入运行 1 FCFS算法 2 最小优先数优先算法 3 抢占式最小优先数优先算法 38 2 自调度方式的特点 有任务的情况下处理机不会空闲分布式调度可以沿用单处理机环境下的就绪队列组方式织和进程调度方法多处理机互斥共享单就绪队列引起的瓶颈重新调度时线程迁移引起的低效性线程切换频繁 39 二 成组调度 1 基本原理把一个进程中的一组线程分配到一组处理机上执行 其优点是 1 若一组线 进 程可以并行执行 就可以减少阻塞情况的发生 减少了切换频率 提高了性能 2 一次调度为一组线程分配处理机 减少了调度频率 减少了系统开销 40 2 为应用程序分配处理机时间的方法 1 为所有的应用程序平均分配处理机时间2 为所有的线程平均分配处理机时间 41 三 专用处理器分配 1 基本原理为一个应用程序的每个线程分配一个处理器 直到该应用程序执行完毕 才释放为该应用程序所分配的所有处理器 42 2 采用专用处理器分配方法的理由 1 专用处理器分配方式的缺点部分处理器的利用率可能不高2 仍然采用专用处理器分配方式的原因 1 在大规模 甚至几百个处理器 高度并行的系统中 单个处理器的利用率不那么重要 2 避免了线程切换 加速了程序运行 43 3 5产生死锁的原因和必要条件 死锁 Deadlock 多个进程因竞争资源或进程推进顺序不当而造成的进程无法继续运行的现象 Deadly Embrace 3 5 1产生死锁的原因3 5 2产生死锁的必要条件3 5 3处理死锁的基本方法 返回本章首页 44 3 5 1产生死锁的原因 一 资源的类型1 剥夺性资源2 非剥夺性资源二 竞争资源引起死锁1 竞争非剥夺性资源2 竞争临时性资源临时资源是指由一个进程产生 被另一进程使用短暂时间后就不再有用的资源 这种资源也叫做消耗性资源 45 临时资源使用实例 正确的进程推进顺序P1 Release S1 Request S3 P2 Release S2 Request S1 P3 Release S3 Request S2 死锁的进程推进顺序P1 Request S3 Release S1 P2 Request S1 Release S2 P3 Request S2 Release S3 46 三 进程推进顺序不当引起死锁 进程推进顺合法进程推进顺序非法 47 3 5 2产生死锁的必要条件 同时具备下列四个必要条件 就会产生产生死锁 1 互斥条件2 不剥夺条件3 请求和保持条件4 环路等待条件 48 3 5 3处理死锁的基本方法 一 预防死锁 消除产生死锁的必要条件二 避免死锁 分配资源时防止进入不安全状态三 检测死锁 不预防死锁 出现死锁就解除四 解除死锁 与检测死锁配合使用 49 3 6预防死锁的方法 3 6 1预防死锁3 6 2系统安全状态3 6 3利用银行家算法避免死锁 返回本章首页 50 3 6 1预防死锁 一 破坏 请求和保持 条件进程运行之前必须提出要使用的全部资源 在该进程需要的资源末得到满足之前 不让它们投入运行 并且当资源一旦分配给某进程之后 就在该进程整个运行期间一直占有该资源 51 二 破坏 不剥夺 条件 系统规定 采用这种方法时 进程应逐个提出资源需求 在进程拥有某些资源的情况下 如果新的资源要求得不到满足时 就必须释放它已经获得的所有资源 从而破坏 不剥夺 条件 下一页 52 三 破坏 环路等待 条件 对设备按类型进行线性排队 并赋予不同的序号 所有进程只能严格地按照编号递增 或递减 的次序去请求资源 亦即 只有低编号的资源要求满足后 才能对高编号资源提出要求 释放资源时 应按编号递减的次序进行 使得进程 资源图不可再产生环路 下一页 53 3 6 2系统的安全状态 一 安全状态1 安全状态的概念所谓安全状态 是指系统能够按某种进程顺序 P1 P2 Pn 为每个进程分配其所需要的资源 直至满足进程对资源的最大需求 使每个进程都可以顺利地执行 如果系统无法找到这样的安全进程序列 则说进程处于不安全状态 54 2 安全状态实例 假定系统中有3个进程P1 P2和P3 共有12台磁带机 进程P1要求总共要求10台磁带机 P2和P3分别要求4台和9台 假设在T0时刻进程P1 P2和P3已分别获得5台 2台和2台磁带机 尚有3台还空闲未分配 具体情况如下表所示 可以分析 在T0时刻系统是安全的 返回本节目录 55 二 安全状态与不安全状态的转换 如果不按照安全序列分配资源 系统就可能由安全状态进入不安全状态实例分析 以前面的例子进行 返回本节目录 56 3 6 3利用银行家算法避免死锁 一 Dijkstra银行家算法的数据结构1 可利用资源向量一维数组 Available j k Rj类资源有k个2 最大需求矩阵Maxn m矩阵 Max i j k 进程i需要Rj类资源的最大数k3 分配矩阵Allocationn m矩阵 Allocation i j k 进程i获得的Rj类资源数k4 需求矩阵Needn m矩阵 Need i j k 进程i还需要Rj类资源k个 57 二 银行家算法 设Requestj是进程Pj的请求向量 如果Requesti j k 表示进程Pj需要k个Rj类资源 Pj发出资源请求后 系统按下列步骤进行检查 1 如果Requesti j Need i j 则转2 否则 出错2 如果Requesti j Available j 则转3 否则 表示无足够资源3 系统试图把资源分配给进程Pi 并修改下面的数据结构 Available j Available j Requesti j Allocation i j Allocation i j Requesti j Need i j Need i j Requesti j 4 系统执行安全性算法 若安全 就把资源分配给进程Pi 否则 恢复原来的资源分配状态 让进程Pi等待 返回本节目录 58 三 安全性算法 1 设置两个向量 向量Work表示系统可提供给进程继续运行所需要的各类资源数目 其初值Work Available 向量Finish表示系统是否有足够的资源分配给进程 其初值Finish i false2 从进程集合中找出满足下列条件的进程 Finish i false Need i j Work j 找到就转3 否则转43 进程Pj获得资源后 便可运行直至结束释放其占用的资源 故应执行下列操作 Work j Work i Allocation i j Finish i true gotostep24 若所有进程都满足Finish i true 表示系统处在安全状态 否则 系统处于不安全状态 返回本节目录 59 四 银行家算法实例 返回本节目录 60 3 7死锁的检测和解除 3 7 1死锁的检测3 7 2死锁的解除 返回本章首页 61 3 7 1死锁的检测 分配资源时若未采取任何限制性措施 系统就必须 1 保存有关资源的请求和分配的信息2 提供一种算法 检测系统是否死锁 62 一 资源分配图 1 资源分配图的定义系统死锁可利用资源分配图描述 资源分配图是由一组节点N和一组边E所组成的对偶G N E 具有下述的定义和限制 1 把N分为两个互斥的子集 即一组进程节点P p1 p2 pn 和一组资源节点R r1 r2 rn 2 对于任意的属于E的e 都连接着P中的一个节点和R中的一个节点 e pi rj 是资源请求边 由pi指向rj 表示进程pi请求一个单位的rj资源 e rj pi 是资源分配边 由rj指向pi 表示把一个单位的rj资源分配给了进程pi 返回本节目录 63 2 资源分配图实例 返回本节目录 64 二 死锁定理 1 利用资源分配图检测系统