基于银行家算法的资源调度研究与实现

刘 璇

（贵阳信息科技学院 信息工程系，贵阳 550025）

0 引 言

在现代操作系统中，利用多道进程的并发执行来提高资源的利用率和吞吐量，为用户程序提供了良好的运行环境，但同时也带来一些新问题。由于计算机系统资源是有限的，并且部分资源还具有独占和排他的特性。计算机系统中打印机的数量、计算机的内存容量、输入输出设备等的数量均是有限的，进程在申请这些资源时只能互斥的使用。如多个进程同时申请同一台打印机时，进程之间会发生互相抢夺，由于打印机数量有限，只能有一个进程得到满足，如果分配不合理，将会造成死锁。

1 死锁

死锁（Deadlock）是指计算机系统中存在多个进程，在执行过程中，相互竞争资源或在进程之间进行某些数据传递、申请等而造成的一种互相等待的现象。若无外界因素的干扰，多个进程都将无法继续推进，所有进程都处于互相等待状态，此时系统产生死锁。

由于资源的使用是互斥的，假设当某个进程提出申请资源时，此资源正在被别的进程所占用，在不可剥夺条件下，若无外力协助，该进程得不到资源的满足。假设每个进程都在等待被其它进程占用的资源，而其它进程也缺少资源，进程在执行完毕前不可能主动放弃资源，这就陷入一种死循环状态，所有进程都在互相等待一种不可能发生的情况。计算机系统中，如果系统的资源分配策略不当，更常见的可能是程序员写的程序有错误等，则会导致进程因竞争资源不当而产生死锁的现象。如有进程、、和资源A、B、C，3个进程所占有的资源和申请的资源如图1所示。

图1 进程资源申请图Fig.1 Process resource application diagram

图中进程占用A资源同时申请B资源；进程占用进程申请的B资源，同时申请C资源；进程占用进程申请的C资源，同时申请进程占用的A资源。由此可见，3个进程之间申请的资源和占有的资源形成一个封闭的环状，在资源不可剥夺情况下，3个进程都在等待别的进程释放自己所需的资源，而别的进程没有执行完毕，不可能释放资源，此时进程陷入永久等待，任何一个进程都得不到满足，都不会执行完毕，都不会释放资源，这就是一种典型的陷入死锁状态。

计算机系统产生死锁的最主要原因是系统资源有限，进程对资源的竞争产生了死锁，所以并发进程对分配资源的顺序就会有一定要求，若能合理的推进顺序，则能在很大程度上降低系统产生死锁的概率。

2 银行家算法

1965年，Dijkstra根据银行系统现金贷款发放思想，提出了避免系统陷入死锁的算法，将其命名为银行家算法（Bankers algorithm）。该算法首先检测进程申请的资源数量系统是否能满足；通过与系统现存可用资源数进行对比分析，若申请资源数小于等于可用资源数，说明当前资源能够满足该进程，可进行资源分配；若大于，则说明当前资源不能进行资源分配，否则系统产生死锁。若在进程的执行过程中还需继续申请资源，则要判断本次申请资源数和已占有资源数之和是否大于进程的最大资源数，若大于，拒绝分配；若小于，还需继续检测系统当前可用资源能否满足进程的此次申请；若能满足进程申请，给予分配，否则拒绝分配。

2.1 银行家算法中的数据结构

假定系统中有个并发进程，，…，P，类资源，，…，R。在银行家算法中需定义1个向量和4个矩阵。

（1）系统可用资源向量［］：表示系统中各类可用资源数量。初始值是系统中类资源全部可用数量，该值随资源的分配与回收动态变化。如：［］，表示系统中现有可用类资源的数量为个。

（2）最大需求矩阵Max［］［］：表示系统中的个进程，每个进程对类资源的最大需求量。如：Max［］［］，表示进程P需要R类资源的数量为个。

（3）分配矩阵［］［］：表示系统中各进程已占用的各类资源数。如：［］［］，表示进程P已获得R类资源的数量为个。

（4）需求矩阵［］［］：表示每个进程所需的各类资源数。如：［］［］，表示进程P还需要分配R类资源个即可执行完毕。

上述3个矩阵之间存在如下关系：

［］［］Max［］［］［］［］

（5）请求矩阵［］［］：表示每个进程当前申请分配各类资源数。如：［］［］，表示进程P需要个R类的资源。

2.2 银行家算法描述

设是进程的请求向量，如果［］，表示进程P需要个类型的资源。当进程P发出资源请求（1，2，…，0）后（表示类资源分别申请1，2，…，0个），系统按以下步骤进行检测，判断是否进行资源分配。

（1）当［］［］［］［］时，不能进行资源分配。因为进程P所申请的资源数已超过其最大需求量，进程P出错。

