4. 处理机调度与死锁问题

# 处理机调度

# 核心概念

# 调度的定义

在多道程序设计系统中，通常会有多个进程（或线程）竞争处理机资源。操作系统必须选择要运行的进程（或线程），并为其分配处理机。完成这一选择工作的操作系统代码称为调度程序（scheduler）。

# 调度的层次

长程调度 (作业调度)
- 也称为宏观调度或高级调度。它决定将哪些作业调入内存准备运行。其主要面向的是从外存后备队列中挑选作业。
- 时间尺度：通常是分钟、小时级别。
中程调度 (内存调度)
- 也称为中级调度。为了缓和内存紧张，它负责将暂时不能运行的进程从内存换出到外存，或在需要时将具备运行条件的进程从外存换入内存。这涉及到了内外存交换。
- 时间尺度：介于长程和短程之间。
短程调度 (进程/线程调度)
- 也称为微观调度或低级调度。它决定就绪队列中的哪个进程（或线程）将获得处理机的使用权。这是最频繁发生的调度。
- 时间尺度：通常是毫秒级别，要求实现效率极高。

# 调度的时机

操作系统需要在以下关键时刻进行处理机调度：

创建一个新进程后。
一个进程运行完毕，或由于某种错误而终止运行时（必须执行）。
一个进程因等待 I/O 或其他事件而进入等待状态时（必须执行）。
当 I/O 中断发生时（可能从运行态切换到就绪态）。
当时钟中断发生时（在分时系统中，用于实现时间片轮转）。

# 调度方式

非抢占式 (Non-preemptive)
- 调度程序一旦将处理机分配给某进程，该进程便会一直运行，直到它自己完成或因等待事件而阻塞。
- 优点：实现简单，系统开销小。
- 适用场景：主要适用于批处理系统，不适用于分时和实时系统。
抢占式 (Preemptive)
- 当一个更高优先级的进程准备就绪时，调度程序可以中断当前正在运行的进程，将处理机分配给新来的高优先级进程。
- 适用场景：主要适用于要求响应及时的分时系统和实时系统。
- 抢占原则：
  - 优先级原则：高优先级进程可抢占低优先级进程。
  - 时间片原则：当运行进程的时间片用完后，系统会剥夺其处理机使用权。

# 调度算法的目标与准则

在评估和选择调度算法时，需要考虑多个目标，这些目标因系统类型而异。

所有系统通用目标
- 公平：确保每个进程都能获得公平的 CPU 份额，防止进程“饿死”。
- 效率 (CPU 利用率)：保持 CPU 及其他系统资源尽可能处于忙碌状态。
批处理系统目标
- 吞吐量：单位时间内完成的作业数量最大化。
- 周转时间：从作业提交到作业完成的总时间最小化。
交互式系统目标
- 响应时间：从用户发出命令到系统首次给出响应之间的时间尽可能短。
实时系统目标
- 保证截止时间 (Deadline)：必须在规定的截止时间前完成任务，避免数据丢失或系统失效。

# 进程行为对调度的影响

计算密集型 (CPU-bound)：进程大部分时间都在进行计算，很少请求 I/O 操作。
I/O 密集型 (I/O-bound)：进程大部分时间都在等待 I/O 操作完成，计算时间很短。

一个好的调度算法应该在这两类进程之间取得平衡，以提高系统整体效率。

# 批处理系统调度算法

# 先来先服务 (First Come First Served, FCFS)

思想：按照进程进入就绪队列的先后顺序进行调度。
特点：
- 实现简单，属于非抢占式算法。
- 对长作业有利，但可能导致短作业等待时间过长。
- 对 CPU 密集型作业有利，而不利于 I/O 密集型作业（因为 I/O 密集型作业的短暂 CPU 使用会被长时间运行的 CPU 密集型作业阻塞）。

# 最短作业优先 (Shortest Job First, SJF)

