梁允（广东电网有限责任公司河源供电局，广东河源　514000）



基于银行家算法的多进程算法资源配置策略研究

梁允
（广东电网有限责任公司河源供电局，广东河源514000）

摘要：系统资源不足会导致多进程算法进入不安全状态，引发死锁等问题，银行家算法是避免死锁的一种重要方法，能保证系统时刻都处于安全状态。银行家算法包括可利用资源向量、最大需求矩阵、分配矩阵、需求矩阵四类数据类型，包括试探分配、安全性检查和资源分配等步骤。采用MFC编程，设计并实现了银行家算法。通过软件测试，证明软件能够有效避免死锁，完成多个进程的资源分配。

关键词：银行家算法；死锁；系统安全；多进程

当系统资源紧张时，多进程算法资源分配不足会导致发生死锁，操作系统在对软件、硬件资源管理时都有可能发生死锁，死锁发生时，发生死锁的多进程算法进程无法继续运行，必须释放进程资源，采用新进程进行计算，因此造成多进程算法算法效率低下。避免死锁算法以Dijkstra于1965年提出的银行家算法最有代表性[1]，对多进程算法资源配置具有重要意义。

在避免死锁的著名算法中，其中较为著名的是由Dijkstra在1965年提出的银行家算法，它是以银行的借贷系统的分配原则为理论背景，为判断并保证T.H.E系统的安全运行为目的的一种算法。现已推广到同一系统中，涉及多个单元向上级进行动态的资源申请及回收，都可以采取这种算法保证系统的稳定运行。

张菊等研究了基于银行家算法的进程安全序列研究仿真，分析了银行家算法的思想，给出了算法描述，并改进了银行家算法[2]；侯刚研究了银行家算法的基本原理并第一次在操作系统教材中揭示了银行家算法的原理[3]；王继奎、王会勇等研究了在银行家算法思想指导下，同时深刻理解安全状态的理论前提下，提出了一种针对系统的某一时刻搜索，所需要配置的进程安全序列算法，并利用面编程语言JAVA实现了该算法，该算法在分析全部安全序列的前提下，实现对系统资源的安全分配以及为系统的进程调度优化提供理论支持[4]；李婧、陈旺虎等分析了使用传统的银行家算法降低系统资源使用效率的主要原因是使用了事先声明的全局最大资源需求量，提出了一种改进算法，该算法用广义表表示每个进程的控制流程及其资源请求图，可以减小银行家算法对系统资源使用效率的影响[5]；彭志勇、赖晓风等利用该算法在高校排课系统中针对选修课程教室安排中的应用，并设计了一种排课的方案，从而使每个教室都能得到充分合理的安排，突出了银行家算法相对其他算法在高校排课系统中的优势[6]。

本文提出了基于银行家算法的多进程算法资源分配策略，进一步促进了银行家算法在多进程算法资源分配策略的应用，有效避免了多任务处理系统中死锁的发生。

1　多进程算法资源分配存在问题

在允许多进程操作的系统中，由于允许通过多个进程的并行运行去改善系统，从而提高系统的工作量，但是可能发生多个进程循环等待它方占有资源，导致程序无限期地僵持下去，也就是所谓死锁。如果没有外力改变这个状态，那么涉及到的进程都将永远处于死锁的状态。其中死锁状态产生，一般是由于竞争资源和进程间在推进顺序中所产生非法逻辑。因此只需在当前的有限资源下，构建一组合法的执行顺序，这样便能很好地避免死锁的发生。银行家算法起源于银行系统的发放贷款，其本质状态和计算机操作系统的资源分配相符。

要想避免死锁，就必须考虑进程是否处于系统所要求的安全状态，这样就可以很好的规避死锁。安全状态指系统按照某种设定的安全进程顺序为某种进程合理的提供资源分配，在此基础上进而满足每个进程对资源的最大需求，这样就使的每个进程都能够顺利完成系统的任务。若在系统中，不存在或无法发现这样的安全序列，那么就称系统处于不安全状态。

通过案例进行简要说明，计算机有4个进程共享20个资源，进程P1、P2、P3、P4分别需要15个资源5个资源，8个资源和10个资源。在Tn时刻，P1，P2，P3，P4分别拥有8个、4个、4个、2个资源，且有2个空闲资源。Tn时刻是安全的，< P1，P2，P3，P4>为存在一个安全序列，只要系统按此序列分配，那么就可以安全地完成系统所需要的资源分配，保证系统的安全。

综上，当进程向系统发出某种资源申请时，需要进行安全性检查。分析系统中进程已分配资源数，当下进程的最大需求资源数及系统可配置资源数，在综合分析后，根据分析结果决定判断系统是否进行资源分配，进而避免系统进入不安全状态。

2　银行家算法

银行家算法是避免死锁的算法中颇具代表性的算法，其得名由于该算法思想来源于银行系统现金贷款的发放。为了保证资金的安全，银行家必须保证顾客对资金的总需求量不超过银行家库存的所有资金；若银行家现有的资金少于顾客所需要的贷款需求时，对顾客的贷款进行推迟处理，同时也必须满足，在有限的时间内，需处理顾客的贷款需求；同时若当顾客得到所需贷款后，也必须在有限的时间内，归还所借取的贷款[8]。

2.1银行家算法数据结构

存在四类数据类型。第1类数据类型称为可利用资源向量，其中的每一个元素代表一类可利用资源的数量，其初始值为系统中该类资源的总量，随着该类资源的分配和回收，使得资源处于动态变化，本文中用含有m个元素的一维数组Available表示。

第2类数据类型称为最大需求矩阵，表示进程分别对应类资源的最大需求量，本文中用n×m的矩阵Max进行表示。

