第六章 多处理器系统和处理器管理
第 6章 多处理器系统和处理器管理
? 6.1 多处理器系统
? 6.2 对称式多处理器系统
? 6.3 调度的层次和作业调度
? 6.4 单处理器系统的处理器调度
? 6.5 多处理器系统的处理器管理和调度
第六章 多处理器系统和处理器管理
6.1 多处理器系统
? 6.1.1 多处理器系统的优点
? 6.1.2 多处理器系统并行性的提高
? 6.1.3 多处理器的硬件组织（省略）
? 6.1.4 多处理器系统分类
? 6.1.5 主从式处理器系统
第六章 多处理器系统和处理器管理
6.1.1 多处理器系统的优点
? 可靠性高
? 高度并行性
? 增强计算能力，而不显著增加费用
? 可以灵活的扩充处理器数目
第六章 多处理器系统和处理器管理
6.1.2 多处理器系统并行性的提高
? 人工检测
? 由程序员发现程序中的并行性，编写并行程
序；
? 自动检测
? 利用编译程序、操作系统和硬件分析和检测
算法内部的并行性（隐性并行性）；
? 循环分配
? 树高降低
?, 不等待, 规则
第六章 多处理器系统和处理器管理
6.1.4 多处理器系统分类
? 从处理器之间的通信方式划分
多处理器系统
共享存储器
（紧密耦合）
分布式存储器
或分布式计算机系统
（松散耦合）
主从式
多处理器系统
对称式
多处理器系统
第六章 多处理器系统和处理器管理
6.1.5 主从式处理器系统
? 也称非对称式处理器系统，指定一个处
理器作为主处理器，其它处理器都是从
处理器。
? 只有主处理器能运行操作系统，从处理
器只能运行用户程序。
第六章 多处理器系统和处理器管理
6.1.5 主从式处理器系统
? 优点
? 只有一个处理器可以运行操作系统程序，简
化了表格互斥问题
? 操作系统代码不需要是可重入的
? 缺点
? 主处理器负载过重
? 可靠性差，完全依赖于主处理器
? 从处理器利用率不高
第六章 多处理器系统和处理器管理
6.2 对称式多处理器系统
(SMP:Symmetric MultiProcessor)
? 系统中的各个处理器地位平等，没有主
从之分
? 每个处理器都可以运行操作系统和内核程序
处理中断、调度进程
? 每个处理器都同样可以控制 I/O设备和系统
中的其他资源
? 系统中所有处理器共享主存储器
第六章 多处理器系统和处理器管理
6.2 对称式多处理器系统
? 多处理器操作系统涉及到的主要问题
? 多个进程或者线程同时并发的执行
? 线程和进程调度问题
? 同步问题
? 存储管理问题
? 可靠性和容错
第六章 多处理器系统和处理器管理
6.3 调度的层次和作业调度
? 处理器调度的层次
? 长期调度：也称作业调度、宏观调度、高级
调度，按照某种原则从磁盘的作业队列和较
互作业中选取作业进入主存；
? 中期调度：也称中级调度，决定哪些进程被
允许参与处理器竞争；
? 短期调度：也称处理器调度、微观调度、低
级调度，按照某种原则将处理器分配给就绪
进程或线程。
第六章 多处理器系统和处理器管理
6.3 调度的层次和作业调度
? 作业状态
? 提交状态：一个作业通过终端向计算机输入
时所处的状态；
? 后备状态：作业在磁盘上等待运行的状态；
? 运行状态：作业被作业调度程序选中而送入
主存，并为之建立进程投入运行；
? 完成运行：作业完成全部运行，释放所有占
用的资源，准备推出系统。
第六章 多处理器系统和处理器管理
6.3 调度的层次和作业调度
? 作业调度,按照某种调度算法从后备作业队列中挑
选作业进入主存中运行
? 作业控制块 JCB
? 作业调度程序的任务
? 按照某种调度算法从后备作业队列中挑选作业
? 为选中的作业分配主存和外设
? 为选中的作业建立相应的进程
? 构建和填写作业运行时所需的有关表格
? 作业结束时完成后续处理工作
第六章 多处理器系统和处理器管理
6.4 单处理器系统的处理器调度
? 处理机调度是对 CPU资源进行合理的分配
使用，以提高处理机利用率，并使各用
户公平地得到处理机资源。
? 本节的主要问题是处理机调度算法和调
度算法特征分析。
第六章 多处理器系统和处理器管理
6.4 单处理器系统的处理器调度
? 6.4.1 调度算法相关评价准则
? 6.4.2 处理器调度算法
第六章 多处理器系统和处理器管理
6.4.1 调度算法相关评价准则
? 选择调度算法时应考虑的问题
? 设计目的是选择算法的主要依据
? 资源利用率是评价性能优劣的重要指标
? 均衡地处理系统和用户的要求
? 高优先级进程应得到优先处理
? 可抢占和不可抢占策略
? 可抢占：可以将处理器从正在运行的进程抢走
? 不可抢占：只要进程在使用处理器，就不能剥夺
它对处理器的使用权
第六章 多处理器系统和处理器管理
6.4.1 调度算法相关评价准则
? 面向用户的调度性能准则
? 周转时间：作业从提交到完成（得到结果）
所经历的时间。包括：在收容队列中等待，
CPU上执行，就绪队列和阻塞队列中等待，
结果输出等待－－批处理系统
? 平均周转时间 T
? 平均带权周转时间（带权周转时间 W是 T(周
转 )/T(CPU执行 )〕
? 响应时间：用户输入一个请求（如击键）到
系统给出首次响应（如屏幕显示）的时间－
－分时系统
第六章 多处理器系统和处理器管理
6.4.1 调度算法相关评价准则
? 面向用户的调度性能准则
? 截止时间：开始截止时间和完成截止时间－
－实时系统，与周转时间有些相似。
? 公平性：不因作业或进程本身的特性而使上
述指标过分恶化。如长作业等待很长时间。
? 优先级：可以使关键任务达到更好的指标。
第六章 多处理器系统和处理器管理
6.4.1 调度算法相关评价准则
? 面向系统的调度性能准则
? 吞吐量：单位时间内所完成的作业数，跟作业本身
特性和调度算法都有关系－－批处理系统
? 平均周转时间不是吞吐量的倒数，因为并发执行的
作业在时间上可以重叠。如：在 2小时内完成 4个作
业，而每个周转时间是 1小时，则吞吐量是 2个作业
/小时
? 处理机利用率：－－大中型主机
? 各种设备的均衡利用：如 CPU繁忙的作业和 I/O繁忙
（指次数多，每次时间短）的作业搭配－－大中型
主机
第六章 多处理器系统和处理器管理
6.4.1 调度算法相关评价准则
? 算法本身的调度性能准则
? 容易实现
? 执行开销
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法
? 先进先出
? 优先级调度
? 时间片轮转
? 最短进程优先
? 最短剩余时间优先
? 最高响应比优先
? 多级反馈队列算法
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法（先进先出）
? 最简单的调度算法
? 按照作业提交或进程变为就绪状态的先
后次序，分派 CPU
? 当前作业或进程占用 CPU，直到执行完或
阻塞，才出让 CPU（非抢占方式）
? 在作业或进程唤醒后（如 I/O完成），并
不立即恢复执行，通常等到当前作业或
进程出让 CPU
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法（先进先出）
? 特点
? 比较有利于长作业，而不利于短作业。
? 有利于 CPU繁忙的作业，而不利于 I/O繁忙
的作业
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法（优先级调度）
? 按照优先级的大小调度，使高优先级进
程或线程得到优先的处理
? 优先级调度分为抢占式和非抢占式两种
? 抢占式：一旦有更高优先级的进程出现，当
前运行进程就必须让出处理器
? 非抢占式：进程一旦占用了处理器，就一直
使用，直到主动让出处理器
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法
（优先级调度）
? 静态优先级
? 创建进程时确定，直到进程终止前都不改变，
通常是一个整数。
? 依据,
? 进程类型（系统进程优先级较高）
? 对资源的需求（对 CPU和内存需求较少的进程，
优先级较高）
? 用户要求（紧迫程度和付费多少）
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法
（优先级调度）
? 动态优先级
? 在创建进程时赋予的优先级，在进程运行过
程中可以自动改变，以便获得更好的调度性
能。
? 依据,
? 在就绪队列中，等待时间延长则优先级提高，从
而使优先级较低的进程在等待足够的时间后，其
优先级提高到可被调度执行；
? 进程每执行一个时间片，就降低其优先级，从而
一个进程持续执行时，其优先级降低到出让 CPU。
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法
（时间片轮转算法）
? 主要用于处理器调度
? 将系统中所有的就绪进程按照 FCFS原则，排成
一个队列。
? 每次调度时将 CPU分派给队首进程，让其执行一
个时间片。时间片的长度从几个 ms到几百 ms。
? 在一个时间片结束时，发生时钟中断。
? 调度程序据此暂停当前进程的执行，将其送到就
绪队列的末尾，并通过上下文切换执行当前的队
首进程。
? 进程可以未使用完一个时间片，就出让 CPU（如
阻塞）。
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法
（时间片轮转算法）
? 时间片长度变化的影响
? 过长－ >退化为 FIFO算法，进程在一个时间片内都执
行完，响应时间长。
? 过短－ >用户的一次请求需要多个时间片才能处理完，
上下文切换次数增加，响应时间长。
? 对响应时间的要求,
? T(响应时间 )=N(进程数目 )*q(时间片 )
? 时间片长度的影响因素,
? 就绪进程的数目：数目越多，时间片越小（当响应时
间一定时）
? 系统的处理能力：应当使用户输入通常在一个时间片
内能处理完，否则使响应时间，平均周转时间和平均
带权周转时间延长。
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法
（最短进程优先）
? 又称短作业优先算法：选择所需运行时间最短的
作业或进程运行
? 优点,
? 比 FIFO改善平均周转时间和平均带权周转时间，缩短
作业的等待时间；
? 提高系统的吞吐量；
? 缺点,
? 对长作业非常不利，可能长时间得不到执行；
? 未能依据作业的紧迫程度来划分执行的优先级；
? 难以准确估计作业（进程）的执行时间，从而影响调
度性能。
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法
（ 最短剩余时间优先）
? 允许比当前进程剩余时间更短的进程来抢
占
? 优点
? 可以用于分时系统
? 保证及时响应用户要求
? 缺点
? 系统开销大
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法
（最高响应比优先）
? 响应比 R = (等待时间 + 要求执行时间 ) /
要求执行时间
? 是 FIFO和最短进程优先的折衷
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法
（多级反馈队列调度）
? 多级反馈队列算法是时间片轮转算法和优
先级算法的综合和发展。
? 优点,
? 为提高系统吞吐量和缩短平均周转时间而照
顾短进程
? 为获得较好的 I/O设备利用率和缩短响应时间
而照顾 I/O型进程
? 不必估计进程的执行时间，动态调节
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法
（ 多级反馈队列调度）
? 设置多个就绪队列，分别赋予不同的优先级，
如逐级降低，队列 1的优先级最高。
? 每个队列执行时间片的长度也不同，规定优先
级越低则时间片越长；
? 新进程进入内存后，先投入队列 1的末尾，按
FIFO算法调度；
? 若按队列 1一个时间片未能执行完，则降低投入
到队列 2的末尾，同样按 FIFO算法调度；如此下
去，降低到最后的队列，则按 "时间片轮转 "算法
调度直到完成。
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法
（ 多级反馈队列调度）
? 当第 1级进程就绪队列为空后，采取调度
第 2级，以此类推；
? 当比运行进程更高级别的队列中到来一个
新进程时，它将抢占运行进程的处理器，
被抢占的进程回到原队列末尾
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法
（ 多级反馈队列调度）
? 原则
? 为提高系统吞吐率和降低平均等待时间而照
顾短进程
? 为得到较好的输入输出设备利用率而照顾输
入输出型进程
? 按进程的运行情况动态的考虑进程性质
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法
（ 多级反馈队列调度）
? 对不同性质进程
? I/O型进程：让其进入最高优先级队列，以及时响应
I/O交互。通常执行一个小时间片，要求可处理完一
次 I/O请求的数据，然后转入到阻塞队列。
? 计算型进程：每次都执行完时间片，进入更低级队
列。最终采用最大时间片来执行，减少调度次数。
? I/O次数不多，而主要是 CPU处理的进程：在 I/O完
成后，放回优先 I/O请求时离开的队列，以免每次都
回到最高优先级队列后再逐次下降。
? 为适应一个进程在不同时间段的运行特点,I/O完成
时，提高优先级；时间片用完时，降低优先级；
第六章 多处理器系统和处理器管理
6.5 多处理器系统的处理器管理和调度
? 6.5.1 多处理器调度的概念
? 6.5.2 多处理器调度模式
? 6.5.3 实时调度
第六章 多处理器系统和处理器管理
6.5.1 多处理器调度的概念
? 多处理器系统的 3个重要特征
? 主存模型
? 一致的主存访问
? 非一致的主存访问
? 非远程主存访问
? 硬件的同步支持
? 软件体系结构
第六章 多处理器系统和处理器管理
6.5.1 多处理器调度的概念
? 硬件同步机制是实现多机系统的最必要
的基本条件，原因
? 多处理机的表格互斥问题突显
? 信号量机制不能正确工作,
? 唤醒丢失问题
? 巨群问题
第六章 多处理器系统和处理器管理
6.5.1 多处理器调度的概念
? 唤醒丢失问题
? 例如：线程 T1已经锁住了资源 R1，在另一个处理器
上运行的线程 T2要访问资源 R1，发现 R1已经被锁，
调用 Wait原语阻塞等待 R1；
? 如果在 T2调用 Wait原语的过程中,T1在另一处理器
上释放 R1，并唤醒所有阻塞于 R1的进程；
? 注意此时 T2还没有被放进 R1的阻塞队列，所以没有
被唤醒；（此时实际上 R1时可用的，但 T2不知道）
? 如果没有线程再访问 R1，就不会有线程来唤醒 T2，
它将永远阻塞下去。这个现象称为唤醒丢失。
第六章 多处理器系统和处理器管理
6.5.1 多处理器调度的概念
? 巨群问题
? 当一个线程释放一个资源，它释放所有等待
的线程；
? 被释放的线程可能在不同的处理器上同时被
调度，再次争夺该资源，可能又有一个线程
锁住资源，其它线程再次回到阻塞状态，引
起唤醒和环境切换的开销。这种现象称为巨
群问题。
? 因为反复争夺资源被阻塞，可能引起饥饿问
题（某些线程总是的不到资源）。
第六章 多处理器系统和处理器管理
6.5.2 多处理器调度模式
? 现代基于线程的多处理器调度模式
? 负载共享调度
? 专用处理器式调度
? 群调度
? 调度类和多处理模式调度
第六章 多处理器系统和处理器管理
6.5.2 多处理器调度模式
（负载共享调度）
? 是一种最简单的调度模式，整个系统维
持一个所有处理器共同使用的全局性可
运行线程队列，每个处理器空闲时都可
以到这个队列中按一定算法挑选运行线
程
第六章 多处理器系统和处理器管理
6.5.2 多处理器调度模式
（负载共享调度）
? 优点
? 系统负载可以平均分配到个处理器上；
? 不需要集中调度，每个处理器空闲时，可以
调度操作系统的线程调度子程序在其上运行；
? 常用调度算法
? 先进先出
? 最少线程数目优先调度
? 可抢占的最少线程数目优先调度
第六章 多处理器系统和处理器管理
6.5.2 多处理器调度模式
（负载共享调度）
? 缺点
? 全局就绪线程队列被所有处理器互斥访问，
成为瓶颈；
? 被抢占的先程再次被调度时，不一定能回到
原来的处理器上执行；
? 同一进程的所有线程不可能同时被处理，不
满足这些线程之间交互和协调的要求。
第六章 多处理器系统和处理器管理
6.5.2 多处理器调度模式
（专用处理器式调度）
? 为每个线程分配一个专门的处理器使用，直到
线程运行完成。
? 适用于系统中有大量处理器的情况，处理器不
是关键资源，更注重系统的吞吐量。
? 优点
? 调度开销小
? 缺点
? 处理器利用率低
第六章 多处理器系统和处理器管理
6.5.2 多处理器调度模式
（群调度）
? 每个应用的线程集合分配给一个处理器集合；
? 每个处理器同一时刻只属于一个处理器集合，
处理器集合可以动态改变；
? 优点
? 通常这样的一组线程在应用逻辑上相互合作，成组
调度提高了这些线程的执行并行度，有利于减少阻
塞和加快推进速度，最终提高系统吞吐量。
? 每次调度可以完成多个线程的分派，在系统内线程
总数相同时能够减少调度次数，从而减少调度算法
的开销
第六章 多处理器系统和处理器管理
6.5.2 多处理器调度模式
（调度类和多模式调度）
? 调度类：属于同一类的进程具有相同的
调度策略，这个类称为调度类
? 分时类
? 实时类
? 由于不同的调度类的调度策略不同，同
一系统中存在多种调度策略，称为多模
式调度
第六章 多处理器系统和处理器管理
6.5.3 实时调度
? 由于网络和多媒体技术的发展，计算机
系统常常要处理实时信息，这就需要调
度算法支持实时进程，及时响应外部事
件。
第六章 多处理器系统和处理器管理
6.5.3 实时调度
? 特点
? 内核可抢先性。
? 延迟时间上限（分配延迟、响应时间、中断
中断处理时间）
? 快速上下文切换：相应地采用较小的调度单
位（如线程）。
? 基线驱动调度。系统必须在基线时间要求期
限内响应事件，如就绪时间、启动或完成截
止时间、处理时间、资源要求、绝对或相对
优先级（硬实时或软实时）。
第六章 多处理器系统和处理器管理
课后作业
? Page 136
? 6.6
? 6.9
? 上交时间：下周
第 6章 多处理器系统和处理器管理
? 6.1 多处理器系统
? 6.2 对称式多处理器系统
? 6.3 调度的层次和作业调度
? 6.4 单处理器系统的处理器调度
? 6.5 多处理器系统的处理器管理和调度
第六章 多处理器系统和处理器管理
6.1 多处理器系统
? 6.1.1 多处理器系统的优点
? 6.1.2 多处理器系统并行性的提高
? 6.1.3 多处理器的硬件组织（省略）
? 6.1.4 多处理器系统分类
? 6.1.5 主从式处理器系统
第六章 多处理器系统和处理器管理
6.1.1 多处理器系统的优点
? 可靠性高
? 高度并行性
? 增强计算能力，而不显著增加费用
? 可以灵活的扩充处理器数目
第六章 多处理器系统和处理器管理
6.1.2 多处理器系统并行性的提高
? 人工检测
? 由程序员发现程序中的并行性，编写并行程
序；
? 自动检测
? 利用编译程序、操作系统和硬件分析和检测
算法内部的并行性（隐性并行性）；
? 循环分配
? 树高降低
?, 不等待, 规则
第六章 多处理器系统和处理器管理
6.1.4 多处理器系统分类
? 从处理器之间的通信方式划分
多处理器系统
共享存储器
（紧密耦合）
分布式存储器
或分布式计算机系统
（松散耦合）
主从式
多处理器系统
对称式
多处理器系统
第六章 多处理器系统和处理器管理
6.1.5 主从式处理器系统
? 也称非对称式处理器系统，指定一个处
理器作为主处理器，其它处理器都是从
处理器。
? 只有主处理器能运行操作系统，从处理
器只能运行用户程序。
第六章 多处理器系统和处理器管理
6.1.5 主从式处理器系统
? 优点
? 只有一个处理器可以运行操作系统程序，简
化了表格互斥问题
? 操作系统代码不需要是可重入的
? 缺点
? 主处理器负载过重
? 可靠性差，完全依赖于主处理器
? 从处理器利用率不高
第六章 多处理器系统和处理器管理
6.2 对称式多处理器系统
(SMP:Symmetric MultiProcessor)
? 系统中的各个处理器地位平等，没有主
从之分
? 每个处理器都可以运行操作系统和内核程序
处理中断、调度进程
? 每个处理器都同样可以控制 I/O设备和系统
中的其他资源
? 系统中所有处理器共享主存储器
第六章 多处理器系统和处理器管理
6.2 对称式多处理器系统
? 多处理器操作系统涉及到的主要问题
? 多个进程或者线程同时并发的执行
? 线程和进程调度问题
? 同步问题
? 存储管理问题
? 可靠性和容错
第六章 多处理器系统和处理器管理
6.3 调度的层次和作业调度
? 处理器调度的层次
? 长期调度：也称作业调度、宏观调度、高级
调度，按照某种原则从磁盘的作业队列和较
互作业中选取作业进入主存；
? 中期调度：也称中级调度，决定哪些进程被
允许参与处理器竞争；
? 短期调度：也称处理器调度、微观调度、低
级调度，按照某种原则将处理器分配给就绪
进程或线程。
第六章 多处理器系统和处理器管理
6.3 调度的层次和作业调度
? 作业状态
? 提交状态：一个作业通过终端向计算机输入
时所处的状态；
? 后备状态：作业在磁盘上等待运行的状态；
? 运行状态：作业被作业调度程序选中而送入
主存，并为之建立进程投入运行；
? 完成运行：作业完成全部运行，释放所有占
用的资源，准备推出系统。
第六章 多处理器系统和处理器管理
6.3 调度的层次和作业调度
? 作业调度,按照某种调度算法从后备作业队列中挑
选作业进入主存中运行
? 作业控制块 JCB
? 作业调度程序的任务
? 按照某种调度算法从后备作业队列中挑选作业
? 为选中的作业分配主存和外设
? 为选中的作业建立相应的进程
? 构建和填写作业运行时所需的有关表格
? 作业结束时完成后续处理工作
第六章 多处理器系统和处理器管理
6.4 单处理器系统的处理器调度
? 处理机调度是对 CPU资源进行合理的分配
使用，以提高处理机利用率，并使各用
户公平地得到处理机资源。
? 本节的主要问题是处理机调度算法和调
度算法特征分析。
第六章 多处理器系统和处理器管理
6.4 单处理器系统的处理器调度
? 6.4.1 调度算法相关评价准则
? 6.4.2 处理器调度算法
第六章 多处理器系统和处理器管理
6.4.1 调度算法相关评价准则
? 选择调度算法时应考虑的问题
? 设计目的是选择算法的主要依据
? 资源利用率是评价性能优劣的重要指标
? 均衡地处理系统和用户的要求
? 高优先级进程应得到优先处理
? 可抢占和不可抢占策略
? 可抢占：可以将处理器从正在运行的进程抢走
? 不可抢占：只要进程在使用处理器，就不能剥夺
它对处理器的使用权
第六章 多处理器系统和处理器管理
6.4.1 调度算法相关评价准则
? 面向用户的调度性能准则
? 周转时间：作业从提交到完成（得到结果）
所经历的时间。包括：在收容队列中等待，
CPU上执行，就绪队列和阻塞队列中等待，
结果输出等待－－批处理系统
? 平均周转时间 T
? 平均带权周转时间（带权周转时间 W是 T(周
转 )/T(CPU执行 )〕
? 响应时间：用户输入一个请求（如击键）到
系统给出首次响应（如屏幕显示）的时间－
－分时系统
第六章 多处理器系统和处理器管理
6.4.1 调度算法相关评价准则
? 面向用户的调度性能准则
? 截止时间：开始截止时间和完成截止时间－
－实时系统，与周转时间有些相似。
? 公平性：不因作业或进程本身的特性而使上
述指标过分恶化。如长作业等待很长时间。
? 优先级：可以使关键任务达到更好的指标。
第六章 多处理器系统和处理器管理
6.4.1 调度算法相关评价准则
? 面向系统的调度性能准则
? 吞吐量：单位时间内所完成的作业数，跟作业本身
特性和调度算法都有关系－－批处理系统
? 平均周转时间不是吞吐量的倒数，因为并发执行的
作业在时间上可以重叠。如：在 2小时内完成 4个作
业，而每个周转时间是 1小时，则吞吐量是 2个作业
/小时
? 处理机利用率：－－大中型主机
? 各种设备的均衡利用：如 CPU繁忙的作业和 I/O繁忙
（指次数多，每次时间短）的作业搭配－－大中型
主机
第六章 多处理器系统和处理器管理
6.4.1 调度算法相关评价准则
? 算法本身的调度性能准则
? 容易实现
? 执行开销
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法
? 先进先出
? 优先级调度
? 时间片轮转
? 最短进程优先
? 最短剩余时间优先
? 最高响应比优先
? 多级反馈队列算法
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法（先进先出）
? 最简单的调度算法
? 按照作业提交或进程变为就绪状态的先
后次序，分派 CPU
? 当前作业或进程占用 CPU，直到执行完或
阻塞，才出让 CPU（非抢占方式）
? 在作业或进程唤醒后（如 I/O完成），并
不立即恢复执行，通常等到当前作业或
进程出让 CPU
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法（先进先出）
? 特点
? 比较有利于长作业，而不利于短作业。
? 有利于 CPU繁忙的作业，而不利于 I/O繁忙
的作业
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法（优先级调度）
? 按照优先级的大小调度，使高优先级进
程或线程得到优先的处理
? 优先级调度分为抢占式和非抢占式两种
? 抢占式：一旦有更高优先级的进程出现，当
前运行进程就必须让出处理器
? 非抢占式：进程一旦占用了处理器，就一直
使用，直到主动让出处理器
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法
（优先级调度）
? 静态优先级
? 创建进程时确定，直到进程终止前都不改变，
通常是一个整数。
? 依据,
? 进程类型（系统进程优先级较高）
? 对资源的需求（对 CPU和内存需求较少的进程，
优先级较高）
? 用户要求（紧迫程度和付费多少）
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法
（优先级调度）
? 动态优先级
? 在创建进程时赋予的优先级，在进程运行过
程中可以自动改变，以便获得更好的调度性
能。
? 依据,
? 在就绪队列中，等待时间延长则优先级提高，从
而使优先级较低的进程在等待足够的时间后，其
优先级提高到可被调度执行；
? 进程每执行一个时间片，就降低其优先级，从而
一个进程持续执行时，其优先级降低到出让 CPU。
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法
（时间片轮转算法）
? 主要用于处理器调度
? 将系统中所有的就绪进程按照 FCFS原则，排成
一个队列。
? 每次调度时将 CPU分派给队首进程，让其执行一
个时间片。时间片的长度从几个 ms到几百 ms。
? 在一个时间片结束时，发生时钟中断。
? 调度程序据此暂停当前进程的执行，将其送到就
绪队列的末尾，并通过上下文切换执行当前的队
首进程。
? 进程可以未使用完一个时间片，就出让 CPU（如
阻塞）。
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法
（时间片轮转算法）
? 时间片长度变化的影响
? 过长－ >退化为 FIFO算法，进程在一个时间片内都执
行完，响应时间长。
? 过短－ >用户的一次请求需要多个时间片才能处理完，
上下文切换次数增加，响应时间长。
? 对响应时间的要求,
? T(响应时间 )=N(进程数目 )*q(时间片 )
? 时间片长度的影响因素,
? 就绪进程的数目：数目越多，时间片越小（当响应时
间一定时）
? 系统的处理能力：应当使用户输入通常在一个时间片
内能处理完，否则使响应时间，平均周转时间和平均
带权周转时间延长。
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法
（最短进程优先）
? 又称短作业优先算法：选择所需运行时间最短的
作业或进程运行
? 优点,
? 比 FIFO改善平均周转时间和平均带权周转时间，缩短
作业的等待时间；
? 提高系统的吞吐量；
? 缺点,
? 对长作业非常不利，可能长时间得不到执行；
? 未能依据作业的紧迫程度来划分执行的优先级；
? 难以准确估计作业（进程）的执行时间，从而影响调
度性能。
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法
（ 最短剩余时间优先）
? 允许比当前进程剩余时间更短的进程来抢
占
? 优点
? 可以用于分时系统
? 保证及时响应用户要求
? 缺点
? 系统开销大
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法
（最高响应比优先）
? 响应比 R = (等待时间 + 要求执行时间 ) /
要求执行时间
? 是 FIFO和最短进程优先的折衷
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法
（多级反馈队列调度）
? 多级反馈队列算法是时间片轮转算法和优
先级算法的综合和发展。
? 优点,
? 为提高系统吞吐量和缩短平均周转时间而照
顾短进程
? 为获得较好的 I/O设备利用率和缩短响应时间
而照顾 I/O型进程
? 不必估计进程的执行时间，动态调节
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法
（ 多级反馈队列调度）
? 设置多个就绪队列，分别赋予不同的优先级，
如逐级降低，队列 1的优先级最高。
? 每个队列执行时间片的长度也不同，规定优先
级越低则时间片越长；
? 新进程进入内存后，先投入队列 1的末尾，按
FIFO算法调度；
? 若按队列 1一个时间片未能执行完，则降低投入
到队列 2的末尾，同样按 FIFO算法调度；如此下
去，降低到最后的队列，则按 "时间片轮转 "算法
调度直到完成。
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法
（ 多级反馈队列调度）
? 当第 1级进程就绪队列为空后，采取调度
第 2级，以此类推；
? 当比运行进程更高级别的队列中到来一个
新进程时，它将抢占运行进程的处理器，
被抢占的进程回到原队列末尾
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法
（ 多级反馈队列调度）
? 原则
? 为提高系统吞吐率和降低平均等待时间而照
顾短进程
? 为得到较好的输入输出设备利用率而照顾输
入输出型进程
? 按进程的运行情况动态的考虑进程性质
第六章 多处理器系统和处理器管理
6.4.2 处理器调度算法
（ 多级反馈队列调度）
? 对不同性质进程
? I/O型进程：让其进入最高优先级队列，以及时响应
I/O交互。通常执行一个小时间片，要求可处理完一
次 I/O请求的数据，然后转入到阻塞队列。
? 计算型进程：每次都执行完时间片，进入更低级队
列。最终采用最大时间片来执行，减少调度次数。
? I/O次数不多，而主要是 CPU处理的进程：在 I/O完
成后，放回优先 I/O请求时离开的队列，以免每次都
回到最高优先级队列后再逐次下降。
? 为适应一个进程在不同时间段的运行特点,I/O完成
时，提高优先级；时间片用完时，降低优先级；
第六章 多处理器系统和处理器管理
6.5 多处理器系统的处理器管理和调度
? 6.5.1 多处理器调度的概念
? 6.5.2 多处理器调度模式
? 6.5.3 实时调度
第六章 多处理器系统和处理器管理
6.5.1 多处理器调度的概念
? 多处理器系统的 3个重要特征
? 主存模型
? 一致的主存访问
? 非一致的主存访问
? 非远程主存访问
? 硬件的同步支持
? 软件体系结构
第六章 多处理器系统和处理器管理
6.5.1 多处理器调度的概念
? 硬件同步机制是实现多机系统的最必要
的基本条件，原因
? 多处理机的表格互斥问题突显
? 信号量机制不能正确工作,
? 唤醒丢失问题
? 巨群问题
第六章 多处理器系统和处理器管理
6.5.1 多处理器调度的概念
? 唤醒丢失问题
? 例如：线程 T1已经锁住了资源 R1，在另一个处理器
上运行的线程 T2要访问资源 R1，发现 R1已经被锁，
调用 Wait原语阻塞等待 R1；
? 如果在 T2调用 Wait原语的过程中,T1在另一处理器
上释放 R1，并唤醒所有阻塞于 R1的进程；
? 注意此时 T2还没有被放进 R1的阻塞队列，所以没有
被唤醒；（此时实际上 R1时可用的，但 T2不知道）
? 如果没有线程再访问 R1，就不会有线程来唤醒 T2，
它将永远阻塞下去。这个现象称为唤醒丢失。
第六章 多处理器系统和处理器管理
6.5.1 多处理器调度的概念
? 巨群问题
? 当一个线程释放一个资源，它释放所有等待
的线程；
? 被释放的线程可能在不同的处理器上同时被
调度，再次争夺该资源，可能又有一个线程
锁住资源，其它线程再次回到阻塞状态，引
起唤醒和环境切换的开销。这种现象称为巨
群问题。
? 因为反复争夺资源被阻塞，可能引起饥饿问
题（某些线程总是的不到资源）。
第六章 多处理器系统和处理器管理
6.5.2 多处理器调度模式
? 现代基于线程的多处理器调度模式
? 负载共享调度
? 专用处理器式调度
? 群调度
? 调度类和多处理模式调度
第六章 多处理器系统和处理器管理
6.5.2 多处理器调度模式
（负载共享调度）
? 是一种最简单的调度模式，整个系统维
持一个所有处理器共同使用的全局性可
运行线程队列，每个处理器空闲时都可
以到这个队列中按一定算法挑选运行线
程
第六章 多处理器系统和处理器管理
6.5.2 多处理器调度模式
（负载共享调度）
? 优点
? 系统负载可以平均分配到个处理器上；
? 不需要集中调度，每个处理器空闲时，可以
调度操作系统的线程调度子程序在其上运行；
? 常用调度算法
? 先进先出
? 最少线程数目优先调度
? 可抢占的最少线程数目优先调度
第六章 多处理器系统和处理器管理
6.5.2 多处理器调度模式
（负载共享调度）
? 缺点
? 全局就绪线程队列被所有处理器互斥访问，
成为瓶颈；
? 被抢占的先程再次被调度时，不一定能回到
原来的处理器上执行；
? 同一进程的所有线程不可能同时被处理，不
满足这些线程之间交互和协调的要求。
第六章 多处理器系统和处理器管理
6.5.2 多处理器调度模式
（专用处理器式调度）
? 为每个线程分配一个专门的处理器使用，直到
线程运行完成。
? 适用于系统中有大量处理器的情况，处理器不
是关键资源，更注重系统的吞吐量。
? 优点
? 调度开销小
? 缺点
? 处理器利用率低
第六章 多处理器系统和处理器管理
6.5.2 多处理器调度模式
（群调度）
? 每个应用的线程集合分配给一个处理器集合；
? 每个处理器同一时刻只属于一个处理器集合，
处理器集合可以动态改变；
? 优点
? 通常这样的一组线程在应用逻辑上相互合作，成组
调度提高了这些线程的执行并行度，有利于减少阻
塞和加快推进速度，最终提高系统吞吐量。
? 每次调度可以完成多个线程的分派，在系统内线程
总数相同时能够减少调度次数，从而减少调度算法
的开销
第六章 多处理器系统和处理器管理
6.5.2 多处理器调度模式
（调度类和多模式调度）
? 调度类：属于同一类的进程具有相同的
调度策略，这个类称为调度类
? 分时类
? 实时类
? 由于不同的调度类的调度策略不同，同
一系统中存在多种调度策略，称为多模
式调度
第六章 多处理器系统和处理器管理
6.5.3 实时调度
? 由于网络和多媒体技术的发展，计算机
系统常常要处理实时信息，这就需要调
度算法支持实时进程，及时响应外部事
件。
第六章 多处理器系统和处理器管理
6.5.3 实时调度
? 特点
? 内核可抢先性。
? 延迟时间上限（分配延迟、响应时间、中断
中断处理时间）
? 快速上下文切换：相应地采用较小的调度单
位（如线程）。
? 基线驱动调度。系统必须在基线时间要求期
限内响应事件，如就绪时间、启动或完成截
止时间、处理时间、资源要求、绝对或相对
优先级（硬实时或软实时）。
第六章 多处理器系统和处理器管理
课后作业
? Page 136
? 6.6
? 6.9
? 上交时间：下周
