（兰州大学信息科学与工程学院 甘肃 730000）

1 基本概念

在银行家的算法中，每个过程都需要预先确定其潜在的最大资源需求，尽管该过程可能能够以少于该数量的速度进行。每个进程都必须保证，如果可以利用最大数量的资源，则它将完成其处理并将其资源返回给系统。

当进程进入等待状态时会发生这种情况，因为该进程所请求的资源正由另一个等待该进程的资源持有，而该等待进程又在等待另一个资源。如果某个进程由于另一个进程正在使用该进程所请求的资源而无法无限期更改其状态，则称该系统处于死锁状态[1]。

大部分死锁问题都和资源有关[2]。资源可分为可抢占资源和不可抢占资源。不可抢占资源是指一旦被进程占用，就无法被释放给其他资源使用，除非占用的进程主动释放；而可占用资源则相反，它可以被占用资源任意释放，和被其他资源使用，可占用资源避免了死锁的发生。

1.1多用户操作系统与单用户操作系统

根据在同一时间最多允许多少个用户同时操作计算机，操作系统可分为单用户操作系统和多用户操作系统。同一时间内允许多个用户同时操作计算机，称为多用户操作系统;反之，同一时间内最多只允许一个用户操作计算机，则称为单用户操作系统。

1.2 安全状态

假设系统中存在n个并发的进程，分别为P1，P2，…，Pn，每个进程完成后，必须将其资源返还给系统，以便下一个进程可以使用，使得n个进程都能顺利完成资源分配，则该序列称为安全序列，此时系统处于安全状态。

只要保持系统时刻处于安全状态，便可避免死锁的发生。

1.3 死锁产生的必要条件

（1）互斥，任一时刻只允许一个进程使用资源，即资源不能同时分配给多个进程。

（2）占有并等待，操作系统环境中某个资源的进程请求新的资源，而这些资源被其他进程所占有，无法释放。

（3）循环等待，存在一个进程的封闭环路，其中每个进程占有环路中下一进程所需的至少一个资源。

（4）非抢占，是指资源不可剥夺，只能被占用它的进程主动释放。

当死锁发生时，以上四个条件必须同时满足。

1.4 死锁的解决办法

1.4.1 死锁的预防

间接防止三个必要条件的发生，或直接防止循环等待。具体方法为：一次请求所有资源，或资源剥夺，适用于状态可以保存和恢复的资源，或资源按序申请，可以在编译时进行检查。

此方法的缺点是：需要预知资源需求，并且进程初始化时间会延长，因此效率会降低。

1.4.2 死锁的避免

寻找可能的安全的运行顺序，操作系统动态做出决定：如果当前资源分配满足，否则导致死锁。死锁的避免需要知道未来进程资源请求，但是这一要求对于计算机来说很难实现。同时进程可能长时间阻塞。

避免策略是资源分配的保守方法[3]。当确定由于后续请求而不会发生死锁时，它们通过允许系统仅根据分配进行转换来控制状态转换。该策略是在进入预期状态之前对其进行分析，以确定是否存在从每个状态仍然可以执行的状态开始的过渡序列。

具体有以下两种方法：第一，拒绝进程启动。如果进程资源请求可能导致死锁，则不启动进程。只有在当前所有进程以及此进程的最大资源请求得到满足时进程才会启动，所以我们考虑最坏的情况下，即所有进程同时提出最大申请时拒绝进程启动。第二，拒绝资源分配。如果本次分配可能导致死锁，则拒绝进程的增量资源请求。

1.4.3 死锁的检测

死锁预防策略是非常保守的，不仅限制了对资源的访问，同时对进程也有一定的限制。在任何可能的情况下，资源总是满足进程的申请；定期检测即每次资源请求时都需要检测是否有死锁情况的发生。这种方法的优点是：能够尽早检测，算法也相对简单[4]。不足的地方在于，每次检测是都需要占用相当长的处理器时间。

死锁检测算法：

（1）标记分配矩阵Allocation中对应行全为0的进程；

（2）初始化向量W为可用矩阵；

（3）找到未标记的进程Pi，其中进程满足：Qik<=Wk(对于k从1 取值到m 成立)，如果找不到满足条件的进程，则终止算法；

