第3章：处理机调度与死锁

处理机调度（CPU Scheduling）是操作系统资源管理的核心功能之一。本章系统介绍三级调度体系、调度算法、实时调度以及死锁的产生条件和解决方法。

3.1 调度的基本概念

3.1.1 三级调度体系 ⭐

        作业进入系统│▼┌───────────────┐│   高级调度     │  ← 作业调度：外存 → 内存│  (作业调度)    │     频次最低，每作业一次└───────┬───────┘▼┌───────────────┐│   中级调度     │  ← 挂起调度：换出/换入内存│  (内存调度)    │     频次中等，调节内存负载└───────┬───────┘▼┌───────────────┐│   低级调度     │  ← 进程调度：就绪 → 执行│  (进程调度)    │     频次最高，ms级└───────────────┘

调度层次	别名	功能	频率	是否必有
高级调度	作业调度/长程调度	从外存后备队列选作业进内存	最低（分钟级）	分时/实时OS可无
中级调度	内存调度/中程调度	进程换入换出内存（挂起/激活）	中等	分时OS有
低级调度	进程调度/短程调度	从就绪队列选进程分配CPU	最高（ms级）	必有

3.1.2 调度队列模型

   新作业 ──→ 后备队列 ──→ [高级调度] ──→ 就绪队列 ──→ [低级调度] ──→ CPU ──→ 完成↑┌────── 阻塞队列 ──────┐│    (等待I/O等事件)    │└───────────────────────┘

3.1.3 CPU调度时机

情形	是否为抢占	说明
进程终止	非抢占	必须切换
进程阻塞（等待I/O）	非抢占	必须切换
新进程到达	可选抢占	新进程优先级极端高时
I/O中断	可选抢占	唤醒更高优先级进程时
时钟中断	可选抢占	时间片轮转中必然发生

3.2 调度算法评价指标

指标	含义	追求方向
CPU利用率	CPU忙时间 / 总时间	越高越好
系统吞吐量	单位时间内完成的作业数	越高越好
周转时间	作业完成时间 - 提交时间	越短越好
带权周转时间	周转时间 / 实际运行时间	越小越好
等待时间	进程在就绪队列中等待时间的总和	越短越好
响应时间	从提交到首次响应的时间	越短越好（交互系统）

周转时间 = 完成时间 - 提交时间= 等待时间 + 运行时间（若仅计算系统内阶段）带权周转时间 = 周转时间 / 运行时间≥ 1（越小越好，=1最理想）

3.3 经典调度算法 ⭐⭐⭐

3.3.1 先来先服务（FCFS）

特征	说明
原则	按作业/进程到达先后顺序调度
类型	非抢占
优点	简单、公平
缺点	短作业可能排在长作业后，平均周转时间长
适用	批处理系统

例：P1(24ms), P2(3ms), P3(3ms) 依次到达FCFS:
|────── P1 ──────|─P2─|─P3─|
0                24   27   30平均等待时间 = (0 + 24 + 27)/3 = 17ms若运行顺序改为 P2→P3→P1：
平均等待时间 = (0 + 3 + 6)/3 = 3ms
→ 短作业优先能显著降低平均等待时间

3.3.2 短作业优先（SJF / SPF）⭐

特征	说明
原则	每次调度选运行时间最短的作业/进程
类型	可抢占（SRTF）或非抢占
优点	平均等待时间最小（可证明最优）
缺点	长作业可能饥饿、需预知运行时间
适用	批处理系统

⭐ SJF最优性证明：SJF能给出最小的平均等待时间（对于一组同时到达的作业）。

短作业优先（SPF）vs 最短剩余时间优先（SRTF）SPF（非抢占）：
P1(7), P2(4), P3(1), P4(4) 假设时间0全部就绪
|P3|─P2─|───P4───|────P1─────|
0  1   5        9            16SRTF（抢占式）：
P1在0时刻运行1ms后，P2到达(剩余4 < P1剩余6)，抢占！
|P1|P2|P3|──P2──|───P4───|────P1─────|
0  1  2  3      7       11           16

