第6章 处理机调度.ppt

1 操作系统原理 2 处理机管理中的重要问题是处理机调度问题 不同类型的操作系统往往采用不同的处理机分配方法 在多用户批处理操作系统中 对处理机的分配分为两级 宏观层次上的作业调度和微观层次上的进程调度 作业调度与进程调度的关系为 每个用户提交的算题任务往往作为系统的一个处理单位 称为作业 这样一道作业在处理过程中又可以分为多个并发的活动单位 称为进程 课程导入 3 第6章处理机调度 6 1处理机的多级调度6 2作业调度6 3进程调度 4 6 1处理机的多级调度 处理机调度的功能处理机调度的分层实现批处理系统中的处理机调度多任务操作系统中的处理机调度多线程操作系统中的处理机调度 5 处理机调度的功能 维护数据结构 制订调度策略 谁优先 给出调度算法 调度策略的实现 实施处理机的分派 分配 不同类型的操作系统往往采用不同的处理机分配方法 6 只有内存的程序才能在CPU上运行 因此 处理机的调度通常分为二层 1 作业调度 又称为宏观调度 2 进程调度 又称为微观调度 处理机调度的分层实现 7 批处理系统中的处理机调度 1 作业调度任务 对存放在辅存设备上的大量作业 以一定的策略进行挑选 分配主存等必要的资源 建立作业对应的进程 使其投入运行 2 进程调度任务 对进入主存的所有进程 确定哪个进程在什么时候获得处理机 使用多长时间 解决对资源的存取 使用方法问题 并提供对资源存取的控制和实施安全保护措施 处理机调度分为两级 作业调度和进程调度 8 多任务操作系统中的处理机调度 在分时系统或支持多任务并发执行个人计算机操作系统中 系统将用户提交的任务处理为进程 一个进程又可以创建多个子进程 形成可以并发执行的多进程 进程调度的任务是 当处理机空闲时 以某种策略选择一个就绪进程去运行 并分配处理机的时间 9 多线程操作系统中的处理机调度 在支持多线程运行的系统中 每个进程都有一个主线程 也可以创建多个线程 系统为进程分配它所需要的资源 而处理机的分配的对象则为线程 系统提供线程调度程序 其功能是 当处理机空闲时 以某种策略选择一个就绪线程去运行 并分配处理机的时间片 10 6 2作业调度 6 2 1作业的状态 提交状态 用户将自己的程序和数据提交给系统 等待输入 后备状态 作业已存放在磁盘上 等待调进入主存 执行状态 作业在主存中运行 完成状态 作业计算完成开始 退出主存 11 12 6 2 2作业调度的功能 1 确定数据结构建立对作业进行控制的数据结构 作业控制块 jcbjobcontrolblock 记录每个作业的类型 状态 资源请求及分配情况 2 确定调度策略与调度算法3 分配资源为选中的作业分配所需要的系统资源 4 善后处理收回该作业所占用的全部资源 撤消作业控制块以及与该作业有关的全部进程 13 作业控制块jcb存在于作业在系统中的整个过程中 它是一个作业存在的标志 作业名 资源要求 资源使用情况估计执行时间进入系统时间最迟完成时间开始执行时间要求的主存量已执行时间要求外设的类型及台数主存地址要求文件量和输出量外设台号 类型 优先级控制方式 状态作业类型 6 2 3作业控制块 14 可采用周转时间和带权周转时间来衡量作业调度算法性能的好坏 6 2 4作业调度算法性能的衡量 1 周转时间一个作业提交给计算机系统到该作业的结果返回给用户所需要的时间 定义ti tci tsi或ti 运行时间 等待时间ti 作业i的周转时间 tsi 作业i的提交时间 tci 作业i的完成时间 2 意义 说明作业i在系统中停留时间的长短 15 3 平均周转时间t 4 如何估价对用户 周转时间越小越好对系统 平均周转时间越小 吞吐量越大 越好 例 作业运行时间等待时间周转时间1515202202040 该调度算法对哪个作业有利呢 原因 周转时间中包含了等待时间 平均周转时间同样也有类似的问题 解决办法 去掉等待时间的影响 16 2 带权周转时间 1 带权周转时间 一个作业的周转时间与其运行时间的比值 2 意义 说明作业i在系统中相对等待时间 3 平均带权周转时间t 精确度 高于周转时间和平均周转时间 17 6 2 5作业调度算法 先来先服务调度算法 FCFS 1 策略 按作业来到的先后次序进行调度 2 特点 简单 易实现 3 讨论在先来先服调度算法下的周转时间与带权周转时间 18 作业提交时间执行时间开始时间完成时间周转时间带权周转时间18 002 008 0010 002 00128 500 5010 0010 502 00439 000 1010 5010 601 601649 500 2010 6010 801 306 5 4 缺点 算法性能最差原因 当短作业排在长作业后面时 等待时间变长 示意图 平均周转时间t 1 725平均带权周转时间w 6 875 19 改进 短作业排在长作业前面 2 短作业优先调度算法 1 策略 按作业请求运行的时间长短进行调度 2 特点 易实现 系统吞吐量高 只照顾短作业 而没有考虑长作业的利益 3 讨论在短作业优先调度算法下的周转时间与带权周转时间 20 作业提交时间执行时间开始时间完成时间周转时间带权周转时间18 002 0028 500 5039 000 1049 500 20 8 0010 002 00110 3010 802 304 610 0010 101 101110 1010 300 804 问题 对长作业极不利 如何解决呢 平均周转时间t 1 55平均带权周转时间w 5 15 21 3 响应比高者优先调度算法 响应比 特点 既短作业优先 以提高效率 又适当考虑长作业 4 优先调度算法 22 思考 1 衡量作业调度算法的标准是 2 现有如下作业序列 作业1 提交时间8 00 运行时间1 00 作业2 提交时间8 30 运行时间3 00 作业3 提交时间9 00 运行时间0 10 作业4 提交时间9 30 运行时间0 5 试用先来先服务和短作业优先调度算法处理该作业序列 问哪种作业调度算法性能更好 23 6 3进程调度 24 6 3 1调度 分派结构 1 调度依照完全确定的策略将一批进程进行排序 将一个进程插入到就绪队列并按一定原则保持队列结构 2 分派当处理机空闲时 移出就绪队列中第一个进程 并赋予它使用处理机的权利 25 26 6 3 2进程调度的功能 1 记录和保持系统中所有进程的有关情况和状态特征 2 决定分配策略 优先调度原则 进程就绪队列按进程优先级高低排序 先来先服务原则 进程就绪队列按进程来到的先后次序排序 3 实施处理机的分配和回收 27 进程调度的时机 当一个进程从运行态切换成阻塞态时 当一个进程从运行态切换成就绪态时 当一个进程从阻塞态切换成就绪态时 当一个进程中止时 执行进程调度一般在下述情况下发生 就绪队列中的某个进程的优先级变得高于当前运行进程的优先级 从而也将引起进程调度 可剥夺方式 不可剥夺方式 28 进程调度准则 1 CPU响应时间 是用户输入一个请求到系统给出首次响应的时间 目的 在分时系统中 使交互式用户的响应时间尽可能短 或尽快处理实时任务 这是分时系统和实时系统衡量调度性能的一个重要指标 29 2 吞吐率单位时间内CPU完成作业 进程 的数量 目的 在批处理系统中 使得单位时间内处理的作业数尽可能多 即吞吐率尽量高 30 3 周转时间是作业从提交到完成所经历的时间 周转时间ti 完成时刻 提交时刻 运行时间 等待时间平均周转时间T ti n平均周转时间 衡量对同一作业流施行不同作业调度算法时它们呈现的目的 使周转时间尽可能短 T越小越好 31 4 资源利用率目的 使得CPU或其他资源的使用率尽可能高且能够并行工作 CPU利用率 CPU有效工作时间 CPU总的运行时间 40 轻负荷系统 90 重负荷系统 当有I O请求时 由于I O设备速度慢 可以CPU优先分配给使用I O设备的进程 32 5 公平性不同的调度算法可能会有利于某一类进程的运行 而不利于其他类的进程 所以在选择并确定算法时必须综合考虑 应能尽量地满足各类进程或作业运行的要求 目的 确保每个用户每个进程获得合理的CPU份额或其他资源份额 不会出现饿死情况 33 6 系统开销包括进程切换 内存空间占用目的 合理的系统开销 34 这些因素一般无法全部满足 因为它们有时相互矛盾 分时系统 重点考虑响应时间 公平性批处理系统 重点考虑吞吐率 周转时间实时系统 要求CPU能及时响应 35 6 3 3进程调度方式 调度方式在按进程优先级调度的系统中 当一进程正在处理机上执行时 若有某个更为 重要而紧迫 的进程需要运行时 系统如何分配处理机 基本的方式有两种 非剥夺方式让正在执行的进程继续执行 直到该进程完成或发生某事件而进入 完成 或 阻塞 状态时 才把处理机分配给 重要而紧迫 的进程 剥夺方式当 重要而紧迫 的进程一到 便暂停正在执行的进程 立即把处理机分配给优先级更高的进程 在实现中还可采用选择可抢占策略 见教材P148 36 6 3 5进程调度算法 进程优先数调度算法预先确定各进程的优先数 系统把处理机的使用权赋予就绪队列中具备最高优先级 优先级和一定的优先数相对应 的就绪进程 优先数的分类及确定 静态优先数 在进程被创建时确定 且一经确定后在整个进程运行期间不再改变 动态优先数 进程优先数在进程运行期间可以改变 37 静态优先数的确定优先数根据进程所需使用的资源来计算 优先数基于程序运行时间的估计 优先数基于进程的类型 动态优先数的确定当进程使用CPU超过一定数值时 降低优先数 当进程进行I O操作 放弃CPU 后 增加优先数 当进程就绪 等待 超过一定数值时 提高优先数 38 2 循环轮转调度算法 当CPU空闲时 选取就绪队列首元素 赋予一个时间片 当时间片用完时 该进程转为就绪态并进入就绪队列末端 1 简单循环轮转调度 时间片q固定 即 就绪队列中的所有进程以等速度向前推进 时间片q的确定 设T为响应时间 N为进程数 则 q Tmax N 3000ms 6 60 50 500ms 当前的响应时间 t q n n为当前进程数 问题 响应时间是变化的 太小时浪费切换时间 例 设q 0 1秒当ni 30时 ti 3秒当nj 3时 tj 0 3秒 39 2 可变时间片循环轮转调度 响应时间T固定 响应时间T固定为用户所能接受的 如3秒 每一轮开始前 根据当前的最大就绪进程数Ni 决定该轮的时间片Qi 即 不同轮转的时间片可能不同 同一轮中各进程的时间片相同 Qi T Ni 40 3 多重时间片循环轮转调度算法 是优先数调度算法和循环轮转调度算法的综合 根据优先数的分布采用多个就绪队列 进程按优先数排在响应的就绪队列中 41 6 3 6调度用的进程调度变迁图 通过进程调度变迁图 可反映出一个系统的进程调度的各种特征 42 1 队列结构 I O等待队一个进程如果请求I O 则进入I O等待队列 低优先就绪队一个进程如果在运行中超过了分配给它的时间片 就进入低优先就绪队列 高优先就绪队列当进程从等待状态变为就绪状态时 则进入高优先就绪队列 43 2 进程调度算法 当CPU空闲时 若高优先就绪队列非空 则从高优先就绪队列中选择一个进程运行 分配时间片为100ms 当CPU空闲时 若高优先就绪队列为空 则从低优先就绪队列中选择一个进程运行 分配时间片为500ms 3 调度效