【软考学习11】死锁问题和银行家算法

本文学习了操作系统进程中的死锁问题，了解死锁产生原因，学习避免死锁的最低资源数计算，最后讲解了如何使用银行家算法来避免死锁现象。

一、死锁产生原因

操作系统中最核心的业务，就是对进程进行管理，尽可能照顾进程之间的同步和互斥关系。

如果进程管理不当，就会造成死锁问题。

所谓进程发生死锁，就是这个进程正在等待一件不可能发生的事件发生。

如果一个或多个进程发生死锁，就可以认为整套系统发生了死锁。

比如一个系统一共四个进程，进程之间的依赖关系如下图所示。

很容易就看出，这套系统发生了死锁。

死锁的发生有着四大条件，缺一不可。

所以要预防死锁问题，就需要打破其中任意一个条件即可。

• 进程互斥条件，即存在互斥资源，如果各进程可以同步执行，就不会发生死锁问题。
• 有保持的等待关系，即存在进程 A 因某原因，等待进程 B 的情况。
• 系统不剥夺进程资源，即进程在执行过程中，操作系统不强制去剥夺进程当前拥有的资源，等到进程执行完成后再回收进程资源。
• 形成环路等待，即进程之间的等待依赖形成了一个环路，如上上图所示。

二、死锁的资源计算

在软考中会有这样一类考题，已知若干进程需要的资源，求至少分配多少资源才不会发生死锁问题。

比如，一套业务系统一共有四个进程，分别为进程 A、进程 B、进程 C、进程 D，这四个进程都需要 6 份资源，求系统至少需要多少份资源，才不会发生死锁问题。

计算公式为 （进程需要资源数 - 1） * 进程数 + 1。

假设出现最坏情况，四个进程分别占用了 5 份资源，如下图所示。

那么只要系统还剩 1 份资源，任意给一个进程，就可以让这个进程成功执行，进程执行后就会把资源释放，系统再分配给其他进程执行，不会发生死锁问题，所以本例题中至少需要的资源为 21。

三、银行家算法

系统发生死锁是很正常的，我们需要主动去预防死锁，即进行有序的资源分配，使用银行家算法。

银行家算法是最有代表性的避免死锁的算法。

为什么叫银行家算法呢？就是这个算法的逻辑很像银行放贷的逻辑，也就是尽可能避免坏账的出现。

银行家算法的业务逻辑如下。

• 不负荷执行：一个进程的最大需求量不超过系统拥有的总资源数，才会被接纳执行。
• 可分期：一个进程可以分期请求资源，但总请求书不可超过最大需求量。
• 推迟分配：当系统现有资源数小于进程需求时，对进程的需求可以延迟分配，但总让进程在有限时间内获取资源。

听起来有点绕，我们还是举个例子来说明。

加入系统中有三类互斥资源 R1、R2、R3，可用资源数分别是 9、8、5，在指定时刻有 P1、P2、P3、P4 和

P5 这五个进程，这些进程的对三类互斥资源的最大需求量和已分配资源数如下表所示，那么系统如何先后运行这五个进程，不会发生死锁问题？

第一步：分析

首先分析首次需求的资源，系统剩余可用资源数分别是 2、1、0，各进程需要的资源数如下表所示。

资源 R1 的剩余可用资源数 = 9 - 1 - 2 - 2 - 1 - 1 = 2。

资源 R2 的剩余可用资源数 = 8 - 2 - 1 - 1 - 2 - 1 = 1。

资源 R3 的剩余可用资源数 = 5 - 1 - 1 - 0 - 0 - 3 = 0。

根据银行家算法不负荷原则【一个进程的最大需求量不超过系统拥有的总资源数，才会被接纳执行】，优先给进程 P2 执行，因为剩余的 0 1 0 资源够让 P2 执行。

第二步：执行 P2

P2 执行之后，释放了刚刚放入的 2 1 0 资源，而且可以释放已分配的 2 1 1 资源，所以此时的资源剩余量。

资源 R1 的剩余可用资源数 = 原资源数 - 执行 P2 消耗数 + P2 执行完释放的资源数 = 2 - 0 +（2 + 0） = 4。

资源 R2 的剩余可用资源数 = 原资源数 - 执行 P2 消耗数 + P2 执行完释放的资源数 = 1 - 1 + （1 + 1） = 2。

资源 R3 的剩余可用资源数 = 原资源数 - 执行 P2 消耗数 + P2 执行完释放的资源数 = 0 - 0 +（0 + 1） = 1。

执行完成 P2 后，操作系统剩余可用资源数为 4 2 1。

第三步：执行 P4

此时操作系统剩余可用资源数为 4 2 1，只能执行进程 P4，因为其他进程资源不够。

P4 执行之后，释放了刚刚放入的 0 0 1 资源，而且可以释放已分配的 1 2 1 资源，所以此时的资源剩余量。

资源 R1 的剩余可用资源数 = 原资源数 - 执行 P4 消耗数 + P4 执行完释放的资源数 = 4 - 0 +（1 + 0） = 5。

资源 R2 的剩余可用资源数 = 原资源数 - 执行 P4 消耗数 + P4 执行完释放的资源数 = 2 - 0 + （2 + 0） = 4。

资源 R3 的剩余可用资源数 = 原资源数 - 执行 P4 消耗数 + P4 执行完释放的资源数 = 1 - 1 +（1 + 1） = 2。

执行完成 P4 后，操作系统剩余可用资源数为 5 4 2。

第四步：执行 P5

此时操作系统剩余可用资源数为 5 4 2，只能执行进程 P5，因为其他进程资源不够。

P5 执行之后，释放了刚刚放入的 2 3 1 资源，而且可以释放已分配的 1 1 3 资源，所以此时的资源剩余量。

资源 R1 的剩余可用资源数 = 原资源数 - 执行 P5 消耗数 + P5 执行完释放的资源数 = 5 - 2 +（1 + 2） = 6。

资源 R2 的剩余可用资源数 = 原资源数 - 执行 P5 消耗数 + P5 执行完释放的资源数 = 4 - 3 + （1 + 3） = 5。

资源 R3 的剩余可用资源数 = 原资源数 - 执行 P5 消耗数 + P5 执行完释放的资源数 = 2 - 1 +（3 + 1） = 5。

执行完成 P5 后，操作系统剩余可用资源数为 6 5 5。

第五步：执行 P1 或者 P3

此时操作系统剩余可用资源数为 6 5 5，可以执行 P1 或 P3。

所以安全执行顺序为 p2 => p4 => p5 => p1 => p3 或 p2 => p4 => p5 => p3 => p1。

或

银行家算法总结

银行家算法的核心思想，就是在分配给进程资源前，首先判断这个进程的安全性，也就是预执行，判断分配后是否产生死锁现象。

如果系统当前资源能满足其执行，则尝试分配，如果不满足则让该进程等待。

通过不断检查剩余可用资源是否满足某个进程的最大需求，如果可以则加入安全序列，并把该进程当前持有的资源回收；不断重复这个过程，看最后能否实现让所有进程都加入安全序列。

安全序列一定不会发生死锁，但没有死锁不一定是安全序列。

四、总结

本文学习了操作系统进程中的死锁问题，了解死锁产生原因，学习避免死锁的最低资源数计算，最后讲解了如何使用银行家算法来避免死锁现象。