操作系统-处理机调度
3.1 处理机调度概述
处理机调度的三个层次
操作系统中存在三个层次的调度，由上到下分别是：
高级调度，即作业调度，存在于多道批处理系统中，分时和实时系统一般不设置高级调度。调度对象是作业，功能是决定从外存后备队列中哪些作业调入内存。每个作业包含程序、数据和作业说明书三部分，并对应一个作业控制块，即 JCB。JCB 中包含作业状态字段，如后备、运行、完成等，系统据此判断作业是否处于可被调度的状态。作业调度的任务有两个：一是根据多道程序度确定接纳作业的数量，二是依据调度算法决定接纳哪些作业。
中级调度，即内存对换，属于存储器管理的对换功能，负责将某些进程调至外存挂起，或将某些进程从外存调入内存就绪。引入中级调度的目的是提高内存利用率和系统吞吐量。
低级调度，即进程调度，这是最频繁发生的调度，决定就绪队列中哪个进程获得 CPU。调度分为三步：保存当前进程的 CPU 现场信息 → 按某种调度算法选取进程 → 把 CPU 分配给被选中的进程。
进程调度机制
进程调度机制包含三个组件：排队器将就绪进程插入相应的就绪队列；分派器从就绪队列中选取一个进程；上下文切换器与 PCB 交互，完成两次上下文切换操作——第一次保存当前进程的 CPU 现场到其 PCB，第二次从被选中进程的 PCB 中恢复 CPU 现场。
上下文切换需要大量 load / store 操作，开销较大。现代硬件采用多组寄存器来优化这一过程，只需修改指针指向当前寄存器组即可完成切换，避免了逐个寄存器的保存和恢复。
进程调度方式
非抢占调度方式：仅在进程运行完毕、主动阻塞（如 I/O 请求）或执行原语（如 Block）时发生调度。优点是实现简单、开销小，适用于大多数批处理系统，但不适用于分时系统和大多数实时系统，因为无法及时响应用户交互或紧急事件。
抢占调度方式：允许强行剥夺当前进程的 CPU。抢占遵循三项原则：优先级原则——高优先级进程到达时可抢占低优先级进程；短进程优先原则——新到的短进程可抢占当前长进程；时间片原则——时间片用完时进程被强制暂停。
处理机调度算法的目标
共同目标
- 资源利用率高
- 公平性——各进程都能获得合理的 CPU 时间
- 平衡性——保持系统资源的均衡使用
- 策略强制执行
批处理系统的目标
- 平均周转时间短
- 系统吞吐量高
- 处理机利用率高
需要注意的是，上述目标之间存在一定矛盾。例如，为了追求高吞吐量，系统可能倾向于调度短作业，但这会延长长作业的等待时间，影响公平性。
分时系统的目标
- 响应速度快
- 系统负载均衡性良好——各用户都能获得及时响应
实时系统的目标
- 保证满足截止时间要求
- 保证可预测性
3.2 调度算法
先来先服务调度算法（FCFS）
First-Come, First-Served。按进程或作业到达的先后顺序调度，既可用于作业调度，也可用于进程调度。实现最简单，但可能产生护航效应：一个长作业先到，后面所有短作业都得等，平均等待时间会变得很长。
短作业优先调度算法（SJF）
Shortest Job First。优先调度运行时间最短的作业或进程，既可用于作业调度，也可用于进程调度。在平均等待时间上表现最优，但有四个致命缺点：
- 运行时间难以准确预知——作业提交时无法精确估计其执行时长
- 对长作业不公平，可能导致长作业饥饿
- 无法实现人机交互——不关心用户响应需求
- 未考虑作业的紧迫程度——一个紧急但较长的作业可能被无限推迟
优先级调度算法
基于进程的紧迫程度进行调度，优先级由外部赋予，既可用于作业调度，也可用于进程调度。
按抢占方式分类：
- 非抢占式优先级调度算法：一旦进程获得 CPU，就一直运行到完成或主动放弃，高优先级进程需要等待当前进程释放 CPU
- 抢占式优先级调度算法：允许高优先级进程抢占正在运行的低优先级进程，响应性好
按优先级是否可变分类：
- 静态优先级：进程创建时确定，运行期间不再改变。依据包括进程类型（系统进程优先于用户进程）、资源需求（CPU 密集型与 I/O 密集型区别对待）、用户要求
- 动态优先级：在运行过程中根据实际情况调整，可防止饥饿
高响应比优先算法（HRRN）
Highest Response Ratio Next。是优先级调度算法的一个特例，通常用于作业调度。响应比公式为：
$$
R = \frac{\text{等待时间} + \text{要求服务时间}}{\text{要求服务时间}}
= \frac{\text{响应时间}}{\text{要求服务时间}}
$$
响应比既考虑了等待时间，也考虑了服务时间。短作业响应比高，长作业等待久了响应比也会升高，兼顾了效率和公平。
轮转调度算法（RR）
Round Robin。属于进程调度算法，基本原理是通过定时中断实现时间片轮转。切换时机有两种：进程在时间片内提前完成则立即调度下一个进程；时间片用完则被放回就绪队列末尾。
时间片的大小是关键参数：过小则上下文切换频繁、系统开销大；过大则退化为 FCFS，失去交互性；适中则应略大于典型交互时间。
多级队列调度算法
将就绪队列拆分为多个独立队列，不同队列可采用不同的调度算法和优先级。例如，可将系统进程、交互式进程、批处理进程分别放入不同队列，各队列按自身策略调度。
在单处理机系统中，多级队列可将不同类型的线程绑定到特定处理机上运行。在多处理机系统中，各队列的进程可并行执行，充分利用多处理机资源。
多级反馈队列调度算法
这是最复杂的通用调度算法，不必事先知道进程所需的执行时间。调度机制如下：
- 设置多个就绪队列，优先级递减，时间片递增。例如第一队列时间片为 1，第二队列为 2，第三队列为 4，以此类推
- 各队列内部采用 FCFS 调度
- 新进程首先进入第 1 队列，若在时间片内未完成则降至下一级队列
- 调度时按队列优先级从高到低选取，支持抢占——若有新进程进入高优先级队列，可抢占低优先级队列中正在运行的进程
性能分析：交互式作业通常在第一队列就能完成，响应速度快；短作业在较高优先级队列中就能执行完，周转时间短；长作业逐级降到低优先级队列，以 RR 方式运行，既保证持续执行又避免饥饿。
3.3 多处理机调度
多处理机系统架构概述
多处理机系统架构多样，主要包括：
- SMP（对称多处理）：各处理机地位相同，每个处理机均可独立进行进程调度，是现代操作系统最常讨论的架构
- ASMP（非对称多处理）：存在主处理机和从处理机之分，主处理机负责调度和分配任务
- NUMA（非一致内存访问）：各处理机访问本地内存速度快、访问远程内存速度慢，调度时需考虑内存位置
- HMP（异构多处理）：不同处理机具有不同的计算能力，如大小核架构，需根据任务特性分配到合适的处理机
本节重点讨论 SMP 架构下的调度问题。
SMP 架构下的调度算法
公共就绪队列调度算法
所有处理机共享一个全局就绪队列，任何处理机空闲时都从该队列中取进程运行。看似简单公平，但存在五个局限性：
- 可能出现竞争条件——多个处理机同时访问队列
- 需要将就绪队列作为互斥资源，使用锁保护
- 处理机调度频率极高，锁竞争开销显著，成为性能瓶颈
- 破坏处理机亲和性——进程可能被调度到任意处理机，缓存反复失效
- 全局队列本身成为单点瓶颈，限制系统可扩展性
由于这些原因，现代操作系统较少采用公共就绪队列方案。
私有就绪队列调度算法
每个处理机维护自己的私有就绪队列。优点是避免了全局锁竞争，处理机亲和性好。缺点是可能导致负载不均衡——某些处理机队列过长而其他处理机空闲，限制了多处理机的性能优势。
两级调度算法
在私有就绪队列的基础上增加一个更高层级的队列，形成两级结构。高层队列负责处理机之间的负载均衡，底层各处理机仍使用私有就绪队列进行本地调度。这种方案兼顾了处理机亲和性与系统负载均衡，是现代操作系统多处理机调度的主流方案。
负载均衡
私有就绪队列是必要的，公共就绪队列不是必要的——私有队列保证了本地调度的高效性，而公共队列的问题可以通过其他方式解决。两级调度算法可以减少负载不均衡，但无法完全消除。为实现负载均衡，必须具备在处理机之间迁移进程的能力。
进程迁移策略
- 推迁移：由源处理机主动将进程推送到其他处理机，通常发生在该处理机负载过高时
- 拉迁移：由空闲处理机主动从其他忙碌处理机的队列中拉取进程
两种策略的主要区别在于触发时机不同，但二者互不排斥，可以并行实现。实际系统中通常还会结合更多策略来优化迁移决策。
处理机亲和性
进程在某处理机运行时，最近访问的数据会缓存在该处理机的高速缓存中。如果进程迁移到另一处理机，原缓存需要设为无效，新处理机需要重新填充缓存，代价很高。因此，大多数 SMP 系统会尽量避免迁移，尽量让进程运行在同一处理机上。
处理机亲和性分为两种形式：软亲和性——调度器尽量保持进程在同一处理机上运行，但在必要时允许迁移；硬亲和性——通过系统调用或策略强制将进程绑定到特定处理机，禁止迁移。
需要注意的是，处理机亲和性与负载均衡之间存在天然矛盾：追求亲和性会阻碍负载均衡，追求均衡又会破坏亲和性。调度算法需要在这两者之间合理权衡。
3.4 实时调度
实现实时调度的基本条件
实时系统对调度有严格要求，需要满足四个条件：
提供必要的调度信息：系统必须掌握就绪时间、开始截止时间、完成截止时间、处理时间、资源要求和优先级等信息，调度算法才能做出正确决策。
系统处理能力强：单处理机系统需要增强处理能力以满足实时任务的时限要求；多处理机系统则需要将可调度条件中的处理机数量从 1 改为 N，从而扩展系统的总处理能力。
采用抢占式调度机制：含有硬实时任务（HRT）的系统必须支持抢占；对于可预知截止时间的任务，可以改用非抢占式调度，但要求任务本身执行时间较短。
采用快速切换机制：包括快速中断响应、短的禁止中断间隔和精简的上下文切换代码，确保系统能及时响应实时事件。
实时调度算法分类
实时调度算法可分为两大类：
非抢占式调度算法
- 非抢占式轮转调度算法：任务主动放弃 CPU 后才切换到下一个任务，适用于软实时系统
- 非抢占式优先级调度算法：即使有更高优先级的任务就绪，也必须等待当前任务完成，响应延迟不可控
抢占式调度算法
- 基于时钟中断的抢占式优先级调度算法：依赖时钟中断触发调度检查，在中断处理程序中判断是否有更高优先级的任务需要抢占
- 立即抢占的优先级调度算法：不等待时钟中断，一旦高优先级任务就绪就立即剥夺当前任务的 CPU，适用于对响应时间要求严格的硬实时系统
最早截止时间优先算法（EDF）
Earliest Deadline First。核心思想是截止时间越早，优先级越高。
- 非抢占式 EDF：适用于非周期实时任务，任务运行期间不会被抢占
- 抢占式 EDF：适用于周期实时任务，新任务到达时若其截止时间更早，则抢占当前任务
EDF 简单直观，在系统过载时性能下降可控，是实时调度中应用最广泛的算法之一。
最低松弛度优先算法（LLF）
Least Laxity First。核心思想是松弛度越低，紧迫程度越高。松弛度公式为：
$$
\text{松弛度} = \text{截止时间} - \text{剩余处理时间} - \text{当前时间}
$$
通常采用抢占式调度。但 LLF 存在明显缺点：当多个任务松弛度相等或接近时，调度器需要频繁做出调度决策，调度开销很大，甚至可能出现颠簸现象——进程在就绪状态和运行状态之间反复切换，导致系统效率严重下降。
优先级倒置
优先级倒置的形成
考虑三个进程：H（高优先级）、M（中优先级）、L（低优先级）。当 L 持有某个共享资源时，H 到达并试图获取该资源，但发现资源被 L 占用，于是 H 被阻塞等待。此时 M 就绪并抢占了 L 的 CPU，因为 M 的优先级高于 L。结果是 H 作为最高优先级进程，反而被中等优先级的 M 间接阻塞，形成了优先级倒置。
简单的解决办法
规定进程进入临界区后处理机不允许被抢占。这种方法简单，但缺点明显：如果临界区很长，高优先级进程的等待时间会很长，严重影响实时性。
动态优先级继承
实用的解决办法是基于动态优先级继承：当 L 持有 H 所需的资源时，系统临时将 L 的优先级提升到 H 的优先级，使得 M 无法抢占 L。L 释放资源后恢复原来的优先级。这样既防止了 M 抢占 L，又缩短了 H 的阻塞时间。这一机制目前已在实时系统中广泛采用。
3.5 进程调度实例
不同操作系统采用不同的进程调度策略。Linux 进程调度基于 CFS（完全公平调度器），采用红黑树维护虚拟运行时间，保证各进程获得公平的 CPU 时间份额。Windows 进程调度采用多级反馈队列的变体，支持 32 个优先级，结合时间片和优先级动态调整。HarmonyOS 进程调度则针对分布式场景进行了优化，支持跨设备的任务调度和资源协调。