第三章处理机调度与死锁

3.1 处理机调度的层次

层次	又称	频率	功能
高级调度（作业调度）	长程调度	最低	从外存后备队列中选择作业调入内存,创建进程
中级调度（内存调度）	中程调度/对换调度	中等	决定哪些进程可参与竞争CPU（挂起/激活）
低级调度（进程调度）	短程调度	最高（最频繁）	从就绪队列中选一个进程分配CPU

⚠️ 低级调度（进程调度）是最基本的调度，任何OS都必须有。多道批处理系统需要高级调度+低级调度，分时系统通常不需要高级调度。

3.2 调度的目标和准则

调度的共同目标

资源利用率高：CPU利用率 = CPU有效工作时间 / 总时间
公平性
平衡性
策略强制执行

不同系统的目标

系统类型	主要目标
批处理	平均周转时间短、吞吐量高、处理机利用率高
分时	响应时间快、均衡性
实时	满足截止时间、可预测性

重要公式⭐

$\bar{T} = \frac{1}{n}\sum_{i=1}^{n}T_i$

其中 $T_i =$ 作业完成时间 $-$ 作业提交时间 = 周转时间

$W_i = \frac{T_i}{T_{si}} \quad \text{（带权周转时间，}T_{si}\text{为实际服务时间）}$

$\bar{W} = \frac{1}{n}\sum_{i=1}^{n}W_i \quad \text{（平均带权周转时间）}$

3.3 调度算法（核心考点⭐⭐⭐）

3.3.1 先来先服务 FCFS

按到达先后顺序调度
非抢占式
对长作业有利，短作业不利
常与其他算法结合使用
既可作业调度,也可进程调度

3.3.2 短作业/进程优先 SJF/SPF

选择估计运行时间最短的作业优先
非抢占式SJF / 抢占式SRTN（最短剩余时间优先）
平均周转时间和平均带权周转时间最小
缺点：①须预知运行时间 ②长作业可能饥饿 ③无法用于交互式系统 ④忽视紧迫性

3.3.3 优先级调度

非抢占式：一旦某进程获得CPU，就一直运行到完成或阻塞
抢占式：有更高优先级进程到达时立即抢占

优先级的类型：

静态优先级：创建时确定，不再改变（依据：进程类型、资源需求、用户要求）
动态优先级：随运行情况动态调整（如等待时间越长优先级越高）

3.3.4 高响应比优先 HRRN

$R_P = \frac{\text{等待时间} + \text{要求服务时间}}{\text{要求服务时间}} = 1 + \frac{\text{等待时间}}{\text{要求服务时间}}$

$R_P$ 最高的优先调度
兼顾短作业和长作业（短作业天然响应比高,长作业等久了响应比也升高）
非抢占式
缺点：每次调度前都要重新计算所有作业的响应比，增加开销

3.3.5 时间片轮转 RR

专门为分时系统设计
所有就绪进程排成FIFO队列，每次分配一个时间片q
q太小 → 上下文切换频繁，开销大
q太大 → 退化为FCFS
q的经验值：略大于一次典型交互的时间

3.3.6 多级队列调度

设置多个就绪队列，不同队列可有不同调度算法和不同优先级
适合多处理机系统

3.3.7 多级反馈队列调度 MLFQ（⭐⭐⭐）

公认的较好的调度算法，兼顾多种类型作业。

算法规则：

设置多个就绪队列，优先级递减，时间片递增
新进程进入第1级队列末尾，按FCFS等待调度
若在当前时间片内未完成，降至下一级队列末尾
仅当第k级队列为空时，才调度第k+1级队列
若有新进程进入较高优先级队列，可抢占当前运行进程

优点：终端型用户（短作业快速响应）、短批处理作业用户（周转时间短）、长批处理作业用户（不会饥饿）都能满足。

3.3.8 公平调度

保证调度：N个进程，每个保证获得1/N的处理机时间。实际/应得比率最小的优先
公平分享调度（FSS）：按用户分配CPU时间，保证用户层面公平

3.4 实时调度

可调度条件

$\sum_{i=1}^{m}\frac{C_i}{P_i} \leq 1 \quad \text{（单处理机）}$

$\sum_{i=1}^{m}\frac{C_i}{P_i} \leq N \quad \text{（N个处理机）}$

其中 $C_i$ = 处理时间， $P_i$ = 周期

实时调度分类

类别	方式	响应时间
非抢占轮转	轮转调度	数秒~数十秒
非抢占优先级	优先级+非抢占	数百ms~数秒
抢占-时钟中断	在时钟中断时抢占	几ms~几十ms
抢占-立即抢占	事件发生立即抢占	几百μs~几ms

