操作系统3-2.ppt

3 1处理机调度的基本概念 一 调度的层次二 调度队列模型三 选择调度方式和算法的若干准则 返回目录 提交 输入管理系统 作业调度 后备 退出 完成 就绪 阻塞 交换调度 中级调度 进程调度 线程调度 一 调度的层次 二 调度队列模型 在OS中的任何一种调度中 都将涉及到进程队列 由此形成了三种类型的调度队列模型 1 仅有进程调度的调度队列模型2 具有高级和低级调度的调度队列模型3 同时具有三级调度的调度队列模型 返回本节 1 仅有进程调度的调度队列模型 进程调度 时间片完 返回 2 具有高级和低级调度的调度队列模型 时间片完 返回 3 同时具有三级调度的调度队列模型 时间片完 进程调度 CPU 进程完成 等待事件 作业调度 中程调度 返回 三 选择调度方式和算法的若干准则 周转时间 常用于批处理系统 定义 作业从提交 完成的时间时间组成 1 驻外等待调度时间 2 驻内等待调度时间 3 执行时间 4 阻塞时间 周转时间不具有区分实际运行时间长短的性质 三 选择调度方式和算法的若干准则 返回 平均周转时间带权周转时间 R 系统为它提供服务的时间 平均带权周转时间 平均周转时间可以衡量不同调度算法对相同任务流的调度性能 带权周转时间衡量长短任务的差别 故带权周转时间W越小越好 三 选择调度方式和算法的若干准则 返回 响应时间快 对交互性作业 概念 键盘提交请求到首次响应时间时间组成 1 输入传送时间 2 处理时间 3 响应传送时间截止时间的保证 特别于实时系统 优先权准则 即需要抢占调度 3 3调度算法 根据系统的资源分配策略所规定的资源分配算法 一 先来先服务调度算法二 短作业 进程优先调度算法三 时间片轮转调度算法四 优先权调度算法五 高响应比优先调度算法六 多级反馈队列调度算法 一 先来先服务 FCFS 调度算法 基本思想 对于作业调度 从后备作业队列中 按进入的时间顺序排队 选择队首一个或几个作业 调入内存 创建进程 放入就绪队列 对于进程调度 从就绪队列中选择一个最先进入队列的进程 将CPU分配于它 一 先来先服务 FCFS 调度算法 FCFS调度算法评价 简单 但效率不高 有利于长作业 进程 不利于短作业 进程 有时为了等待长作业的执行 而使短作业的周转时间变得很大 从而平均周转时间也变大 现在操作系统中 已很少用该算法作为主要调度策略 尤其是在分时系统和实时系统中 但它常被结合在其它调度策略中使用 二 短作业 进程优先调度算法 短作业优先调度算法 SJF 从后备队列中选择一个或若干个估计运行时间最短的作业 将它们调入内存运行 短进程优先调度算法 SPF 从就绪队列中选出一个估计运行时间最短的进程 将处理机分配给它 可采用抢占或者非抢占调度方式 二 短作业 进程优先调度算法 优点 1 能有效降低作业 进程的平均等待时间 2 提高吞吐量 3 能有效缩短作业 进程的周转时间 缺点 1 对长作业 进程不利 2 不考虑作业 进程的紧迫程度 3 作业执行时间仅为估计 三 时间片轮转调度算法RoundRobin 轮转法是一种基于时钟的抢占策略 以一个周期性间隔产生的时钟中断依次进行各个进程的调度 当时钟中断发生时 当前正在运行的进程被置于就绪队列中 然后再基于FCFS策略选择下一个就绪进程运行 它主要用于分时系统中 轮转法设计的问题是时间片的长度 举例 例 一个分时OS 10个终端 时间片100ms 每个用户的请求进程要300ms的时间处理 问终端用户提出二次请求的时间间隔最少是多少 解 响应时间 100ms 10 1s 每个用户的请求要获得3个时间片才能处理完 要轮转3次 才能都处理完 所以终端用户的二次请求时间间隔最少应为3s 三 时间片轮转调度算法RR 注 保证了就绪队列中的所有进程在给定的时间内 均能获得一时间片来执行 若进程的执行时间少于时间片 则自愿释放CPU 时间片将影响 太长 FCFS 太短 上下文切换频繁 HPF Highest Priority First 需为每个进程设置一个由数字表示的优先数 进程优先数的大小应与进程所对应事件的紧迫程度相对应 当需要进行处理机分配时 系统在可运行的进程中选择优先数最高者使其投入运行 进程的优先数反映了进程运行的优先级别 故又将其称作优先级算法 四 优先权调度算法 HPF 思考 优先数如何存放 PCB 1 静态优先级优先权在创建进程时确定 且在进程的整个运行期间保持不变 一般用整数表示 小表示优先级高 确定原则 进程类型 系统进程 用户进程 进程对资源的需求 要求少的优先权高 用户要求 紧急程度和付费情况 优点 缺点 优先权的类型 简单 开销较少 公平性差 对低优先数进程 优先权的类型 2 动态优先权动态优先级在进程的存在过程中不断发生变化 动态优先级的变化取决于 进程的等待时间进程的运行时间进程使用资源的类型等此优先数确定方法资源利用率高 公平性好 但开销较大 实现较为复杂 最高响应比优先算法采用动态优先级 四 优先权调度算法 续 非抢占式优先权算法 系统一旦把处理机分配给就绪队列中优先权最高的进程后 该进程便一直执行下去 直到完成或因发生某事件而放弃处理机时 系统方可重新分配处理机 非抢占式优先权算法 例1 EG1 进程到达时间服务时间优先数P1073P2242P3414P4541平均周转时间 7 0 15 2 16 4 11 5 4 9 5平均等待时间 0 9 11 2 4 5 5 优先数越小优先级越高 四 优先权调度算法 续 抢占式优先权算法 系统把处理机分配给就绪队列中优先权最高的进程 使之执行 但在其执行期间 只要出现了另一个优先权更高的进程 进程调度程序就立即停止当前进程的执行 重新将处理机分配给新到的优先权最高的进程 抢占式优先权算法 例2 EG2 进程到达时间服务时间优先数P1073P2242P3414P4541平均周转时间 15 0 10 2 16 4 9 5 4 9 75平均等待时间 8 4 11 0 4 5 75 各种算法结果值的比较 返回 进程到达时间服务时间P107P224P341P454SJF抢占 平均周转时间 16 0 7 2 5 4 11 5 4 7平均等待时间 11 2 5 4 4 4 7 5 4 3 五 高响应比优先权调度算法HRP 优先权的变化为 为响应比 如等待时间相同 则要求服务时间愈短 其优先权愈高 SPF 如要求服务时间相同 优先权决定于等待时间 FCFS 对长作业 若等待时间足够长 优先权也高 也能获得CPU 算法HRP示例 HRP的调度性能 2 14 0 3 9 15 13 3 9 13 20 15 TA 3 TB 7 TC 9 TD 14 TE 7 8 00 8 3 6 4 5 2 2 0 4 6 A B C D E WE 3 50 WA 1 WB 1 17 WC 2 25 WD 2 80 E C D A B 周转时间T 结束时间Tc 到达时间Tin 3 0 3 周转时间T 带权周转时间W 周转时间T 服务时间Tr 3 3 1 带权周转时间W 平均 9 4 4 4 2 25 9 6 5 5 1 6 9 8 2 2 1 5 RC RD RE RD 13 6 5 5 2 4 RE 13 8 2 2 3 5 五 高响应比优先权调度算法HRP 不同调度算法对同一个作业 进程的性能分析 返回 六 多级反馈队列调度算法MFQ 就绪队列1 8ms 就绪队列2 16ms 就绪队列3 32ms 就绪队列n FCFS 多级反馈队列调度 处理机 终止 设置多个就绪队列 并为每个队列赋予不同的优先级 队列1的优先级最高 其余队列逐个降低 每个队列中进程执行时间片的大小也各不相同 进程所在队列的优先级越高 其相应的时间片就越短 当一个新进程进入系统时 首先将它放入队列1的末尾 按FCFS等待调度 如能完成 便可准备撤离系统 反之由调度程序将其转入队列2的末尾 按FCFS再次等待调度 如此下去 进入队列n按RR算法调度执行 仅当队列1为空时 才调度队列2中的进程运行 若队列I中的进程正执行 此时有新进程进入优先级较高的队列中 则新进程将抢占运行 六 多级反馈队列调度算法MFQ 六 多级反馈队列调度算法MFQ 多级反馈队列算法有如下特点 短优先 运算型进程有较长的时间片 采用了动态优先级 采用了可变时间片 返回 各种常用调度算法的比较 返回 练习1 有5个批处理任务A B C D E几乎同时到达一计算中心 其预计运行时间分别为10 6 2 4和8分钟 其优先级分别为3 5 2 1 4 这里5是最高优先级 问 按优先级调度 先来先服务 假设提交顺序为ABCDE 最短作业优先调度的平均周转时间 返回 练习1