（2）当［］［］［］时，不能分配资源，进程P进入等待状态。

（3）除以上两种情况外，系统可给予分配，但是需要修改相应的数据结构为：

（4）检测系统安全性。调用安全性算法检查系统安全状态，如果检测结果为安全状态，则给进程P分配所申请资源；否则进程P不能分配资源，并修改进程为等待资源状态，恢复下列数据结构后返回。

2.3 安全性算法

安全性算法是银行家算法的子算法（如22节中步骤4）。为了保证安全性检查，在不影响、Max、和的状态下，需新建两个向量（临时变量）、的数据结构，用以检验系统的安全状态。

其中，工作向量［］表示系统可分配给进程使用的各类资源数（有类资源），其初始值与相等；完成向量［］表示系统是否有足够的资源分配给所有待分配资源的进程。若［］［］，则表示系统资源量不满足；反之可以满足。

安全性检测算法实现步骤如下：

对工作向量和完成向量进行初始化：

工作向量初始值与相等，中的所有位全为。当有足够资源分配给进程P时，再令［］。

从进程集合中寻找满足条件：［］、［］［］≤［］的一个进程。若满足条件，则表明系统当前资源能满足进程P的所有资源申请，转去执行步骤3；否则表示系统不能满足当前所有进程的资源申请，则执行步骤4。

当进程P分配到资源后，将继续执行直至完成整个进程。之后，释放所占用的全部资源，转回步骤2继续调度下一个可满足资源申请的进程。此时工作向量和完成向量调整如下：

对于任意（1，2，…，），都使得［］的值为真，则系统处于安全状态；否则，系统处于不安全状态。

执行安全性算法的本质，就是找到一个符合当前系统资源的安全序列。如果该序列存在，则系统所有进程都可顺利往前推进。系统按照该序列调度进程，系统就不会产生死锁现象，使操作系统处于安全状态。

3 算法建模

算法建模分为两个模块：银行家算法模块和安全性算法模块。用户通过输入数据，分别对可利用资源矩阵、最大需求矩阵Max、分配矩阵、需求矩阵赋初值。采用C语言编程实现。

3.1 银行家算法模块

银行家算法模块主要是通过对进程所申请资源的、、向量之间关系进行判断，判断系统当前资源能否满足该进程，能否对该进程进行资源分配。实现过程如下：

（1）如果满足≤条件，表示进程申请的资源数小于等于该进程运行所需的所有资源数，则转向步骤（2）继续判断；否则，系统出错。

（2）如果≤条件成立，表示进程所申请的资源数小于或等于当前系统可用资源数，满足该进程提出的申请，则分配资源给进程；否则，进程处于阻塞态。

（3）系统执行安全性算法。

3.2 安全性算法模块

安全性算法模块主要是对系统的安全性进行检测，通过遍历所有进程P，对完成向量的值进行判断，从而判断系统是否处于安全队列。实现过程如下：

（1）设置两个向量

①工作向量：，表示系统可用的各类资源数，其初值与相等；

②完成向量：表示系统是否有足够资源满足进程，表示有，表示没有。

（2）若［］≤，则执行（3）；否则执行（4）（为资源类别）

（3）给进程P分配所申请资源，进程执行完成时回收所有资源。；［］；转（2）。

（4）若所有进程都使得［］，则表示系统处于安全状态；反之系统处于不安全状态。

4 设计与实现

设计中寻找安全序列的部分使用循环结构完成，通过分别处理循环的终止条件确定系统是否安全。若满足条件［］的值为，并且［，］小于或等于［］时，说明系统处于安全状态，此时将［］向量置为。循环中设置一个变量来累加计数，当该变量与进程数量相等时，说明已将［］向量全部置为，则终止循环。

对于不安全系统，不可将向量［］都置为，必定存在。由于需要不断循环查找并尝试分配，在寻求一个安全序列时，若在一轮的寻找中没有一个可以安全执行的进程，则说明往后也不存在安全的进程，即可跳出循环，结束寻找。银行家算法流程如图2所示。

图2 银行家算法流程图Fig.2 Banker algorithm flow chart

资源分配过程关键代码如下：

程序运行结果截图如图3所示。

图3 程序运行结果Fig.3 Program running result diagram

5 结束语

经仿真实验得出，银行家算法虽然无法从本质上解决死锁问题，但是该算法可以提高多进程并发算法的资源利用率，能预测当前系统是否处于安全状态，在避免死锁的方面有较突出的表现。由于死锁产生的根本原因是资源的数量不足，并且银行家算法在计算过程中要不断的检测每个进程占有资源、还需资源以及系统可用资源的情况，整个过程将耗费大量时间。为此，相关问题还有待进一步探索研究。