银行家算法详细计算：安全性检测、资源分配、死锁避免

文章目录前言摘要一、从银行家算法计算题出错说起二、银行家算法数据结构2.1 基本数据结构2.2 计算Need矩阵三、安全性检测算法3.1 安全性检测步骤3.2 查找安全序列技巧四、资源请求算法4.1 资源请求处理4步骤4.2 资源请求完整模拟五、银行家算法计算技巧5.1 手工计算技巧5.2 资源请求判断技巧六、银行家算法总结6.1 核心要点6.2 考研408重点前言银行家算法是408操作系统死锁避免的必考计算题。如何判断系统是否处于安全状态安全序列如何找资源请求如何处理试探性分配如何回退理解安全性检测的完整流程、Need矩阵的计算、Work向量的更新、安全序列的查找顺序、资源请求算法的四步检查才能掌握死锁避免计算的本质。摘要从银行家算法计算题频繁出错问题出发剖析银行家算法的核心计算方法。通过Available向量的资源统计、Max矩阵的最大需求、Allocation矩阵的已分配、Need矩阵的仍需资源、Work向量的模拟分配、Finish数组的完成标记揭秘安全性检测的完整计算逻辑。配合详细手工模拟给出408满分解题的透彻理解。一、从银行家算法计算题出错说起周四上午哈吉米做408死锁避免计算题场景1安全性检测做错题目 系统有3类资源A、B、C数量分别为10、5、7 当前状态 Allocation Max Available A B C A B C A B C P0 0 1 0 7 5 3 3 3 2 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矩阵算错 2. Work向量更新错 3. 找不到安全序列 4. 步骤混乱哈吉米“银行家算法步骤太多容易算错。”南北绿豆“需要标准化的计算流程——先算Need再找安全序列。”场景2资源请求处理出错题目接上 P1请求资源Request(1, 0, 2) 能否分配 哈吉米的错误 1. 忘记检查Request ≤ Need 2. 忘记检查Request ≤ Available 3. 试探性分配后没有安全性检测 4. 不知道如何回退哈吉米“资源请求算法有4步检查容易漏步骤。”阿西噶阿西“银行家算法要严格按步骤不能跳步。”二、银行家算法数据结构2.1 基本数据结构南北绿豆“银行家算法用5个数据结构。”数据结构定义假设 n个进程P0-P4 m种资源A、B、C 数据结构 1. Available可用资源向量 长度m的向量 Available[i]资源i的可用数量 2. Max最大需求矩阵 n×m矩阵 Max[i][j]进程i对资源j的最大需求 3. Allocation已分配矩阵 n×m矩阵 Allocation[i][j]进程i已分配的资源j数量 4. Need仍需资源矩阵 n×m矩阵 Need[i][j]进程i还需要的资源j数量 Need[i][j] Max[i][j] - Allocation[i][j] 5. Work工作向量 长度m的向量 模拟分配过程中的可用资源 初始Work Available数据结构关系关系公式 1. Need Max - Allocation 2. Allocation Need Max 3. ΣAllocation Available 系统资源总数哈吉米“Need矩阵要用Max减Allocation计算。”2.2 计算Need矩阵Need矩阵详细计算给定 Allocation Max A B C A B C 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 3Need计算表进程Need[A]Need[B]Need[C]计算过程P0743(7-0, 5-1, 3-0)P1122(3-2, 2-0, 2-0)P2600(9-3, 0-0, 2-2)P3011(2-2, 2-1, 2-1)P4431(4-0, 3-0, 3-2)完整Need矩阵 Need A B C P0 7 4 3 P1 1 2 2 P2 6 0 0 P3 0 1 1 P4 4 3 1验证Need矩阵检查Need Allocation Max P0(7,4,3) (0,1,0) (7,5,3) ✓ P1(1,2,2) (2,0,0) (3,2,2) ✓ P2(6,0,0) (3,0,2) (9,0,2) ✓ P3(0,1,1) (2,1,1) (2,2,2) ✓ P4(4,3,1) (0,0,2) (4,3,3) ✓ 全部正确 ✓南北绿豆“Need矩阵计算是第一步必须准确。”三、安全性检测算法3.1 安全性检测步骤安全性检测5步骤步骤1初始化 Work Available Finish[i] false所有进程 步骤2查找进程 找到满足条件的进程i - Finish[i] false - Need[i] ≤ Work 步骤3模拟分配 Work Work Allocation[i] Finish[i] true 记录进程i到安全序列 步骤4重复 重复步骤2、3 步骤5判断 if (所有Finish[i] true): 系统安全 ✓ 输出安全序列 else: 系统不安全 ❌安全性检测详细计算初始数据 Available (3, 3, 2) Allocation Need A B C A B C P0 0 1 0 7 4 3 P1 2 0 0 1 2 2 P2 3 0 2 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1逐步检测表步骤Work检查进程Need≤Work?选择Finish安全序列初始(3,3,2)---全false[]1(3,3,2)P0(7,4,3)≤(3,3,2)?✗--(3,3,2)P1(1,2,2)≤(3,3,2)?✓P1true[P1]2(5,3,2)P0(7,4,3)≤(5,3,2)?✗-[P1](5,3,2)P2(6,0,0)≤(5,3,2)?✗-[P1](5,3,2)P3(0,1,1)≤(5,3,2)?✓P3true[P1,P3]3(7,4,3)P0(7,4,3)≤(7,4,3)?✓P0true[P1,P3,P0]4(7,5,3)P2(6,0,0)≤(7,5,3)?✓P2true[P1,P3,P0,P2]5(10,5,5)P4(4,3,1)≤(10,5,5)?✓P4true[P1,P3,P0,P2,P4]结果 所有Finish true ✓ 系统安全 安全序列P1 → P3 → P0 → P2 → P4Work向量更新详解为什么Work Work Allocation 模拟进程执行完成 进程获得Need资源 → 执行 → 完成后释放所有资源Allocation → Work增加 ✓ 例子 P1完成前 Work (3,3,2) P1持有(2,0,0) P1完成后 释放(2,0,0) Work (3,3,2) (2,0,0) (5,3,2) ✓哈吉米“Work向量模拟了进程完成后释放资源。”3.2 查找安全序列技巧查找顺序优化技巧优先选择Need小的进程 原因 Need小的进程容易满足 → 容易找到安全序列 例子 Work (3,3,2) P1: Need (1,2,2) ← Need小优先选择 P4: Need (4,3,1) ← Need大后选择 先满足P1 → Work增加 → 更容易满足其他进程 ✓可能有多个安全序列系统状态 Work (5,3,2) P1: Need (1,2,2) ✓可以 P3: Need (0,1,1) ✓也可以 安全序列不唯一 序列1P1 → P3 → ... 序列2P3 → P1 → ... 都是合法的安全序列 ✓ 题目要求 给出一个安全序列 → 任意一个即可找不到安全序列的情况场景 Work (1, 0, 0) 所有进程的Need P0: (2, 1, 0) P1: (1, 1, 1) P2: (3, 0, 0) 检查 P0: (2,1,0) ≤ (1,0,0)? ✗ P1: (1,1,1) ≤ (1,0,0)? ✗ P2: (3,0,0) ≤ (1,0,0)? ✗ 没有进程能满足 ❌ → 无安全序列 → 系统不安全南北绿豆“找到一个进程能满足就继续找不到任何进程就不安全。”四、资源请求算法4.1 资源请求处理4步骤请求处理流程进程Pi请求资源Request[i] 步骤1检查请求合法性 if (Request[i] Need[i]): 错误超过最大需求 拒绝 步骤2检查资源是否足够 if (Request[i] Available): 等待资源不足 步骤3试探性分配 Available Available - Request[i] Allocation[i] Allocation[i] Request[i] Need[i] Need[i] - Request[i] 步骤4安全性检测 执行安全性算法 步骤5判断结果 if (系统安全): 正式分配 ✓ else: 恢复原状态 ❌ Available Available Request[i] Allocation[i] Allocation[i] - Request[i] Need[i] Need[i] Request[i] 进程等待资源请求详细计算示例题目 在前面安全状态下P1请求资源Request(1, 0, 2) 当前状态 Available (3, 3, 2) P1: Allocation (2, 0, 0) Need (1, 2, 2)请求处理计算表步骤检查/操作计算结果1. 合法性Request ≤ Need?(1,0,2) ≤ (1,2,2)✓2. 资源够Request ≤ Available?(1,0,2) ≤ (3,3,2)✓3. 试探分配Available Available - Request(3,3,2) - (1,0,2) (2,3,0)-Allocation[P1] Allocation Request(2,0,0) (1,0,2) (3,0,2)-Need[P1] Need - Request(1,2,2) - (1,0,2) (0,2,0)-试探分配后的新状态 Available (2, 3, 0) Allocation Need A B C A B C P0 0 1 0 7 4 3 P1 3 0 2 0 2 0 ← 变化 P2 3 0 2 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1步骤4安全性检测轮次Work检查进程Need≤Work?选择Work更新安全序列初始(2,3,0)----[]1(2,3,0)P1(0,2,0)≤(2,3,0)?✓(5,3,2)[P1]2(5,3,2)P3(0,1,1)≤(5,3,2)?✓(7,4,3)[P1,P3]3(7,4,3)P0(7,4,3)≤(7,4,3)?✓(7,5,3)[P1,P3,P0]4(7,5,3)P2(6,0,0)≤(7,5,3)?✓(10,5,5)[P1,P3,P0,P2]5(10,5,5)P4(4,3,1)≤(10,5,5)?✓(10,5,7)[P1,P3,P0,P2,P4]结果 找到安全序列P1 → P3 → P0 → P2 → P4 ✓ 步骤5正式分配 系统安全 → 同意P1的请求 保持试探分配的新状态如果不安全的情况假设P1请求Request(0, 2, 0) 步骤1-3试探分配 Available (3,3,2) - (0,2,0) (3,1,2) 安全性检测 Work (3,1,2) 检查P0(7,4,3) ≤ (3,1,2)? ✗ 检查P1(1,0,2) ≤ (3,1,2)? ✓ 分配P1Work (3,1,2) (2,0,0) (5,1,2) 检查P0(7,4,3) ≤ (5,1,2)? ✗ 检查P2(6,0,0) ≤ (5,1,2)? ✗ 检查P3(0,1,1) ≤ (5,1,2)? ✓ 分配P3Work (5,1,2) (2,1,1) (7,2,3) 检查P0(7,4,3) ≤ (7,2,3)? ✗B不够 检查P2(6,0,0) ≤ (7,2,3)? ✓ ... 假设最终找不到安全序列 ❌ 步骤5回退 撤销试探分配 恢复原状态 P1等待阿西噶阿西“不安全就回退保证系统始终处于安全状态。”4.2 资源请求完整模拟完整请求处理流程图否是否是是否进程Pi请求RequestRequest≤ Need?错误超过最大需求Request≤ Available?进程等待资源不足试探性分配Available - RequestAllocation RequestNeed - Request执行安全性检测找到安全序列?正式分配保持新状态回退恢复原状态分配成功请求处理关键点关键1试探分配前检查 Request ≤ Need不超过需求 Request ≤ Available资源够 关键2试探分配是临时的 先假设分配 检查安全性 不安全则回退 ✓ 关键3安全性检测用新状态 用更新后的Available、Allocation、Need 检查能否找到安全序列 关键4回退要完整 三个向量/矩阵都要恢复 Available Request Allocation - Request Need Request哈吉米“资源请求算法就是加了安全性检测的分配算法。”五、银行家算法计算技巧5.1 手工计算技巧计算流程总结第1步计算Need矩阵 Need Max - Allocation 逐个计算列表展示 第2步初始化Work和Finish Work Available Finish全部false 第3步循环查找 for each 进程: if (Finishfalse Need≤Work): 选中该进程 第4步更新Work Work Work Allocation Finish true 记录到安全序列 第5步重复第3-4步 直到所有Finishtrue或无进程满足 第6步判断结果 全true → 安全输出序列 有false → 不安全画表技巧建议表格格式 步骤 | Work | P0 | P1 | P2 | P3 | P4 | 选择 | 安全序列 -----|------|----|----|----|----|----|----------- 初始 |(3,3,2)| ✗ | ✓ | ✗ | ✗ | ✗ | P1 | [P1] 1 |(5,3,2)| | | | ✓ | | P3 | [P1,P3] 2 |(7,4,3)| ✓ | | | | | P0 | [P1,P3,P0] ... 符号说明 ✓Need≤Work可以选择 ✗NeedWork不满足 空已完成Finishtrue常见错误及避免错误原因避免方法Need算错减法错误列表逐项计算验证NeedAllocationMaxWork更新错加法错误明确写出WorkWorkAllocation漏检进程遗漏某进程用表格逐个打勾顺序错误NeedWork仍选择每次明确检查Need≤Work南北绿豆“用标准表格逐步填写避免出错。”5.2 资源请求判断技巧快速判断方法技巧1先看资源够不够 if (Request Available): 直接判断等待 ✓ 无需试探分配 技巧2检查是否明显不安全 试探分配后 if (新Available很小 剩余Need都很大): 大概率不安全 技巧3优先级检查 先满足Need小的进程 → 如果它们都满足不了 → 不安全请求判断示例题目 P4请求Request(3, 3, 0) 当前Available (3, 3, 2) 快速判断 Request (3,3,0) Available (3,3,2) Request ≤ Available? ✓ 刚好够 试探分配 新Available (0,0,2) 检查所有Need P0: (7,4,3) ≤ (0,0,2)? ✗ P1: (1,2,2) ≤ (0,0,2)? ✗ P2: (6,0,0) ≤ (0,0,2)? ✗ P3: (0,1,1) ≤ (0,0,2)? ✗ P4: (1,3,1) ≤ (0,0,2)? ✗假设 没有任何进程满足 ❌ → 明显不安全 → 不需要详细计算 ✓阿西噶阿西“掌握技巧快速判断节省时间。”六、银行家算法总结6.1 核心要点南北绿豆总结数据结构Available、Max、Allocation、Need、Work、FinishNeed计算Need Max - Allocation安全性检测查找满足Need≤Work的进程更新Work重复安全序列所有进程Finishtrue的执行顺序资源请求4步检查合法性、资源够、试探分配、安全性检测不安全处理回退试探分配进程等待6.2 考研408重点阿西噶阿西必考题型 ✓ 计算Need矩阵 ✓ 安全性检测找安全序列 ✓ 资源请求能否分配 ✓ 判断系统是否安全 ✓ 画出安全性检测过程表 必记公式 ✓ Need[i][j] Max[i][j] - Allocation[i][j] ✓ Work Work Allocation[i]进程i完成后 ✓ 初始Work Available 必记要点 ✓ 安全状态存在安全序列所有进程能完成 ✓ 不安全状态不存在安全序列 ✓ 安全序列所有进程按某顺序执行都能完成 ✓ 查找条件Finish[i]false Need[i]≤Work ✓ Work更新Work Work Allocation[i] ✓ 资源请求Request≤Need且Request≤Available ✓ 试探分配临时修改状态检测安全性 计算步骤安全性检测 1. 计算Need Max - Allocation 2. 初始化WorkAvailableFinish全false 3. 找进程iFinish[i]false Need[i]≤Work 4. Work Work Allocation[i]Finish[i]true 5. 重复3-4直到全true或无进程满足 6. 全true→安全否则不安全 计算步骤资源请求 1. 检查Request ≤ Need不超需求 2. 检查Request ≤ Available资源够 3. 试探分配三个数据结构更新 4. 安全性检测 5. 安全→分配不安全→回退 典型考题 题给定系统状态和Need矩阵判断是否安全 答 画表列出每步Work、检查的进程、选择结果 例如 Work(3,3,2) P1: Need(1,2,2)≤(3,3,2) ✓ 选P1 Work(5,3,2) P3: Need(0,1,1)≤(5,3,2) ✓ 选P3 ... 所有进程Finishtrue 安全序列P1→P3→P0→P2→P4 系统安全哈吉米“掌握了银行家算法详细计算408死锁避免的计算题就完全拿下了。”参考资料《操作系统概念》第9版- Abraham Silberschatz《现代操作系统》第4版- Andrew S. Tanenbaum《计算机操作系统》第4版- 汤小丹408统考大纲 - 操作系统部分