思想：选择预计运行时间最短的作业（进程）优先执行。
特点：
- 相比 FCFS，能显著改善平均周转时间。
- 可能导致长作业“饿死”，即长时间得不到调度。
- 最大的挑战在于难以准确预估作业的执行时间。

# 最短剩余时间优先 (Shortest Remaining Time, SRT)

思想：这是 SJF 算法的抢占式版本。调度程序总是选择剩余执行时间最短的进程运行。当一个新进程进入就绪队列且其所需时间比当前运行进程的剩余时间还短时，会发生抢占。
特点：能为新的短作业提供非常好的服务。

# 最高响应比优先 (Highest Response Ratio Next, HRRN)

思想：通过综合考虑等待时间和要求服务时间来确定优先级。
响应比公式：
$\text{响应比} = \frac{\text{等待时间} + \text{要求服务时间}}{\text{要求服务时间}} = 1 + \frac{\text{等待时间}}{\text{要求服务时间}}$
特点：
- 是 FCFS 和 SJF 之间的折中算法。
- 既照顾了短作业（分母小），又通过等待时间（分子）的增加提高了长作业的优先级，防止其“饿死”。

# 交互式系统调度算法

# 时间片轮转 (Round Robin, RR)

思想：为每个进程分配一个固定的时间段，称为时间片 (quantum)。进程在该时间片内运行，如果时间片用完但进程尚未结束，则被剥夺 CPU 并放回就绪队列的末尾。
特点：
- 实现简单、公平，所有进程被同等对待。
- 时间片长度是性能关键：
  - 过短：导致频繁的进程切换，增加系统开销，降低 CPU 效率。
  - 过长：退化为 FCFS 算法，导致交互请求的响应时间变长。
  - 合理的折衷值通常在 20ms 到 50ms 之间。

# 优先级调度 (Priority Scheduling)

思想：为每个进程分配一个优先级，调度程序总是选择优先级最高的就绪进程来运行。
优先级类型：
- 静态优先级：进程创建时指定，运行期间不变。
- 动态优先级：进程的优先级在其生命周期内可以改变（例如，等待时间越长，优先级越高，以防止低优先级进程“饿死”）。
优化：为了让 I/O 密集型进程获得更好的服务，可以动态提升其优先级（例如，优先级设为 1/f，f 为该进程在上一时间片中计算时间所占的比重）。
组合使用：可以按优先级将进程分组，在组间采用优先级调度，在组内采用时间片轮转调度。

# 多级反馈队列 (Multiple Feedback Queue)

思想：为解决不同类型进程的需求（如 CPU 密集型需要长服务时间，交互型需要快响应），设立多个优先级不同的就绪队列。
- 高优先级队列分配的时间片较短。
- 低优先级队列分配的时间片较长。
- 进程在一个队列的时间片用完后，会降级到下一个队列。
特点：能较好地兼顾各种类型进程的需求，是比较通用和高效的调度算法。

# 最短进程优先 (Shortest Process Next)

思想：SJF 算法在交互式系统中的应用。通过预测下一轮 CPU 执行的长度来选择进程。
预测方法：通常使用老化 (aging) 技术，基于历史执行时间进行加权平均来预测下一次的执行时间。
- 假设上次估计值为 $T_0$ ，本次实际测量值为 $T_1$ ，则新的估计值为 $aT_0 + (1-a)T_1$ 。

# 保证调度 (Guaranteed Scheduling)

思想：向用户做出明确的性能保证，并努力实现它。例如，若系统中有 n 个进程，则保证每个进程获得 1/n 的 CPU 处理时间。
实现：系统跟踪每个进程已使用的 CPU 时间，计算其应得时间和实得时间的比率，并优先调度比率最低的进程。

思想：调度时不仅考虑进程，还考虑进程的拥有者（用户）。避免一个用户通过创建大量进程来占用绝大部分 CPU 资源。
实现：将 CPU 时间在用户之间进行公平分配，然后再将每个用户分得的时间分配给其拥有的进程。

