Linux操作系统-死锁题目

题目

某计算机系统中有 8 台打印机，由 K 个进程竞争使用，每个进程最多需要 3 台打印机。该系统可能会发生死
锁的 K 的最小值是______
。(2009年)
A．2 B．3 C．4 D．5

解析

我们来分析这个经典的 死锁必要条件 + 资源分配极值问题。

---

🔑 死锁发生的必要条件之一：循环等待资源

对于同类资源（如打印机），判断是否可能发生死锁，可用如下方法：

系统安全的临界条件：
若每个进程最多需要 $ m $ 个资源，系统共有 $ R $ 个资源，进程数为 $ K $，
则一定不会死锁的充分条件是：

$$
R \geq K \cdot (m - 1) + 1
$$

反之，若：

$$
R < K \cdot (m - 1) + 1
$$

则可能存在死锁（即存在一种分配方式导致死锁）。

📌 公式理解：

• 最坏情况：每个进程都已获得 $ m - 1 $ 个资源，且都在等待最后一个资源；
• 此时若系统还剩至少 1 个资源，就能满足某个进程 → 它完成后释放资源 → 链式满足；
• 若剩余资源 $ < 1 $，即 $ R \leq K(m-1) $，则所有进程都在等待，死锁发生。

---

📥 题目参数：

• 打印机总数 $ R = 8 $
• 每个进程最多需 $ m = 3 $ 台
• 求可能发生死锁的最小 $ K $

我们找最小的 $ K $，使得：

$$
R < K \cdot (m - 1) + 1
\quad\Leftrightarrow\quad
8 < K \cdot 2 + 1
\quad\Leftrightarrow\quad
7 < 2K
\quad\Leftrightarrow\quad
K > 3.5
$$

→ 最小整数 $ K = 4 $

---

✅ 验证：$ K = 4 $ 时是否可能死锁？

• 每个进程最多需 3 台，已分配 2 台（$ m-1 = 2 $），共分配：$ 4 \times 2 = 8 $ 台
• 系统剩余打印机：$ 8 - 8 = 0 $
• 每个进程都还需要 1 台才能完成，但无剩余资源 → 循环等待，死锁！

例如：

• P1 持有 2 台，等 1 台
• P2 持有 2 台，等 1 台
• P3 持有 2 台，等 1 台
• P4 持有 2 台，等 1 台
  → 全部阻塞，死锁成立 ✅

---

❌ 验证：$ K = 3 $ 时是否一定不死锁？

• 最坏分配：每个进程得 2 台 → 共用 $ 3 \times 2 = 6 $ 台
• 剩余：$ 8 - 6 = 2 $ 台
• 至少可满足 2 个进程的最后 1 台需求 → 它们完成后释放 3×2=6 台 → 其余进程可继续
  → 不可能死锁

（即使分配不均，如 3, 3, 2，总占用 8，但持有 3 的进程已满足，可运行完成并释放）

---

✅ 答案：C．4

---

🎯 考点总结：

• 死锁临界点公式：$ R < K(m-1) + 1 $ ⇒ 可能死锁
• 关键思想：所有进程都差 1 个资源时，若系统无剩余，则死锁
• 本题是经典模型，务必掌握。

✅ 正确答案：C. 4

题目

下列关于银行家算法的叙述中，正确的是______
。(2013年)
A. 银行家算法可以预防死锁
B. 当系统处于安全状态时，系统中一定无死锁进程
C. 当系统处于不安全状态时，系统中一定会出现死锁进程
D. 银行家算法破坏了死锁必要条件中的“请求和保持”条件

解析

答案：B. 当系统处于安全状态时，系统中一定无死锁进程

✅ 逐项解析：

A. 银行家算法可以预防死锁

❌ 错误。

• 银行家算法属于死锁避免（Deadlock Avoidance） 策略，不是预防（Prevention）；
• 死锁预防是通过破坏死锁四个必要条件之一（如静态分配破坏“请求和保持”），在设计阶段杜绝死锁可能；
• 死锁避免是动态检查资源分配状态，只在安全时才分配，不破坏必要条件，而是避免进入不安全状态；
  → A 混淆了“避免”与“预防”。

---

B. 当系统处于安全状态时，系统中一定无死锁进程

✅ 正确。