（4）如果找到进程Pi，将其分配矩阵向量加入W，即Wk=Wk+Aik，返回（3）。

此时，死锁发生当且仅当存在未标记的进程，即未标记的进程可能会引发死锁。

2 银行家算法

2.1 算法数据结构

（1）可分配资源向量Available

含有m个元素的数组向量，其中的每一个元素代表一类可利用的资源数目。如果Available[j]=K，则表示系统中现有可分配的Rj类资源K个。

（2）最大需求矩阵Max[N，M]

一个n 行m 列的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i，j]=K，则表示进程Pi需要Rj类资源的最大需求量为K。

（3）分配矩阵Allocation[N，M]

一个n 行m 列的矩阵，它定义了每个进程已占用每种资源的数量。如果Allocation[i，j]=K，则表示进程Pi当前占有Rj类资源的数目为K。

（4）需求矩阵Need[N，M]

这也是一个n 行m 列的矩阵，表示每个进程申请的每种资源数目。如果Need[i，j]=K，则表示进程Pi正在申请Rj类资源K个。

三个矩阵之间存在以下关系：Need[i，j]=Max[i，j]-Allocation[i，j]。即，需求矩阵是最大需求量减去已分配的资源量。

2.2 进程申请资源的情况

假设Rij=(Cij-Aij)。设Ri是进程Pi的请求向量，如果Ri[j]=K，表示进程Pi 需要Rj类资源的个数为K。Ri 与Need的关系可能为以下3 种情况：

（1）Ri>Need[i]。这种情况表示该进程的资源需求已大于它所声明的最大值。此时无法满足该进程的申请。

（2）Ri=Need[i]。这种情况表示操作系统满足该进程的全部申请的资源数。

（3）Ri

2.3 银行家算法的描述

当进程Pi发出资源请求后，系统按下述步骤进行检查[5]；

（1）如果Ri>Need[i]，便转向步骤（2）；否则显示出错，系统认定为非法请求，因为它所需的资源数已超过它事先声明的最大值。

（2）如果Ri≤Available，便转向步骤（3）；否则，表示目前操作系统中没有足够资源进行分配，Pi须等待其他进程执行完释放资源。

（3）假设系统将资源分配给进程Pi，则需修改几个矩阵的值：

Available ：=Available-Ri；

Allocation ：=Allocation+Ri；

Needi：=Needi-Ri；

2.4 系统安全性算法步骤：

（1）设置2个向量：Work[i]表示资源向量和Finish[i]表示资源够标识向量[6]。W 即资源向量，代表当前能够提供给进程使用总数，F 代表有效向量，表示当前完成的进程返还给操作系统的资源总数。初始化假设Fi=false，满足一定条件则置为true。

（2）当某个进程满足条件Fi=false 以及（C-A）ij＜Vj，则跳转到步骤（3），否则跳转到步骤（4）。

（3）当进程Pi获得资源后，顺利执行操作，完成后释放该进程分配得到的资源

Vj=Vj+Aij

Fi=true

继续执行步骤（2）。

（4）如果所有进程的Fi=true都完成，则系统处于安全状态，可以完成资源分配工作。只要有进程的有效向量为false 则说明此进程可能会有死锁发生。

3 银行家算法的应用

3.1 高校排课

排课系统是学校在完成高质量教学过程中必须要重视的问题。随着学校招生人数增加和学生课程的丰富度逐年上升，而学校的资源又是有限的，用传统的人工管理方式排课就显得比较烦琐，所以如何在短时间内排出整个学校的课程，让教室和教师的资源都能得到充分利用，学生的课程负担平衡，上完课后会及时归还教室资源，就显得尤为重要[7]。如果教务处安排不合理，就会陷入死锁状态，还可能会产生冲突，这样的安排显然就是不适用的。

算法的基本思想是：先安排选其中一门课的学生上课，等这批学生上完课后就会释放资源，然后可以安排下一批学生进行上课，以此类推[8]。这样选其他课程的学生就可以分配到足够多的资源，从而老师和学校能够正常完成教学目标。

3.2 网络爬虫资源分配[9]

