第二十一课死锁预防与死锁避免第一部分先理解银行家算法为什么叫银行家算法来看一个故事。假设你是一家银行。你现在有100万元来了三个客户。A最多需要60万B最多需要40万C最多需要50万注意这里说的是最多需要。不是现在就要。例如今天。A先借30万银行还能借。因为还有70万但是。如果A后来又借30万。B借40万。C借50万。银行是不是一下没钱了如果大家都没完成。没人还钱。银行是不是可能崩所以。银行每借一次钱。都会先想借给你之后我还有没有办法保证所有人最终都能完成如果可以。借。如果不可以。拒绝。这就是银行家算法。第二部分什么叫安全状态教材定义存在一个安全序列使所有进程都能顺利完成。这一句话第一次看。几乎没人懂。我们换成人话。假设三个进程P1 P2 P3资源还剩5如果操作系统发现可以这样安排。P2 ↓ 完成 ↓ 释放资源 ↓ P1 ↓ 完成 ↓ 释放资源 ↓ P3最后三个都能结束。那么现在就是安全状态Safe State注意。不是一起完成。而是存在一种执行顺序。第三部分什么叫安全序列刚才那个顺序。P2 ↓ P1 ↓ P3就是安全序列Safe Sequence所以教材一定会考。区别名称含义安全状态存在至少一个安全序列安全序列一个能够让所有进程完成的执行顺序很多同学会混。第四部分危险状态Unsafe State很多人最容易误解。危险状态是不是已经死锁不是一定记住。危险状态 ≠ 死锁为什么来看。假设现在资源越来越少。已经找不到安全序列。那么现在就是危险状态。但是。如果后面有进程提前释放资源。还是可能恢复。所以危险只是可能死锁。不是一定。口诀安全状态 → 一定不会死锁。危险状态 → 可能死锁但不一定已经死锁。这是考试最爱出的判断题。第五部分死锁预防上一课我们学过死锁发生必须满足四个条件。那最简单怎么办破坏其中一个条件。这就是死锁预防Deadlock Prevention。方法一破坏请求并保持规定所有进程必须一次申请全部资源。例如你要打印机。扫描仪。必须一起申请。不能先拿打印机。再申请扫描仪。这样就不会拿着一个。等另一个。是不是破坏了请求并保持缺点资源利用率低。因为很多资源可能一直空着。方法二破坏不可剥夺规定如果申请失败。已经拿到的资源。全部还回去。以后重新申请。例如已经拿着打印机。申请扫描仪。失败。操作系统直接收回打印机。这样别人可以继续。缺点有些资源不能随便抢。例如打印机已经打印一半。抢走是不是坏了所以不是所有资源都适合。方法三破坏循环等待规定所有资源编号。例如R1 R2 R3 R4规定必须按编号申请。例如可以R1 ↓ R2 ↓ R3不能反过来。于是等待永远不会形成一个圈。教材这一种最喜欢考。第六部分死锁避免预防比较严格。资源利用率低。于是提出避免。思想不是禁止。而是每次申请。先试一试。如果借出去。还能保持安全状态。批准。否则拒绝。这就是银行家算法。第七部分银行家算法流程思想版假设P1申请2个资源。操作系统不会马上给。而是先模拟。假装 已经 给了。然后检查有没有安全序列。如果有。真正分配。如果没有。恢复。拒绝。整个过程像银行审批贷款。第八部分为什么叫避免因为它不是死锁以后解决。而是在发生之前。避免进入危险状态。所以叫Deadlock Avoidance死锁避免第九部分预防 vs 避免★★★★★这是考试最喜欢考的表格。项目死锁预防死锁避免思想破坏四个必要条件不进入危险状态是否限制申请很严格较灵活资源利用率较低较高是否需要知道最大需求不需要需要最后一行一定记住。银行家算法必须知道每个进程最多需要多少资源。否则怎么模拟第十部分口诀★★★★★预防破坏条件避免进入危险银行家先模拟 后分配一句口诀预防靠破坏避免靠判断先试再分配安全才批准。第十一部分本课重点必须掌握✅ 安全状态存在安全序列。✅ 安全序列一种能让所有进程完成的执行顺序。✅ 危险状态可能死锁不等于已经死锁。必须会区分状态是否一定死锁安全状态❌ 一定不会死锁危险状态❌ 不一定死锁死锁状态✅ 已经死锁必须知道死锁预防破坏四个必要条件。死锁避免银行家算法。第二十二课银行家算法计算题一、先认识四张表银行家算法一定会给你四组数据。例如进程MaxAllocationP073P152P232还有Available 3很多同学第一眼就懵了。其实每一列都很好理解。① Max最大需求表示这个进程最多需要多少资源。例如P0Max 7说明P0这一生最多需要7 个资源。不是现在。而是最多。② Allocation已分配表示操作系统已经给了多少资源。例如Allocation 3说明P0手里已经有3 个资源。③ Need还需要考试不会直接给。需要自己算。公式Need Max - Allocation例如Max 7 Allocation 3那么Need 4意思P0还需要4 个资源。④ Available剩余资源表示系统现在还有多少空闲资源。例如Available 3说明系统还能借出去3 个资源。二、第一步计算 Need来看完整例子。进程MaxAllocationP073P152P232Available3先算Need。进程NeedP04P13P21因为7-34 5-23 3-21第一步结束。三、第二步找能完成的进程规则Need ≤ Available谁满足。谁先执行。现在Available 3看看P0Need 4够吗不够。P1Need 3够。可以完成。P2Need 1也够。也可以。说明这里有两个选择。例如我们先选P2。四、第三步释放资源P2完成。是不是应该把之前占有的资源还回来P2Allocation2所以系统资源增加。原来Available 3现在变成3 2 5注意增加的是Allocation不是 Need。因为归还的是已经占有的资源。五、继续找现在Available 5看看P0Need 4可以。P1Need 3也可以。例如选P1。完成。释放Allocation 2于是Available 7最后P0Need4系统有7完成。释放3。结束。于是安全序列就是P2 ↓ P1 ↓ P0这就是安全序列Safe Sequence六、考试完整步骤拿到题目。一定按下面四步。第一步算Need公式Need Max - Allocation第二步找Need ≤ Available的进程。第三步执行释放Allocation更新Available第四步重复。直到全部完成。或者找不到任何可执行进程。七、什么时候是不安全状态假设Available只有1看看Need。P0 4 P1 3 P2 2有没有一个满足Need ≤ 1没有。于是没有任何进程可以完成。说明找不到安全序列。于是进入危险状态。注意这里还是危险。不是已经死锁。八、银行家算法真正干什么假设P1申请一个资源。操作系统不会马上给。而是先模拟给了之后重新计算Available。重新计算安全序列。如果还能找到安全序列。批准。否则拒绝。九、多资源怎么办刚才我们只有一种资源。实际考试一般三个资源。例如A B C表格变成进程Max(A,B,C)Allocation(A,B,C)P0(7,5,3)(0,1,0)Need仍然公式Need Max - Allocation只是每一种资源分别计算。例如Need (7,5,3) - (0,1,0) (7,4,3)判断也是逐列比较。例如Need (2,1,3) Available (3,2,4)比较2≤3 1≤2 3≤4全部成立。才能执行。只要有一种资源不够就不能执行。十、一张流程图开始 ↓ 计算Need ↓ Need≤Available ↓ 是 ↓ 执行 ↓ 释放Allocation ↓ 更新Available ↓ 继续 ↓ 全部完成 ↓ 是 ↓ 安全状态 ────────── 否 ↓ 危险状态十一、口诀★★★★★银行家四步口诀。先算Need ↓ 找能完成 ↓ 归还Allocation ↓ 继续循环一句话算 Need找进程还资源再循环。十二、本课重点★★★★★必须会四个量名称含义公式Max最大需求已知Allocation已分配已知Need尚需资源Max − AllocationAvailable剩余资源已知/动态更新必须知道安全序列就是能够让所有进程全部完成的顺序。必须知道更新Available加的是Allocation不是Need。