最早截止时间优先 EDF

截止时间越早，优先级越高
可用于抢占式/非抢占式
对隐式截止期任务集（ $D_i=P_i$ ），单处理机下 $\sum C_i/P_i \le 1$ 是充要条件
若任务模型不满足 $D_i=P_i$ ，则需结合具体约束（如 $D_i$ 与 $P_i$ 关系、是否可抢占）进一步判定

Rate Monotonic（RM）补充

RM为固定优先级实时调度（周期越短优先级越高）
RM充分条件（不是必要条件）：

$U = \sum_{i=1}^{n}\frac{C_i}{P_i} \le n\left(2^{1/n}-1\right)$

当 $n \to \infty$ 时，上界趋近于 $\ln 2 \approx 0.693$

最低松弛度优先 LLF

$\text{松弛度} = \text{必须完成时间} - \text{剩余运行时间} - \text{当前时间}$

松弛度越小，越紧迫，优先级越高
松弛度=0时必须立即执行
主要用于抢占式调度

优先级倒置问题⭐

问题：高优先级进程被低优先级进程间接阻塞。

典型场景：P1(高)→P2(中)→P3(低)。P3进入临界区持有共享资源；P1需要该资源被阻塞；P2就绪抢占P3运行→P3无法释放资源→P1一直被阻塞。

解决方案：

简单方法：进程进入临界区后，不允许被抢占（缺点：临界区长则影响系统）
动态优先级继承：P3继承P1的高优先级→P2无法抢占P3→P3尽快完成释放资源→P1得以运行

3.5 Linux CFS调度器

调度器类优先级：Stop > Real_Time > Fair > Idle
友好值nice：-20~+19，默认0
虚拟运行时间vruntime：nice值越大，vruntime增长越快；调度时选vruntime最小的
实时调度：SCHED_FIFO / SCHED_RR，静态优先级0-99
普通调度：优先级100-139（对应nice -20~+19）

3.6 死锁（核心考点⭐⭐⭐）

死锁的定义

多个进程因竞争资源而造成的一种互相等待的僵局。

死锁的四个必要条件

条件	说明
互斥条件	资源一次只供一个进程使用
请求和保持条件	进程持有至少一个资源,又请求新资源,但新资源被占用而阻塞,此时不释放已持有的
不可抢占条件	已获得的资源未使用完之前不能被强行夺走
循环等待条件	存在进程-资源的环形等待链

⚠️ 四个条件缺一不可。循环等待是死锁的必要不充分条件（有循环等待不一定死锁,但死锁必有循环等待）

死锁的处理策略

策略	方法
预防	破坏四个必要条件之一(除互斥外)
避免	银行家算法（动态检测安全性）
检测和解除	资源分配图,死锁定理
忽略（鸵鸟策略）	不处理,如UNIX/Linux一般采用

死锁预防

破坏条件	方法	缺点
请求和保持	一次性申请全部资源	资源浪费严重,可能饥饿
不可抢占	请求新资源不满足时释放已有的	实现复杂,可能导致已有工作丢失
循环等待	资源编号,按序申请	资源编号不灵活,可能浪费

银行家算法（⭐⭐⭐核心）

数据结构：

$Available[m]$ ：当前各类资源的可用数量
$Max[n][m]$ ：每个进程对各类资源的最大需求
$Allocation[n][m]$ ：已分配给每个进程的各类资源数量
$Need[n][m]$ ：每个进程还需要的各类资源数量

$Need[i][j] = Max[i][j] - Allocation[i][j]$

安全性算法：

初始化： $Work = Available$ ， $Finish[i] = false$
找满足条件的进程 $P_i$ ： $Finish[i]=false$ 且 $Need[i] \leq Work$
若找到： $Work = Work + Allocation[i]$ ， $Finish[i] = true$ ，转第2步
若不能找到：检查所有 $Finish[i]$ ，若全为true→安全（输出安全序列）；否则→不安全

银行家算法完整数值示例（⭐⭐⭐ 高频大题）

题目：系统有 A、B、C 三类资源，初始可用量为 $(3,3,2)$ 。5个进程当前状态如下：

进程 Max (A,B,C) Allocation (A,B,C) Need (A,B,C)
$P_0$ (7,5,3) (0,1,0) (7,4,3)
$P_1$ (3,2,2) (2,0,0) (1,2,2)
$P_2$ (9,0,2) (3,0,2) (6,0,0)
$P_3$ (2,2,2) (2,1,1) (0,1,1)
$P_4$ (4,3,3) (0,0,2) (4,3,1)

