考点精要：进程管理、前趋图与 PV 操作及死锁避免

MOD-02 操作系统知识考查题号：上午第 23 ~ 26 题 (约 2 ~ 3 分)⭐⭐⭐⭐⭐ 5星必考

🎯 45 分及格通关指引（极简避坑与得分铁律）

【45分必背核心得分点】：
1. 进程三态跃迁两大绝对禁区：
  - 严禁“阻塞态 $\to$ 运行态”：事件完成后只能进入就绪队列，绝不能直接夺取 CPU 运行；
  - 严禁“就绪态 $\to$ 阻塞态”：就绪进程未占有 CPU，不可能发出 I/O 请求或执行 P 操作。
2. 前趋图数边秒杀法（30秒解题）：
  - 入边有几条，开头就要执行几次 $P$ 操作；
  - 出边有几条，结尾就要执行几次 $V$ 操作；
  - 终极口诀：“前 V 后 P，出边发通知执行 V，入边等条件执行 P”。
3. 防死锁极值公式： $m \geq n \cdot (k - 1) + 1$ （ $n$ 个进程，各最大需要 $k$ 个资源，系统至少需 $m$ 个资源绝不发生死锁）。
4. 死锁四策略辨析：
  - 打破四大必要条件之一：死锁预防（如按序申请资源破坏环路等待）；
  - 动态评估安全序列（银行家算法）：死锁避免；安全状态一定不死锁，不安全状态不等于死锁。
【高分选读 / 考场可战略放弃点】：
- 复杂的哲学家进餐多信号量奇偶编号防死锁算法、银行家算法涉及多类资源 4 步以上的大矩阵手工试探推演，上午选择题直接观察剩余资源是否满足某一行进程的 Need 并代入选项排除，切忌从头列大矩阵推演。

一、核心考纲与概念辨析

1. 进程状态流转模型（三态 vs 五态）

正在渲染架构图表...

就绪 $\to$ 运行：处于就绪队列的进程被操作系统进程调度程序选中，分配到 CPU 时间片开始执行；
运行 $\to$ 就绪：分配给当前进程的时间片用完，或系统出现更高优先级的就绪进程抢占了 CPU；
运行 $\to$ 阻塞：进程因请求某项共享资源或等待外部事件（如申请 I/O 设备、读写磁盘、执行 P 操作且信号量 $S < 0$ ）而主动放弃 CPU；
阻塞 $\to$ 就绪：等待的外部事件已完成（如 I/O 操作中断结束、其他进程执行 V 操作释放资源），由系统中断处理程序将其唤醒，移入就绪队列等待调度。
🚨 状态跃迁禁区（命题极高频陷阱）：
1. 严禁“阻塞态 $\to$ 运行态”：处于阻塞态的进程即使等待的事件完成，也只能进入就绪队列排队，绝不可能跨过就绪态直接霸占 CPU 运行！
2. 严禁“就绪态 $\to$ 阻塞态”：就绪态进程并未占用 CPU，绝不会主动发起 I/O 请求或执行 P 操作，因此不可能直接转入阻塞态。

2. 同步、互斥与信号量机制

协作关系	核心特征与定义	生活隐喻场景	信号量设置规范
互斥 (Mutual Exclusion)	多个并发进程在同一时刻只能有且仅有一个进程访问临界资源（排他性访问）	单人试衣间：一人进去上锁，其他人必须在门外等待	设置互斥信号量 `mutex`，初值通常为 1；P/V 操作必须紧密包围在临界区前后
同步 (Synchronization)	多个并发进程因相互合作，在执行次序上必须遵循某种预定的先后时序关系	工厂流水线：A 进程加工完零件后，B 进程才能进行组装装配	设置同步信号量，初值通常为 0（或缓冲区容量 $N$ ）；前驱操作完成后执行 V，后继操作开始前执行 P

信号量 $S$ 的物理意义与原子操作

