摘 要：银行家算法是一种应用于操作系统安全的死锁避免方法。本文分析了银行家算法思想，给出了算法描述。在Delphi集成开发环境下进行了仿真实验，得到了进程执行的安全序列。同时文中也对银行家算法提出了改进的意见。
关键词：进程；死锁；银行家算法；安全检查
中图分类号：TP391.41 文献标识码：a DoI: 10.3969/j.issn.1003-6970.2012.02.007
Simulation Research on Process Safe Sequence Based on Banker’s Algorithm ZHaNG Ju(Department of Information Engineering, Liaoning Provincial College of Communications, Shenyang 110122,China)
【Abstract】 Banker ’s algorithm is a method for the security of operating system. this paper analyzes the banker’s algorithm, gives a
description of the algorithm. The simulation experiments are carried out in the integrated development environment of Delphi, which obtained the safe sequences of process. At the same time, this paper also puts forward improved opinions on the banker’s algorithm.
【Key words】Process; Deadlock; Banker’s algorithm; Safe sequence
0 引 言
在计算机系统中有很多独享资源，在任何时刻它们只能被一个进程使用，比如打印机、磁带机和文件等。另一方面，系统中的资源数目是有限的，请求使用资源的进程数却可能很多，从而产生“供-需”矛盾。如果分配不当，或进程推进速度巧合，就会使系统中的某些进程相互等待从而无法继续工作。在没有外力驱动的情况下，该组并发进程停止向前推进，陷入永久等待状态，发生死锁（Deadlock）。简单地说，所谓“ 死锁”是指系统中存在一组（至少两个或以上）进程，它们中的每一个都占用了某种资源而又都在等待其中另一个所占用的资源，这种等待永远不会结束，这就是“死锁”，或者说这一组进程处于“死锁”状态[1]。
计算机系统产生死锁的根本原因是资源有限，即系统提供的资源太少，不能满足并发进程对于资源的需求，但这一现象是无法避免的。在系统资源紧张的情况下，引发系统死锁的另一个主要原因是进程推进顺序不合适[3]。
最早艾兹格・迪杰斯特拉（Dijkstra）在1965年为T.H.E系统设计的一种避免死结产生的算法，它是一种能够避免死锁的调度方法，它是以银行借贷系统的分配策略为基础的，故称为银行家算法。在计算机系统中，操作系统好比银行家，资源就是资金，进程相当于银行客户。该算法用于判断判断并保证计算机系统的安全运行。所谓安全性就是指能在有限的时间内，能保证所有进程得到自己需要的全部资源，那么称系统处于“安全状态”；否则称系统处于“不安全状态”。在系统处于安全状态时，不会发生死锁；在系统处于不安全状态时，系统有可能发生死锁[2]。
1 银行家算法的数据结构表示
1.1 可利用资源Available向量
它是一个含有m 个元素的数组，其中每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。如果Available[j]=k表示系统中现有Rj类资源k个。
1.2 最大需求量Max矩阵
这是一个n x m 的矩阵，定义为系统中n 个进程中的每一个进程对m 类资源的最大需求。如果Max[i][j]=k，表示进程i当前已分得Rj类资源的最大数目为k。
1.3 已分配资源Allocation矩阵
这是一个n x m 的矩阵，它定义了当前系统中每一类资源已分配给每一进程的资源数。如果Allocation[ i][j]=k，表示进程当前已分得Rj类资源的数目为k。
1.4 还需资源量Need矩阵
它是一个n x m 的矩阵，定义为每一个进程尚需的各类资源数，如果Need[i][j]=k，表示进程i还需要Rj类资源k个，方能完成其任务。
1.5 剩余资源量Available向量
三个矩阵之间存在以下关系：
Need[ i][j]= Max[i][j]- Available[i][j]
银行家算法用Max，Allocation，Need和Available向量描述系统的状态。Allocation，Need和Available是银行家算法运行的依据，而Max必须预先说明。如果把银行家算法应用到实际的操作系统中，必须能够预先确定Max数组的值。
2 银行家算法的基本思想及描述
2.1 算法思想
当进程Pi提出资源请求时，系统检查如下：
（1）首先进行判断，进程请求是否大于还需资源量，即如果Request 2.2 安全性检查算法
（1）初始化，设两个向量
① 可用资源量Work，Work= Available 表示系统当前时刻可提供给进程的各类资源数目，它含有m个元素。
②“能执行完”标识Finish，初始时假设所有进程的“能执行完”Finish=0 假设初始时系统没有足够的资源分配给进程。（2）从进程集合中找到一个能够满足下述原语的进程
Finish[i]=0
Need[i] 3 仿真研究
3.1 利用Delphi 集成开发环境进行仿真
（1）本系统的开发基于window xp操作系统，在Delphi平台上实现了系统仿真；
（2）采用灵活的设计结构，用户根据需要选择相应操作；
（3）本系统分成五大模块，仿真系统框图如图2所示：
图2 仿真系统框图
Fig.2 Block diagram of simulation system
系统说明：系统功能说明及使用指南。
初始化：系统数据的初始化，可以动态输入数据。
银行家算法：进行模拟分配探测，可以有效避免死锁，可以提供安全性保证。
安全性检测：用于查看系统是否处于安全状态，系统会给出当前状态下是否安全的结论。
安全序列：用于优化资源分配和进程调度，系统会给出所有可能的进程安全序列；
用户可以根据需要选择相应的操作。
3.2 初始化数据
T0时刻输入基本数据，系统中有5个进程P={P00，P01，P02，P03，P04}，有4种类型的资源R={R00,R01,R02，R03}，每一种资源的数量分别为6、3、4、2。T0时刻，已知各个进程的最大需求量如表1所示，资源分配情况如表2所示。
根据Max和Allocation，可得资源还需量，见表3。此时，剩余可用资源R{ R00,R01,R02，，R03}={1,0,2,0}，即work= Available ={1,0,2,0}。
3.3 测试验证
首先进行T0时刻的安全性检测，可得T0时刻的安全性分析表，如表3所示。得到T0时刻存在一个安全序列（ P03，P00，P01，P02，P04），故系统是安全的。
假设此时P00进程提出请求向量Request（1,0,0,0），输入请求向量，执行银行家算法得到的安全序列统计Seqcount=6，安全序列如下：
（P03，P00，P01，P02，P04），（P03，P00，P01，P04，P02），（P03，P00，P02，P01，P04），
（P03，P00，P02，P04，P01），（P03，P00，P04，P01，P02），（P03，P00，P04，P02，P01）
Seqcount>0表示T0时刻P00进程提出请求后，按银行家算法模拟分配，Seqcount=6 表示可以有6种进程推进顺序，能使各个进程可以顺利结束，系统的状态时安全的。可见，T0时刻系统是安全的，可以满足P01进程提出的资源请求，允许分配。经验证结果是正确的。
4 结束语
银行家算法是一种应用于操作系统安全的死锁避免方法。本文分析了银行家算法思想，给出了算法描述。在Delphi 集成开发环境下进行了仿真实验和扩充，得到了一个有使用价值的系统，系统的使用效果是令人满意的。此算法经改进后还可用在排课表、柔性制造等涉及资源分配和调度的诸多领域中[3-5]。
参考文献
[1] 汤子赢，哲凤屏，汤小丹.计算机操作系统[M].西安: 西安电子科技大学出版社,1996,119-128. TANG Z Y，ZHE F P,TANG X D. Computer Operating Systems[M].Xi’an: Xi’an Electronic and Science University press,1996,119-128. (in Chinese)
[2] 宗大华，宗涛，陈吉人.操作系统（第3版）[M].北京: 人民邮电出版社，2011,181-184. ZONG D H,ZONG T，CHEN J R. Operating Systems(Third Edition)[M].Beijing: People’s Posts and Telecommunications Press,2011,181-184. (in Chinese)
[3] Kim，Chang Wan; Tanchoco，J.M.A. Deadlock prevention in manfacturing systems with AGV systems: Banker’s algorithm approach. Journal of Manufacturing Science & Engineering,1997,119,4(B):849.(in American)
[4] 徐刚，吴智铭. 银行家算法在柔性制造系统中的改进和应用[J].计算机集成制造系统,2004,10(1): 70-76. XUE G，WU ZH M. Modification and Application of Banker’s Algorithm for FMS[J]. Computer integrated manufacturing system,2004,10(1): 70-76. (in Chinese)
[5] 彭志勇，赖晓风.银行家算法在高校排课系统中的应用[J].西华师范大学计算机学院,2011，25(2):57-59. PENG Z Y,LAI X F. Banker’s Algorithm in the University System of Arrangement[J].School of Computer Science，China West Normal University，2011，25(2):57-59. (in Chinese)