多资源银行家算法:从一道三资源题理清请求处理的两道关卡

操作系统课学到死锁避免,课件给了一道多资源银行家算法题:三类资源 R1=10、R2=5、R3=7,五个进程 P0–P4。题目分四问,前两问是常规的安全性和请求判断,后两问考理解深度。做第 1 问时还算顺利,但第 2、3 问一开始没看懂题在问什么——"P1 请求 (1,0,2)"到底是哪个表变了?这篇文章记录从困惑到理清的过程,以及最终形成的完整认识。

题目与初始数据

进程AllocationMaxNeed
P0(0,1,0)(7,5,3)(7,4,3)
P1(2,0,0)(3,2,2)(1,2,2)
P2(3,0,2)(9,0,2)(6,0,0)
P3(2,1,1)(2,2,2)(0,1,1)
P4(0,0,2)(4,3,3)(4,3,1)

已分配 (7,2,5),Available = (10,5,7) − (7,2,5) = (3,3,2)。Need = Max − Allocation 按分量算。

我的困惑在哪

第 1 问安全性检查我会做:找一个 Need ≤ Work 的进程先跑,释放资源,继续找。序列 P1→P3→P2→P4→P0,Work 轨迹 (3,3,2)→(5,3,2)→(7,4,3)→(10,4,5)→(10,4,7)→(10,5,7),安全。

但第 2 问"P1 请求 (1,0,2)"让我卡住了。我当时的理解是:Available 直接从 (3,3,2) 减去请求变成新值?那请求到达时,Allocation、Need 这些表哪个在变?

后来才明白,我把两件事混在一起了:请求的到来和试分配的假想。

请求处理算法的两道关卡

银行家算法其实分两半,课件里往往只强调前半(安全性算法),但请求处理才是它的日常工作。

关卡 1:合法性检查。Request 要同时满足:

  • Request ≤ Need_i:没超出自己声明的剩余需求,否则违规
  • Request ≤ Available:手头有这么多空闲资源,否则让它等

关卡 2:试分配 + 重跑安全性。假设先给了,算三个新值:

Available'    = Available − Request
Allocation_i' = Allocation_i + Request
Need_i'       = Need_i − Request

然后对这个假想状态重跑安全性算法:安全→真批准;不安全→撤销,请求挂起等待。

关键区分:请求到达时三张表一个都不改,试分配只是草稿纸上的"假设"。安全才真的改表,不安全就当没发生过。

第 2 问:P1 请求 (1,0,2)

关卡 1 两个比较都过。试分配:

  • Available’ = (3,3,2) − (1,0,2) = (2,3,0)
  • Allocation₁’ = (2,0,0) + (1,0,2) = (3,0,2)
  • Need₁’ = (1,2,2) − (1,0,2) = (0,2,0)

对假想状态 Work = (2,3,0) 重跑:

步骤进程Need新 Work
1P1(0,2,0)(5,3,2)
2P3(0,1,1)(7,4,3)
3P2(6,0,0)(10,4,5)
4P4(4,3,1)(10,4,7)
5P0(7,4,3)(10,5,7)

末行恰好回到总量,批准。

第 3 问:P4 请求 (3,3,0)(独立场景)

Need₄ = (4,3,3) − (0,0,2) = (4,3,1),关卡 1 通过。试分配:

  • Available’ = (3,3,2) − (3,3,0) = (0,0,2)
  • Need₄’ = (4,3,1) − (3,3,0) = (1,0,1)

对 Work = (0,0,2) 检查所有进程:P0 (7,4,3) ✗、P1 (1,2,2) ✗、P2 (6,0,0) ✗、P3 (0,1,1) ✗、P4’ (1,0,1) ✗。全都不满足,无安全序列 → 撤销,P4 挂起。

为什么"空闲够"不够

同一 Available (3,3,2):

  • P1 拿走 (1,0,2) 剩 (2,3,0)——还有余地,五个进程能排完全部跑完
  • P4 拿走 (3,3,0) 剩 (0,0,2)——几乎掏空,所有人的 Need 都塞不进去

请求合法 + 空闲够,只过了第一关。真正的批准标准是第二关:给了之后,假设所有进程按最坏情况(拿满 Max)来要,系统还能否保证它们全部完成。够"这一次分配"不等于够"保证所有人最终完成"。

不安全 ≠ 死锁

这是我第 3 问结论里的表述问题。我当时写"否则会造成死锁",应该修正为"进入不安全状态,可能造成死锁"。

  • 死锁:进程已经互相持有资源、循环等待,谁都动不了——已发生的事实
  • 不安全:不存在"保证所有进程都能完成"的序列,但此刻并没有死锁;进程未必真按最坏情况走(可能少申请、提前释放)

类比:不安全像站在悬崖边的平台上——还没掉下去,但下一步往哪迈都可能掉下去。银行家的策略是根本不让你站上这个平台,而不是上去之后再想办法。

算术自查的两个习惯

做这道题我犯了两次同类错误,总结出两个自查点:

  1. 不变式:安全序列最后一步 Work 必须恰好等于系统总量 (10,5,7),每行 Work 各分量都不能超过它。我第 1 问草稿末行写 (9,5,7),靠这个发现错了。
  2. 释放的是 Allocation’:试分配后完成的进程,归还的是新占用(如 P1 归还 (3,0,2),不是原来的 (2,0,0))。分量减法也要逐个减,我猜 Available’=(2,3,1) 时 R3 那步 2−2 算成了 1。

复盘

这次最大的收获是分清了两件事:安全性算法是"当前状态能不能找到一条全跑完的路",请求处理算法是"新请求来了要不要现在给"。后者多了试分配这一步——先假设给,看后果,再决定真给不给。

以前对"不安全"的理解比较模糊,以为就是死锁前兆。现在明确:不安全只是"没有保证",不是"已经卡住";银行家宁可保守,也不赌那个"可能不会死锁"。

仍需留意:做题时容易把试分配当成真改表,或者觉得安全序列可以复用。实际上每个请求都改了三张表,必须对假想状态重新推演,没有捷径。

Logo

openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目,面向数字基础设施四大核心场景(服务器、云计算、边缘计算、嵌入式),全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构

更多推荐