华中科技大学电信系操作系统.ppt

第六章多处理器系统和处理器管理 掌握多处理器分类调度的层次调度算法的性能评价各种调度算法的基本思想了解多处理器硬件组织结构Windows2000 XP的调度思想 无论是在操作系统控制下执行的程序 还是操作系统程序自己 都最终是要在处理器上执行 以便实现其功能 计算机系统的核心是中央处理器 如果一个计算机系统只包括一个中央处理器 称之为单处理器系统 如果有多个中央处理器 则称之为多处理器系统 6 1多处理器系统 随着信息和网络技术的发展 进入信息时代 带给计算机领域的一个重要的趋势是越来越普遍的使用多重处理 即配置一个有几个甚至几百个处理器的计算机系统 主要原因是由于人们要求处理的信息越来越庞大 要求具有更高性能更高处理速度的计算机系统 多处理器系统的优点 可靠性 高度并行性 多处理器可增强单处理器计算机系统的能力 而又不比显著增加费用 价格 建立多重处理 既增强了系统的处理能力 又不必增强完整的额外系统 多处理器系统提供了重要的灵活性 多处理器的硬件组织 总线式结构单总线结构多总线结构交叉开关结构多端口存储器结构 单总线结构 多总线结构 交叉开关式结构 多端口存储器结构 核心 多端口存储器模块 6 2多处理器系统的分类 多处理器簇 Cluster 又称分布式系统 多处理器簇是指每个处理器都有自己专用的存储器 每个单元都有自包含的计算机 计算机之间的通信或者经由专用的线路 或者通过网络 共享存储器的多处理器系统多个处理器共享公用存储器 每个处理器共享对公用存储器中的程序和数据的访问 这种多处理器系统常分为 主从式多处理器结构和对称式多处理器结构 主 从式处理器系统 在主从式处理器系统中 指定一个处理器作为主处理器 其他处理器皆为从处理器 由于处理器地位是不平等的 所以又称为非对称 只有主处理器可运行操作系统 从处理器仅可执行用户程序 主 从处理器系统的缺点 主处理负载过重 主处理器故障将引起整个系统故障 可靠性差 若主处理器不能充分有效地满足从处理器的服务请求 从处理器的利用率会降低 对称式多处理器系统 系统中有多个处理器 所有的处理器处于同等地位每个处理器都可以运行操作系统和内核程序处理中断 调度进程等 每个处理器都同样可以控制I O设备和系统中其他资源 系统中所有处理器共享主存储器 没有自己私用的存储器 SMP的组织 处理器 缓存 处理器 缓存 处理器 缓存 存储器 I O I O 6 3调度的层次 从处理机调度的对象 时间 功能等不同角度 我们可把处理机调度分成不同类型 按照调度的层次 调度可分为三级 长期调度按照某种原则从磁盘某些盘区的作业队列和交互作业中选取作业进入主存 并为作业做好运行前的准备工作和作业完成后的善后工作 中期调度决定哪些进程被允许参与竞争处理资源 将进程的部分或全部换出到外存上 将当前所需部分换入到内存 短期调度按照某种原则将处理器分配给就绪进程或线程 处理机调度的层次 1 作业调度 作业的状态 提交状态作业被提交给机房后或用户通过终端键盘向计算机中键入其作业时所处的状态 后备状态作业的全部信息都已通过输入设备输入 并由操作系统将其存放在磁盘的某些盘区中等待运行 运行状态作业调度程序选中而被送入主存 并建立进程投入运行 完成状态作业完成其全部运行 释放其所占用的全部资源 作业调度 作业调度由作业调度程序来完成作业调度时的两个决定接纳多少个作业 作业调度每次要接纳多少个作业进入内存 取决于多道程序度 应根据系统的规模和运行速度等因素 接纳哪些作业 即应将哪些作业从外存调入内存 这取决于所采用的调度算法 作业调度程序的功能 按照某种调度算法从后备作业队列中挑选作业为选中的作业分配主存和外设资源为选中的作业建立相应的进程为选中的作业运行时所需的有关表格 如作业表等作业结束时完成该作业的善后处理作业 选择调度算法时考虑的问题 设计目标资源利用率均衡地处理系统和用户地要求在使用优先级地系统中 每个进程都有一个优先级 调度算法应优先运行高优先级进程在使用优先数的系统中 调度策略还可分为 可抢占 和 不可抢占 两种方式 调度的性能准则 我们可从不同的角度来判断处理机调度算法的性能 如用户的角度 处理机的角度和算法实现的角度 实际的处理机调度算法选择是一个综合的判断结果 面向用户的调度性能准则面向系统的调度性能准则调度算法本身的调度性能准则 周转时间 作业从提交到完成 得到结果 所经历的时间 包括 在收容队列中等待 CPU上执行 就绪队列和阻塞队列中等待 结果输出等待 批处理系统平均周转时间t平均带权周转时间 带权周转时间W是t 周转 t CPU执行 响应时间 用户输入一个请求 如击键 到系统给出首次响应 如屏幕显示 的时间 分时系统截止时间 开始截止时间和完成截止时间 实时系统 与周转时间有些相似 公平性 不因作业或进程本身的特性而使上述指标过分恶化 如长作业等待很长时间 优先级 可以使关键任务达到更好的指标 面向用户的调度性能准则 面向用户的调度性能准则 平均周转时间t ti tci tsi 面向用户的调度性能准则 平均带权周转时间w为 tri为作业i的实际执行时间一般来说 系统应选择使作业的平均周转时间 或带权周转时间 短的某种算法 因为 作业的平均周转时间越短 意味着这些作业在系统内停留的时间越短 因而系统资源的利用率也就越高 2 面向系统的调度性能准则 吞吐量 单位时间内所完成的作业数 跟作业本身特性和调度算法都有关系 批处理系统平均周转时间不是吞吐量的倒数 因为并发执行的作业在时间上可以重叠 如 在2小时内完成4个作业 而每个周转时间是1小时 则吞吐量是2个作业 小时处理机利用率 大中型主机各种设备的均衡利用 如CPU繁忙的作业和I O繁忙 指次数多 每次时间短 的作业搭配 大中型主机3 调度算法本身的调度性能准则易于实现执行开销比 处理器调度的两种方式 非抢占方式 采用该方式 一旦将处理器分配给某进程后 便让进程一直执行 直到该进程完成和其因等待某事件而阻塞时 才将处理器分配给其他进程 优点 实现简单 系统开销小缺点 难以满足紧急任务的要求 处理器调度的两种方式 抢占方式采用这种方式 允许调度程序根据某种原则停止正在处理器上运行的进程 将处理器重新分配给其他进程 优点 能满足及时响应紧急任务缺点 增加了系统开销 6 4单处理调度算法 先进先出调度算法优先级调度算法时间片轮转算法最短进程优先调度算法最短剩余时间优先调度算法最高响应比优先调度算法多级反馈队列调度算法 调度实质就是一种资源分配 调度算法是指根据系统的资源分配策略分配资源的算法 有的算法适用于作业调度 有的算法适用于进程调度 有的两者都适应 先进先出调度算法 基本原则 按照作业提交或进程进入就绪队列的先后次序来选择 调度方式 不可抢占 缺点 比较有利于长作业 而不利于短作业 有利于CPU繁忙的作业 而不利于I O繁忙的作业 应用 不作为主要的调度策略 尤其不能用于分时和实时系统 常结合其他调度策略使用 可用于作业调度和进程调度 先进先出调度算法 优先级调度算法 原则 按照进程的优先级大小来调度 高优先级进程得到优先处理 应用 可用于作业调度和进程调度 主要 用于进程调度时 可分为 非抢占 的优先级调度法 可抢占 的优先级调度法 UNIX系统进程调度算法 优先级调度算法 优先级的确定方式 静态优先级 优先级在进程创建时确定 且在进程整个运行期间保持不变 动态优先级 在创建进程时赋予优先级 在进程运行过程中可以自动改变 以便获得更好的调度性能 在就绪队列中 等待时间延长则优先级提高 从而使优先级较低的进程在等待足够的时间后 其优先级提高到可被调度执行 进程每执行一个时间片 就降低其优先级 从而一个进程持续执行时 其优先级降低到出让CPU 时间片轮转算法 原则 将系统中所有的就绪进程按照FIFO原则 排成一个队列 每次调度时将CPU分派给队首进程 让其执行一个时间片 时间片的长度从几个ms到几百ms 在一个时间片结束时 发生时钟中断 调度程序据此暂停当前进程的执行 将其送到就绪队列的末尾 并通过上下文切换执行当前的队首进程 进程可以未使用完一个时间片 就出让CPU 如阻塞 调度方式 可抢占策略应用 用于进程调度 特别适用于分时系统 时间片长度的确定 时间片长度变化的影响过长 退化为FIFO算法 进程在一个时间片内都执行完 响应时间长 过短 用户的一次请求需要多个时间片才能处理完 上下文切换次数增加 响应时间长 对响应时间的要求 T 响应时间 N 进程数目 q 时间片 时间片长度的影响因素 就绪进程的数目 数目越多 时间片越小 当响应时间一定时 系统的处理能力 应当使用户输入通常在一个时间片内能处理完 否则使响应时间 平均周转时间和平均带权周转时间延长 最短进程优先调度算法 原则 从就绪队列中挑选所需运行时间最短的进程进入主存运行 调度方式 非抢占 策略 应用 不适用于分时系统优点 比FCFS改善平均周转时间和平均带权周转时间 缺点 对长作业非常不利 可能长时间得不到执行 未能依据作业的紧迫程度来划分执行的优先级 难以准确估计作业的执行时间 从而影响调度性能 最短进程优先调度算法 最短剩余时间优先算法 短作业优先调度算法的变型 原则 让运行到作业完成时所需运行时间最短的进程优先得到处理 包括新进入系统的进程 调度方式 可抢占 策略 新进入系统的进程有可能抢占处理机 优点 降低作业的平均等待时间 缺点 估计运行时间 系统开销大 应用 可用于分时系统 最高响应比优先调度算法 原则 引入动态优先级机制 响应比高者得到优先调度 动态优先数为 等待时间 要求的服务时间要求的服务时间调度方式 非抢占 策略 缺点 调度前 需计算优先数 开销大 最高响应比优先调度算法 优点 是一种较好的折中算法 如果作业的等待时间相同 则要求的服务时间越短 其优先数越高 因此 有利于短作业 当要求的服务时间相同时 作业的优先数取决于等待时间 因而实现了FIFO 对长作业 当其等待时间越长 其优先数会越高 最高响应比优先调度算法 最高响应比优先调度算法 开始时只有作业1 作业1被选中 执行时间2 0作业1完成后 响应比依次为 1 5 0 5 0 5 1 0 1 0 1 0 5 0 2 0 2 因此作业3响应比最高 作业3被选中 执行时间0 1 作业3完成后 响应比依次为 1 6 0 5 0 5 0 6 0 2 0 2 作业2响应比最高 作业2被选中 执行时间0 5 作业2完成 作业4执行0 2 多级反馈队列算法 多级反馈队列算法是时间片轮转算法和优先级算法的综合和发展 优点 为提高系统吞吐量和缩短平均周转时间而照顾短进程为获得较好的I O设备利用率和缩短响应时间而照顾I O型进程不必估计进程的执行时间 动态调节 基本实现 设置多个就绪队列 分别赋予不同的优先级 如逐级降低 队列1的优先级最高 优先级和时间片相结合 每个队列执行时间片的长度不同 规定优先级越低则时间片越长 按FIFO原则调度 新进程进入内存后 先投入队列1的末尾 动态优先级 若按队列1一个时间片未能执行完 则降低投入到队列2的末尾 同样按FIFO算法调度 如此下去 降低到最后的队列 则按 时间片轮转 算法调度直到完成 仅当较高优先级的队列为空 才调度较低优先级的队列中的进程执行 如果进程执行时有新进程进入较高优先级的队列 则抢先执行新进程 并把被抢先的进程投入原队列的末尾 多级反馈队列 几点说明 I O型进程 让其进入最高优先级队列 以及时响应I O交互 通常执行一个小时间片 要求可处理完一次I O请求的数据 然后转入到阻塞队列 计算型进程 每次都执行完时间片 进入更低级队列 最终采用最大时间片来执行 减少调度次数 I O次数不多 而主要是CPU处理的进程 在I O完成后 放回优先I O请求时离开的队列 以免每次都回到最高优先级队列后再逐次下降 为适应一个进程在不同时间段的运行特点 I O完成时 提高优先级 时间片用完时 降低优先级 多级反馈队列调度算法具有较好的性能 能满足各类用户的需要 对分时交互型短作业 系统通常可在第一队列规定的时间片内让其完成工作 使终端型用户都感到满意 对短的批处理作业 通常 只需在第一或第一 第二队列中各执行一个时间片就能完成工作 周转时间仍然很短 对长的批处理作业 它将依次在第一 第二 队列中获得时间片并运行 决不会出现得不到处理的情况 Windows2000 XP调度算法 Windows2000 XP的调度是基于内核级线程的 它支持抢占式调度 包括多个优先数层次 在某些层次线程的优先数是固定的 在另一些层次线程的优先数将根据执行的情况动态调整 它的调度策略是一个多级反馈