408 高频考点精讲:银行家算法¶
模块归属:操作系统 · 进程管理
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生
一、 考情档案¶
1. 考查频次与题型分布¶
- 近十年考查频次:3 次(2018 年第 26 题、2020 年第 27 题、2022 年第 26 题)。
- 历年总考查频次:6 次(自 2009 年 408 统考设立以来,先后在 2009 年、2011 年、2014 年、2018 年、2020 年、2022 年多次考查)。
- 主要出题形式:单项选择题(分值稳定为每题 2 分)。在各高校自主命题期末考试、复试笔试以及统考潜在综合应用题中,银行家算法亦是经典的综合大题(8~10 分)考查模型。
2. 命题特点分析¶
- 核心考查切入点:命题高度聚焦于“安全性检测算法”的单步推演与安全序列判定。
- 资源维度的演进趋势:试题考查经历由浅入深的过程。早期偏重单类资源系统的边界推理(如 2018 年第 26 题);中期延伸至二维资源矩阵的计算推导(如 2020 年第 27 题);近期则深入考查三类及以上多维资源系统的分支推演与全安全序列组合计数(如 2022 年第 26 题)。
- 常见失分诱因:
- 回收资源时混淆变量,误将最大需求量 \(\text{Max}\)$ \text{或尚需量} $\(\text{Need}\) 累加入可用向量;
- 忽略已分配资源数为 0 的边界情况(进程执行后系统可用资源无实质增量);
- 向量大小比对未逐分量检验,因某单一资源不足导致误判;
- 混淆“不安全状态”与“死锁状态”的内涵差异。
3. 近十年考查年份分布表格¶
+-------------------+---------------------------------------------------+
| 考试年份 | 考查题号及分值 |
+-------------------+---------------------------------------------------+
| 2016 年 | 未考查 |
| 2017 年 | 未考查 |
| 2018 年 | 第 26 题(单项选择题,2 分) |
| 2019 年 | 未考查 |
| 2020 年 | 第 27 题(单项选择题,2 分) |
| 2021 年 | 未考查 |
| 2022 年 | 第 26 题(单项选择题,2 分) |
| 2023 年 | 未考查 |
| 2024 年 | 未考查 |
| 2025 年 | 未考查 |
+-------------------+---------------------------------------------------+
二、 具体考察内容¶
1. 核心概念与机制原理¶
(1) 死锁处理策略的定位¶
操作系统处理死锁的策略分为四类: 1. 死锁预防(Deadlock Prevention):通过破坏产生死锁的四个必要条件(互斥、占有并等待、不可剥夺、循环等待)之一,从设计机制上杜绝死锁。缺点是资源利用率低。 2. 死锁避免(Deadlock Avoidance):在资源动态分配过程中,利用某种策略监测系统状态,若分配后系统仍处于安全状态则予以分配,否则暂不分配。银行家算法(Banker's Algorithm)是最具代表性的死锁避免算法。 3. 死锁检测(Deadlock Detection):允许死锁发生,系统定时运行死锁检测程序(如通过资源分配图化简),确定是否已产生死锁。 4. 死锁解除(Deadlock Recovery):当检测到死锁发生后,通过资源剥夺、撤销进程等方式解除死锁状态。
(2) 安全状态与不安全状态的精确定义¶
- 安全状态(Safe State):系统能按某种进程推进顺序(如 \(\langle P_1, P_2, \dots, P_n \rangle\)$ \text{)为每个进程分配所需资源,直至满足每个进程的最大资源需求,使每个进程均可顺利运行完成。序列} $\(\langle P_1, P_2, \dots, P_n \rangle\) 称为一个安全序列。若系统存在至少一个安全序列,则系统处于安全状态。
- 不安全状态(Unsafe State):若系统中不存在任何安全序列,则系统进入不安全状态。
- 拓扑包含关系: $$ \text{死锁状态} \subsetneq \text{不安全状态} $$ $$ \text{安全状态} \cap \text{不安全状态} = \emptyset $$
- 安全状态必定不会发生死锁;
- 发生死锁必定处于不安全状态;
- 进入不安全状态并不等价于已经发生死锁。不安全状态仅意味着存在死锁风险,若后续进程在未达到最大需求量前提前释放资源,系统仍有可能脱离不安全状态。
(3) 银行家算法的核心数据结构¶
设系统中有 \(n\)$ \text{个并发进程} $\(\{P_1, P_2, \dots, P_n\}\),\(m\)$ \text{类互斥共享资源} $\(\{R_1, R_2, \dots, R_m\}\)。
- 可利用资源向量 \(\text{Available}[1..m]\): 一维数组,\(\text{Available}[j] = k\)$ \text{表示系统当前现有} $\(R_j\)$ \text{类可用资源} $\(k\) 个。
- 最大需求矩阵 \(\text{Max}[1..n, 1..m]\): \(n \times m\)$ \text{矩阵,} $\(\text{Max}[i, j] = k\)$ \text{表示进程} $\(P_i\)$ \text{对} $\(R_j\)$ \text{类资源的最大总需求数为} $\(k\)。
- 分配矩阵 \(\text{Allocation}[1..n, 1..m]\): \(n \times m\)$ \text{矩阵,} $\(\text{Allocation}[i, j] = k\)$ \text{表示进程} $\(P_i\)$ \text{当前已分配持有的} $\(R_j\)$ \text{类资源数为} $\(k\)。
- 需求矩阵 \(\text{Need}[1..n, 1..m]\): \(n \times m\)$ \text{矩阵,} $\(\text{Need}[i, j] = k\)$ \text{表示进程} $\(P_i\)$ \text{尚需的} $\(R_j\)$ \text{类资源数为} $\(k\)。
(4) 银行家算法与安全性检测算法流程¶
① 资源请求响应(银行家算法主流程)¶
设进程 \(P_i\)$ \text{发出资源请求向量} $\(\text{Request}_i[1..m]\): 1. 边界校验:若 \(\text{Request}_i[j] \le \text{Need}[i, j]\)$ \text{对任意} $\(j \in [1, m]\) 均成立,转步骤 2;否则报错(请求量超出其声明的最大需求)。 2. 容量校验:若 \(\text{Request}_i[j] \le \text{Available}[j]\)$ \text{对任意} $\(j \in [1, m]\)$ \text{均成立,转步骤 3;否则表示当前可用资源不足,} $\(P_i\) 须阻塞等待。 3. 试探性分配:系统假定满足该请求,执行试探性状态变更: $\(\text{Available} = \text{Available} - \text{Request}_i\)$ $\(\text{Allocation}[i] = \text{Allocation}[i] + \text{Request}_i\)$ $\(\text{Need}[i] = \text{Need}[i] - \text{Request}_i\)$ 4. 安全性检测:调用安全性检测算法。若检测结果为安全,则正式将资源分配给 \(P_i\)$ \text{;若检测结果为不安全,则废弃该试探性分配,恢复原数据结构状态,} $\(P_i\) 进入阻塞等待。
② 安全性检测算法(Safety Algorithm)¶
- 初始化辅助向量:
- 工作向量:\(\text{Work} = \text{Available}\)(表示系统当前可分配给进程推进的各类资源量)。
- 完成标志向量:\(\text{Finish}[i] = \text{false} \quad (1 \le i \le n)\)。
- 进程遍历搜索:在未完成进程集合中寻找满足如下条件的进程 \(P_i\): $$ \text{Finish}[i] == \text{false} \quad \text{且} \quad \forall j \in [1, m], \; \text{Need}[i, j] \le \text{Work}[j] $$
- 若找到满足条件的进程 \(P_i\),转步骤 3;
- 若找不到满足条件的进程,转步骤 4。
- 模拟运行与资源回收: 假定进程 \(P_i\) 获得全部所需资源并顺利运行完成,释放其占有的全部资源归还系统: $\(\text{Work} = \text{Work} + \text{Allocation}[i]\)$ $\(\text{Finish}[i] = \text{true}\)$ 将 \(P_i\) 记录至安全序列,返回步骤 2 继续为其余进程寻找推进路径。
- 终止判定:
- 若对所有 \(i \in [1, n]\)$ \text{均有} $\(\text{Finish}[i] == \text{true}\),则判定系统处于安全状态,找到有效安全序列;
- 若存在某个 \(i\)$ \text{使得} $\(\text{Finish}[i] == \text{false}\),则判定系统处于不安全状态。
2. 核心定理推导与计算模型¶
(1) 基础约束方程与资源守恒性¶
在任意合法状态下,系统必须满足以下两组基础代数方程: - 需求代数关系: $\(\text{Need}[i, j] = \text{Max}[i, j] - \text{Allocation}[i, j] \quad (1 \le i \le n, \; 1 \le j \le m)\)$ - 全局资源守恒关系: $\(\text{Total}[j] = \text{Available}[j] + \sum_{i=1}^n \text{Allocation}[i, j] \quad (1 \le j \le m)\)$ 其中 \(\text{Total}[j]\)$ \text{为系统中} $\(R_j\) 类物理资源的总配额。
(2) 工作向量的单调非递减性定理¶
- 定理:在安全性检测算法的执行过程中,工作向量 \(\text{Work}\) 满足逐分量单调非递减性质。
- 推导证明: 设第 \(k\)$ \text{步调度进程} $\(P_i\)$ \text{,更新后的工作向量为} $\(\text{Work}^{(k)}\)$ \text{。由于已分配矩阵各元素非负,即} $\(\forall j \in [1, m], \text{Allocation}[i, j] \ge 0\),故: $\(\text{Work}^{(k)}[j] = \text{Work}^{(k-1)}[j] + \text{Allocation}[i, j] \ge \text{Work}^{(k-1)}[j]\)$ 因此,每有一个进程成功模拟执行,系统的可用资源池容量单调递增(在已分配数为 0 时保持不变),后续进程获得满足的充分条件逐步宽松。
(3) 搜索树与安全序列分支计数模型¶
在算法执行第 \(k\)$ \text{步时,若候选就绪集合} $\(S = \{ P_i \mid \text{Finish}[i] == \text{false} \land \text{Need}[i] \le \text{Work} \}\)$ \text{包含多个元素(} $\(|S| \ge 2\)),则产生搜索分支。 设状态空间树的根节点为初始状态 \((\text{Work}^{(0)}, \text{Finish}^{(0)})\)$ \text{,每个分支代表调度不同进程的演化路径。安全序列的总个数等于该搜索树中深度为} $\(n\) 且到达叶节点的有效路径总数。 若每一步候选集合大小恒为 1,则安全序列唯一;若某一步出现多分支,且各分支均能遍历全部进程,则产生多个合法安全序列。
3. 核心对比辨析¶
表 1:死锁处理策略机制对比¶
| 维度 | 死锁预防 | 死锁避免(银行家算法) | 死锁检测及解除 |
|---|---|---|---|
| 施加时机 | 作业进入前或编译运行前 | 运行中每次资源请求时 | 资源分配后定期检测 |
| 资源限制机制 | 静态破坏死锁四个必要条件 | 动态检测是否保持安全状态 | 不做限制,允许死锁发生 |
| 系统运行时开销 | 极小(无须动态计算) | 较大(每次请求做矩阵比对) | 中等(取决于检测触发周期) |
| 资源利用率 | 极低(易造成资源严重浪费) | 较高(按需动态分配) | 最高(最大化并发度) |
| 典型代表算法 | 一次性分配法、按序分配法 | 银行家算法 | 资源分配图化简、死锁定理 |
表 2:系统运行状态判定对比¶
| 状态特征 | 安全状态 | 不安全状态(非死锁) | 死锁状态 |
|---|---|---|---|
| 安全序列存在性 | 存在至少一条安全序列 | 不存在任何安全序列 | 不存在任何安全序列 |
| 死锁发生的必然性 | 绝无可能发生死锁 | 可能发生死锁,亦可能安全结束 | 已经发生死锁,处于互相等待僵局 |
| 进程推进可能 | 所有进程均可按序顺利完成 | 若后续进程需求减少仍可完成 | 陷入死锁的进程均无法自主推进 |
| 调度器处理措施 | 允许资源分配 | 拒绝试探分配,进程阻塞等待 | 启动解除机制(剥夺资源或终止进程) |
三、 近十年真题精讲(2016~2025)¶
【真题 1】2018 年 408 第 26 题 · 单类资源系统安全性检测与不安全状态判定¶
题目¶
假设系统中有 4 个同类资源,进程 P1、P2 和 P3 需要的资源数分别为 4、3 和 1,P1、P2 和 P3 已申请到的资源数分别为 2、1 和 0,则执行安全性检测算法的结果是( )。
A. 不存在安全序列,系统处于不安全状态
B. 存在多个安全序列,系统处于安全状态
C. 存在唯一安全序列 P3、P1、P2,系统处于安全状态
D. 存在唯一安全序列 P3、P2、P1,系统处于安全状态
【解析】¶
- 知识定位:单类物理资源环境下的安全性检测算法执行与安全状态判别。
- 核心推导步骤:
- 统计资源参数:
- 系统资源总量:\(\text{Total} = 4\)。
- 各进程最大需求量 \(\text{Max}\):\(P_1: 4, \; P_2: 3, \; P_3: 1\)。
- 各进程已分配量 \(\text{Allocation}\):\(P_1: 2, \; P_2: 1, \; P_3: 0\)。
- 系统当前已分配资源总和:\(2 + 1 + 0 = 3\)。
- 当前可用资源量:\(\text{Available} = \text{Total} - \sum \text{Allocation} = 4 - 3 = 1\)。
- 计算尚需资源量 \(\text{Need} = \text{Max} - \text{Allocation}\):
- \(P_1\): \(\text{Need}_1 = 4 - 2 = 2\);
- \(P_2\): \(\text{Need}_2 = 3 - 1 = 2\);
- \(P_3\): \(\text{Need}_3 = 1 - 0 = 1\)。
- 执行安全性检测推导:
- 初始状态:\(\text{Work} = \text{Available} = 1\)。
- 第 1 轮比对:
- \(P_1\): \(\text{Need}_1 = 2 > \text{Work}(1)\),不满足;
- \(P_2\): \(\text{Need}_2 = 2 > \text{Work}(1)\),不满足;
- \(P_3\): \(\text{Need}_3 = 1 \le \text{Work}(1)\),满足条件。 此时只能优先选择 \(P_3\) 进入安全序列。
- 模拟 \(P_3\) 运行完成并释放资源: $\(\text{Work} = \text{Work} + \text{Allocation}_3 = 1 + 0 = 1\)$ 核心陷阱注意:\(P_3\) 此前占有的资源数为 0,其运行完毕释放后,系统可用资源数仍然为 1。
- 第 2 轮比对: 当前 \(\text{Work} = 1\)$ \text{。检查剩余未完成进程} $\(P_1, P_2\):
- \(P_1\): \(\text{Need}_1 = 2 > 1\),无法满足;
- \(P_2\): \(\text{Need}_2 = 2 > 1\),无法满足。 系统无法继续推进任何未完成进程,此时 \(\text{Finish}[1] = \text{false}, \text{Finish}[2] = \text{false}\)。
- 推导结论:系统中无法构建容纳全体进程的完整安全序列,因此不存在安全序列,系统处于不安全状态。
- 选项逐项排查:
- 选项 A 正确:不存在安全序列,系统处于不安全状态。
- 选项 B 错误:算法在此状态下无法推进,不存在任何有效安全序列。
- 选项 C 错误:误以为 \(P_3\)$ \text{释放后可用资源会增多;实际上} $\(P_3\)$ \text{占有数为 0,释放后可用资源仍为 1,无法满足} $\(P_1\) 尚需的 2 个资源。
- 选项 D 错误:同理,\(P_3\)$ \text{释放后可用资源无法满足} $\(P_2\) 尚需的 2 个资源。
正确答案:A
【真题 2】2020 年 408 第 27 题 · 二类资源银行家算法推导与唯一安全序列求解¶
题目¶
某系统中有 A、B 两类资源各 6 个,t 时刻资源分配及需求情况如下表所示。
| 进程 | A 已分配数量 | B 已分配数量 | A 需求总量 | B 需求总量 |
|---|---|---|---|---|
| P1 | 2 | 3 | 4 | 4 |
| P2 | 2 | 1 | 3 | 1 |
| P3 | 1 | 2 | 3 | 4 |
t 时刻安全性检测结果是( )。
A. 存在安全序列 P1、P2、P3
B. 存在安全序列 P2、P1、P3
C. 存在安全序列 P2、P3、P1
D. 不存在安全序列
【解析】¶
- 知识定位:两类互斥共享资源环境下的状态矩阵运算、安全性检测推导与安全序列求解。
- 核心推导步骤:
- 计算当前可用资源向量 \(\text{Available}\):
- 资源总量:\(\text{Total} = (6, 6)\)。
- 已分配资源总量计算:
- A 类资源已分配量:\(\sum \text{Allocation}_A = 2 + 2 + 1 = 5\);
- B 类资源已分配量:\(\sum \text{Allocation}_B = 3 + 1 + 2 = 6\)。
- 当前可用向量: $\(\text{Available} = (6 - 5, \; 6 - 6) = (1, 0)\)$
- 构建尚需矩阵 \(\text{Need} = \text{Max} - \text{Allocation}\):
- \(P_1\): \(\text{Need}_1 = (4 - 2, \; 4 - 3) = (2, 1)\);
- \(P_2\): \(\text{Need}_2 = (3 - 2, \; 1 - 1) = (1, 0)\);
- \(P_3\): \(\text{Need}_3 = (3 - 1, \; 4 - 2) = (2, 2)\)。
- 分步执行安全性检测算法:
- 第 1 步:初始工作向量 \(\text{Work} = \text{Available} = (1, 0)\)。 比对各进程的需求向量 \(\text{Need} \le \text{Work}\):
- \(P_1\): \(\text{Need}_1(2, 1) \not\le (1, 0)\)(A 类、B 类均不足);
- \(P_2\): \(\text{Need}_2(1, 0) \le (1, 0)\)(满足需求);
- \(P_3\): \(\text{Need}_3(2, 2) \not\le (1, 0)\)(A 类、B 类均不足)。 因此,首个执行的进程唯一确定为 \(P_2\)。排除选项 A。
- 第 2 步:模拟 \(P_2\) 运行完毕并释放其占有的全部资源: $\(\text{Work} = \text{Work} + \text{Allocation}_2 = (1, 0) + (2, 1) = (3, 1)\)$ 当前可用资源更新为 \((3, 1)\)$ \text{。比对未完成进程} $\(P_1, P_3\):
- \(P_1\): \(\text{Need}_1(2, 1) \le (3, 1)\)(\(2 \le 3\)$ \text{且} $\(1 \le 1\),满足条件);
- \(P_3\): \(\text{Need}_3(2, 2) \not\le (3, 1)\)(B 类资源需 2 个,当前仅 1 个,不足)。 因此,第二个执行的进程唯一确定为 \(P_1\)。排除选项 C。
- 第 3 步:模拟 \(P_1\) 运行完毕并释放其占有的全部资源: $\(\text{Work} = \text{Work} + \text{Allocation}_1 = (3, 1) + (2, 3) = (5, 4)\)$ 当前可用资源更新为 \((5, 4)\)$ \text{。比对未完成进程} $\(P_3\):
- \(P_3\): \(\text{Need}_3(2, 2) \le (5, 4)\)(\(2 \le 5\)$ \text{且} $\(2 \le 4\),满足条件)。 \(P_3\) 顺利执行完毕。
- 推导结论:系统中所有进程的 \(\text{Finish}\)$ \text{均置为} $\(\text{true}\)$ \text{,得到唯一的安全序列为} $\(\langle P_2, P_1, P_3 \rangle\)。
- 选项逐项排查:
- 选项 A 错误:初始可用资源 \((1, 0)\)$ \text{无法满足} $\(P_1\)$ \text{需求} $\((2, 1)\)。
- 选项 B 正确:安全序列 \(\langle P_2, P_1, P_3 \rangle\) 严格满足每一步可用资源约束。
- 选项 C 错误:\(P_2\)$ \text{完成后可用资源为} $\((3, 1)\)$ \text{,无法满足} $\(P_3\) 对 B 类资源的需求(需 2 个,仅剩 1 个)。
- 选项 D 错误:系统存在有效安全序列,处于安全状态。
正确答案:B
【真题 3】2022 年 408 第 26 题 · 多类资源安全性检测与安全序列分支计数¶
题目¶
系统中有三个进程 P0、P1、P2 及三类资源 A、B、C。若某时刻系统分配资源的情况如下表所示,则此时系统中存在的安全序列的个数为( )。
| 进程 | 已分配资源数 (A, B, C) | 尚需资源数 (A, B, C) | 可用资源数 (A, B, C) |
|---|---|---|---|
| P0 | 2, 0, 1 | 0, 2, 1 | 1, 3, 2 |
| P1 | 0, 2, 0 | 1, 2, 3 | |
| P2 | 1, 0, 1 | 0, 1, 3 |
A. 1
B. 2
C. 3
D. 4
【解析】¶
- 知识定位:三维资源状态下的安全性检测、搜索空间分支判定与安全序列总数枚举。
- 核心推导步骤:
- 整理各进程初始状态矩阵:
- 当前可用向量:\(\text{Available} = (1, 3, 2)\)。
- 已分配矩阵 \(\text{Allocation}\):
- \(P_0\): \((2, 0, 1)\);
- \(P_1\): \((0, 2, 0)\);
- \(P_2\): \((1, 0, 1)\)。
- 尚需矩阵 \(\text{Need}\):
- \(P_0\): \((0, 2, 1)\);
- \(P_1\): \((1, 2, 3)\);
- \(P_2\): \((0, 1, 3)\)。
- 阶段 1:首个进程调度判定:
初始工作向量 \(\text{Work} = (1, 3, 2)\)。逐一比对各进程尚需资源:
- \(P_0\): \(\text{Need}_0(0, 2, 1) \le \text{Work}(1, 3, 2)\)(\(0 \le 1, 2 \le 3, 1 \le 2\),全部分量满足);
- \(P_1\): \(\text{Need}_1(1, 2, 3) \not\le \text{Work}(1, 3, 2)\)(C 类资源需 3 个,当前仅 2 个,超额);
- \(P_2\): \(\text{Need}_2(0, 1, 3) \not\le \text{Work}(1, 3, 2)\)(C 类资源需 3 个,当前仅 2 个,超额)。 因此,首个能够被满足并调度的进程唯一确定为 \(P_0\)。
- 阶段 2:模拟 \(P_0\) 释放资源并更新工作向量: \(P_0\) 运行完成,归还占有的全部资源: $\(\text{Work} = \text{Work} + \text{Allocation}_0 = (1, 3, 2) + (2, 0, 1) = (3, 3, 3)\)$
- 阶段 3:剩余进程比对与分支展开:
当前 \(\text{Work} = (3, 3, 3)\)$ \text{。检查剩余进程} $\(P_1, P_2\):
- \(P_1\): \(\text{Need}_1(1, 2, 3) \le (3, 3, 3)\)(全部分量满足);
- \(P_2\): \(\text{Need}_2(0, 1, 3) \le (3, 3, 3)\)(全部分量满足)。 此时 \(P_1\)$ \text{与} $\(P_2\) 均可作为下一步的执行进程,搜索树在此产生分支:
- 分支路径 1:选择先调度 \(P_1\):
- \(P_1\) 运行结束,释放其占有的资源: $\(\text{Work}' = (3, 3, 3) + \text{Allocation}_1(0, 2, 0) = (3, 5, 3)\)$
- 调度剩余进程 \(P_2\):\(\text{Need}_2(0, 1, 3) \le (3, 5, 3)\),满足条件。
- 形成合法安全序列:\(\langle P_0, P_1, P_2 \rangle\)。
- 分支路径 2:选择先调度 \(P_2\):
- \(P_2\) 运行结束,释放其占有的资源: $\(\text{Work}'' = (3, 3, 3) + \text{Allocation}_2(1, 0, 1) = (4, 3, 4)\)$
- 调度剩余进程 \(P_1\):\(\text{Need}_1(1, 2, 3) \le (4, 3, 4)\),满足条件。
- 形成合法安全序列:\(\langle P_0, P_2, P_1 \rangle\)。
- 推导结论: 系统中存在的有效安全序列仅有以上 2 个,即 \(\langle P_0, P_1, P_2 \rangle\)$ \text{与} $\(\langle P_0, P_2, P_1 \rangle\)。
- 选项逐项排查:
- 选项 A 错误:漏算了 \(P_0\)$ \text{完成后,系统资源充裕使得} $\(P_1\)$ \text{与} $\(P_2\) 可互换顺序调度的分支情况。
- 选项 B 正确:系统中恰好存在 2 个合法安全序列。
- 选项 C 错误:3 个进程的全排列最大为 6 种,本题首位进程固定,后两位至多构成 \(1 \times 2! = 2\) 种排列,不可能出现 3 个。
- 选项 D 错误:若首轮有两个候选进程且次轮均分叉,才可能产生 4 个序列;本题首轮候选唯一。
正确答案:B
四、 综合考法拓展¶
1. 综合大题应用与标准化解题模板¶
在 408 统考综合应用题或名校自主命题大题中,银行家算法属于标准化的“送分题型”。此类题目通常考查对动态请求的判定与安全性表格的规范书写。
综合大题标准设问框架¶
通常题干给出一个系统的资源分配状态,并提出两类问题: 1. 基础状态判断:判断此时系统是否处于安全状态,要求写出安全性检测工作表并给出一个安全序列。 2. 动态请求决策:某时刻某进程 \(P_i\)$ \text{提出请求向量} $\(\text{Request}_i\),问系统能否立即将资源分配给该进程,并说明理由。
五步标准解题模板¶
- 步骤 1:两级边界检查
- 检查 1(自身合理性):判断是否 \(\text{Request}_i \le \text{Need}_i\)。若超额,回答:“不予分配,所请求资源数已超出其声明的最大需求量”。
- 检查 2(系统可用性):判断是否 \(\text{Request}_i \le \text{Available}\)。若不足,回答:“不能立即分配,当前系统可用资源不足,进程须阻塞等待”。
- 步骤 2:试探性分配更新 明确写出三组向量更新结果: $\(\text{Available} = \text{Available} - \text{Request}_i\)$ $\(\text{Allocation}_i = \text{Allocation}_i + \text{Request}_i\)$ $\(\text{Need}_i = \text{Need}_i - \text{Request}_i\)$
- 步骤 3:构建标准安全性检测工作表 在答题纸上画出标准表格,严禁草率心算: | 进程 | Work (工作向量) | Need (尚需资源) | Allocation (已分配) | Work + Allocation (释放后可用) | Finish (完成标志) | | :---: | :---: | :---: | :---: | :---: | :---: | | ... | ... | ... | ... | ... | true |
- 步骤 4:给出推导结论与安全序列 若表格所有行 \(\text{Finish}\)$ \text{均为} $\(\text{true}\)$ \text{,明确写出:“存在安全序列} $\(\langle \dots \rangle\),系统处于安全状态”。
- 步骤 5:最终决策指示 “故系统可以立即满足该进程的资源请求,将资源分配给进程 \(P_i\)$ \text{”。(若不安全,则回答:“系统将进入不安全状态,故不能分配该资源,恢复原状态,进程} $\(P_i\) 等待”)。
2. 跨考点综合脉络¶
(1) 与 PV 操作(信号量机制)的结合考查¶
在进程同步互斥大题中,信号量初值即为系统可用资源数。 - 若进程申请多类互斥资源时出现交叉加锁(例如进程 1 先 \(\text{P}(S_1)\)$ \text{再} $\(\text{P}(S_2)\)$ \text{,进程 2 先} $\(\text{P}(S_2)\)$ \text{再} $\(\text{P}(S_1)\)),极易诱发死锁。 - 银行家算法从分配策略层面提供动态避免机制,要求操作系统在执行等价于 P 操作的分配前,预先进行安全性推演。
(2) 与资源分配图化简(死锁检测)的对比串联¶
- 死锁定理与图化简:针对已经分配完毕的系统静态切片进行“事后检测”。寻找非阻塞且非独立的进程节点,若图最终能完全化简,则无死锁。
- 银行家算法:在资源提出分配申请时进行“事前避免”。必须满足即使进程提出最大需求 \(\text{Max}\),系统依然能够依靠现有资源与释放资源周转完成。
(3) 银行家算法在工程实现中的局限性¶
在现代通用操作系统(如 Linux、Windows)中,内核未直接采用银行家算法作为通用分配机制,原因如下: 1. 进程最大需求 \(\text{Max}\) 难以预知:动态创建的进程其最终执行路径受输入数据影响,无法在创建时精准预报最大资源需求量; 2. 进程数与资源数高度动态化:现代系统支持动态加载、热插拔与高频进程创建退出,固定维度的矩阵维护开销高昂; 3. 算法时间复杂度:安全性检测的时间复杂度为 \(O(m \cdot n^2)\),在实时调度或高并发环境下难以承受频繁计算的延迟开销。
五、 考点速记清单¶
1. 核心要点速记¶
- 状态三环论:安全状态绝无死锁;不安全状态未必死锁;死锁必是不安全状态。
- 安全序列特性:安全序列不唯一;只要找到一条安全序列,即可断定系统处于安全状态。
- 资源回收本质:进程运行完成释放的是已分配资源(\(\text{Allocation}\)$ \text{),而不是需求资源(} $\(\text{Need}\)$ \text{或} $\(\text{Max}\))。
- 零分配陷阱:若某个进程已分配资源为 0(\(\text{Allocation} = 0\)),其执行完毕后不会给系统贡献新的可用资源。
2. 核心计算公式汇总¶
3. 高频避坑指南¶
- 多维向量比较陷阱:比较 \(\text{Need}_i \le \text{Work}\) 时,必须保证每一类资源的分量均小于或等于工作向量的对应分量。只要有一类资源不足,该进程就无法被调度。
- 试探分配回滚意识:在综合题中,若试探分配后安全性检测失败,必须在答题中显式声明“恢复分配前状态,进程阻塞等待”。
- 安全序列分支枚举陷阱:计算安全序列总个数时,切忌盲目套用阶乘公式。必须一步一步根据 \(\text{Work}\) 向量的动态释放值绘制搜索树,统计抵达最终深度的叶节点总数。
4. 408 极速解题口诀¶
算差求尚需,比对可用池;
入列收已配,工作累加积;
多路生分支,全通保安全。