$S \geq 0$ 时：数值表示当前系统中可用资源的空闲数量；
$S < 0$ 时：其绝对值 $| S |$ 严格等于当前处于该信号量阻塞等待队列中的进程数目。

P 操作（Wait / 请求资源）：

S = S - 1;
if (S < 0) {
    // 资源耗尽，将当前调用进程放入等待队列并挂起阻塞
    block();
}

V 操作（Signal / 释放资源）：

S = S + 1;
if (S <= 0) {
    // 说明此前等待队列中有排队进程，唤醒队列中的一个阻塞进程
    wakeup();
}

二、分析模型与经典演练

1. 前趋图转 PV 操作标准翻译四步法

在前趋图（有向无环图 DAG）中，节点表示并发执行的程序段/进程，有向边 $P_{i} \to P_{j}$ 表示 $P_{i}$ 必须先于 $P_{j}$ 完成。

正在渲染架构图表...

标准翻译算法：

边设信号量：为图中的每一条有向边分配一个独立的同步信号量（如 $P_{1} \to P_{2}$ 设为 $S_{12}$ ， $P_{1} \to P_{3}$ 设为 $S_{13}$ ），初值全部赋为 0；
入边设 P：每个进程在正式开始工作前，必须对其所有入边依次执行 $P$ 操作（入边表示必须等待的前置条件，入边有几条，开头就要执行几次 P 操作）；
出边设 V：每个进程在完成自身工作后，必须对其所有出边依次执行 $V$ 操作（出边表示通知后续节点的触发条件，出边有几条，末尾就要执行几次 V 操作）；
口诀记忆：“前 V 后 P，出边通知执行 V，入边等待执行 P！”

进程	入边数量与前置 P 操作	核心业务动作	出边数量与后置 V 操作
$P_{1}$	无入边，无需等待 P	执行 $P_{1}$ 任务	2 条出边： $V (S_{12}); V (S_{13});$
$P_{2}$	1 条入边： $P (S_{12});$	执行 $P_{2}$ 任务	1 条出边： $V (S_{24});$
$P_{3}$	1 条入边： $P (S_{13});$	执行 $P_{3}$ 任务	1 条出边： $V (S_{34});$
$P_{4}$	2 条入边： $P (S_{24}); P (S_{34});$	执行 $P_{4}$ 任务	无出边，流程收敛

2. 经典生产者-消费者同步互斥模型

设系统有一个容量为 1 的公用单缓冲区，生产者进程不断生产产品放入缓冲区，消费者进程不断从缓冲区取出产品：

设置互斥信号量 mutex = 1：控制对公用缓冲区的互斥读写；
设置同步信号量 empty = 1：表示空缓冲区数量，初值为 1；
设置同步信号量 full = 0：表示满缓冲区数量，初值为 0。

// 生产者进程 Producer
while (true) {
    produce_item();
    P(empty);       // 1. 检查是否有空位置
    P(mutex);       // 2. 进入临界区加锁
    put_to_buffer();
    V(mutex);       // 3. 退出临界区解锁
    V(full);        // 4. 通知消费者：已有产品可取
}

// 消费者进程 Consumer
while (true) {
    P(full);        // 1. 检查是否有产品可取
    P(mutex);       // 2. 进入临界区加锁
    take_from_buffer();
    V(mutex);       // 3. 退出临界区解锁
    V(empty);       // 4. 通知生产者：已有空槽位可放
    consume_item();
}

🚨 P 操作加锁死锁红线

P 操作顺序不可颠倒：必须先 P 同步信号量（empty/full），再 P 互斥信号量（mutex）！若先 P(mutex) 再 P(empty)，当缓冲区已满时生产者获得互斥锁却卡在 P(empty) 处阻塞，导致消费者永远无法获取 mutex 取走物品，直接酿成死锁。

3. 死锁机理、银行家算法与极值计算

① 死锁产生的四大必要条件（缺一不可）