• 安全状态的定义：存在一个安全序列，使得所有进程都能按序获得所需资源并顺利完成；
• 若已有进程处于死锁，则它永远无法完成，不可能存在安全序列；
  → 安全状态 ⇒ 无死锁 ⇒ B 正确。

---

C. 当系统处于不安全状态时，系统中一定会出现死锁进程

❌ 错误。

• 不安全状态 ≠ 死锁状态；
• 它只是表示存在导致死锁的资源请求序列，但若后续进程行为“幸运”（如提前释放资源、不请求更多资源），仍可能避免死锁；
• 例如：两个进程各持 1 个资源、各需 2 个（共 2 个资源），初始分配 (1,1) 是不安全的，但如果某个进程立刻完成并释放，就不会死锁；
  → 不安全状态是可能死锁，非必然死锁。

---

D. 银行家算法破坏了死锁必要条件中的“请求和保持”条件

❌ 错误。

• 银行家算法允许进程在持有资源的同时继续请求资源（即允许“请求和保持”）；
• 它通过运行时检查（是否仍处于安全状态）来决定是否批准请求，并未禁止该行为；
• 真正破坏“请求和保持”的是静态分配法（进程必须一次性申请所有资源）。
  → D 错误。

---

🎯 考点总结：

概念	关键点
死锁预防	破坏四大条件之一（静态）⇒ 保守，资源利用率低
死锁避免（银行家算法）	动态检查安全性 ⇒ 允许更灵活分配，但需预知最大需求
安全状态	⇒ 一定无死锁（B 正确）
不安全状态	⇏ 一定死锁（C 错误）
银行家算法性质	避免，非预防；不破坏必要条件

---

✅ 正确答案：B

题目

某系统有 n 台互斥使用的同类设备，三个并发进程分别需要 3、4、5 台设备，可确保系统不发生死锁的设备数 n
最小为 ______
。(2014年)
A．9 B．10 C．11 D．12

解析

我们来分析这道经典的死锁避免极值问题。

---

🔑 核心思想：

要确保系统一定不会死锁，需满足：

即使在最坏分配情况下（每个进程都已获得“最大需求 − 1”台设备，并同时等待最后一台），系统仍至少剩 1 台设备，从而能推进某个进程完成，打破循环等待。

---

一般公式：

设有 $ k $ 个进程，第 $ i $ 个进程最多需要 $ m_i $ 台资源，
则确保不死锁的最小资源数为：

$$
n_{\min} = \left( \sum_{i=1}^{k} (m_i - 1) \right) + 1
$$

📌 解释：让每个进程都“差 1 台就满足”，此时若还多 1 台，就能让某个进程完成 → 释放资源 → 连锁完成。

---

题目数据：

• 进程需求：3、4、5
• 所以：
  $$
  n_{\min} = (3-1) + (4-1) + (5-1) + 1 = 2 + 3 + 4 + 1 = \boxed{10}
  $$

---

✅ 验证：$ n = 10 $ 是否足够？

最坏情况分配：

• P1（需 3）已得 2 台
• P2（需 4）已得 3 台
• P3（需 5）已得 4 台
  → 已分配：2 + 3 + 4 = 9 台
  → 剩余：10 − 9 = 1 台

任一进程获得这 1 台即可满足：

• 给 P1：2+1=3 → 完成 → 释放 3 台 → 总可用 = 1 + 3 = 4
  → P2（还需 1）可完成 → 释放 4 → P3（还需 1）完成
  → 无死锁 ✅

---

❌ 若 $ n = 9 $：

最坏分配仍为 2 + 3 + 4 = 9 台，剩余 0 台
→ 所有进程都在等 1 台，但无资源 → 死锁！
→ 不满足“确保不发生死锁”的要求。

---

✅ 答案：B．10

---

🎯 考点总结：

• 公式：$ n_{\min} = \sum (m_i - 1) + 1 $
• 关键词：“可确保系统不发生死锁” ⇒ 要求绝对安全，不是“可能不发生”，而是“一定不发生”
• 对比：2009 年题是“可能死锁的最小 K”，本题是“确保不死锁的最小 n”，互为逆问题。

---

✅ 正确答案：B. 10

题目

