Cha9 单处理器调度调度的类型长程调度 决定哪个进程进入系统中程调度 决定哪个进程回到内存短程调度 决定哪个进程获得 CPU
I/O调度 决定哪个进程使用 I/O设备调度和进程状态转换新建就绪 /挂起阻塞 /挂起就绪阻塞运行 退出长程 长程中程中程短程调度的层次新建 退出就绪阻塞运行就绪 /挂起阻塞 /挂起长程调度中程调度短程调度用于调度的排队图
CPU
交互用户批作业事件等待事件发生阻塞队列阻塞挂起就绪队列就绪挂起超时长程调度
系统可以创建一个 /多个新进程
– 一个作业终止时
– CPU利用率太低
接受哪个作业创建进程
– 先来先服务
– 系统性能相关指标
优先级
等待时间
I/O需求引起短期调度的事件
时钟中断
I/O中断
OS调用
信号
非抢占方式
抢占方式调度准则面向用户 面向系统与性能相关周转时间响应时间最后期限吞吐量
CPU使用率平衡资源其他 优先权可预测性 公平强制优先级优先级的使用
CPU
RQ0
RQ1
RQn
……
阻塞队列允许进入剥夺阻塞唤醒
RQ0> RQ1… > RQn
会导致饥饿调度策略
常用参数
w进程进入系统的时间
e进程执行的时间
s进程所需的总时间
决策模式非 剥夺－只能由进程主动释放 CPU
剥夺－ OS可以强制获得 CPU
各种调度策略的特点算法 选择函数 决策模式
FCFS先来先服务 Max(w) 非剥夺循环 常数 剥夺
SPN最短进程 Min(s) 非剥夺
SRT最短剩余时间 Min(s-e) 剥夺
HRRN最高相应比 Max[(w+s)/s] 非剥夺反馈 剥夺进程调度示例进程 到达时间 服务时间
A 0 3
B 2 6
C 4 4
D 6 5
E 8 2
FCFS
0 5 10 15 20
A
B
C
D
E
FCFS适合长进程
设备利用率低
一般和优先级策略结合标准化的周转时间进程到达时间服务时间开始时间结束时间周转时间标准化周转时间
W 0 1 0 1 1 1
X 1 100 1 101 100 1
Y 2 1 101 102 100 100
Z 3 100 102 202 199 1.99
标准化周转时间＝周转时间 /服务时间
FCFS适合长进程时间片大小的影响响应时间时间段时间段 >平均交互时间时间段 <平均交互时间其他进程运行虚拟循环调度
CPU
I/O队列 n
I/O队列 1
就绪队列辅助队列
……
循环 q=1
0 5 10 15 20
A
B
C
D
E
循环 q=4
0 5 10 15 20
A
B
C
D
E
最短进程优先
长进程会饿死
不适合分时系统和事务处理最短剩余时间
增加了剥夺机制的 SPN
需要记录过去的服务时间
响应时间快
对长进程不利最高响应比
响应比＝ (等待时间 +服务时间 )/服务时间
响应时间快
长短作业的平衡较好反馈调度
CPU
CPU
CPU
RQ0
RQ1
RQn
实时计算系统的正确性不仅取决于计算的逻辑结果，还依赖于产生结果的时间最后期限－必须开始或结束的时间硬实时任务与软实时任务实时调度的基本条件
提供必要的信息
– 就绪时间，开始 /完成截止时间，处理时间
– 资源要求，优先级
系统处理能力强
– Sum(处理时间 /周期 )<=1
采用抢占式调度机制
具有快速切换机制
– 快速响应外部中断
– 快速分派任务调度算法分类
非抢占式调度算法
– 轮转调度
– 优先调度
抢占式调度算法
– 基于时钟中断
– 立即抢占实时进程调度
P1 P2 …… Pn p
实时进程到达
P1 p
P1 p
剥夺点
P1 p
立即剥夺放在就绪队列头放在就绪队列尾常用实时调度算法－ EDF
最早截止时间优先 earliest deadline first
开始截止时间任务执行任务到达
1 3 4 2
1 3 4 2
1 2 3 4
抢占式或非抢占式调度常用实时调度算法－ LLF
最低松弛度优先 least lexity first
A1 A2 A3 A4 A5
B1 B2
A1
B1
A2
B1
A3
B2
A4
B2
20 40 60 80
A1-10
B1-25
A2=20
B1-15
A间隔 20处理 10
B间隔 50处理 25
10
30
40
45
55
70
80
A2-0
B1-15
A3-10
B1-5
A3-5
B2-30
A4=15
B2-20
多处理器系统的类型多处理器系统 multiprocessor system
紧密耦合 MPS和松散耦合 MPS
– 共享内存和 I/O设备
– 各有自己的内存和 I/O设备
对称 MPS和非对称 MPS
– 各处理器的功能结构相同
– 一个主处理器多个从处理器进程分配方式
对称 MPS中
– 静态分配方式
一个进程固定分配到某处理器
– 动态分配方式
一个进程可能被不同处理器执行
非对称 MPS中
– 主机执行系统程序
– 从机执行用户程序进程分配方式
A
B
Z
…
A
B
Z
…
静态分配方式
调度开销小
忙闲不均动态分配方式
负载分摊
进程切换开销处理器 进程队列进程分配方式
A
B
Z
…
非对称 MPS
系统简单
主机瓶颈进程调度方式
自调度方式
成组调度方式
专用处理器分配方式自调度方式
系统的公共就绪队列
可用单处理机环境的算法
算法移植容易
不会忙闲不均
瓶颈问题
低效性
线程切换频繁成组调度方式
面向所有进程平均分配处理器时间
面向所有线程平均分配处理器时间
减少线程切换
减少调度频率处理器 程序 A 程序 B
1 线程 1 线程 1
2 线程 2 空闲
3 线程 3 空闲
4 线程 4 空闲
1/2 1/2
4/5 1/5
线程数对加速比的影响
FFT
矩阵相乘线程数加速比
8
I/O调度 决定哪个进程使用 I/O设备调度和进程状态转换新建就绪 /挂起阻塞 /挂起就绪阻塞运行 退出长程 长程中程中程短程调度的层次新建 退出就绪阻塞运行就绪 /挂起阻塞 /挂起长程调度中程调度短程调度用于调度的排队图
CPU
交互用户批作业事件等待事件发生阻塞队列阻塞挂起就绪队列就绪挂起超时长程调度
系统可以创建一个 /多个新进程
– 一个作业终止时
– CPU利用率太低
接受哪个作业创建进程
– 先来先服务
– 系统性能相关指标
优先级
等待时间
I/O需求引起短期调度的事件
时钟中断
I/O中断
OS调用
信号
非抢占方式
抢占方式调度准则面向用户 面向系统与性能相关周转时间响应时间最后期限吞吐量
CPU使用率平衡资源其他 优先权可预测性 公平强制优先级优先级的使用
CPU
RQ0
RQ1
RQn
……
阻塞队列允许进入剥夺阻塞唤醒
RQ0> RQ1… > RQn
会导致饥饿调度策略
常用参数
w进程进入系统的时间
e进程执行的时间
s进程所需的总时间
决策模式非 剥夺－只能由进程主动释放 CPU
剥夺－ OS可以强制获得 CPU
各种调度策略的特点算法 选择函数 决策模式
FCFS先来先服务 Max(w) 非剥夺循环 常数 剥夺
SPN最短进程 Min(s) 非剥夺
SRT最短剩余时间 Min(s-e) 剥夺
HRRN最高相应比 Max[(w+s)/s] 非剥夺反馈 剥夺进程调度示例进程 到达时间 服务时间
A 0 3
B 2 6
C 4 4
D 6 5
E 8 2
FCFS
0 5 10 15 20
A
B
C
D
E
FCFS适合长进程
设备利用率低
一般和优先级策略结合标准化的周转时间进程到达时间服务时间开始时间结束时间周转时间标准化周转时间
W 0 1 0 1 1 1
X 1 100 1 101 100 1
Y 2 1 101 102 100 100
Z 3 100 102 202 199 1.99
标准化周转时间＝周转时间 /服务时间
FCFS适合长进程时间片大小的影响响应时间时间段时间段 >平均交互时间时间段 <平均交互时间其他进程运行虚拟循环调度
CPU
I/O队列 n
I/O队列 1
就绪队列辅助队列
……
循环 q=1
0 5 10 15 20
A
B
C
D
E
循环 q=4
0 5 10 15 20
A
B
C
D
E
最短进程优先
长进程会饿死
不适合分时系统和事务处理最短剩余时间
增加了剥夺机制的 SPN
需要记录过去的服务时间
响应时间快
对长进程不利最高响应比
响应比＝ (等待时间 +服务时间 )/服务时间
响应时间快
长短作业的平衡较好反馈调度
CPU
CPU
CPU
RQ0
RQ1
RQn
实时计算系统的正确性不仅取决于计算的逻辑结果，还依赖于产生结果的时间最后期限－必须开始或结束的时间硬实时任务与软实时任务实时调度的基本条件
提供必要的信息
– 就绪时间，开始 /完成截止时间，处理时间
– 资源要求，优先级
系统处理能力强
– Sum(处理时间 /周期 )<=1
采用抢占式调度机制
具有快速切换机制
– 快速响应外部中断
– 快速分派任务调度算法分类
非抢占式调度算法
– 轮转调度
– 优先调度
抢占式调度算法
– 基于时钟中断
– 立即抢占实时进程调度
P1 P2 …… Pn p
实时进程到达
P1 p
P1 p
剥夺点
P1 p
立即剥夺放在就绪队列头放在就绪队列尾常用实时调度算法－ EDF
最早截止时间优先 earliest deadline first
开始截止时间任务执行任务到达
1 3 4 2
1 3 4 2
1 2 3 4
抢占式或非抢占式调度常用实时调度算法－ LLF
最低松弛度优先 least lexity first
A1 A2 A3 A4 A5
B1 B2
A1
B1
A2
B1
A3
B2
A4
B2
20 40 60 80
A1-10
B1-25
A2=20
B1-15
A间隔 20处理 10
B间隔 50处理 25
10
30
40
45
55
70
80
A2-0
B1-15
A3-10
B1-5
A3-5
B2-30
A4=15
B2-20
多处理器系统的类型多处理器系统 multiprocessor system
紧密耦合 MPS和松散耦合 MPS
– 共享内存和 I/O设备
– 各有自己的内存和 I/O设备
对称 MPS和非对称 MPS
– 各处理器的功能结构相同
– 一个主处理器多个从处理器进程分配方式
对称 MPS中
– 静态分配方式
一个进程固定分配到某处理器
– 动态分配方式
一个进程可能被不同处理器执行
非对称 MPS中
– 主机执行系统程序
– 从机执行用户程序进程分配方式
A
B
Z
…
A
B
Z
…
静态分配方式
调度开销小
忙闲不均动态分配方式
负载分摊
进程切换开销处理器 进程队列进程分配方式
A
B
Z
…
非对称 MPS
系统简单
主机瓶颈进程调度方式
自调度方式
成组调度方式
专用处理器分配方式自调度方式
系统的公共就绪队列
可用单处理机环境的算法
算法移植容易
不会忙闲不均
瓶颈问题
低效性
线程切换频繁成组调度方式
面向所有进程平均分配处理器时间
面向所有线程平均分配处理器时间
减少线程切换
减少调度频率处理器 程序 A 程序 B
1 线程 1 线程 1
2 线程 2 空闲
3 线程 3 空闲
4 线程 4 空闲
1/2 1/2
4/5 1/5
线程数对加速比的影响
FFT
矩阵相乘线程数加速比
8