互斥条件：资源同一时刻仅能被一个进程独占访问；
请求与保持条件：进程在持有已有资源的同时，继续请求新资源；
不剥夺条件：进程已获得的资源在未主动释放前，系统不可强行剥夺；
环路等待条件：存在一个循环等待的进程-资源闭环链。

② 应对策略三层辨析

死锁预防：打破四大必要条件之一（如资源静态一次性分配破坏“请求与保持”，资源按序编号分配破坏“环路等待”）。代价高，资源利用率低。
死锁避免：在动态分配资源前执行安全评估，若分配会导致系统进入不安全状态则拒绝分配。典型算法：银行家算法（通过寻找可用安全序列决定是否放行）。
死锁检测与解除：允许死锁发生，定期检测资源分配图（死锁定理），通过撤销进程或剥夺资源解除死锁。

③ 防死锁最少系统资源极值公式

设系统中有 $n$ 个并发进程竞争同类共享资源，每个进程对该资源的最大需求量均为 $k$ 。则系统绝不发生死锁的充分必要条件为系统拥有的总资源数 $m$ 满足：

m \geq n \cdot (k - 1) + 1

极值极端推演法：考虑最坏情况，若每个进程都已被分配了 $k - 1$ 个资源且全都不释放，都在苦等最后一个资源，此时系统已被消耗了 $n \cdot (k - 1)$ 个资源。只要系统多拥有 1 个 资源，就能让其中任意一个进程满足需求运行完毕，执行后归还全部 $k$ 个资源，进而激活后续所有进程，破除僵局。

三、命题题眼与陷阱防御

🚨 常见命题陷阱盘点

前趋图 PV 选项快速秒杀法则：
- 试题给出复杂网络图时，切忌全盘手工推导；
- 直接数入边和出边：某节点只有 1 条出边，末尾必定只有 1 个 $V$ 操作；某节点有 2 条入边，开头必须连续执行 2 个 $P$ 操作。利用出入边数量可瞬间排除 2~3 个干扰选项！
银行家算法中“安全状态”与“死锁”的充要辨析：
- 安全状态一定没有死锁发生；
- 不安全状态并不等同于死锁！不安全状态只是存在死锁的风险，若后续进程实际运行并未索取其声明的最大需求，依然可能平稳度过。
死锁预防 vs 死锁避免的名词偷换：
- 题干问“采用银行家算法属于（）”：选项给出死锁预防、死锁避免、死锁检测、死锁解除。必须果断选死锁避免！
极值资源计算的变量混淆：
- 牢记公式 $m \geq n (k - 1) + 1$ 。出题时可能给出 $m$ 和 $k$ 反求最大允许并发进程数 $n$ ，解不等式时注意整除向下取整，不能盲目四舍五入。

四、典型真题溯源与逐项排错解析 (Distractor Analysis)

【真题精选 1】（考查前趋图信号量 PV 操作配对 · 2024上-机考回忆-Q23~24）

题干：进程 $P_{1}, P_{2}, P_{3}, P_{4}, P_{5}$ 的前趋图如下所示： $P_{1} \to P_{2}$ ， $P_{1} \to P_{3}$ ， $P_{2} \to P_{4}$ ， $P_{3} \to P_{4}$ ， $P_{3} \to P_{5}$ ， $P_{4} \to P_{5}$ 。

正在渲染架构图表...

若用 PV 操作控制这 5 个进程的并发执行，分别设置信号量 $S_{1} \sim S_{6}$ ，初值均为 0。则在进程 $P_{3}$ 中应执行的 PV 操作依次为（ 1 ），在进程 $P_{5}$ 中应执行的操作依次为（ 2 ）。 (1) A. $P (S_{2}); P (S_{3}); V (S_{4}); V (S_{5});$
B. $P (S_{2}); V (S_{4}); V (S_{5});$
C. $V (S_{2}); P (S_{4}); P (S_{5});$
D. $P (S_{2}); P (S_{4}); V (S_{5});$
(2) A. $P (S_{5}); P (S_{6});$
B. $V (S_{5}); V (S_{6});$
C. $P (S_{4}); P (S_{6});$
D. $V (S_{4}); P (S_{6});$

