7.7 KiB
CPU 调度
1. 调度的层级
高级调度 ：又叫做作业调度，从外存中选取一个或者多个作业，为其分配内存，设备，IO等等资源。简而言之就是实现了内存与外存之间的调度，让每个调度在生命周期中只用调入一次调出一次 中级调度： 又叫做内存调度，将暂时被无法运行的进程挂起， 换出到外存 低级调度： 按照特性算法从就绪队列中选择一个进程， 分配CPU， 是操作系统中最频繁的调度， 通常几十微秒执行一次
2. 调度的时机
- 创建新进程之后
- 进程正常结束或者终止之后
- 当进程因被如IO， 信号量之类的操作阻塞之后
3. 调度的指标
- CPU 利用率：
CPU_{利用率} = \dfrac{CPU有效工作时间}{CPU有效工作时间 + CPU空闲等待时间} - 系统吞吐量：单位时间内 CPU 完成的进程数量
- 周转时间：$T_{周转} = T_{完成} - T_{到达}$，进程从提交到完成的总时间
- 带权周转时间：$T_{带权周转} = \dfrac{T_{周转}}{T_{服务}}$，周转时间与服务时间的比值，衡量进程相对延迟，值越大说明等待时间相对服务时间越长
- 等待时间：$T_{等待} = T_{周转} - T_{服务}$，进程在就绪队列中等待的时间总和
- 响应时间：$T_{响应} = T_{首次运行} - T_{到达}$，从提交到首次被 CPU 运行的时间
4. 调度算法
4.1 先来先服务（FCFS, First Come First Served）
非抢占式算法，按照进程到达的先后顺序进行调度。
| 优点 | 缺点 |
|---|---|
| 实现简单，公平 | 对短作业不友好, 利好长作业 |
| 每个进程都能被执行 | 平均等待时间长比较长 |
4.2 短作业优先（SJF, Shortest Job First）
非抢占式算法，选择服务时间（CPU 突发时间）最短的进程优先执行。
| 优点 | 缺点 |
|---|---|
| 平均周转时间、平均等待时间最优 | 长作业可能饥饿（Starvation） |
| 证明为最优平均等待时间算法 | 难以准确估计进程运行时间 |
最短剩余时间优先（SRTF, Shortest Remaining Time First）：SJF 的抢占式版本。每当新进程到达时，如果其剩余时间比当前运行进程的剩余时间短，则抢占 CPU。
4.3 高响应比优先（HRRN, Highest Response Ratio Next）
计算每个就绪进程的响应比，选择响应比最高的进程执行。
响应比 = \frac{等待时间 + 服务时间}{服务时间} = 1 + \frac{等待时间}{服务时间}
| 优点 | 缺点 |
|---|---|
| 综合考虑等待时间和运行时间 | 每次调度需要计算所有进程的响应比，开销较大 |
| 避免长作业饥饿 | 非抢占式，无法处理紧急任务 |
4.4 时间片轮转（RR, Round Robin）
抢占式算法，按照就绪队列的顺序，每个进程轮流获得固定长度的时间片（Time Slice）。
时间片大小对性能的影响：
| 时间片 | 影响 |
|---|---|
| 过大 → 退化为 FCFS，响应时间变差 | |
| 过小 → 上下文切换开销过大，降低 CPU 利用率 |
经验法则：时间片应略大于一次典型交互所需的 CPU 时间（通常 10~100ms），使大多数进程能在一个时间片内完成。
| 优点 | 缺点 |
|---|---|
| 响应时间短，适合交互式系统 | 时间片设置敏感 |
| 公平性好，每个进程都能获得 CPU | 上下文切换频繁 |
4.5 优先级调度（Priority Scheduling）
每个进程分配一个优先级，就绪队列中优先级最高的进程优先执行。
- 非抢占式：当前进程运行完成后才进行调度
- 抢占式：当新到达进程的优先级更高时，抢占当前进程
注意：优先级调度可能导致低优先级进程饥饿。解决方案：老化（Aging）——逐渐提升长时间等待的低优先级进程的优先级。
| 优点 | 缺点 |
|---|---|
| 可以区分不同任务的紧急程度 | 低优先级进程可能饥饿 |
| 灵活，支持静态/动态优先级 | 需要解决优先级反转问题 |
4.6 多级反馈队列（MLFQ, Multilevel Feedback Queue）
综合了多种调度方法的优点，是现代化操作系统中最常用的调度算法。
核心思想：
- 设置多个不同优先级的就绪队列
- 各队列内部使用 RR 调度（时间片不同，优先级越高的队列时间片越小）
- 新进程先进入最高优先级队列
- 进程用完时间片仍未完成，降级到下一级队列
- 优先级高的队列不空，不执行低优先级队列
老化机制：防止进程在低优先级队列中饥饿，定期将长时间等待的进程提升到高优先级队列。
| 优点 | 缺点 |
|---|---|
| 兼顾交互型和计算型进程 | 参数配置复杂 |
| 响应时间短，吞吐量高 | 可能被恶意进程"玩弄"（如故意在时间片结束前释放 CPU） |
| 避免饥饿 |
4.7. 算法对比总结
| 算法 | 抢占式 | 饥饿问题 | 平均等待时间 | 响应时间 | 适用场景 |
|---|---|---|---|---|---|
| FCFS | ❌ | ❌ | 长 | 长 | 批处理系统 |
| SJF | ❌ | ✅ 长作业饥饿 | 最短 | 长 | 批处理系统 |
| SRTF | ✅ | ✅ 长作业饥饿 | 最短 | 较长 | 批处理系统 |
| HRRN | ❌ | ❌ | 较短 | 较长 | 批处理系统 |
| RR | ✅ | ❌ | 较长 | 短 | 交互式系统 |
| 优先级调度 | 可选 | ✅ 低优先级饥饿 | — | — | 实时系统 |
| MLFQ | ✅ | ❌ | 短 | 短 | 通用操作系统 |
5. 多处理机调度
多处理机系统拥有多个 CPU（或处理器核心），调度问题比单处理机更复杂，需要解决任务分配、负载均衡、处理器亲和性等问题。
5.1 多处理机架构
根据处理器之间的关系，多处理机系统分为两种架构：
对称多处理（SMP, Symmetric Multi-Processing）
所有处理器对等，每个处理器独立运行调度程序，从就绪队列中选择进程执行。
| 队列方式 | 描述 |
|---|---|
| 每个处理器独立队列 | 每个 CPU 维护自己的就绪队列，减少锁竞争，但可能导致负载不均 |
| 共享全局队列 | 所有 CPU 共享一个就绪队列，负载自动均衡，但存在锁竞争瓶颈 |
| 优点 | 缺点 |
|---|---|
| 可靠性高，一个 CPU 故障不影响其他 CPU | 需要处理多处理器同步问题 |
非对称多处理（ASMP, Asymmetric Multi-Processing）
一个主处理器（Master）负责调度决策和数据结构管理，其他从处理器（Slave）只执行主处理器分配的任务。
| 优点 | 缺点 |
|---|---|
| 无需处理同步问题，实现简单 | 主处理器可能成为性能瓶颈 |
| 适合专用系统（如 DSP + 通用 CPU） | 主处理器故障则系统瘫痪 |
5.2 处理器亲和性（Processor Affinity）
将进程/线程绑定到特定处理器上执行，利用 CPU 缓存（Cache）局部性，避免因进程迁移导致的缓存失效开销。
| 类型 | 描述 |
|---|---|
| 软亲和性（Soft Affinity） | 操作系统尽力让进程在同一个 CPU 上运行，但不强制保证 |
| 硬亲和性（Hard Affinity） | 通过系统调用将进程硬性绑定到指定 CPU 上 |
5.3 负载均衡（Load Balancing）
在 SMP 系统中，负载均衡确保所有 CPU 的工作量大致相等。
| 机制 | 描述 |
|---|---|
| 推送迁移（Push Migration） | 系统定期检查每个 CPU 的负载，将过载 CPU 的任务推送给空闲 CPU |
| 拉取迁移（Pull Migration） | 空闲 CPU 主动从其他 CPU 的就绪队列中拉取任务执行 |
负载均衡与处理器亲和性存在冲突：迁移进程会破坏缓存局部性，降低性能。