软考高项必学:银行家算法,用真题案例搞定资源调度题

    今天咱们就用2018年5月的这道真题，把银行家算法的核心逻辑、解题步骤和考试技巧讲透，保证看完就能上手做题。

    题目：阅读下列说明，回答问题1至问题3，将解答填入答题纸的对应栏内。某项目由P1、P2、P3、P4、P5五个活动组成，五个活动全部完成之后项目才能够完成。每个活动都需要用到R1、R2、R3三种互斥资源，三种资源都必须达到活动的资源需求量，活动才能开始。已分配资源只有在完成本活动后才能被其他活动所用。

    目前项目经理能够调配的资源有限，R1、R2、R3的可用资源数分别为9、8、5。活动对资源的需求量、已分配资源数和各活动历时见下表(假设各活动之间没有依赖关系):

【问题1】

基于以上案例，简要叙述最优的活动步骤安排。

【问题2】

基于以上案例，请计算项目的完工时间(详细写出每个活动开始时间、占用资源和完成时间，以及项目经理分配资源的过程)。

【问题3】在制订项目计划的过程中，往往受到资源条件的限制，经常采用资源平衡和资源平滑方法，请简要描述二者的区别。

一、先搞懂：银行家算法到底在解决什么问题？

    你可以把系统想象成一个「资源银行」，手里有固定数量的R1、R2、R3三种资源（就像现金），而P1~P5这五个活动就是「来借钱的客户」。

    每个客户都会提前说：「我最多需要借多少（Max）」，现在已经借了多少（Allocation），还需要多少（Need）。银行家算法的核心就是：在资源有限的情况下，找出一种「借钱顺序」，让每个客户最后都能借够钱、把事办完，最后把钱全还回来，不会出现「谁也借不到钱、谁也还不了钱」的死锁局面。

    对应到软考里，就是：在资源受限的项目里，怎么安排活动执行顺序，让所有活动都能完成，项目总工期最短。

二、先算清账：拿到题先做这两步

    不管题目怎么变，第一步永远是「算清楚家底」，这是所有计算的基础。

 第一步：算「还需要多少资源」（Need）

    公式只有一个：还需要的 = 最多要的 - 已经拿到的，也就是：Need = Max - Allocation

    咱们拿真题数据来算一遍（直接看表格里的「资源需求」就是Max，「已分配资源数」就是Allocation）：

小技巧：算的时候逐行逐列减，别搞反顺序，高项里这一步算错后面全白搭。

   第二步：算「银行还剩多少资源」（Available）

    系统总资源是固定的：R1=9，R2=8，R3=5。先把所有活动已经拿走的资源加起来，再用总资源去减：

● 已分配R1总和：1+2+2+1+1 = 7

● 已分配R2总和：2+1+0+2+1 = 6

● 已分配R3总和：1+1+0+0+3 = 5

    所以银行剩余资源：Available = (9-7, 8-6, 5-5) = (2, 2, 0)

三、核心解题：怎么找「最优执行顺序」？

    银行家算法的核心就是找安全序列——也就是「先让谁干活，后让谁干活」，让所有活动都能拿到足够资源做完。

    核心逻辑：找「能喂饱的活动」，喂饱了就把它的资源收回来

    一句话总结步骤：

    ● 看当前剩余资源（Available），能喂饱哪个活动（它的Need ≤ Available）；

    ● 让这个活动先干活，干完后把它已经拿到的所有资源都还给银行；

    ● 银行资源变多了，再去喂下一个活动；

    ● 重复直到所有活动都喂饱。

    咱们用真题一步步推：

    初始状态

    剩余资源：(2, 2, 0)，还没完成的活动：P1、P2、P3、P4、P5

 第一轮找能喂饱的活动：

    逐个看Need和剩余资源对比：

    ● P1：(5,2,0) → 5>2，喂不饱

    ● P2：(0,2,0) → 0≤2、2≤2、0≤0，能喂饱

    ● P3：(6,0,1) → 6>2，喂不饱

    ● P4：(2,0,0) → 2≤2、0≤2、0≤0，能喂饱

    ● P5：(0,3,1) → 3>2，喂不饱

    先选P2（也可以选P4，顺序不唯一）：

    ● 让P2先干3周，干完后把它的资源(2,1,1)全还回来

    ● 剩余资源更新：(2+2, 2+1, 0+1) = (4, 3, 1)

第二轮找能喂饱的活动：

    剩余资源：(4, 3, 1)，还没完成的活动：P1、P3、P4、P5

    逐个对比：

    ● P1：(5,2,0) → 5>4，喂不饱

    ● P3：(6,0,1) → 6>4，喂不饱

    ● P4：(2,0,0) → 2≤4、0≤3、0≤1，能喂饱

    ● P5：(0,3,1) → 3≤3、1≤1，能喂饱