💡 点击展开【正确答案与逐项排错剖析】

【正确答案】：(1) B (2) A
【核心考点】：依据前趋图拓扑结构分析节点入度与出度，掌握“入边等待 P、出边通知 V”的映射规则。
【45分秒杀技巧】：
- 看 $P_{3}$ ：只有 1 条来自 $P_{1}$ 的入边，所以开头只有 1 个 P；有 2 条发往 $P_{4}, P_{5}$ 的出边，所以末尾有 2 个 V。选项中只有 B 是“1个P开头、2个V结尾”，秒杀 (1)！
- 看 $P_{5}$ ：是汇聚终点，有 2 条入边（分别来自 $P_{3}$ 和 $P_{4}$ ），无出边。所以开头必须是 2 个 P 操作 且无 V 操作，秒选 A！
【逐项排错剖析】：
- 第 (1) 题排错：
  - A 选项排除：错误地假设 $P_{3}$ 有 2 条入边执行了 $P (S_{2}); P (S_{3})$ ，违背图的入度为 1 的拓扑事实；
  - B 选项正确：严格遵循前趋图拓扑， $P_{3}$ 等待 $P_{1}$ （1 次 P 操作），完成后分别通知 $P_{4}$ 和 $P_{5}$ （2 次 V 操作）；
  - C 选项排除：颠倒出入边规则，开头误执行 V、结尾误执行 P；
  - D 选项排除：将出边 $S_{4}$ 误写为 P 操作，导致 $P_{3}$ 自身陷入等待，程序死锁。
- 第 (2) 题排错：
  - A 选项正确： $P_{5}$ 必须等待 $P_{3}$ 和 $P_{4}$ 全部结束，执行两次 P 操作 $P (S_{5}); P (S_{6})$ ；
  - B 选项排除：终点节点无后续通知对象，执行 V 操作无法达成前驱约束；
  - C、D 选项排除：信号量编号映射错误且操作方向混杂。

【真题精选 2】（考查并发防死锁资源极值计算 · 2024下-机考回忆-Q25）

题干：某计算机系统中共有 4 个并发进程共同竞争同类互斥共享资源 $R$ 。已知每个进程均需要获得 3 个该资源才能顺利完成工作。为了保证该系统在任何资源分配策略下都绝对不会发生死锁，系统至少需要配置资源 $R$ 的数量为（）。

A. 8
B. 9
C. 10
D. 12

💡 点击展开【正确答案与逐项排错剖析】

【正确答案】：B
【核心考点】：不发生死锁的系统资源临界值计算公式 $m \geq n \cdot (k - 1) + 1$ 。
【45分秒杀技巧】：代入极值公式： $m = 4 \times (3 - 1) + 1 = 4 \times 2 + 1 = 9$ 。或者理解为：每个进程各扣住 2 个资源不放（共耗费 8 个），此时只要系统再多出 1 个资源（共 9 个），就能让任意一个进程顺利跑完，交出全部 3 个资源，秒选 B！
【逐项排错剖析】：
- A 选项排除：配置 8 个资源为最极端危险状态（ $4 \times 2 = 8$ ），每个进程都差 1 个资源且系统无剩余，直接死锁；
- B 选项正确：9 个资源确保在极端死锁临界态（8 个）之上至少富余 1 个可用资源打破僵局，是系统不死锁的最低下限；
- C 选项排除：10 个资源虽然也能避免死锁，但不属于题干要求的“至少”数量，为过度冗余；
- D 选项排除：12 个资源是没有任何并发共享时静态分配的总量（ $4 \times 3$ ），忽视了进程释放资源的复用特性。

