操作系统中的进程调度算法：抢占式调度与非抢占式调度的区别、实现策略与应用场景

描述
抢占式调度与非抢占式调度是操作系统中进程调度器的两种基本调度模式。它们定义了当一个新进程到达或进程状态改变时，调度器是否允许中断当前正在运行的进程，并将CPU分配给另一个进程。这个选择直接影响系统的响应性、吞吐量、公平性以及调度开销，是理解实时系统、分时系统和批处理系统行为的关键。

解题过程/讲解
我将分以下步骤详细讲解：

1. 基本定义与核心区别
2. 工作流程对比
3. 实现策略与典型算法
4. 优缺点分析
5. 应用场景

1. 基本定义与核心区别

• 非抢占式调度： 一旦进程获得CPU并开始执行，它将一直运行，直到自愿地释放CPU控制权。释放控制权的情况通常包括：

  • 进程主动调用阻塞式的系统调用（如I/O操作、等待信号量）。
  • 进程正常终止（结束运行）。
  • 在早期的协作式多任务系统中，进程显式地调用yield()函数。

• 抢占式调度： 调度器可以在任何时候中断当前正在运行的进程，将CPU重新分配给另一个“更紧急”或“更合适”的进程。触发抢占的事件包括：

  • 具有更高优先级的进程变为就绪状态。
  • 当前进程的时间片用完。
  • 中断处理程序执行完毕，发现有一个更高优先级的进程在等待。

核心区别一句话总结： 调度决策的时机由谁决定。非抢占式由进程自身决定（被动释放），抢占式由调度器/操作系统内核决定（主动剥夺）。

2. 工作流程对比（以两个进程为例）

假设有两个进程：P1（运行时间为10ms）和P2（运行时间为1ms，在P1开始运行2ms后到达）。

• 非抢占式（如FCFS）：

  1. 时间0: P1开始运行。
  2. 时间2: P2到达，进入就绪队列。但由于是非抢占，P1继续运行。
  3. 时间10: P1运行结束，释放CPU。
  4. 时间10: 调度器选择P2开始运行。
  5. 时间11: P2运行结束。
  • 结果： P2的等待时间 = 10 - 2 = 8ms。平均周转时间较长，短作业P2被长作业P1“阻塞”。

• 抢占式（如基于时间片的轮转RR，或最短剩余时间优先SRTF）：

  1. 时间0: P1开始运行。
  2. 时间2: P2到达。调度器比较：P1剩余8ms，P2需要1ms。在SRTF中，P2剩余时间更短，立即抢占P1的CPU。P1被放回就绪队列。
  3. 时间2: P2开始运行。
  4. 时间3: P2运行结束。
  5. 时间3: 调度器选择就绪队列中唯一的P1，继续运行剩余的8ms。
  • 结果： P2的等待时间 = 0ms。平均周转时间显著缩短，响应性更好，但发生了上下文切换开销。

3. 实现策略与典型算法

• 非抢占式调度常见算法：

  • 先来先服务： 严格按照到达顺序执行，直到进程结束或阻塞。
  • 非抢占式最短作业优先： 只在当前运行的进程结束时，从就绪队列中选择一个预计运行时间最短的进程运行。
  • 非抢占式优先级调度： 只在当前进程结束时，选择优先级最高的进程运行。

• 抢占式调度常见算法：

  • 时间片轮转： 每个进程被分配一个固定的时间片。进程用完时间片后，会被时钟中断强制剥夺CPU，放到就绪队列末尾。
  • 抢占式最短剩余时间优先： 每当新进程到达，就重新比较所有进程（包括正在运行的进程）的剩余运行时间，总是调度剩余时间最短的。这需要频繁的抢占。
  • 抢占式优先级调度： 当一个更高优先级的进程变为就绪时（如从阻塞中唤醒），立即抢占当前低优先级进程的CPU。
  • 多级反馈队列： 结合了时间片轮转和优先级。进程在不同队列间移动，时间片大小不同，调度决策是抢占式的。
  • 所有实时调度算法： 如最早截止时间优先、速率单调调度。为了保证截止时间，必须允许高优先级任务抢占低优先级任务。

实现关键： 抢占式调度依赖于硬件定时器中断和内核中保存/恢复进程上下文（寄存器状态、程序计数器等）的能力。当抢占发生时，内核必须完整地保存当前进程的上下文，并加载新进程的上下文。

4. 优缺点分析

5. 应用场景

• 非抢占式调度的典型场景：

  • 早期的批处理系统和协作式多任务操作系统（如Windows 3.x, Classic Mac OS）。
  • 某些嵌入式实时系统： 在任务高度确定、运行时间固定且已知，并且所有任务都设计为在指定时间内主动释放CPU的情况下，非抢占式调度能提供最少的调度开销和确定的延迟。
  • 内核关键路径： 操作系统内核在处理某些关键数据结构（如页表、调度队列）时，会临时禁用抢占，以保证操作的原子性。

• 抢占式调度的典型场景：

  • 现代通用操作系统： 如Linux, Windows, macOS。它们都使用抢占式内核，确保系统的交互性和响应性。
  • 硬实时和软实时系统： 必须保证高优先级任务能立即抢占低优先级任务，以满足严格的截止时间要求。
  • 任何需要支持多任务、且希望防止单个进程故障（如死循环）导致整个系统无响应的环境。

总结： 抢占式调度是现代操作系统的基石，它牺牲了一部分性能和确定性，换来了强大的响应性、公平性和健壮性。理解这两种模式，是设计、分析和调试多任务系统的关键基础。在实际系统中，两者常常结合使用，例如在内核的大部分代码路径允许抢占，但在极短的临界区内临时禁用抢占。