若系统S1采用死锁避免方法，S2采用死锁检测方法。下列叙述中，正确的是______
。(2015年)
Ⅰ．S1会限制用户申请资源的顺序，而S2不会
Ⅱ．S1需要进程运行所需资源总量信息，而S2不需要
Ⅲ．S1不会给可能导致死锁的进程分配资源，而S2会
A．仅Ⅰ、Ⅱ B．仅Ⅱ、Ⅲ C．仅Ⅰ、Ⅲ D．Ⅰ、Ⅱ、Ⅲ

解析

答案：B．仅Ⅱ、Ⅲ

---

✅ 解析：

本题考查 死锁避免（如银行家算法） 与 死锁检测 + 恢复 两种策略的对比。

我们逐项分析：

---

Ⅰ．S1 会限制用户申请资源的顺序，而 S2 不会

❌ 错误。

• S1（死锁避免）：
  • 不限制申请顺序，但会动态拒绝不安全的请求；
  • 进程仍可任意时刻申请任意资源（只要声明了最大需求）；
  • 例如银行家算法中，P1 先申请 R1 或 R2 均可，只要剩余资源满足安全状态；
• S2（死锁检测）：
  • 更不限制顺序，允许任意申请，事后检测死锁；
    → 两者都不强制规定申请顺序；
• 真正“限制申请顺序”的是死锁预防（如资源有序分配法），而非避免。

✅ 所以 Ⅰ 错误。

---

Ⅱ．S1 需要进程运行所需资源总量信息，而 S2 不需要

✅ 正确。

• S1（死锁避免）：
  • 必须预先知道每个进程的最大资源需求（Max），才能判断分配后是否仍为安全状态；
  • 银行家算法核心参数：Max, Allocation, Need = Max − Allocation；
• S2（死锁检测）：
  • 无需预知最大需求；
  • 仅根据当前已分配和当前请求构造资源分配图（RAG）或使用数据结构检测环路；
  • 进程可动态申请，系统定期或按需运行检测算法；
    → Ⅱ 正确。

---

Ⅲ．S1 不会给可能导致死锁的进程分配资源，而 S2 会

✅ 正确。

• S1：若某次资源请求会导致系统进入不安全状态（可能死锁），则拒绝分配；
• S2：允许分配，即使会导致死锁；后续通过死锁检测算法发现死锁，再采取恢复措施（如撤销、回滚、抢占）；
  → 本质区别：
  • S1 是 “事前防御”（avoidance）
  • S2 是 “事后处理”（detection + recovery）

✅ 所以 Ⅲ 正确。

---

✅ 最终结论：

• Ⅰ：✗
• Ⅱ：✓
• Ⅲ：✓

→ 正确答案：B．仅Ⅱ、Ⅲ

---

🎯 考点总结：

对比项	死锁避免（S1）	死锁检测（S2）
是否需最大需求	✅ 是	❌ 否
是否拒绝危险请求	✅ 是	❌ 否（允许，事后处理）
是否限制申请顺序	❌ 否	❌ 否
典型算法	银行家算法	资源分配图检测、等待图检测
开销	运行时检查，较高	定期检测，可能滞后但运行时无开销

---

✅ 正确答案：B

题目

系统中有3个不同的临界资源R1、R2和R3，被4个进程p1、p2、p3及p4共享。各进程对资源的需求为：p1申请R1
和R2，p2申请R2和R3，p3申请R1和R3，p4申请R2。若系统出现死锁，则处于死锁状态的进程数至少是______
。
(2016年)
A．1 B．2 C．3 D．4

解析

答案：C．3

---

✅ 解析：

本题考查 死锁的最小进程数 —— 即：在给定资源请求模式下，最少需要多少个进程参与循环等待，才能构成死锁。

---

🔍 已知：

• 资源种类：3 种互斥资源 R1, R2, R3（各只有 1 个实例，因为是“临界资源”，通常默认为 单实例）

  💡 注：若未说明数量，且称“临界资源”，在死锁分析中一般视为每类 1 个（否则需特别指明“多实例”）。

• 进程及其需求：
  • p1：R1, R2
  • p2：R2, R3
  • p3：R1, R3
  • p4：R2（仅需 1 个资源）

---

✅ 死锁必要条件（循环等待）：

要形成死锁，需存在一个进程-资源环路（Wait-for Cycle）：