将银行家算法中核心的递归思想引入到请求集生成过程中，这是一种全局递归的思想。允许当前节点进入的条件是：测试每个纳入请求级的数组是否合法。合法指的是当前节点进入之后是否可以保障下一个节点进入请求集。

当利用银行家算法对网络爬虫资源时，能够有效提高资源率并避免死锁。

3.3 智能家居能源管理

目标是建立一个智能家居模型，它能够根据预先定义的标准，决定哪些过程应该提供必要的资源。标准包括在预定的到期时间之前完成该过程，将分配的资源保持在某个阈值以下，并且标准易扩展，因此对任何其他资源的当前分配数量的额外限制可以施加到其中的任何一个。为了使过程更简单，结果更加明了，假设如下：资源数量必须预先定义并保持不变；所有流程都预先确定每个流程需要多少资源；完成后，每个进程返回所有分配的资源，因此可以通过分配给其他进程来重新利用；且每个过程都在有限的时间内完成。

为了满足所有性能要求，对银行家算法进行了修改[10]。

引入离散化的概念。离散化是指将每个过程分成几个子过程，每个子过程持续一个离散化周期，这样可以满足资源和过程数量恒定的假设。此外，假设在一个离散化周期内，资源数量恒定。同时我们将时间进行分片，选择足够小的时间片，随着子过程数量的增加，时间片越小，系统越复杂。另一方面，时间片越小，与用户的通信的时间就越短。

引入进程优先级。为了区分进程执行的紧急程度，引入进程的优先级[11]。假设将进程分为两组，第一组由用户进行管理，第二组由修改后的银行家算法进行管理。第一组的过程具有最高优先级，同时每个进程都分配了默认优先级——第一组优先级为2，第二组优先级为0。优先级的高低代表开始执行时间的紧迫性，优先级越高，排队等待执行的时间越短。除此之外，第一组进程的优先级是恒定的，如果没有足够的资源来立即执行这种类型的过程，请求将会被忽略。如果银行家算法管理的进程的优先级增加到1，则表示该进程必须在这个特定的时间开始执行。如果优先级值超过1，进程将无法及时完成[12]。如果没有足够的资源来执行第二组的过程，则将第二组进程将被推迟，直到执行条件得到满足。

动态调整需求矩阵。默认情况下，在开始时，所有定义的进程都需要给予低成本资源支持。根据流程的优先级和资源的可用性，每个进程的资源需求必须在每个时间片中进行调整。因为在最初的银行家算法中，每个过程对所有必要资源的需求都存储在需求矩阵中，这对应于需求矩阵的改变。由于所有当前进程的资源需求都存储在矩阵需求中，所以矩阵会根据当前可用的资源、每个进程的优先级和管理策略的变化而变化。如果所选择的管理策略是标准策略方法模拟，那么需求矩阵的值也会发生变化。

动态调整可分配矩阵。可分配资源存储在可分配矩阵中，它的大小对应于资源的数量。可分配字眼矩阵包含当前可用资源的数量。首先，计算优先级高于或等于1的所有流程的总使用量[13]。然后将极限值和最大值进行比较。如果需求量大于极限值，可分配矩阵中的值将精确地增加到当下时间的需求量，以执行优先级高于或等于1的所有进程。如果对需求值大于最大值，可分配矩阵中的取值则会增加到最大值。计算完所有矩阵后，将资源分配给进程。即进程可以开始执行。

通过对以上条件的改进，算法考虑的角度更加全面和人性化，使得智能家居模型能够带给居住者更安全和舒适的体验。在经典的银行家算法中，会检查将资源分配给进程是否会导致系统进入不安全状态，即可能的死锁。在这里省略了安全检查，原因是智能住宅不会陷入算法意义上的死锁状态[14]。

3.4 制造系统

制造系统由一组不同的资源组成，如缓冲器、机器人机械手臂和自动驾驶车辆，需要对这些资源进行处理和控制，以执行特定的生产功能。控制制造系统的需求源于生产操作使用的资源数量有限，因此需要资源共享。控制策略需要考虑资源的优先级分配和避免死锁状态。设计控制器时要考虑三个主要问题：第一，操作的精确顺序；第二如何避免死锁；第三，在出现冲突情况下，如何分配进程优先级。离散事件控制器的本质基本上与其他控制器相似：基于系统的当前状态和想要获得的结果，控制器应该自主地决定采取哪些行动来实现目标，同时需要考虑要花费最少的能量[15]。

