第 6章 多处理 器 系统和处理器管理
?调度的层次和作业调度
?单处理器系统的处理器调度
?多处理器系统
?对称多处理器系统
?多处理器系统的处理器管理和调度
6.1 调度的层次和作业调度
一、调度层次
1、作业运行
2、处理机调度
3、处理机长期，短期调度关系
1、作业运行
程
序
员
操作
员
输入
机
磁 盘
作业
内存
打
印
结
束
A B C D
作业状态
? 提交状态（ A）,用户将作业交给 机房，输
入输入机。
? 后备状态（ B）,作业信息输入输入机，存
放在磁盘的某些盘区，等待操作系统接受。
? 运行状态（ C）,作业被调度送入内存运行。
? 完成状态（ D）,作业全部完成，释放资源，
退出系统。
2、调度层次
处理器调度分为三级,
? 长期调度（作业调度）
? 中期调度
? 短期调度（进程调度）
长期调度
? 按某种原则挑选作业投入运行
? 为作业创建进程
? 为选中作业分配资源
中期调度
决定哪些作业允许参于竞争处理机资源。
作用：起到短期调整系统负荷，以平顺系统。
方式：“挂起”，“解挂”。
短期调度
按某种原则将处理机分配给就绪进程。
进程调度属操作系统内核，执行频率很高。
3、处理机长期，短期调度关系
提交 后备
阻塞
就绪 运行
完成
作业
注册
作业
调度
进程
调度
作业
终止
运行
二、作业调度
1、作业调度的职能
2、作业控制块
3、调度性能的衡量
1、作业调度的职能
? 记录已进入系统的作业情况 JCB
? 调度算法：按照某种调度算法从后备状态挑选作
业运行。
? 运行准备：为选中作业创建进程，分配主存和外
设。
? 结束善后处理：收回资源，输出必要信息。
作业进入后备状态建立 作业退出系统时撤消
2、作业控制块
? 作业存在唯一标志
? 作业调度的依据
? 记录作业的有关信息，反映作业运行情况
? 内容
进入系统时建立 退出系统时撤消
作业名
资源要求
资源使用情况
类型说明
状态
3、调度性能的衡量
平均周转时间,
作业 k的周转时间 Tk = 完成时间 - 提交时间
= 等待时间 + 运行时间
平均周转时间 T = ?Tk / 作业数
6.2 单处理器系统的处理器调度
处理器调度的主要功能：按一定的
算法，动态地把处理机分配给就绪
队列中的某个进程
1,选择调度算法时应考虑的问题
? 设计目标
? 资源利用率
? 均衡地处理系统和用户要求
? 优先级
? 可抢占和不可抢占
2,调度算法
? 先进先服务调度算法
? 最短作业优先调度算法
? 时间片轮转算法
? 优先级调度算法
? 最短剩余时间优先调度算法
? 最高响应比优先
? 多级反馈队列调度算法
(1) 先进先出调度算法
其原则按照作业到达系统或进程进入就绪
队列先后次序来选择。
FIFO是一种非抢占算法。
例题
进程 到达时间 服务时间 优先数
1 0 3 2
2 2 6 5
3 4 4 3
4 6 5 6
5 8 2 1
作业 1 作业 2 作业 3 作业 4 作业 5
0 3 9 13 18 20
平均周转时间
T=1/5（ 3+7+9+12+12） =8.60
（ 2）短作业优先调度算法
根据 JCB估算运算时间，选取最短作业为
调度对象
短作业优先调度是非抢占算法。
缺点：会使长作业饥饿。
作业 1 作业 2 作业 5 作业 3 作业 4
0 3 9 11 15 20
T=1/5（ 3+7+11+14+3） =7.60
（ 3）时间片轮转调度算法
把 CPU的时间分割成时间片，处于就绪
状态的进程轮流获得时间片。
时间片轮转调度算法是抢占算法。
其调度算法的性能取决于时间片 Q。
Q=4（ 时间片为 4）
作业 1 作业 2 作业 3 作业 4 作业 5 作业 2 作业 4
0 3 7 11 15 17 19 20
T=1/5（ 3+17+7+14+9） =10.00
（ 4）优先级调度算法
选择优先数高的进程和作业作为调度对象。
? 按抢占与否优先数可分,
非抢占的优先调度算法
可抢占的优先调度算法
? 按静态，动态优先数可分,
静态优先数
动态优先数
非抢占的优先调度
作业 1 作业 2 作业 4 作业 3 作业 5
0 3 9 14 18 20
T=1/5（ 3+7+14+8+12） =8.8
可抢占的优先调度
作业 1 作业 2 作业 4 作业 2 作业 3 作业 1 作业 5
0 2 6 11 13 17 18 20
T=1/5（ 18+11+13+5+12） =11.8
（ 5）最短剩余时间优先调度算法
? 基本思想：让从运行到完成所需时间最
短的作业优先得到处理。
? 最短剩余时间：从作业当前运行到完成
所需时间。
? 最短剩余时间优先调度是抢占算法。
? 用于分时系统
? 其轮转时间最优
作业 1 作业 2 作业 3 作业 5 作业 2 作业 4
0 3 4 8 10 15 20
T=1/5（ 3+13+4+14+2） =7.20
（ 6）最高响应比优先
响应比 =
等待时间 +服务时间
服务时间
最高响应比是 FIFO和短作业优先的折中。
最高响应比是一种非抢占算法。
作业 1 作业 2 作业 3 作业 5 作业 4
0 3 9 13 15 20
T=1/5（ 3+7+9=9+12） =8.00
（ 8）多级反馈队列调度算法
? 系统中有多个就绪队列
? 各级就绪队列具有不同的时间片
? 各级队列均按 FIFO原则排队
? 调度方法,首先调度优先级高的进程，
当优先级高的进程为空，才调度下一级。
例题
进程 到达时间 服务时间 优先数
1 0 3 2
2 2 6 5
3 4 4 3
4 6 5 6
5 8 2 1
作业名 到达时刻 完成时刻 运行时间
J1 0 2 2 J2 2 3 1
? J1 4 3 J3 4 5 1
J2 6 2 J4 6 7 1
J3 8 2 J5 8 9 1
J4 10 2 ? J5 11 2
J2 12 3 J3 13 3
J4 14 3 J2 15 4
? J3 16 4 J4 17 4
J2 18 5 ? J4 19 5
? J2 20 6
Q=1（ 每级反馈队列每一级时间片为 1）
1 1 2 1 3 2 4 3 5 4 5 2 3 4 2 3 4 2 4 2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
T=1/5（ 4+18+12+13+3） =10.00
Q=2**N（ 每级反馈队列每一级时间片以 2幂次方递增）
1 1 2 1 3 2 2 4 5 3 3 4 4 5 2 2 2 3 4 4
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
T=1/5（ 4+15+14+14+6） =10.06
?调度的层次和作业调度
?单处理器系统的处理器调度
?多处理器系统
?对称多处理器系统
?多处理器系统的处理器管理和调度
6.1 调度的层次和作业调度
一、调度层次
1、作业运行
2、处理机调度
3、处理机长期，短期调度关系
1、作业运行
程
序
员
操作
员
输入
机
磁 盘
作业
内存
打
印
结
束
A B C D
作业状态
? 提交状态（ A）,用户将作业交给 机房，输
入输入机。
? 后备状态（ B）,作业信息输入输入机，存
放在磁盘的某些盘区，等待操作系统接受。
? 运行状态（ C）,作业被调度送入内存运行。
? 完成状态（ D）,作业全部完成，释放资源，
退出系统。
2、调度层次
处理器调度分为三级,
? 长期调度（作业调度）
? 中期调度
? 短期调度（进程调度）
长期调度
? 按某种原则挑选作业投入运行
? 为作业创建进程
? 为选中作业分配资源
中期调度
决定哪些作业允许参于竞争处理机资源。
作用：起到短期调整系统负荷，以平顺系统。
方式：“挂起”，“解挂”。
短期调度
按某种原则将处理机分配给就绪进程。
进程调度属操作系统内核，执行频率很高。
3、处理机长期，短期调度关系
提交 后备
阻塞
就绪 运行
完成
作业
注册
作业
调度
进程
调度
作业
终止
运行
二、作业调度
1、作业调度的职能
2、作业控制块
3、调度性能的衡量
1、作业调度的职能
? 记录已进入系统的作业情况 JCB
? 调度算法：按照某种调度算法从后备状态挑选作
业运行。
? 运行准备：为选中作业创建进程，分配主存和外
设。
? 结束善后处理：收回资源，输出必要信息。
作业进入后备状态建立 作业退出系统时撤消
2、作业控制块
? 作业存在唯一标志
? 作业调度的依据
? 记录作业的有关信息，反映作业运行情况
? 内容
进入系统时建立 退出系统时撤消
作业名
资源要求
资源使用情况
类型说明
状态
3、调度性能的衡量
平均周转时间,
作业 k的周转时间 Tk = 完成时间 - 提交时间
= 等待时间 + 运行时间
平均周转时间 T = ?Tk / 作业数
6.2 单处理器系统的处理器调度
处理器调度的主要功能：按一定的
算法，动态地把处理机分配给就绪
队列中的某个进程
1,选择调度算法时应考虑的问题
? 设计目标
? 资源利用率
? 均衡地处理系统和用户要求
? 优先级
? 可抢占和不可抢占
2,调度算法
? 先进先服务调度算法
? 最短作业优先调度算法
? 时间片轮转算法
? 优先级调度算法
? 最短剩余时间优先调度算法
? 最高响应比优先
? 多级反馈队列调度算法
(1) 先进先出调度算法
其原则按照作业到达系统或进程进入就绪
队列先后次序来选择。
FIFO是一种非抢占算法。
例题
进程 到达时间 服务时间 优先数
1 0 3 2
2 2 6 5
3 4 4 3
4 6 5 6
5 8 2 1
作业 1 作业 2 作业 3 作业 4 作业 5
0 3 9 13 18 20
平均周转时间
T=1/5（ 3+7+9+12+12） =8.60
（ 2）短作业优先调度算法
根据 JCB估算运算时间，选取最短作业为
调度对象
短作业优先调度是非抢占算法。
缺点：会使长作业饥饿。
作业 1 作业 2 作业 5 作业 3 作业 4
0 3 9 11 15 20
T=1/5（ 3+7+11+14+3） =7.60
（ 3）时间片轮转调度算法
把 CPU的时间分割成时间片，处于就绪
状态的进程轮流获得时间片。
时间片轮转调度算法是抢占算法。
其调度算法的性能取决于时间片 Q。
Q=4（ 时间片为 4）
作业 1 作业 2 作业 3 作业 4 作业 5 作业 2 作业 4
0 3 7 11 15 17 19 20
T=1/5（ 3+17+7+14+9） =10.00
（ 4）优先级调度算法
选择优先数高的进程和作业作为调度对象。
? 按抢占与否优先数可分,
非抢占的优先调度算法
可抢占的优先调度算法
? 按静态，动态优先数可分,
静态优先数
动态优先数
非抢占的优先调度
作业 1 作业 2 作业 4 作业 3 作业 5
0 3 9 14 18 20
T=1/5（ 3+7+14+8+12） =8.8
可抢占的优先调度
作业 1 作业 2 作业 4 作业 2 作业 3 作业 1 作业 5
0 2 6 11 13 17 18 20
T=1/5（ 18+11+13+5+12） =11.8
（ 5）最短剩余时间优先调度算法
? 基本思想：让从运行到完成所需时间最
短的作业优先得到处理。
? 最短剩余时间：从作业当前运行到完成
所需时间。
? 最短剩余时间优先调度是抢占算法。
? 用于分时系统
? 其轮转时间最优
作业 1 作业 2 作业 3 作业 5 作业 2 作业 4
0 3 4 8 10 15 20
T=1/5（ 3+13+4+14+2） =7.20
（ 6）最高响应比优先
响应比 =
等待时间 +服务时间
服务时间
最高响应比是 FIFO和短作业优先的折中。
最高响应比是一种非抢占算法。
作业 1 作业 2 作业 3 作业 5 作业 4
0 3 9 13 15 20
T=1/5（ 3+7+9=9+12） =8.00
（ 8）多级反馈队列调度算法
? 系统中有多个就绪队列
? 各级就绪队列具有不同的时间片
? 各级队列均按 FIFO原则排队
? 调度方法,首先调度优先级高的进程，
当优先级高的进程为空，才调度下一级。
例题
进程 到达时间 服务时间 优先数
1 0 3 2
2 2 6 5
3 4 4 3
4 6 5 6
5 8 2 1
作业名 到达时刻 完成时刻 运行时间
J1 0 2 2 J2 2 3 1
? J1 4 3 J3 4 5 1
J2 6 2 J4 6 7 1
J3 8 2 J5 8 9 1
J4 10 2 ? J5 11 2
J2 12 3 J3 13 3
J4 14 3 J2 15 4
? J3 16 4 J4 17 4
J2 18 5 ? J4 19 5
? J2 20 6
Q=1（ 每级反馈队列每一级时间片为 1）
1 1 2 1 3 2 4 3 5 4 5 2 3 4 2 3 4 2 4 2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
T=1/5（ 4+18+12+13+3） =10.00
Q=2**N（ 每级反馈队列每一级时间片以 2幂次方递增）
1 1 2 1 3 2 2 4 5 3 3 4 4 5 2 2 2 3 4 4
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
T=1/5（ 4+15+14+14+6） =10.06