选P4：

    ● 让P4干2周，干完还资源(1,2,0)

● 剩余资源更新：(4+1, 3+2, 1+0) = (5, 5, 1)

第三轮找能喂饱的活动：

剩余资源：(5, 5, 1)，还没完成的活动：P1、P3、P5

逐个对比：

● P1：(5,2,0) → 5≤5、2≤5、0≤1，能喂饱

● P3：(6,0,1) → 6>5，喂不饱

● P5：(0,3,1) → 0≤5、3≤5、1≤1，能喂饱

先让P1干1周（也可以先干P5）：

● 干完还资源(1,2,1)

● 剩余资源更新：(5+1, 5+2, 1+1) = (6, 7, 2)

  第四轮找能喂饱的活动：

剩余资源：(6, 7, 2)，还没完成的活动：P3、P5

逐个对比：

● P5：(0,3,1) → 完全能喂饱

● P3：(6,0,1) → 6≤6、0≤7、1≤2，能喂饱

先让P5干4周，干完还资源(1,1,3)：

● 剩余资源更新：(6+1, 7+1, 2+3) = (7, 8, 5)

最后一轮：只剩P3

P3的Need=(6,0,1)，剩余资源(7,8,5)完全够，让P3干3周，干完还资源，所有活动都完成。

最终得到的安全序列（示例）

P2 → P4 → P1 → P5 → P3（也可以是P2→P4→P5→P1→P3等，只要逻辑对都算对）

四、回到真题：项目工期怎么算？

结合上面的顺序，咱们把每个活动的时间线理清楚：

● P2和P4可以并行，从第0周开始，P4在第2周结束，P2在第3周结束；

● 第3周后，资源释放，P1和P5开始并行；

● P1在第4周结束，释放资源后P3开始，和P5并行到第7周一起结束。

项目总完工时间：7周

五、高项考试：这些坑千万别踩！

● 算错Need：一定要记牢「还需要的 = 最多要的 - 已经拿到的」，别搞反成「已经拿到的 - 最多要的」；

● 资源回收错：活动干完后，要把已经分配给它的所有资源都还回来，不是只还「还需要的那部分」；

● 比较逻辑错：判断能不能喂饱，是每一类资源都要满足「Need ≤ 剩余资源」，不是只看某一类；

● 安全序列唯一误区：安全序列不只有一种，只要能让所有活动都干完的顺序都是对的，考试时不用纠结顺序；

● 忽略并行：高项里这类题经常要考虑「哪些活动可以同时干」，别傻乎乎按顺序一个个排，会把工期算长。

六、写在最后

银行家算法在软考高项里，其实就是「算清楚账→找能喂饱的活动→回收资源→重复」的循环，没有想象中那么复杂。

只要你把这道真题的逻辑吃透，考试时遇到同类题，照着这个步骤一步步算，肯定能拿到分。

    最近陆陆续续开始各地区发布报名通知了，我们也会持续关注这些通知，并滚动更新这个报名时间这个栏目，大家记得关注自己所在地区的报名时间，每年总有那么几位同学忘记报名的，要注意啦！今天四川开始报名了！河北千呼万唤，终于出来报名通知了，至此，全国各地区的报名通知全部都出来了！

    这里再给大家说一下，很多同学都在问某个地区的报名时间没看到通知，然后过来问我们具体的通知地址，其实大家可以直接到软考报名官网查看，入口都已经给出来了！比如广东地区：

    这个地址我也给大家再发一下：

https://bm.ruankao.org.cn/sign/welcome

  其他注意事项：提前准备好登记照、证明材料、身份认证，尽早提交报名申请，预留充足的审核时间。关注审核结果，通过后，记得及时缴纳考试费！！！

    全国报名统一官网：中国计算机技术职业资格网 www.ruankao.org.cn

    登记照准备：白色背景，jpg格式。

    软考报名可能需要提供报考地（省市）个人所属证明材料：

    1、居住证明，由当地公安部门出具，或当地电子版居住证明，可能有居住时限要求，大家需要提前准备好；
    2、所在考区的当地户口簿/身份证的照片或扫描件；
    3、所在考区的当地近6个月社保证明，需盖有社保局公章；（最常用）
    4、在校考生报考需要提供学生证或者本校出具的学生在籍证明；
    5、符合【单独划线】申报条件的报考人员此次可能还需要在报名同时提交单独划线申请或证明材料。

    上面提及的证明材料，报名时可能只需提供1种即可。有的地区只认工作社保证明，有的地区只认工作所在地，有的地区无归属地要求，可单独划线的地区请大家仔细阅读报考地公示的文件要求，以最新公布的为准。

    根据统一安排，考生须先在“国家网络身份认证”APP上完成实名认证（需要手机具备NFC功能），认证成功后，使用“国家网络身份认证”APP右上角扫码功能扫描报名系统上的二维码完成登录。

1

扫

我