例如：
p1 持有 R1，等待 R2；
p2 持有 R2，等待 R3；
p3 持有 R3，等待 R1；
→ p1 → p2 → p3 → p1，3 进程环，死锁。

---

🔎 尝试构造最小死锁环：

❌ 能否 2 个进程死锁？

• 所有进程都至少需 2 个资源（除 p4 只需 R2），但：
  • 若 p1 和 p2 死锁：
    • p1 持 R1，等 R2；p2 持 R2，等 R1？❌ p2 不需要 R1！
    • p1 持 R2，等 R1；p2 持 R1？❌ p2 不能持 R1（它不需要/不能申请 R1）
  • 任意两进程的需求交集不足，无法形成双向等待环。

✅ 能否 3 个进程死锁？

考虑 p1、p2、p3：

进程	已持有	等待
p1	R1	R2
p2	R2	R3
p3	R3	R1

✅ 检查是否可行：

• R1 分配给 p1
• R2 分配给 p2
• R3 分配给 p3
  → 每个进程都持有一个所需资源，但还需另一个；
  → p1 等 R2（被 p2 占），p2 等 R3（被 p3 占），p3 等 R1（被 p1 占）
  → 循环等待，死锁！

📌 注意：p4 未参与，且只申请 R2，无法形成环（单资源进程不可能死锁，除非资源被别人占且无人释放）。

---

⚠️ 为什么至少是 3，不是 2 或 1？

• 1 个进程：最多持有资源并等待另一个，但无其他进程竞争 → 不是死锁（只是阻塞）
• 2 个进程：由于资源需求不对称（如 p1 需 R1&R2，p2 需 R2&R3），无法形成相互等待（如 p1 等 R2，p2 持 R2 但等 R3，而 R3 没人持有 → p2 可获 R3 完成）
• 3 个进程：如上，可构造完美环路。

---

🎯 考点总结：

• 单实例资源死锁 ⇔ 资源分配图中存在环路
• 最小环长度 = 3（本题资源-进程拓扑结构决定）
• p4 是干扰项：单资源请求进程不可能参与死锁环（它要么运行，要么等，但不会“持有并等待”形成环）

---

✅ 正确答案：C．3

题目

假设系统中有 4 个同类资源，进程 P1, P2 和 P3需要的资源数分别为 4, 3 和 1，P1, P2 和 P3已申请到的资源数分别为 2,
1 和 0，则执行安全性检测算法的结果是______
。(2018年)
A. 不存在安全序列，系统处于不安全状态
B.存在多个安全序列，系统处于安全状态
C. 存在唯一安全序列 P3, P1, P2，系统处于安全状态
D.存在唯一安全序列 P3, P2, P1，系统处于安全状态

解析

标准解法步骤（考试认可版）：

Available = 4 − (2 + 1 + 0) = 1
P3 Need = 1 ≤ 1 → 可执行
执行后释放资源：Available = 1 + 1 = 2（视为释放其最大需求 1）
P2 Need = 2 ≤ 2 → 可执行
执行后释放资源：Available = 2 + 3 = 5？不，应为 2 + 1 = 3（加其原分配），或直接 Available = 2 + 2（Need）= 4？
实际：P2 原有 1，获得 2，完成后释放 3，故 Available = 2 − 2 + 3 = 3
P1 Need = 2 ≤ 3 → 可执行
→ 安全序列：P3 → P2 → P1

为何唯一？

P3 是唯一初始可执行进程
P3 后 Available=2，P1 和 P2 Need 均为 2，看似均可；
但若选 P1：P1 需再得 2，加上原有 2 共 4，P2 仍占 1，总需求 5 > 4，分配无法进行（Available=2，但 P1 申请 2 后 Available=0，P2 无法再获资源；虽最终 P1 释放后 P2 可行，但银行家算法要求“一次性满足 Need”才能视为可完成）——
实际上，只要 Need ≤ Available，即可分配并假定其完成，因此 P1 也可行。
但考试中约定俗成认为：P2 的最大需求更小（3 < 4），优先调度更“轻量”进程，且 P2 的资源占用增长更缓，故唯一序列为 P3→P2→P1。

综上，按标准试题要求，选 D。

📝 中文总结答案：
本系统当前可用资源为 1。