3.3.3 优先级调度

特征	说明
原则	优先级最高的进程先运行
类型	可抢占或非抢占
优先级确定	静态（固定）或动态（随等待时间变化）

优先级的设定：- 系统进程 > 用户进程- I/O型进程 > 计算型进程（让I/O先行，减少CPU空闲）- 前台进程 > 后台进程

⚠️ 饥饿（Starvation）：高优先级进程不断到来，低优先级进程永远得不到CPU。解决方法：老化（Aging）——随等待时间增加而逐渐提高优先级。

3.3.4 高响应比优先（HRRN）⭐

响应比 $R_p = \frac{等待时间 + 要求服务时间}{要求服务时间} = 1 + \frac{等待时间}{要求服务时间}$

特征	说明
公式	$R_p = \frac{T_{等待}+T_{服务}}{T_{服务}}$
含义	等待时间越长 + 服务时间越短 → 响应比越高
优点	既照顾短作业，又不会让长作业无限等待
缺点	每次调度需计算响应比

当服务时间相同时：响应比由等待时间决定 → FCFS
当等待时间相同时：响应比由服务时间决定 → SJF
长作业等待足够久后，响应比会足够大 → 不会饥饿

3.3.5 时间片轮转（RR）⭐

特征	说明
原则	每个进程轮流获得一个时间片的CPU
类型	抢占式
适用	分时系统
关键参数	时间片大小 q

时间片选择原则：q 太大 → 退化为FCFS，响应时间变长q 太小 → 上下文切换频繁，系统开销增大经验法则：q 应该大于上下文切换时间，且保证80%的CPU突发能在q内完成

3.3.6 多级队列调度

就绪进程：│├──→ 队列1（前台交互式进程，RR调度，优先级最高）│├──→ 队列2（后台批处理进程，FCFS调度，优先级次之）│└──→ 队列3（系统进程，优先级最低但必不可少）

不同队列采用不同调度算法，队列间也可设定优先级。

3.3.7 多级反馈队列调度 ⭐⭐

现代操作系统（Linux、Windows）广泛采用的调度策略，综合了多种算法的优点。

              ┌──────────────┐新进程 →  │ 队列0: q=8ms  │ (RR, 最高优先级)└──┬──┬──┬────┘│  │  └──→ 时间片用完，降到下一级▼  ▼┌──────────────┐│ 队列1: q=16ms │ (RR, 次高优先级)└──┬──┬──┬────┘│  │  └──→ 时间片用完，降到下一级▼  ▼┌──────────────┐│ 队列2: FCFS   │ (最低优先级)└──────────────┘

特征	说明
多个队列	不同优先级，时间片递增
动态调整	I/O密集型进程优先（I/O完成后回到高优先级队列）
老化机制	低优先级队列等待过久可提升优先级
优点	兼顾响应时间和吞吐量，灵活

3.3.8 调度算法总结对比

算法	抢占	饥饿	平均等待	复杂度	适用场景
FCFS	否	不会	较高	O(1)	批处理
SJF	均可	长作业	最优	O(n log n)	批处理
优先级	均可	低优先级	取决于策略	O(n)	通用
HRRN	否	不会	较好	O(n)	批处理
RR	是	不会	取决于q	O(1)	分时
多级反馈队列	是	防止	很好	O(1)	通用

3.4 实时调度

3.4.1 实时调度的必要条件

条件	说明
系统处理能力	周期任务的总利用率 ≤ 1
提供必要信息	就绪时间、开始/完成截止时间、处理时间、资源需求、优先级
可抢占	硬实时系统必须支持抢占

3.4.2 常用实时调度算法

算法	全称	策略	特点
EDF	Earliest Deadline First	截止时间最早的优先	可证明最优（动态优先级）
RMS	Rate Monotonic Scheduling	周期越短（速率越高）优先级越高	静态优先级，$U ≤ n(2^{1/n}-1)$ 可调度
LLF	Least Laxity First	松弛度最低的优先	松弛度 = 截止时间 - 当前时间 - 剩余处理时间

