基于银行家算法进程安全序列仿真研究.docVIP

基于银行家算法进程安全序列仿真研究 　　摘 要：银行家算法是一种应用于操作系统安全的死锁避免方法。本文分析了银行家算法思想，给出了算法描述。在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，表示进程