9处理机调度-

处理机调度 调度的类型与模型调度算法实时系统中的调度多处理机调度 主要目的 处理机管理的工作是对CPU资源进行合理的分配使用 以便提高处理机利用率 并使各用户公平地得到处理机资源 本节介绍处理机调度算法并对调度算法的特点进行简单分析 调度的类型 高级调度中级调度低级调度 高级调度 高级调度 又称为 宏观调度 作业调度 从用户工作流程的角度 一次提交的若干个作业 对每个作业进行调度 时间上通常是分钟 小时或天 作业调度出现在批处理系统中或者是实时系统中 分时系统中没有作业调度程序接纳多少个作业 取决于允许多少个作业同时在内存运行 多道程序度 接纳哪些作业 取决于采用的调度算法 中级调度 内外存交换 又称为 中级调度 从存储器资源的角度 将进程的部分或全部换出到外存上 将当前所需部分换入到内存 注意 指令和数据必须在内存里才能被CPU直接访问 低级调度 低级调度又称为 微观调度 进程或线程调度 决定就绪队列中的哪个进程将获得处理机因为进程调度执行频繁 通常是几十毫秒执行一次 有两种实现方式 非剥夺式剥夺式 剥夺的原则如下 时间片原则优先权原则短作业 进程 优先原则 进程调度的队列 作业调度与进程调度队列 三级调度方式的队列 针对多个就绪对列的进程调度 挂起进程模型 针对多个就绪对列的进程调度 调度的性能准则 从不同的角度来判断处理机调度算法的性能如用户的角度系资源使用的角度实际的处理机调度算法选择是一个综合的判断结果 面向用户的调度性能准则1 周转时间 批处理系统 作业从提交到完成 得到结果 所经历的时间 包括 在收容队列中等待 CPU上执行 就绪队列和阻塞队列中等待 结果输出等待外存等待时间 就绪等待时间 CPU执行时间 I O操作时间平均周转时间 带权平均周转时间响应时间 分时系统 用户输入一个请求 如击键 到系统给出首次响应 如屏幕显示 的时间 面向用户的调度性能准则2 截止时间的保证 实时系统 开始截止时间 任务必须开始的最迟时间完成截止时间 任务必须完成的最迟时间是评价实时性能的重要指标 优先级 代表任务运行的紧迫程度 紧迫的任务具有高优先级别 严格的情况可采用剥夺调度方式 公平性 不因作业或进程本身的特性而影响对作业的调度性能 比如造成长作业等待很长时间一直得不到运行的情况 面向系统的调度性能准则 吞吐量 单位时间内所完成的作业数 批处理系统调度考虑的因素 处理机利用率 使CPU尽量处于忙碌状态 大型主机考虑的因素 各种资源的均衡利用 如CPU繁忙的作业和I O繁忙的作业搭配 大型主机考虑的因素 调度算法 操作系统中的调度的实质是一种资源分配这些调度算法有的适用于作业调度 有的适用于进程调度 有的两者都适用 先来先服务 FCFS FirstComeFirstService 这是最简单的调度算法 按先后顺序调度 按照作业提交或进程变为就绪状态的先后次序 分派CPU当前作业或进程占用CPU 直到执行完或因申请资源而阻塞 如申请I O 才出让CPU 非剥夺方式 在资源得到满足后作业或进程则被唤醒 如I O完成 并不立即恢复执行 通常等到正在运行的作业或进程出让CPU 因为是非剥夺方式 FCFS的特点比较有利于长作业 而不利于短作业 有利于CPU繁忙的作业 不利于I O繁忙的作业 FCFS P1 P2 链头 Pn 就绪队列按进程创建的时间先后排序 PCB集合 中断现场保护区 中断现场保护区 中断现场保护区 短作业优先 SJF ShortestJobFirst 又称为 短进程优先 SPN ShortestProcessNext 这是对FCFS算法的改进 其目标是减少平均周转时间 对预计执行时间短的作业 进程 优先分派处理机 通常后来的短作业不抢先正在执行的作业 SJF的特点 优点 比FCFS改善平均周转时间和平均带权周转时间 缩短作业的等待时间 提高系统的吞吐量 缺点 对长作业非常不利 可能长时间得不到执行 未能依据作业的紧迫程度来划分执行的优先级 难以准确估计作业 进程 的执行时间 从而影响调度性能 时间片轮转算法 RoundRobin 本算法基本思路是通过以时间片轮转 提高进程并发性和加快响应时间 从而提高资源利用率 轮转调度 最初的队列形成可按照FCFS或者按照优先级排队为每个进程分配一个时间片 轮流运行调度信息包括了进程进入就绪队列的时间和时间片大小 P1 P2 链头 Pn 中断现场保护区 中断现场保护区 中断现场保护区 时间片轮转算法 将系统中所有的就绪进程按照FCFS原则 排成一个队列 每次调度时将CPU分派给队首进程 让其执行一个时间片 时间片大小可以规定为几毫秒到几百毫秒不等 在时间片结束时 会产生时钟中断 调度程序据此暂停当前进程的执行 将其送到就绪队列的末尾 并通过上下文切换执行当前的队首进程 进程可以在时间片没用完之前 自愿放弃使用CPU 如运行完毕 或者由于等I O而被阻塞 时间片长度的确定 时间片长度q过长 退化为FCFS算法 进程在一个时间片内都执行完 导致对短的交互式请求的响应时间变长 过短 用户的一次请求需要多个时间片才能处理完 导致过多的进程切换降低了CPU效率比较合理的折衷考虑 可设时间片为100ms响应时间T T 响应时间 N 进程数目 q 时间片 就绪进程的数目N 如果响应时间固定 就绪进程的数目越多 时间片越小 q 1 q 4 五个进程按时间片运行的情况 五个进程分时运行的周转时间运算 优先级算法 PriorityScheduling 平衡各进程对响应时间的要求 适用于作业调度和进程调度 可分成可剥夺式非可剥夺式 优先数法 P1 P2 链头 Pn 就绪队列按进程的优先级排序 中断现场保护区 中断现场保护区 中断现场保护区 静态优先级 创建进程时确定 直到进程终止前都不改变 通常是一个整数 决定优先级的因素有 进程类型 系统进程优先级较高 对资源的需求 对CPU和内存需求较少的进程 优先级较高 用户要求 紧迫程度和付费多少 动态优先级 在创建进程时赋予的优先级 可以在进程运行过程中自动改变如 等待时间越长优先级越高在就绪队列中的进程 随着等待时间的积累 其优先级不断提高 经过一段时间后 其优先级可达到最高 从而获得调度执行 执行的时间越长优先级越低运行中的进程每执行一个时间片 其优先级便降低一定的值 如果一个进程持续执行 其优先级便可降低到不再为最高的而让出CPU 最高响应比优先调度算法 响应比的计算等待时间相同 短作业优先 要求服务的时间短 要求服务时间相同 优先权决定于等待时间 FCFS 对于长作业 若等待时间过长 优先权可提高 多级队列算法 Multiple levelQueue 本算法引入多个就绪队列 通过各队列的区别对待 达到对不同类型的作业的处理 比如交互型作业为前台 批处理型作业为后台作业 根据作业或进程的性质或类型的不同 将就绪队列再分为若干个子队列 每个作业固定归入一个队列 不同队列可有不同的优先级 不同的时间片大小 不同的调度策略等 多级反馈队列算法 RoundRobinwithMultipleFeedback 多级反馈队列算法是时间片轮转算法和优先级算法的综合和发展 其特点是 为提高系统吞吐量和缩短平均周转时间而照顾短进程为获得较好的I O设备利用率和缩短响应时间而照顾I O型进程不必事先知道进程的执行时间 可在不同队列中动态调节 多级反馈队列算法 设置多个就绪队列 分别赋予不同的优先级 如逐级降低 队列1的优先级最高 每个队列执行时间片的长度也不同 规定优先级越低则时间片越长 如逐级加倍新进程进入内存后 先投入队列1的末尾 按FCFS算法调度 若按队列1一个时间片未能执行完 则降低投入到队列2的末尾 同样按FCFS算法调度 如此下去 降低到最后的队列 则按 时间片轮转 算法调度直到完成 仅当较高优先级的队列为空 才调度较低优先级的队列中的进程执行 如果进程执行时有新进程进入较高优先级的队列 则抢先执行新进程 并把被抢先的进程投入原队列的末尾 分级轮转法 轮转 链头指针 FCFS 最高优先级 最低优先级 次高优先级 实时调度 要求更详细的调度信息 如 就绪时间 开始或完成截止时间 处理时间 资源要求 绝对或相对优先级 硬实时或软实时 采用可剥夺式调度 快速中断响应 在中断处理时 硬件 关中断的时间尽量短 快速任务分派 相应地采用较小的调度单位 如线程 实时调度算法 时间片轮转非剥夺式优先权调度基于时钟中断剥夺式优先权调度立即剥夺式调度 用于实时信息处理 用于不严格的实时控制系统 基于时钟中断 用于大多数实时系统中 各种算法的调度时机 用于对外部事件快速响应的实时系统中 基于开始截止时间的任务调度 基于完成截止时间的任务调度 B1 25 B2 75 B3 125 A1 10 A3 50 A2 30 A4 70 A5 90 A6 110 A7 130 B1 20 B1 5 B2 15 B2 10 B3 20 A1 A2 A3 A4 A5 A6 A7 A8 150 多处理机调度 与单处理机调度的区别 注重整体运行效率 而不是个别处理机的利用率 调度方式增多 同构 异构有不同的调度方式 进程的调度比单处理机的复杂调度单位广泛采用线程提高并行度 对称式多处理系统 SMP 按控制方式 同构的SMP调度可分为 集中控制静态调度动态调度分散控制自调度 非对称式多处理系统 ASMP 主 从处理机系统由主处理机管理一个公共就绪队列 并分派进程给从处理机执行 各个处理机有固定分工如 执行OS的系统功能 I O处理 应用程序等 OS的核心驻留在主机上进程调度由主机执行 主机一旦故障 会使整个系统瘫痪 固定和非固定的处理机分配 静态分配 staticassignment 每个CPU设立一个就绪队列 进程从开始执行到完成 都在同一个CPU上 优点 调度算法开销小 缺点 容易出现忙闲不均 动态分配 dynamicassignment 各个CPU采用一个公共就绪队列 队首进程每次分派到当前空闲的CPU上执行 每个处理机为各自选取运行的进程 自调度 self scheduling 各个CPU采用一个公共就绪队列 每个处理机都可以从队列中选择适当进程来执行 需要对就绪队列的数据结构进行互斥访问控制 是最常用的算法 实现时易于移植采用单处理机的调度技术 自调度的问题 瓶颈问题各处理机共享的就绪队列低效问题被阻塞的进程重新运行是不一定仍在阻塞前的处理机上运行 那么高速缓存中的内容需要重置线程切换问题由于合作中的几个线程没有同时运行而受阻 进而被切换下来 成组调度 gangscheduling 将一个进程中的一组线程 每次同时分派到一组处理机上执行 在剥夺处理机时要同时对这一组线程进行剥夺 优点通常这样的一组线程在应用逻辑上相互合作 成组调度提高了这些线程的执行并行度 有利于减少阻塞和加快推进速度 最终提高系统吞吐量 每次调度可以完成多个线程的分派 能够减少调度次数 从而减少调度算法的开销 两种成组调度 面向所有的应用程序平均分配处理机时间面向所有的线程平均分配处理机时间N个处理机M个应用程序 每个应用程序可有1 M的时间去占有N个处理机 空闲时间为 1 5和3 4相乘 15 空闲时间为 1 2和3 4相乘 37 5 专用处理机调度 dedicatedprocessorassignment 为进程中的每个线程都固定分配一个CPU 直到该线程执行完成 缺点 线程阻塞时 造成CPU的闲置 优点 线程执行时不需切换 相应的开销可以大大减小 推进速度更快 适用场合 CPU数量众多的高度并行系统 单个CPU利用率已不太重要 小结 调度的类型调度性能准则 面向用户 面向系统 调度算法 FCFS SJF RR 多级队列 优先级 多级反馈队列调度算法的性能分析 依据上述准则 实时调度 同构 异构方式下的不同调度算法多处理机调度 自调度 成组调度 专用处理机调度 习题 一个供销商与三个喝冰水者 口渴的人必须有三样东西 水 冰和茶杯才能喝到冰水 有三个人 每人手中仅有一样上述东西第四个人是服务员该人可以无限地提供这三样东西没有人喝水时 服务员便随机地提供其中的两样东西放在桌上如果这两样东西是口渴的人所需要的 则按需要收起 便可喝一杯冰水 喝完后则通知服务员 此过程反复进行 写一个管程 控制口渴者和服务员的活动过程 习题解答 一个供销商与三个喝冰水者 提供冰和水 提供杯子和水 提供杯子和冰 有杯子glass 有水water 有冰ice ProcedureseverWhile true drinkers Serve Cobeginsever drinker1 drinker2 drinker3 coend Proceduredrink