【避免进程死锁】银行家算法

编程知识更新时间:2023-04-23 23:33:05

一、概述

银行家算法（Banker’s Algorithm）是一个避免进程死锁的著名算法，由 Dijkstra 于 1965 年提出。本文为笔者的读书笔记，结构如下：

死锁
银行家算法
例子展示
补充：鸵鸟算法和实际系统中对死锁的处理方式

二、死锁

既然银行家算法就是为了解决进程死锁而出现的，那么首先我们应该先来了解下什么是死锁，以及死锁产生的4个条件。

2.1 什么是死锁

如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件，那仫该组进程就是死锁的。下图为一个进程死锁的例子：

图中有 4 个进程 P1、P2、P3、P4，它们分别持有资源 A、B、C、D，而 P1 的运行需要 B 资源，P2 的运行需要 C 资源，P3 的运行需要 D 资源，而 P4 的运行则是需要 A 资源，但是这些资源都被 P1~P4 这 4 个进程所分别持有，而它们在运行结束之前是不会主动释放自己所持有的资源的。在这种情况下就会造成一种僵持的局面，即为死锁。

2.2 死锁的4个必要条件

从上面的例子中，总结得出死锁的4个必要条件如下：

互斥使用：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，那么请求进程只能等待，直到占有资源的进程用毕释放。
请求和保持：指进程已经至少保持一个资源，但又提出了新的资源请求，而该资源又被其它进程占有，此时请求进程阻塞，但又对自己已获得的请求资源不放。
不可抢占：指进程已经获得的资源，在未使用完之前，不可被剥夺，只能在使用完时由自己释放。
循环等待：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{ P0, P1, P2, … , Pn }中的 P0 正在等待 P1 占用的资源；P1 正在等待 P2 占用的资源, … , Pn 正在等待 P0 占用的资源。

之所以特地强调是必要条件，是因为这 4 个条件之一不出现，系统就不会有死锁的情况发生。而避免死锁的策略，最为著名的就是银行家算法了；除此之外还有鸵鸟算法，这个算法比较适用于极少发生死锁的情况。

三、银行家算法

为了方便后续的理解，首先来解释一下以下三个概念：

安全序列： 指的是一个进程序列 { P1, …, Pn } 是安全的，即对每一个进程 Pi（1≤ i ≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。

安全状态： 如果存在一个由系统中所有进程构成的安全序列，那么系统就处于安全状态，安全状态的下的系统一定不会发生死锁。
不安全状态： 系统中所有进程无法构成一个安全序列，不安全状态不一定会导致死锁。

接着我们来了解一下银行家算法所用到的数据结构，假设系统中存在进程数为 n，资源种类为 m：

可利用资源数组 Available：含有 m 个元素的数组，每个元素代表一类可利用资源的数目。例如 Available[i] = K 表示目前系统中可利用的 Ri 类资源有 K 个。
进程最大需求矩阵 Max：一个 n×m 的矩阵。它定义了系统中 n 个进程中的每一个进程对 m 类资源的最大需求。例如 Max[i][j] = K 表示进程 Pi 对资源 Rj 的最大需求量为 K。
分配矩阵 Allocation：同样是一个 n×m 的矩阵。它定义了系统中每一类资源当前已分配给每一进程的资源数。例如 Allocation[i][j] = K 表示进程 Pi 已分配的资源 Rj 的数量为 K。
需求矩阵 Need：同样是一个 n×m 的矩阵。它定义了每一个进程尚需的各类资源数。例如 Need[i][ij] = K 表示进程 Pi 尚需资源 Rj 的数量围殴 K。

从上面的介绍我们可以得知，Max[i][j] = Allocation[i][j] + Need[i][j]。那么接下来我们就来看看银行家算法是如何保证系统不发生死锁的，它总共可分为以下 4 步，我们将进程 Pi 所申请的资源数表示为为 Requesti。

如果 Requesti ≤ Needi，转向步骤2；否则出错，因为进程所申请的资源数目已经超过了它实际所需要的数目。
如果 Requesti ≤ Availablei，转向步骤3；否则表示系统中没有足够的资源满足进程 Pi 的需求，Pi 必须等待。
系统尝试把申请的资源分配给进程 Pi，并修改以下数据结构中的数值:

Availablei = Availablei - Requesti
Allocationi = Allocationi + Requesti
Needi = Needi - Requesti

系统执行安全性算法，检查此次尝试资源分配之后，系统是否处于安全状态。如果安全，则正式把资源分配给进程 Pi，完成本次分配；否则的话，将尝试分配作废，恢复原来的资源分配状态，让 Pi 等待。

