02. 处理机调度

处理机调度

基本概念

调度对象

进程调度：在多道程序系统中，从就绪队列中选择一个进程分配 CPU。

线程调度：在多线程系统中，从就绪线程中选择一个线程分配 CPU。

调度时机

1. 进程结束：当前进程执行完毕
2. 时间片用完：分时系统中时间片耗尽
3. 进程阻塞：进程等待 I/O 或其他资源
4. 高优先级进程就绪：抢占式调度中高优先级进程到达
5. 进程主动放弃 CPU：进程调用 yield()等函数

调度切换

上下文切换：从一个进程切换到另一个进程时，需要保存当前进程的状态并恢复新进程的状态。

切换开销：

• 保存和恢复寄存器
• 更新内存管理单元（MMU）
• 刷新缓存
• 更新内核数据结构

调度准则

面向用户的准则

1. 周转时间：从进程提交到完成的时间

   • 周转时间 = 完成时间 - 提交时间
   • 平均周转时间 = Σ 周转时间 / 进程数

2. 响应时间：从用户请求到系统响应的时间

   • 响应时间 = 首次获得 CPU 时间 - 提交时间

3. 等待时间：进程在就绪队列中等待的总时间

   • 等待时间 = 周转时间 - 执行时间

4. 截止时间：实时系统中进程必须完成的时间

面向系统的准则

1. CPU 利用率：CPU 忙碌时间的百分比

   • CPU 利用率 = CPU 忙碌时间 / 总时间

2. 吞吐量：单位时间内完成的进程数

   • 吞吐量 = 完成的进程数 / 总时间

3. 公平性：所有进程获得 CPU 的机会应该公平

4. 可预测性：调度算法的行为应该可预测

调度方式

非抢占式调度

特点：

• 一旦进程获得 CPU，就一直执行到结束或阻塞
• 调度决策简单
• 响应时间不可预测

适用场景：

• 批处理系统
• 实时性要求不高的系统

抢占式调度

特点：

• 正在执行的进程可能被其他进程抢占
• 响应时间短
• 调度决策复杂

适用场景：

• 分时系统
• 实时系统
• 交互式系统

典型调度算法

1. 先来先服务（FCFS）

算法描述：

• 按照进程到达就绪队列的顺序进行调度
• 非抢占式调度算法

特点：

• 实现简单
• 公平性好
• 平均等待时间长
• 对短进程不利

示例：

进程  到达时间  执行时间  开始时间  完成时间  周转时间  等待时间
P1    0        6        0        6        6        0
P2    2        4        6        10       8        4
P3    4        2        10       12       8        6
P4    6        8        12       20       14       6

平均周转时间 = (6+8+8+14)/4 = 9
平均等待时间 = (0+4+6+6)/4 = 4

2. 短作业优先（SJF）

算法描述：

• 选择执行时间最短的进程优先执行
• 非抢占式版本：SJF
• 抢占式版本：最短剩余时间优先（SRTF）

特点：

• 平均周转时间最短
• 对长进程不公平
• 需要预知进程执行时间

示例：

进程  到达时间  执行时间  开始时间  完成时间  周转时间  等待时间
P1    0        6        0        6        6        0
P3    4        2        6        8        4        2
P2    2        4        8        12       10       6
P4    6        8        12       20       14       6

平均周转时间 = (6+4+10+14)/4 = 8.5
平均等待时间 = (0+2+6+6)/4 = 3.5

3. 时间片轮转（RR）

算法描述：

• 为每个进程分配一个时间片
• 进程用完时间片后，CPU 分配给下一个进程
• 抢占式调度算法

特点：

• 公平性好
• 响应时间短
• 时间片大小影响性能

时间片选择：

• 时间片太小：上下文切换开销大
• 时间片太大：退化为 FCFS
• 一般选择 10-100ms

示例（时间片=2）：

时间  0  2  4  6  8  10 12 14 16 18 20
P1   |--|--|--|--|--|--|
P2      |--|--|--|--|--|--|
P3         |--|--|--|--|--|--|
P4            |--|--|--|--|--|--|

4. 优先级调度

算法描述：

• 为每个进程分配一个优先级
• 选择优先级最高的进程执行
• 可以是抢占式或非抢占式

优先级确定：

• 静态优先级：进程创建时确定，运行期间不变
• 动态优先级：根据进程行为动态调整

优先级调整策略：

• 等待时间越长，优先级越高
• CPU 使用时间越长，优先级越低
• I/O 密集型进程优先级高于 CPU 密集型进程

5. 多级反馈队列

算法描述：

• 设置多个优先级队列
• 新进程进入最高优先级队列
• 用完时间片后降级到下一级队列
• 低优先级队列时间片更长

特点：

• 结合了多种算法的优点
• 对短进程有利
• 长进程最终会得到执行

队列设置示例：

队列0：优先级最高，时间片1ms
队列1：优先级高，时间片2ms
队列2：优先级中，时间片4ms
队列3：优先级低，时间片8ms
队列4：优先级最低，时间片16ms

实时调度

实时系统特点

1. 时间约束：任务必须在规定时间内完成
2. 可预测性：系统行为必须可预测
3. 可靠性：系统必须稳定可靠

实时调度算法

1. 最早截止时间优先（EDF）：

• 选择截止时间最早的进程执行
• 动态优先级调度
• 理论上最优的实时调度算法

2. 速率单调调度（RMS）：

• 周期任务的优先级与周期成反比
• 周期越短，优先级越高
• 静态优先级调度

3. 最小松弛时间优先（LLF）：

• 选择松弛时间最小的进程执行
• 松弛时间 = 截止时间 - 当前时间 - 剩余执行时间

多处理器调度

调度策略

1. 全局调度：

• 所有 CPU 共享一个就绪队列
• 调度器为所有 CPU 选择进程
• 负载均衡效果好

2. 局部调度：

• 每个 CPU 有独立的就绪队列
• 进程绑定到特定 CPU
• 减少进程迁移开销

负载均衡

目标：使各 CPU 的负载尽可能均衡

策略：

• 工作窃取：空闲 CPU 从繁忙 CPU 窃取进程
• 负载迁移：将进程从繁忙 CPU 迁移到空闲 CPU
• 动态负载均衡：根据负载情况动态调整

调度性能评价

评价指标

1. CPU 利用率：CPU 忙碌时间的百分比
2. 吞吐量：单位时间内完成的进程数
3. 周转时间：进程从提交到完成的时间
4. 等待时间：进程在就绪队列中的等待时间
5. 响应时间：从请求到响应的时间

性能比较