$Available = (10,5,7) - (7,2,5) = (3,3,2)$

求安全序列：

步骤选进程 Work (A,B,C) Need≤Work? 执行后 Work+=Alloc
1 $P_1$ (3,3,2) (1,2,2)≤(3,3,2) ✓ (3,3,2)+(2,0,0)=(5,3,2)
2 $P_3$ (5,3,2) (0,1,1)≤(5,3,2) ✓ (5,3,2)+(2,1,1)=(7,4,3)
3 $P_4$ (7,4,3) (4,3,1)≤(7,4,3) ✓ (7,4,3)+(0,0,2)=(7,4,5)
4 $P_2$ (7,4,5) (6,0,0)≤(7,4,5) ✓ (7,4,5)+(3,0,2)=(10,4,7)
5 $P_0$ (10,4,7) (7,4,3)≤(10,4,7) ✓ (10,4,7)+(0,1,0)=(10,5,7)

✅ 所有进程均可完成 → 安全序列 $\langle P_1, P_3, P_4, P_2, P_0\rangle$

追问：若 $P_1$ 此时请求 $(1,0,2)$ ，能否分配？

试分配： $Available=(3,3,2)-(1,0,2)=(2,3,0)$ ， $Alloc_1=(3,0,2)$ ， $Need_1=(0,2,0)$

再跑安全性算法： $P_1→P_3→P_4→P_2→P_0$ ，仍安全 → 可以分配

进程	Max (A,B,C)	Allocation (A,B,C)	Need (A,B,C)
$P_0$	(7,5,3)	(0,1,0)	(7,4,3)
$P_1$	(3,2,2)	(2,0,0)	(1,2,2)
$P_2$	(9,0,2)	(3,0,2)	(6,0,0)
$P_3$	(2,2,2)	(2,1,1)	(0,1,1)
$P_4$	(4,3,3)	(0,0,2)	(4,3,1)

步骤	选进程	Work (A,B,C)	Need≤Work?	执行后 Work+=Alloc
1	$P_1$	(3,3,2)	(1,2,2)≤(3,3,2) ✓	(3,3,2)+(2,0,0)=(5,3,2)
2	$P_3$	(5,3,2)	(0,1,1)≤(5,3,2) ✓	(5,3,2)+(2,1,1)=(7,4,3)
3	$P_4$	(7,4,3)	(4,3,1)≤(7,4,3) ✓	(7,4,3)+(0,0,2)=(7,4,5)
4	$P_2$	(7,4,5)	(6,0,0)≤(7,4,5) ✓	(7,4,5)+(3,0,2)=(10,4,7)
5	$P_0$	(10,4,7)	(7,4,3)≤(10,4,7) ✓	(10,4,7)+(0,1,0)=(10,5,7)

⚠️ 银行家算法是死锁避免策略，不是死锁预防。它不破坏任何必要条件，而是在每次资源分配前检测安全性。

死锁检测

资源分配图的简化：

找到既不阻塞又不孤立的进程节点 $P_i$ （其请求可被满足）
消去 $P_i$ 的所有边（相当于 $P_i$ 执行完归还资源）
重复直到无法再简化

死锁定理：当且仅当资源分配图不可完全简化时，系统处于死锁状态。

死锁解除

终止进程：终止所有死锁进程 / 逐个终止直到解除死锁
资源剥夺：从死锁进程中抢占资源分配给其他进程
选择终止/剥夺的依据：优先级、已执行时间、已使用资源量、进程性质（交互/批处理）

🎯 本章真题锚点与最短模板

高频题号（2009-2025）：2009Q24/Q25、2010Q26、2011Q23、2014Q23/Q24、2016Q24/Q25、2018Q24/Q26、2019Q27/Q30、2021Q23、2025Q26
优质例题：给出进程到达时间+服务时间，分别按FCFS/SJF/RR计算平均周转时间，并判断是否存在饥饿。
最短解题模板：
1. 先画甘特图（含抢占时刻）。
2. 算每进程完成时刻→周转时间→带权周转时间。
3. 死锁题先写“四必要条件”，再用安全序列/资源分配图做判定。

⚡ 秒杀版口令卡（10秒回忆）

口令：调度先画图，不画必错时刻。
口令：周转=完成-到达，带权=周转/服务。
口令：死锁先四条件，再判安全序列。

第三章 处理机调度与死锁