安全性算法同样可分为以下 4 步：
1.设置两个数组 Work 和 Finish，其中 Work 表示系统可提供给进程继续运行的各类资源的空闲资源数目，它含有 m 个元素，安全性算法开始执行时，Worki = Availablei；而 Finish 表示系统是否有足够的资源分配给进程，使之运行完成。开始时，Finishi = false，当有足够的资源分配给 Pi 时，Finishi = true。

2.从进程集合中找到一个满足下述条件的进程：
Finish i = false, Need i ≤ Work i 如果找到执行步骤3，否则的话执行步骤4。

3.当进程 Pi 获得资源后，可顺利执行直到完毕，并释放出分配给它的资源，所以执行：
Finish i = true, Work i = Work i + Allocation i 继续执行步骤2。
4.如果所有进程的 Finishi 都为 true，表明系统处于安全状态，否则就是处于不安全状态。

以上就是银行家算法的思想了，通过银行家算法，我们可以有效地预防死锁发生的情况，但是它也存在以下缺点：

银行家算法要求客户数保持固定不变，这在多道程序系统中是难以做到的。
银行家算法保证所有客户在有限的时间内得到满足，但实时客户要求快速响应，所以要考虑这个因素。
由于要寻找一个安全序列，实际上增加了系统的开销。

接下来我们就通过一个实际的例子来看看银行家算法的实现过程。

四、例子展示

假设有进程 P1、P2、P3、P4 和资源 R1、R2、R3，其中 R1~R3 在系统中的数量分别为 9、3、6。在 T0 时刻，P1~P4 对资源的最大需求量和已分配资源数量如下表所示：

从上面的表格中，我们可以补齐 Need 以及 Available 的数量，如下所示：

假设在 T1 时刻，进程 P2 申请资源数为 (1, 0, 2)，即 R1 申请数量为1、R2 申请数量为 0、R3 申请数量为 2，那么，根据算法：

申请的资源数 Requesti ≤ Needi 条件符合，转向步骤 2。
申请的资源数 Requesti ≤ Availablei 条件也符合，转向步骤 3。
系统进行尝试性分配，此时表的资源数量变为：
然后就会进行安全性算法进行检测了：
- 此时我们的表格如下所示：
- 接下来执行步骤 2，找出满足：Finishi = false, Needi ≤ Worki 的进程，很明显就是 P2 了，执行步骤 3。
- 当进程 P2 获得足够的资源并执行完成之后，此时 Finish2 = true，并且 P2 执行完之后会释放资源，继续继续步骤 2，此时的表格如下所示：
- 返回步骤 2 之后，由于此时 Work 为（6, 2, 3）所以 P1、P3、P4 均满足步骤 2 中的条件，它们均可以进行逐个执行，直到所有进程的 Finishi 为 true，此时系统就被判定处于安全状态了，系统状态如下所示：
系统被判定处于安全状态时，系统的尝试性分配就会变为真正的分配了。

通过这个例子我们就能了解银行家算法的基本思路了，对于判定为不安全状态而不执行分配的情况，我们只需要按照上面的步骤一步步进行分析即可。

五、补充

5.1 鸵鸟算法

在避免进程死锁的算法中，除了可以运用银行家算法之外，还有一种算法，即鸵鸟算法，它首先假设这样的问题出现的概率很低，然后对于出现该问题的情况选择忽略，就像鸵鸟一样遇到危险选择把头钻进沙子中对问题视而不见一样。

而对于死锁问题，如果出现的概率很低，久久才出现一次的话，鸵鸟算法的做法就是忽略这个死锁。

5.2 死锁的检测与恢复

既然银行家算法可以达到预防死锁的效果，那么在实际的操作系统中，是否就是直接使用银行家算法的呢？

答案为否。一般来说，由于操作系统有并发，共享以及随机性等特点，通过预防和避免的手段达到排除死锁的目的是很困难的。这需要较大的系统开销，而且不能充分利用资源。为此，一种简便的方法是系统为进程分配资源时，不采取任何限制性措施，但是提供了检测和解脱死锁的手段：能发现死锁并从死锁状态中恢复出来。

实际的操作系统中往往采用死锁的检测与恢复方法来排除死锁：

死锁检测与恢复是指系统设有专门的机构，当死锁发生时，该机构能够检测到死锁发生的位置和原因，并能通过外力破坏死锁发生的必要条件，从而使得并发进程从死锁状态中恢复出来。
一旦发现了死锁，就要消除死锁，让系统从死锁的状态中恢复过来。其中最简单最暴力的方法就是直接重启系统，但是这意味着在这之前完成的工作都会付之东流。另一个方法是杀死进程，剥夺资源。它也会分为两种情况：一种是一次性撤消参与死锁的全部进程，剥夺全部资源；另一种是逐步撤消参与死锁的进程，逐步收回死锁进程占有的资源。逐步撤销进程要按照一定的规则，例如按照进程的优先级从小到大撤销进程，将代价降到最小。