【操作系统】银行家算法（安全序列判定）

考点频率★★★★★计算题必考每年下午题或选择题中至少出现一次难度⭐⭐⭐⭐建议把“安全序列判定”理解成“模拟进程运行小游戏”按照固定步骤逐步推导不要跳步1️⃣ 安全序列判定的目标银行家算法的核心目标就是避免系统进入不安全状态。而判定系统是否处于安全状态的工具就是“安全序列判定”。安全序列一个进程的执行顺序如 P1 → P3 → P0 → P2 → P4使得系统按照这个顺序依次让每个进程运行完毕每个进程在运行时都能获得它所需的全部资源。判定目标给定当前系统状态包括 Available、Allocation、Max判断是否存在这样一个安全序列。如果存在说明系统当前是安全的可以继续分配资源如果不存在说明系统将处于不安全状态应避免分配。2️⃣ 数据结构回顾在进行判定之前先明确四个核心矩阵/向量数据结构含义Available可用资源当前系统中每类资源还剩多少个可用Max最大需求每个进程总共需要多少资源才能执行完毕Allocation已分配每个进程当前已经占用了多少资源Need仍需资源每个进程完成执行还需要多少资源计算公式Need Max - Allocation注意Need是判定过程中的核心比较对象必须用 Max 减去 Allocation千万不能直接用 Max。3️⃣ 安全序列判定的标准步骤初始化设置Work Available当前可用资源设置Finish[i] false所有进程均未完成标记为 false查找满足条件的进程遍历所有未完成的进程找到一个进程Pi满足Need[i] Work即当前可用资源能完全满足该进程的剩余需求模拟释放若找到则假定该进程运行完毕释放其占用的所有资源Work Work Allocation[i]将该进程标记为完成Finish[i] true将Pi记录到安全序列中循环迭代重复步骤2-3直到某轮遍历找不到任何满足条件的进程为止判定结论若所有进程的Finish都为true则系统处于安全状态上述记录的顺序就是安全序列否则系统处于不安全状态不存在安全序列4️⃣ 完整计算示例软考典型题题目某系统中有三类资源 A、B、C总资源数分别为(10, 5, 7)。当前系统中有 5 个进程 P0 ~ P4其 Allocation 和 Max 如下表进程Allocation已分配Max最大需求P0(0, 1, 0)(7, 5, 3)P1(2, 0, 0)(3, 2, 2)P2(3, 0, 2)(9, 0, 2)P3(2, 1, 1)(2, 2, 2)P4(0, 0, 2)(4, 3, 3)问题请问当前系统是否存在安全序列若存在请写出一个安全序列。第1步计算 Need 矩阵Need Max - Allocation进程Need还需P0(7, 4, 3)P1(1, 2, 2)P2(6, 0, 0)P3(0, 1, 1)P4(4, 3, 1)第2步计算 Available当前可用资源已分配资源总量 将所有 Allocation 按列相加A 类02320 7B 类10010 2C 类00212 5总资源数 - 已分配总量 AvailableAvailable (10-7, 5-2, 7-5) (3, 3, 2)第3步执行安全性检查逐轮模拟Work (3, 3, 2)Finish [false, false, false, false, false]轮次查找过程结果第1轮遍历所有进程找Need[i] (3,3,2)- P0: (7,4,3) ≤ (3,3,2)❌- P1: (1,2,2) ≤ (3,3,2)✅3≥1, 3≥2, 2≥2选中P1。Work (3,3,2) (2,0,0) (5,3,2)Finish[1]true。安全序列P1第2轮继续遍历从未完成的找- P0: (7,4,3) ≤ (5,3,2)❌- P2: (6,0,0) ≤ (5,3,2)❌65- P3: (0,1,1) ≤ (5,3,2)✅选中P3。Work (5,3,2) (2,1,1) (7,4,3)Finish[3]true。安全序列P1 → P3第3轮继续遍历- P0: (7,4,3) ≤ (7,4,3)✅正好相等选中P0。Work (7,4,3) (0,1,0) (7,5,3)Finish[0]true。安全序列P1 → P3 → P0第4轮继续遍历- P2: (6,0,0) ≤ (7,5,3)✅- P4: (4,3,1) ≤ (7,5,3)✅注这里存在两个可选进程任意选择一个均可银行家算法只要求找到一条安全序列不要求唯一若先选P2Work (7,5,3) (3,0,2) (10,5,5)Finish[2]true。安全序列P1 → P3 → P0 → P2第5轮最后只剩 P4(4,3,1) ≤ (10,5,5)✅选中P4。Work (10,5,5) (0,0,2) (10,5,7)Finish[4]true。安全序列P1 → P3 → P0 → P2 → P4结论所有进程 Finish 均为 true系统处于安全状态一个安全序列为P1 → P3 → P0 → P2 → P4。注如果在第4轮先选 P4也能得到另一个合法安全序列 P1 → P3 → P0 → P4 → P2。只要存在任一安全序列系统就是安全的。5️⃣ 常见易错点软考丢分重灾区易错点正确理解直接用 Max 与 Work 比较必须用Need Max - Allocation因为进程已经持有了一部分资源完成进程后忘记释放已分配资源Work Work Allocation不是Work Work Need某轮没找到进程就立刻判定不安全通常从头开始重新遍历因为 Work 变化后之前不满足条件的进程可能变成满足条件软考中推荐每轮从头遍历多个进程同时满足时随便选一个可以随便选因为只要存在安全序列任意选择都能导向安全状态但如果一个选择导致死胡同可以回溯尝试另一个这是算法正确性保证——在实际做题时选任意一个能继续的即可不会出现“选错导致错误结论”的情况认为不安全状态就是死锁不安全状态 ≠ 死锁只是系统处于高风险区有可能发生死锁6️⃣ 经典例题选择题题目某系统当前可用资源 Available (2, 1)进程 P1 的 Need (2, 1)Allocation (0, 0)。若系统采用银行家算法则以下判定正确的是 。A. 系统一定安全B. 系统一定不安全C. 无法判定需要看其他进程的状态D. 系统处于死锁解析安全序列判定必须检查所有进程能否依次完成。只知道 P1 一个进程的状态无法确定系统是否安全。如果其他进程占用了大量资源且无法释放系统仍可能不安全。选C。7️⃣ 记忆口诀安全判定四步走Work 等于 AvailableNeed 小于等于 Work 才能走。模拟释放 Work 加Finish 标记为真够。全部 Finish 才算安全中途停滞就是不安全。8️⃣ 小测验评论区对答案假设上一题第4节中系统当前状态不变P2 发出请求Request (1, 0, 0)。银行家算法在试分配后执行安全序列判定时Available变为多少是否存在安全序列本专栏日更2篇点击头像 → 专栏《软考中级高频考点》订阅第一时间接收新内容#软考中级 #软件设计师 #银行家算法 #安全序列 #死锁避免 #操作系统