在处理制造系统的建模和控制时，有三种主要工具：Petri网，图论方法和自动机。Petri网算法理论上非常强大，并且提供了较好的仿真结果，但是对于大规模系统，仍然存在复杂性较高的问题[16]。银行家算法是一种死锁避免策略，控制资源分配以确保系统始终是处于安全状态的，并且其复杂度低于Petri网算法。矩阵模型与Petri网直接对应，将矩阵模型或相应的Petri网中给出的系统需求量转换成银行家算法所需的矩阵。在制造系统中，每个部分都有清晰的开始和结束的标志，即输入和输出标志，对应制造系统的一组操作和一组资源，为了获得矩阵模型，可以以if-then 规则的形式描述系统进程。同时每个规则对应于表示为x的二进制逻辑状态向量的一个分量。如果满足部分规则的所有先决条件，则满足特定规则，即向量x的相应元素从“相应设置为“置为。此时根据进程的开始和结束标志管理进程和分配资源。

可分配矩阵和需求矩阵的数值大小取决于系统结构和当前状态，随着系统的变化而变化。进程每次请求资源时，银行家算法都会更新可分配矩阵和需求矩阵，并检查这种分配是否处于安全状态，检查完毕后资源被一个接一个地顺序分配给进程。如果所有进程都可以成功结束，而没有处于死锁状态，则状态是安全的。

尽管对于给定的系统，时间复杂性没有问题，但是对于较大规模的系统，应该考虑使用稀疏矩阵对制造系统进行模拟，同时更新存储器管理系统和算法[17]。

3.5 救援物资的分配

当灾害发生后，如何对救援工作进行统筹安排，是一切工作的中心。为了让受灾群众能够及时获得救援物资，需要一种合理的分配方式。银行家算法利用了广度优先搜索的策略，解决了有向图中单个源点到其他顶点的最短路径问题[18]。

首先利用GIS技术对受灾情况有一个大致的分析和了解，通过受灾区域的分口分布、受灾持续时间等等估算受灾损失程度，进一步利用银行家算法与GIS相结合，使得受灾物资运送到受灾地点的时间最短[19]。

4 银行家算法的实现实例

T0 时刻若出现下述资源分配情况：

（1）初始状态

首先用最大需求矩阵减去分配矩阵得到每个进程的需求矩阵：

图1 初始状态

（2）P2 进程完成

我们可以观察到，可分配矩阵小于P2 进程的需求矩阵，所以只能分配给P2 矩阵，注意进程执行完后，需要将资源返还给可分配向量，同时将关于P2 进程的其他矩阵清零。

图2 P2 进程完成

（3）P1 进程完成

图3 P1 进程完成

（4）P3 进程完成

图4 P3 进程完成

（5）P4 进程完成

图5 P4 进程完成

（6）总结：此时我们可以判断，可以进行资源分配，且不会发生死锁状态。且实例存在安全序列P2->P1->P3->P4。

5 银行家算法的改进[20]

在银行家算法中，如果某些进程处于等待状态，说明没有合适的方法提供安全序列。

提出一种等待状态处理算法提供一个安全的序列：它取决于需求矩阵needi=1，21e，分配矩阵Allocationi=1，21l和可用资源矩阵Available。

如果进程要等待状态，则必须遵循以下步骤：

（1）needi和need（i+1到最后）进行比较。

（2）以最少的需求和最大限度地进行过程分配。

（3）如果可用资源矩阵Available

（4）Available=Available+Allocationi

（5）重复（1）至（4），直到进程将进入运行状态。

6 总结

本文基于银行家算法，对算法进行了分析，对应用进行了举例说明。银行家算法能够合理安排已有资源，从而提高了资源利用率。不仅利用在高校排课中，同时在网络爬虫资源配置和家庭智能家居能源分配上也有一定的应用。在并发和分布式系统的资源分配算法中，我们还必须考虑多种资源类型。在银行家算法的基础上，不断对算法进行研究和改进，就能有效避免死锁的发生。