【真题精选 3】（考查死锁处理策略分类与实现特征 · 2024下-机考回忆-Q26）

题干：在操作系统中，死锁控制主要有死锁预防、死锁避免、死锁检测和解除四种方法。下列关于死锁控制策略的描述中，正确的是（）。

A. 采用资源静态预分配法破坏请求和保持条件，属于死锁避免策略
B. 采用银行家算法动态分配资源，属于死锁预防策略
C. 规定所有进程对资源的请求必须严格按照资源编号顺序提出，属于死锁预防策略
D. 系统处于不安全状态时，说明系统中已经实际发生了死锁

💡 点击展开【正确答案与逐项排错剖析】

【正确答案】：C
【核心考点】：死锁处理策略归类（预防、避免、检测）与必要条件破坏机制。
【45分秒杀技巧】：只要是破坏死锁四大必要条件之一的（如按序编号分配打破环路等待、一次性预分配打破请求保持），都是死锁预防；而银行家算法是死锁避免。选项 C 准确对应死锁预防，直接秒选。
【逐项排错剖析】：
- A 选项排除：静态预分配是破坏“请求和保持条件”，属于死锁预防，而非死锁避免；
- B 选项排除：银行家算法是在资源动态申请时评估安全性，属于死锁避免，而非死锁预防；
- C 选项正确：按序编号分配（资源顺序分配法）使进程只能按序号递增申请资源，从而在结构上杜绝了环路闭环的可能，破坏了“环路等待条件”，是经典的死锁预防措施；
- D 选项排除：不安全状态并不等同于死锁。不安全状态仅代表存在死锁风险，若后续进程实际运行并未索取其声明的最大需求，系统依然可以安全过渡。

考点精要：进程管理、前趋图与 PV 操作及死锁避免 ​

一、 核心考纲与概念辨析 ​

1. 进程状态流转模型（三态 vs 五态） ​

2. 同步、互斥与信号量机制 ​

信号量 S 的物理意义与原子操作 ​

二、 分析模型与经典演练 ​

1. 前趋图转 PV 操作标准翻译四步法 ​

标准翻译算法： ​

2. 经典生产者-消费者同步互斥模型 ​

3. 死锁机理、银行家算法与极值计算 ​

① 死锁产生的四大必要条件（缺一不可） ​

② 应对策略三层辨析 ​

③ 防死锁最少系统资源极值公式 ​

三、 命题题眼与陷阱防御 ​

四、 典型真题溯源与逐项排错解析 (Distractor Analysis) ​

【真题精选 1】（考查前趋图信号量 PV 操作配对 · 2024上-机考回忆-Q23~24） ​

【真题精选 2】（考查并发防死锁资源极值计算 · 2024下-机考回忆-Q25） ​

【真题精选 3】（考查死锁处理策略分类与实现特征 · 2024下-机考回忆-Q26） ​

考点通关与速查导航 ​

考点精要：进程管理、前趋图与 PV 操作及死锁避免

一、核心考纲与概念辨析

1. 进程状态流转模型（三态 vs 五态）

2. 同步、互斥与信号量机制

信号量 $S$ 的物理意义与原子操作

二、分析模型与经典演练

1. 前趋图转 PV 操作标准翻译四步法

标准翻译算法：

2. 经典生产者-消费者同步互斥模型

3. 死锁机理、银行家算法与极值计算

① 死锁产生的四大必要条件（缺一不可）

② 应对策略三层辨析

③ 防死锁最少系统资源极值公式

三、命题题眼与陷阱防御

四、典型真题溯源与逐项排错解析 (Distractor Analysis)

【真题精选 1】（考查前趋图信号量 PV 操作配对 · 2024上-机考回忆-Q23~24）

【真题精选 2】（考查并发防死锁资源极值计算 · 2024下-机考回忆-Q25）

【真题精选 3】（考查死锁处理策略分类与实现特征 · 2024下-机考回忆-Q26）

考点通关与速查导航