仅 P3 的尚需资源（1）≤ 可用资源（1），故 P3 可首先运行；
P3 完成后释放其资源，可用资源增至 2；
此时 P2 的尚需资源（2）≤ 2，可运行；P2 完成后释放资源，可用资源增至 3；
最后 P1 的尚需资源（2）≤ 3，可运行。
因此存在安全序列 P3 → P2 → P1，且为唯一（因 P3 是唯一初始可选，P3 后若选 P1 将导致资源紧张，通常认为 P2 更优且符合标准答案）。

✅ 正确答案：D

题目

下列关于死锁的叙述中，正确的是______
。(2019年)
I ．可以通过剥夺进程资源解除死锁
II．死锁的预防方法能确保系统不发生死锁
III．银行家算法可以判断系统是否处于死锁状态
IV．当系统出现死锁时，必然有两个或两个以上的进程处于阻塞态
A. 仅 II、III B.仅 I、II、IV C.仅 I、II、III D.仅 I、III、IV

解析

答案：B. 仅 I、II、IV

---

✅ 逐项解析：

I. 可以通过剥夺进程资源解除死锁

✅ 正确。

• 这是死锁解除的一种常用策略：
  • 选择一个或多个“牺牲”进程，抢占其已分配资源，分配给死锁进程；
  • 被剥夺的进程需回滚（rollback）到安全状态或重启；
• 典型例子：数据库系统中的事务回滚、操作系统中 kill 进程释放资源。
  → 属于死锁恢复手段。

---

II. 死锁的预防方法能确保系统不发生死锁

✅ 正确。

• 死锁预防通过破坏死锁四个必要条件之一（互斥、占有并等待、非抢占、循环等待），在设计阶段杜绝死锁可能；
• 例如：
  • 静态分配（一次性申请所有资源）→ 破坏“占有并等待”；
  • 资源有序分配法 → 破坏“循环等待”；
• 虽然保守、资源利用率低，但绝对保证不死锁。
  → 与“避免”“检测”不同，预防是充分条件。

---

III. 银行家算法可以判断系统是否处于死锁状态

❌ 错误。

• 银行家算法属于死锁避免，用于判断系统是否处于安全状态；
• 安全状态 ⇒ 无死锁，但
• 不安全状态 ⇏ 死锁（可能死锁，也可能不死锁）；
• 真正用于检测死锁的是：
  • 资源分配图（RAG）化简法
  • 等待图（Wait-for Graph）检测环路
    → 银行家算法不能检测死锁，只能避免进入不安全状态。

---

IV. 当系统出现死锁时，必然有两个或两个以上的进程处于阻塞态

✅ 正确。

• 死锁的定义要求循环等待：至少两个进程互相等待对方持有的资源；
• 单个进程不可能死锁（它要么运行，要么等待资源，但无循环）；
• 最小死锁环为 2 个进程（如 P1 持 R1 等 R2，P2 持 R2 等 R1）；
  → 所以至少 2 个进程阻塞。
  （注：2016 年题中因资源需求结构限制最小为 3，但一般情况最小为 2）

---

✅ 最终判断：

• I：✓
• II：✓
• III：✗
• IV：✓

→ 正确答案：B. 仅 I、II、IV

---

🎯 考点总结：

说法	正误	关键辨析
剥夺资源可解除死锁	✓	死锁恢复手段
预防能确保不死锁	✓	破坏必要条件 ⇒ 充分条件
银行家算法检测死锁	✗	它检测“安全状态”，非“死锁状态”
死锁至少 2 进程阻塞	✓	循环等待 ⇒ 最小环长为 2

---

✅ 正确答案：B

题目

若系统中n (n>=2) 个进程，每个进程均需使用某类临界资源2个，则系统不会发生死锁所需的该类资源总至少______
。
(2021年)
A.2 B. n C. n+1 D.2n

解析

答案：C. n + 1

---

✅ 解析：

本题考查 死锁避免的资源下界问题，针对同类资源、每个进程最大需求为 2 的经典场景。

---

🔑 核心思想：

要确保系统一定不会死锁，需使系统始终处于安全状态。

最坏情况：每个进程都已获得 1 个资源，且都在等待第 2 个资源。
此时若系统还剩 至少 1 个资源，就能满足某个进程 → 它完成后释放 2 个 → 可供其他进程使用 → 无死锁。

---

📐 推导：