# 实时系统调度算法

实时系统对时间的要求极为严格，其核心是任务必须在截止时间内完成。

硬实时 (Hard Real-Time, HRT)：必须严格满足截止时间，任何延迟都可能导致灾难性后果。
软实时 (Soft Real-Time, SRT)：偶尔超过截止时间是可以容忍的。

# 可调度性条件

对于一组周期性事件，如果事件 $i$ 的周期为 $P_i$ ，处理该事件需要 $C_i$ 秒的 CPU 时间，那么在单处理机系统中，这组事件是可调度的（即所有任务都能满足截止时间）的充分条件是：

$\sum_{i=1}^m \frac{C_i}{P_i} \le 1$

该公式表示所有任务的 CPU 利用率之和不能超过 100%。

# 速率单调调度 (Rate Monotonic Scheduling, RMS)

类型：静态优先级调度算法。
思想：根据任务的速率（频率）来分配优先级，频率越高（周期越短）的任务，优先级越高。
调度：运行时，调度程序总是选择就绪队列中优先级最高的任务执行，必要时可抢占当前任务。

# 最早截止时限优先 (Earliest Deadline First, EDF)

类型：动态优先级调度算法。
思想：任务的优先级根据其截止时间的临近程度动态改变，截止时间越早，优先级越高。
调度：调度程序总是选择就绪队列中截止时间最早的进程执行。

# 最小裕度优先 (Least Laxity First, LLF)

类型：动态优先级调度算法。
思想：根据任务的裕度 (laxity) 或松弛度 (slack) 来决定优先级，裕度最小的进程优先级最高。
裕度计算：
裕度 = (截止时刻 - 当前时刻) - 剩余运行时间

# 死锁

# 死锁的基本概念

# 死锁的定义

死锁 (Deadlock) 是指系统中两个或多个进程无限期地等待一个永远不会发生的条件，导致所有相关进程都无法继续向前推进的系统状态。

# 产生死锁的原因

竞争资源：系统中供多个进程共享的资源不足以同时满足它们的需求，导致进程间对资源的竞争。
进程推进顺序不当：进程在运行过程中，请求和释放资源的顺序不合理，导致相互等待。

# 资源分类

按抢占性：
- 可抢占资源：可以从占有它的进程处强制剥夺而不会导致错误（如 CPU、内存）。
- 不可抢占资源：一旦分配给一个进程，就只能由该进程主动释放，不能被强制剥夺（如打印机、磁带机）。死锁主要与此类资源有关。
按使用方式：共享资源和独占资源。
按使用期限：
- 永久性资源：可重复使用的资源（如硬件设备）。
- 临时性资源：也称消耗性资源，由一个进程产生，被另一个进程使用后即消失（如消息、信号）。

# 死锁发生的四个必要条件

以下四个条件必须同时满足，才可能发生死锁：

互斥 (Mutual Exclusion)：资源在任一时刻只能被一个进程使用。
请求和保持 (Hold and Wait)：进程在持有至少一个资源的同时，又去请求其他进程正占有的新资源。
非抢占 (No Preemption)：进程已经获得的资源不能被强制剥夺，只能由该进程使用完毕后主动释放。
环路等待 (Circular Wait)：存在一个进程资源的循环等待链，链中的每个进程都在等待下一个进程所持有的资源。

# 处理死锁的策略

# 死锁忽略 (鸵鸟算法)

思想：忽略死锁问题，假设它永远不会发生。这就像鸵鸟遇到危险时把头埋进沙子里。
原因：
- 在某些系统中，死锁发生的概率极低。
- 预防或检测死锁的代价远高于死锁发生后手动重启系统的代价。
应用：大多数通用操作系统（如 UNIX, Linux, Windows）都采用此策略。

# 死锁预防 (Deadlock Prevention)