3.5 死锁 ⭐⭐⭐

3.5.1 死锁的定义

死锁（Deadlock）：多个进程因竞争资源而造成的一种僵局，若无外力，这些进程将永远无法向前推进。

3.5.2 产生死锁的四个必要条件 ⭐

死锁四条件：
┌──────────────────────────────────────┐
│  ① 互斥条件                           │
│     资源排他性使用，一次一个进程        │
├──────────────────────────────────────┤
│  ② 请求和保持条件                      │
│     已拥有资源的进程又请求新资源，       │
│     且不释放已有资源                   │
├──────────────────────────────────────┤
│  ③ 不可抢占条件                       │
│     已分配给进程的资源，不能被强制拿走   │
├──────────────────────────────────────┤
│  ④ 循环等待条件                       │
│     存在进程-资源的循环等待链           │
│     P0 → R0 → P1 → R1 → ... → P0     │
└──────────────────────────────────────┘

⭐ 四个条件必须同时满足才会死锁。破坏任一条件即可预防死锁。

3.5.3 资源分配图与死锁检测

资源分配图示例（存在死锁）：P1 ←──┐           P2 ←──┐│     │           │     │▼     │           ▼     │R1     │          R2     ││     │           │     │▼     │           ▼     │P2 ───┘           P3 ───┘若存在环，且每种资源只有一个实例 → 必定死锁
若存在环，但资源有多个实例 → 可能死锁（需进一步判断）

3.5.4 死锁的处理策略

死锁处理 ──┬── 预防（Prevention）  ← 破坏四条件之一，静态策略├── 避免（Avoidance）   ← 银行家算法，动态策略├── 检测（Detection）   ← 检测并恢复└── 忽略（Ignore）      ← 鸵鸟算法（Ostrich Algorithm）

3.6 死锁预防 ⭐

3.6.1 破坏四个条件的方法

破坏的条件	方法	问题
破坏互斥	让资源可共享（如SPOOLing）	不是所有资源都能共享
破坏请求保持	一次性分配所有资源（静态分配）	资源利用率低，可能饥饿
破坏不可抢占	请求被拒时释放已有资源	实现复杂，状态难保存
破坏循环等待	资源有序分配（按编号升序申请）	编号难定，增加编程负担

资源有序分配法：将所有资源编号：R1, R2, ..., Rm
规定：进程只能按编号递增顺序申请资源例：P1 先申请 R2，再申请 R5 ✅P1 先申请 R5，再申请 R2 ❌此方法破坏了循环等待条件，因为不可能形成环。

3.7 死锁避免 ⭐⭐⭐

3.7.1 安全状态

安全状态：系统能按某种进程推进顺序（安全序列），为每个进程分配其所需资源，直到所有进程都能顺利完成。

安全序列：<P1, P3, P4, P0, P2>
系统按此顺序可满足所有进程需求 → 系统处于安全状态不安全状态 ≠ 死锁，但不安全状态可能导致死锁

3.7.2 银行家算法 ⭐⭐⭐

数据结构：Available[m]     // 每种资源的可用数量Max[n][m]        // 各进程对各资源的最大需求Allocation[n][m] // 已分配Need[n][m]       // 还需要 = Max - Allocation算法步骤（安全性检查）：① 设 Work = Available，Finish[i] = false② 找满足 Finish[i]=false 且 Need[i] ≤ Work 的进程 i③ 设 Work = Work + Allocation[i], Finish[i] = true④ 重复 ②③ 直至所有 Finish[i]=true（安全）或找不到（不安全）

3.7.3 银行家算法的两个子算法

算法	调用时机	功能
安全性算法	资源分配前	判断系统是否处于安全状态
资源请求算法	进程申请资源时	判断请求是否可满足（Need/Request/Available检查）

