第4章处理器调度

第四章处理器调度 1 调度及其类型 关于调度 调度是操作系统的基本功能 几乎所有的系统资源在使用前都要经过调度 处理器是计算机系统中最重要的资源 其调度策略常表征操作系统的某种特征 调度类型 1 1作业调度 高级调度 宏观调度 长期调度 主要工作和任务 根据某种策略或算法 从后备作业中选择若干作业 分配必要的资源 建立相应进程 加载相应的程序和数据并等待进程调度为其指派处理器 作业完成后的善后工作 时间尺度分钟 小时 天 1 2中级调度 进程对换 中期调度 交换调度 设置原因内存资源缺乏 进程阻塞 进程数目过多 主要工作和作用 内存与外存间进程交换 系统短期调整 常用于具有虚拟存贮技术的系统或分时系统中 1 3进程调度 微观调度 低级调度 短期调度 主要工作和要求 选择就绪进程占用处理器并实现转接 常驻内存 对系统性能影响重大 时间尺度毫秒级 1 4三级调度之间的关系 作业身份的转换 竞争CPU过程中内存资源紧张或不足的处理 处理器的真正指派 调度实例1 MULTICS系统其调度方案为 限定后备状态作业数 60 限定内存作业道数 8 定时交换 2秒 说明 小范围内多道 大范围内分时 2 UNIX系统其调度方案为 核心程序中的sched程序段负责进程映象的换入换出 相当于中级调度 核心程序中的swtch程序段负责分配CPU 相当于进度调度 2 调度性能评价2 1调度的实质与操作系统的设计目标调度的实质是为了达到主观上某些设计目标 设计目标 尽可能多的作业 处理器 忙 I O设备充分利用 公平合理 2 2设计调度算法的因素 选择算法应与系统的整个设计目标一致 注意系统资源的均衡使用 防止某些作业长期得不到调度 尽量公平合理 算法不应过于复杂 2 3有关指标说明与用户相关的指标 周转时间指作业从提交到完成 得到结果 所经历的时间 响应时间指用户输入一个请求 如击键 到系统给出首次响应 如屏幕显示 的时间 公平性指调度算法不会因作业或进程本身的特性而使上两个指标过分恶化 与系统相关的指标 吞吐量指单位时间内所完成的作业数 作业平均周转时间T Ti n其中n为被测定作业流中的作业数 Ti Tci Tsi 即作业执行时间 等待调度时间 Tci 作业i的完成时刻 Tsi作业i的提交时刻 作业平均带权周转时间W Wi n 其中Wi Ti tRi tRi 作业i的实际执行时间 系统利用率指处理器的利用率及各种设备的均衡利用率 n i 1 n i 1 3 作业调度3 1单道批处理系统的调度算法 先来先服务算法FCFS按作业到达的先后次序进行调度 优先考虑在系统中等待时间最长的作业 而不论其要求的执行时间的长短 示例假定四个作业的到达顺序如下 1 要求运行时间2秒 2 要求运行时间60秒 3 要求运行时间2秒 4 要求运行时间2秒 忽略四个作业在机外的等待时间 计算T与W T 48 5W 16 76 短作业优先算法SJF优先调度要求运行时间最短的作业 上例T 19 5W 1 8 响应比高者优先算法HRN响应比Rp 作业响应时间tR 要求执行时间其中tR 到此次调度时已等待时间 要求执行时间故Rp 1 作业已等待时间 要求执行时间1 防止无限制调度延迟 2 照顾先来后到 3 照顾短作业 3 2多道批处理系统的调度算法需要考虑的因素 CPU对I O等待时间问题 T与W的定量计算问题算法讨论 基于先来先服务算法 基于优先级调度算法 示例B5500计算机操作系统实行由用户根据作业的紧急程度在其作业申请表中指定一个优先数 系统依据这个优先数将作业的JCB插入相应的优先级队列中 示例IBM360 370系统中按作业的类别划分优先级 如图A类 I O繁忙的作业B类 I O和CPU均衡的作业C类 CPU繁忙的作业D类 其它一般的作业 2 1 A A类 优先级0 A B C类 B C类 X类 优先级1 优先级2 优先级3 优先级高 优先级低 2 1 B 2 1 C 2 1 D 调度规则1 用户说明其作业类别及该类中的优先数 2 作业注册程序对作业先按类排列 同类中按优先数排序 3 主存用户区分区 规定各分区接纳的作业类型 4 作业调度从相应类的作业中挑选优先级高的作业投入运行 分时和优先级相结合调度算法用于分时系统及某些引入分时机制的多道批处理系统中 示例MULTICS系统采用分时和优先级结合的调度算法 1 后备作业按优先级分成多个队列 2 作业指定一个优先级范围 L1 L2 任何时刻作业的优先级Li都满足1 L1 Li L2 n 3 会话型作业 分时作业 优先级从1到P1 非会话型 批处理 作业优先级从P2到n 允许P2 P1 P值越小 优先级越高 4 每一后备作业队列分配相应时间片qi 且qi 1 2qi 5 调度优先当前最高优先级队列的作业 若其分配的时间片用完 则返回低一级后备队列等待下次调度 综合考虑资源要求调度算法综合考虑一个作业的对资源的要求 4 进程调度4 1进程调度的功能 记录系统中所有进程的执行情况 选择占有处理器的进程 进行进程上下文切换 4 2进程调度的时机与引起进程调度的原因及进程调度的方式有关 引起进度调度的原因 当前执行进程执行完毕 当前执行进程由于请求某个事件受阻 分时系统中时间片用完 强占式系统中高优先级进程就绪 进程调度的方式 可强占式 剥夺式 调度 不可强占式 非剥夺式 调度 4 3进程调度性能评价定性指标 调度的可靠性 调度的简洁性定量指标 CPU的利用率 进程在就绪队列中的等待时间与执行时间比率 4 4进程调度算法 简单轮转法 时间片轮转法 时间片时钟法 遵循FCFS原则形成一个队列 每次选择队首进程并给定固定值的时间片q投入运行 若时间片到而未完成的进程将再次进入队尾 等待下一轮调度 关于时间片q其中T是系统的响应时间 N是系统规定的同时就绪的进程数 1 与系统响应速度2 与系统要求N值3 与CPU性能4 与进程切换时间i 执行 特点简单 方便 公平 缺乏灵活性 首 尾 就绪队列 IO阻塞队列 时间片到 进程结束 作业调度 建立进程 IO完成 IO请求 调度选中 固定周期轮转法 时间片可变 当就绪进程数目不足时 保持T不变 增大q值 使短作业尽快完成 减少进程切换次数 减轻系统开销 优先级高者优先调度设定优先级 数 方式1 静态优先级 数 法进程建立时由系统指定并在其生命期中一直保持不变 按进程类型 按资源需求量 外部标准 2 动态优先级 数 法进程建立时所指定的优先级在进程运行过程中可不断变化 以获得更好的调度性能 线性修改优先级固定时刻增加或修改进程优先级 进程I O请求受阻时适当增加 进程长期用满时间片而中断 适当降低 非线性修改优先级进程初期其优先级不变或线性改变 若某种情况出现 则突然增加其优先级 多级队列调度按优先级高低不同设立两级或多级队列 进程调度先从高优先级队列挑选 同一队列实行FCFS或轮转法调度 高优先级就绪队列 中优先级就绪队列 低优先级就绪队列 执行 时间片完 时间片完 时间片完 q 50ms q 100ms q 500ms 带反馈多级队列调度依据进程运行的不同情况进行带反馈的调整 改变其所在队列 执行 低优先就绪队列 高优先就绪队列 中优先就绪队列 阻塞队列 阻塞队列 阻塞队列 时间片完 q 500ms q 100ms q 50ms IO完成 IO完成 IO完成 盘IO 终端IO 页面IO 进程创建 4 5进程调度的实现 就绪队列组织包括FIFO 优先级排序队列 优先级无序链表方式 分派程序dispatch算法参见教材 第四章处理机调度 作业 1 下面调度算法哪些适合于作业调度 哪些适合于进程调度 1 先来先服务2 轮转法3 短作业优先4 优先级高者优先5 长作业优先2 试述多级队列调度算法中不同队列具有大小时间片的优点 3 解释下面算法对短作业的优待程度 1 FCFS2 轮转法3 多级队列反馈 4 许多调度算法是参数化的 下面各对算法间有什么联系 1 优先级与SJF2 多级队列反馈与FCFS3 优先级与FCFS4 轮转法与FCFS5 某动态优先级调度算法 当作业等待CPU时 在就绪队列中 其优先级以a速率改变 当作业运行时 占据CPU 其优先级以b速率改变 下面情况中 将是什么算法 1 若b a 02 若b a 0 6 给定一组作业J1 J2 Jn 它们的运行时间分别是T1 T2 Tn 假定这些作业同时到达 并将在一台CPU上按单道方式运行 证明 按SJF 则平均周转时间最短 7 有四道作业情况如下 作业号提交时间 小时 运行时间 小时 18 002 0028 500 5039 000 1049 500 20 采用单道运行 按下面调度算法 分别计算作业的平均周转时间T和平均带权周转时间W 1 FCFS2 SJF3 HRN 8 比较下面算法对短作业的优待程度和对长作业的虐待程度 1 FCFS2 SJF3 HRN9 设某系统调度如图 q 50ms 系统中有两进程A和B 执行逻辑如图 假定t 0时刻 A B在就绪队列中 A在B先 忽略进程切换时间 P V操作本身时间不计 按下表填写两进程从t 0时刻到t 170ms间的状态变化 执行 就绪 阻塞 调度 超时 P S V S P S 20ms 30ms A V S 30ms 20ms B 初值S 0 时间 执行态进程 就绪态进程 阻塞态进程 发生事件 t 0 A B 10 设某系统调度如图 系统中有两作业A和B 执行逻辑如图 其中磁带IO系统立即响应并须在500ms完成 磁盘IO系统立即响应并须在100ms完成 假定t 0时刻作业A执行 B在高优先就绪队列中就绪 忽略进程切换时间 系统工作时间不计 按下表填写两作业的执行情况 作业A 计算 计算 计算 带IO 带IO 带IO 150ms 150ms 150ms 作业B 计算 计算 盘IO 盘IO 250ms 150ms 执行 低优先就绪 阻塞 30ms 超时 盘IO完成 高优先就绪 阻塞 带IO申请 盘IO申请 带IO完成 100ms 时间 运行 带IO阻塞 发生事件 t 0 A 盘IO阻塞 高优先就绪 低优先就绪 11 假定进程状态变迁如图 试问1 什么时间