思想：通过设定限制性策略，破坏死锁发生的四个必要条件之一，从而从根本上杜绝死锁。
具体措施：
- 破坏互斥条件：允许资源共享。但对于打印机这类本身不能共享的资源，可以通过假脱机（SPOOLing）技术，将互斥设备改造为共享设备。此方法局限性大。
- 破坏请求和保持条件：采用预先静态分配法，要求进程在运行前一次性申请所有需要的资源。这会严重降低资源利用率，并可能导致进程“饿死”。
- 破坏非抢占条件：允许系统剥夺已分配给进程的资源。实现复杂且可能导致已完成的工作失效。
- 破坏环路等待条件：采用有序资源分配法，将所有资源按类型进行线性排序，并要求所有进程都按序号递增的顺序申请资源。这会限制新设备的增加，并给编程带来不便。

# 死锁避免 (Deadlock Avoidance)

思想：在资源动态分配过程中，系统会预先判断本次分配是否会导致系统进入不安全状态。如果会，则暂时不予分配，从而避免进入可能导致死锁的状态。
安全状态与不安全状态：
- 安全状态：系统能找到一个安全的进程推进序列（例如 <P1, P2, ..., Pn>），使得每个进程 Pi 都能顺利获得其所需资源并完成。系统处于安全状态则一定不会发生死锁。
- 不安全状态：系统找不到任何一个安全序列。进入不安全状态不一定会发生死锁，但可能会。死锁避免就是确保系统永远不会进入不安全状态。
银行家算法 (Banker's Algorithm)
- 背景：最著名的死锁避免算法，它要求进程在运行前声明所需各类资源的最大数量。
- 核心：当进程请求资源时，系统执行一个安全性检查：
  1. 假定将资源分配给该进程。
  2. 检查系统剩余资源能否满足至少一个进程的最大需求。
  3. 如果能，则假定该进程执行完毕并释放所有资源，然后继续检查剩余进程。
  4. 如果所有进程都能通过这种方式执行完毕（即找到了一个安全序列），则系统状态是安全的，可以执行本次分配。否则，系统状态是不安全的，拒绝本次资源请求。
- 算法数据结构：
- 安全性算法步骤：
- 优缺点：
  - 优点：相比死锁预防，资源分配的限制条件更宽松，资源利用率更高。
  - 缺点：要求已知进程所需资源的最大值，且资源和进程数量固定，在实际系统中难以应用。

# 死锁检测与解除 (Deadlock Detection and Recovery)

思想：不采取预防或避免措施，允许死锁发生。系统通过定时运行的检测算法来判断是否已发生死锁，如果检测到死锁，则采取解除措施。
死锁检测
- 资源分配图 (Resource Allocation Graph, RAG)：一种描述资源和进程状态的有向图。
  - 结点：进程（圆圈）和资源类型（方框）。
  - 边：
    - 申请边：从进程指向资源（Pi -> Rj），表示 Pi 正在请求 Rj。
    - 分配边：从资源指向进程（Rj -> Pi），表示 Rj 已分配给 Pi。
- 死锁定理：如果资源分配图中不存在环路，则系统没有死锁。如果图中存在环路，则可能存在死锁。若每个资源类中只有一个实例，则环路是死锁的充要条件。
- 图的化简：通过寻找不被阻塞的进程，释放其资源，并消除其相关的边。如果最终能消除所有边，使所有进程都成为孤立结点，则图是可完全化简的，系统无死锁。否则，不可化简，存在死锁。
- 可化简资源图示例 (无死锁)
- 不可化简资源图示例 (有死锁)
死锁解除 (Recovery)
- 剥夺资源法：从一个或多个进程中强制剥夺部分资源，分配给死锁进程，直到死锁环路被打破。
- 撤销进程法：
  - 终止所有死锁进程。
  - 按照某种策略（如按优先级、已执行时间等）逐个终止进程，直到死锁解除。这是最常用但代价最高的方法。