第3类数据类型称为分配矩阵，表示每一类资源已分配给每一个进程的资源数量，本文中用n×m的矩阵Allocation表示。

第4类数据类型称为需求矩阵，表示每一个进程尚需的各类资源数量，本文中用n×m的矩阵Need表示。

2.2银行家算法流程

银行家算法流程图如图1所示。

当进程Pi提出资源申请时，系统执行以下步骤：

（1）若Requesti≤Need(i，j)，跳转到下一步，否则错误返回；

图1　银行家算法流程图

（2）若Requesti≤Available，跳转到下一步，否则进程等待；

（3）假设系统试分配及安全性检查通过，则可以进行分配，分配算法为：

系统安全性检查算法如图2所示。

图2　安全性检查算法流程图

首先，定义两个状态向量，工作向量(Work)和状态向量(Finish)。Work向量表示系统可以提供给进程的资源量。执行算法时，Work的初值为系统可利用的资源量；Finish的状态表示系统是否能够进行资源分配，其初始状态为false，当判断足够后，再令其为true。然后在从进程的集合中找到一个可以满足状态向量为false同时满足需求向量小于工作向量进程，如果可以找到，则执行下一步，否则跳转到最后一步，确定系统安全。此时当进程获得资源后，可顺利执行，当完成需要时，释放所获得的资源，继续执行上一步。最后如果所有进程的都完成，表示系统处于安全状态，否则系统处于一个不够安全的状态。

安全性检查程序流程图如图3所示。

图3　安全性检查程序流程图

3　银行家算法的程序设计

本文采用Visual C++ 6.0设计Windows界面程序，程序设计语言为C++。界面分为三部分：参数输入区域，资源分配区域和结果显示区域。用户在参数输入区域输入可利用资源、进程名称、进程所需最大需求矩阵、进程的分配矩阵、等信息，单击动态添加按键添加进程资源，单击安全检查，可以检查当前所有进程对当前资源的申请是否安全，是否会使系统因资源不足或其他原因进入不安全状态从而不能完成分配。如果进程申请资源安全，软件则提示安全，否则提示不安全。

软件可以支持最多10类资源进行分配，如图4所示。可利用资源向量为[5，5，5，5，5，5，5，5，5，5]，输入进程名称process0，输入pro⁃cess0最大需求矩阵为[1，1，2，1，1，1，1，1，1，1]，process0分配矩阵为[0，0，0，0，0，0，0，0，0，0]，需求矩阵为[1，1，2，1，1，1，1，1，1，1]，完成输入之后单击“动态添加”按键添加进程成功。单击“安全检查”按键，即提示系统状态安全，可以执行分配操作。

开始执行分配，在进程名称文本框输入“process0”以及申请资源量。假设输入的申请资源量为[1，1，1，1，1，1，1，1，1，1]，单击“申请资源”，软件弹出“资源分配后安全，可以分配”的消息提示框，表明输入的资源量可以满足申请要求并执行申请请求。单击确认，进程process0已经分配资源为[1，1，1，1，1，1，1，1，1，1]，尚需分配资源为[0，0，1，0，0，0，0，0，0，0]，表明process0申请资源成功。此时系统可用资源数向量由原来的[5，5，5，5，5，5，5，5，5，5]变为[4，4，4，4，4，4，4，4，4，4]，系统为进程process0分配资源成功，如图5所示。

图4　软件安全性检查

图5　进程资源分配

4　结论

由于银行家算法需要不断检测每个进程对各类资源的占用和申请情况从而保证系统处于安全状态，从而耗费了大量时间，目前大部分系统都没有采用这个算法，也没有任何关于死锁的检查。但银行家算法在多进程算法资源配置策略中有重要的意义，可以大大提高多进程算法资源的利用率，并有效地预测系统的安全性，避免死锁的发生。

参考文献：

［1］彭媛.基于系统安全性的死锁避免算法［J］.武汉生物工程学院学报，2006（1）：40-42.

［2］张菊.基于银行家算法的进程安全序列仿真研究［J］.软件，2012，33（2）：21-23.

［3］侯刚.深入解析银行家算法［J］.潍坊学院学报，2006（3）：46-48.

［4］王继奎，王会勇.基于银行家算法的进程安全序列全搜索算法［J］.甘肃科学学报，2009 （2）：152-154.

［5］李婧，陈旺虎.基于广义表的银行家算法［J］.西北师范大学学报：自然科学版，2002（3）：30-33.

［6］彭志勇，赖晓凤.银行家算法在高校排课系统中的应用［J］.西昌学院学报：自然科学版，2011（6）：25-2.

(编辑：向飞)

The Research of Multi-Process Allocation Strategy Based on Banker Algorithm

LIANG Yun
（Heyuan Power Supply Bureau，Heyuan517000，China）

Abstract:Deadlock is the important affair of multi-user operating system. Insufficient system resource will cause the multi-process algorithm into unsafe state，lead to deadlock problem. Banker algorithm is an important method to avoid deadlock，guarantees the system always in safe state. There are four data structures in Banker algorithm: available resource vector，maximum demand matrix，allocation matrix and need matrix. Banker algorithm includes heuristic allocation，security check and resource allocation. In this paper，Banker algorithm is designed and implemented by MFC programming. According to the test results，it is proved that this software can avoid deadlock effectively and complete resource allocation for multi-processes.

Key words:Banker algorithm；deadlock；system safety；multi-process

作者简介：梁允，男，1986年生，广东河源人，硕士，工程师。研究领域：电力信息技术。

收稿日期：2015－08－11

DOI:10. 3969 / j. issn. 1009-9492. 2015. 11. 031

中图分类号：TP39

文献标识码：A

文章编号：1009－9492 ( 2015 ) 11－0119－04