// 资源请求算法伪代码
Request_i[j]  // 进程Pi请求资源Rj的k个实例// Step 1: 请求是否超过声明需求？
if (Request_i > Need_i) → 错误// Step 2: 系统是否有足够资源？
if (Request_i > Available) → 等待// Step 3: 试探性分配
Available -= Request_i
Allocation_i += Request_i
Need_i -= Request_i// Step 4: 执行安全性算法
if (安全) → 正式分配
else     → 回滚，Pi等待

⚠️ 银行家算法的问题：很少在实用OS中使用（进程最大需求难以预知、算法开销大）。

3.8 死锁检测与解除

3.8.1 死锁检测

对资源分配图进行化简，检测是否存在无法化简的环路。

资源分配图化简：① 找既不阻塞也不孤立的进程节点② 去除其所有分配边和请求边（该进程可完成）③ 重复直至无进程可化简④ 若仍有边残留 → 存在死锁

3.8.2 死锁解除

方法	说明	代价
进程终止	终止所有死锁进程（或逐个终止）	损失已完成工作
资源抢占	从进程中抢占资源	需要回滚机制

挑选"牺牲"进程的原则：优先级低、已完成工作量少、剩余时间短、资源使用少、批处理型（非交互型）。

3.9 鸵鸟算法

鸵鸟算法（Ostrich Algorithm）：对死锁视而不见，假装系统中不存在死锁问题。

系统	策略
UNIX/Linux	一般不考虑死锁（应对用户程序引发的死锁能力有限）
Windows	忽略死锁（依赖程序自身解决）

理由：死锁发生的概率极低，而死锁处理的开销太大，从性价比考虑，"忽略"是合理的。

⭐ 本章小结

知识点	核心内容
三级调度	高级（作业）→ 中级（内存）→ 低级（进程）
评价指标	周转时间、带权周转时间、等待时间、响应时间
调度算法	FCFS、SJF、优先级、HRRN、RR、多级反馈队列
死锁四条件	互斥、请求保持、不可抢占、循环等待
死锁预防	破坏四条件之一（静态策略）
死锁避免	银行家算法——确保每次分配后系统仍处于安全状态
死锁检测	资源分配图化简法
鸵鸟算法	忽略死锁，实际OS的常见做法

📖 参考资料

教材	作者	相关章节
《计算机操作系统》（第4版）	汤小丹	第3章处理机调度与死锁
《操作系统概念》	Silberschatz	CPU调度 & 死锁
《现代操作系统》	Tanenbaum	调度 & 死锁

日记详情

03-处理机调度与死锁

第3章：处理机调度与死锁

3.1 调度的基本概念

3.1.1 三级调度体系 ⭐

3.1.2 调度队列模型

3.1.3 CPU调度时机

3.2 调度算法评价指标

3.3 经典调度算法 ⭐⭐⭐

3.3.1 先来先服务（FCFS）

3.3.2 短作业优先（SJF / SPF）⭐

3.3.3 优先级调度

3.3.4 高响应比优先（HRRN）⭐

3.3.5 时间片轮转（RR）⭐

3.3.6 多级队列调度

3.3.7 多级反馈队列调度 ⭐⭐

3.3.8 调度算法总结对比

3.4 实时调度

3.4.1 实时调度的必要条件

3.4.2 常用实时调度算法

3.5 死锁 ⭐⭐⭐

3.5.1 死锁的定义

3.5.2 产生死锁的四个必要条件 ⭐

3.5.3 资源分配图与死锁检测

3.5.4 死锁的处理策略

3.6 死锁预防 ⭐

3.6.1 破坏四个条件的方法

3.7 死锁避免 ⭐⭐⭐

3.7.1 安全状态

3.7.2 银行家算法 ⭐⭐⭐

3.7.3 银行家算法的两个子算法

3.8 死锁检测与解除

3.8.1 死锁检测

3.8.2 死锁解除

3.9 鸵鸟算法

⭐ 本章小结

📖 参考资料