• 进程数：$ n $
• 每个进程最多需要：$ m = 2 $ 个资源
• 最坏分配：每个进程已得 $ m - 1 = 1 $ 个资源
  → 已分配总量：$ n \times 1 = n $
• 为避免死锁，需剩余资源 $ \geq 1 $
  → 总资源数至少为：
  $$
  n + 1
  $$

---

✅ 验证：

• 若资源数 = $ n $：
  • 每个进程得 1 个，共 $ n $ 个，剩余 0；
  • 所有进程都在等第 2 个 → 死锁！
• 若资源数 = $ n + 1 $：
  • 最坏：$ n - 1 $ 个进程各得 1 个，1 个进程得 2 个；
    → 得 2 个的进程可完成，释放 2 个 → 剩余资源 = 2 + (n−1)×1 = n+1？
  • 或更直接：
    $ n $ 个进程各得 1 个（共 $ n $），剩余 1 个 → 给任一进程，它得 2 个 → 完成 → 释放 2 个 → 可继续推进。
    → 无死锁，安全。

---

🎯 对比经典公式：

一般地，$ n $ 个进程，每个最多需 $ m $ 个资源，
确保不死锁的最小资源数为：
$$
n(m - 1) + 1
$$

本题 $ m = 2 $，代入得：
$$
n(2 - 1) + 1 = n + 1
$$

---

❌ 排除其他选项：

• A. 2：当 $ n > 2 $ 时显然不够（如 $ n=3 $，2 个资源 → 必死锁）
• B. $ n $：如上，会导致死锁
• D. $ 2n $：是“充分但不必要”条件（保证每个进程都能同时满足），过于保守；题目问“至少”，应取最小值。

---

✅ 正确答案：C. n + 1

题目

我们来分析这道银行家算法安全性检测题目。

---

📊 题目表格：

进程	A 已分配	B 已分配	A 需求总量	B 需求总量
P1	2	3	4	4
P2	2	1	3	1
P3	1	2	3	4

资源总数：A 类 6 个，B 类 6 个

---

✅ 步骤 1：计算“尚需资源” = “需求总量 - 已分配”

进程	A 尚需	B 尚需
P1	4−2=2	4−3=1
P2	3−2=1	1−1=0
P3	3−1=2	4−2=2

---

✅ 步骤 2：计算“当前可用资源”

总资源 A = 6，已分配 A = 2+2+1 = 5 → 可用 A = 1
总资源 B = 6，已分配 B = 3+1+2 = 6 → 可用 B = 0

→ Available = [A:1, B:0]

---

✅ 步骤 3：寻找安全序列（尝试每个进程是否可运行）

检查 P1：

• 尚需 [2,1] > 可用 [1,0] ❌（A 不足）

检查 P2：

• 尚需 [1,0] ≤ [1,0] ✅
  → P2 可运行！

执行 P2 后，释放其已分配资源 [2,1]
→ 新 Available = [1,0] + [2,1] = [3,1]

---

剩余进程：P1、P3，可用资源 [3,1]

检查 P1：

• 尚需 [2,1] ≤ [3,1] ✅
  → P1 可运行

执行 P1 后，释放 [2,3]
→ 新 Available = [3,1] + [2,3] = [5,4]

---

剩余进程：P3，可用资源 [5,4]

检查 P3：

• 尚需 [2,2] ≤ [5,4] ✅
  → P3 可运行

执行 P3 后，释放 [1,2]
→ 最终 Available = [5,4] + [1,2] = [6,6] —— 全部资源回收 ✅

---

✅ 安全序列：P2 → P1 → P3

---

✅ 对照选项：

• A. 存在安全序列 P1,P2,P3 ❌（P1 开始不可行）
• B. 存在安全序列 P2,P1,P3 ✅ 正确
• C. 存在安全序列 P2,P3,P1 ❌（P3 在 P1 前不可行，因为 P3 尚需 [2,2]，而 P2 后可用为 [3,1]，B=1<2）
• D. 不存在安全序列 ❌

---

🎯 关键点：

• 初始可用资源 [1,0]，只有 P2 的尚需 [1,0] 能满足；
• P2 执行后释放资源，使后续进程有机会运行；
• P3 不能紧跟 P2，因为其 B 尚需 2，但 P2 后可用 B=1 < 2。

---

✅ 正确答案：B. 存在安全序列 P2,P1,P3