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 Msx(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适合长进程循环 q=1
0 5 10 15 20
A
B
C
D
E
循环 q=4
0 5 10 15 20
A
B
C
D
E
时间片大小的影响响应时间时间段时间段 >平均交互时间时间段 <平均交互时间其他进程运行虚拟循环调度
CPU
I/O队列 n
I/O队列 1
就绪队列辅助队列
……
最短进程优先
长进程会饿死
不适合分时系统和事务处理最短剩余时间
增加了剥夺机制的 SPN
需要记录过去的服务时间
响应时间快
对长进程不利最高响应比
响应比＝ (等待时间 +服务时间 )/服务时间
响应时间快
长短作业的平衡较好反馈调度
CPU
CPU
CPU
RQ0
RQ1
RQn
实时计算系统的正确性不仅取决于计算的逻辑结果，还依赖于产生结果的时间最后期限－必须开始或结束的时间硬实时任务与软实时任务实时 OS的特点
可确定性
响应性
用户控制
可靠性
故障弱化运行实时调度的基本条件
提供必要的信息
– 就绪时间，开始 /完成截止时间，处理时间
– 资源要求，优先级
系统处理能力强
– 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
调度的分类
有关的状态和队列转换
调度的准则
不同的调度算法调度的类型长程调度 决定哪个进程进入系统中程调度 决定哪个进程回到内存短程调度 决定哪个进程获得 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 Msx(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适合长进程循环 q=1
0 5 10 15 20
A
B
C
D
E
循环 q=4
0 5 10 15 20
A
B
C
D
E
时间片大小的影响响应时间时间段时间段 >平均交互时间时间段 <平均交互时间其他进程运行虚拟循环调度
CPU
I/O队列 n
I/O队列 1
就绪队列辅助队列
……
最短进程优先
长进程会饿死
不适合分时系统和事务处理最短剩余时间
增加了剥夺机制的 SPN
需要记录过去的服务时间
响应时间快
对长进程不利最高响应比
响应比＝ (等待时间 +服务时间 )/服务时间
响应时间快
长短作业的平衡较好反馈调度
CPU
CPU
CPU
RQ0
RQ1
RQn
实时计算系统的正确性不仅取决于计算的逻辑结果，还依赖于产生结果的时间最后期限－必须开始或结束的时间硬实时任务与软实时任务实时 OS的特点
可确定性
响应性
用户控制
可靠性
故障弱化运行实时调度的基本条件
提供必要的信息
– 就绪时间，开始 /完成截止时间，处理时间
– 资源要求，优先级
系统处理能力强
– 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
