用C#实现和改进银行家算法

1、用C#实现和改进银行家算法Implementation and Improvement of Bankers Algorithmby C# LanguageZHANG Fan, ZHANG Wen(School of Informational Engineering, ZhongzhouUniversity, Zhengzhou 450000, China): Bankers algorithm is a kind of avoidance based onthe safety of operating system.The paper implement the bankers algor

2、ithm by C# language,and improved the algorithm aiming at some hidden danger.在计算机操作系统中， 死锁是指并发进程彼此等待对方占有 的资源，这些进程在得到对方占有的资源之前又不会释放自己占 有的资源， 从而造成进程永远无法执行的状态。 死锁的产生不但 严重地影响系统资源的利用率， 而且可能会给死锁进程所对应的 事件带来不可预期的后果，甚至导致整个系统崩溃。显然，死锁 是人们所不期望的。银行家算法是基于计算机操作系统安全而设计的一种死锁 避免策略。 所谓安全是指在有效时间内， 操作系统资源分配可以 保证所有进程得到所需的

3、资源。 传统的银行家算法在一个新进程 进入系统时， 要求它必须声明其最大资源需求量， 但由于计算机 执行速度较快， 当新进程声明其最大资源需求量时， 如果有其它 进程申请资源， 操作系统可分配的资源实例可能会发生改变， 使 得原本安全的系统变得不安全， 笔者就这一问题对银行家算法进 行改进， 在资源分配前， 将进程发出的资源申请与系统可用资源 重新进行比较，确保系统在安全状态下分配资源。1 算法的总体设计1.1 算法说明在计算机系统中， 银行家相当于操作系统， 银行家管理的资 金相当于操作系统管理的资源， 用户向银行家贷款的过程相当于 进程向操作系统请求分配资源的过程。 算法要求按照操作系统制

4、 定的规则为进程分配资源， 当进程首次申请资源时， 要测试该进 程的最大资源需求量， 如果系统现有资源可以满足它的最大需求 量，则按当前的申请分配资源，否则就推迟分配。当进程在执行 中继续申请资源时， 先测试该进程已占用的资源量与本次申请的 资源量之和是否超过了该进程的最大资源需求量。 若超过则拒绝 分配资源，若没有超过则再测试系统现有资源能否满足该进程尚 需的最大资源量， 若能满足则按当前的申请分配资源， 否则也要 推迟分配。1.2 算法所需要的数据结构1) int Availablem：记录当前各类资源中资源实例的数量； 2) int Claimn,m 记录每个进程所需各类资源的资源实例

5、最大值； 3) int Allocationn,m ：记录每个进程占有各资源类 中的资源实例的数量； 4) int Needn,m ：记录每个进程尚需各 个资源类中的资源实例的数量； 5) int Requestn,m ：记录每 个进程当前申请各个资源类中的资源实例的数量。1.3 算法的流程步骤一：如果 Requests Needi，则转步骤二；否则进 程申请资源量超过所声明的最大资源需求量，带错返回。步骤二：如果 Requests Available，则转步骤三； 否则当前无法满足本次申请，进程 pi 必须等待。步骤三：假设系统分配资源，将相应的数据结构改为：Available= Avail

6、able- Requesti；Allocation= Allocation+ Requesti；Needi= Needi-Requesti ； 步骤四：如果上述分配导致的新状态是安全的， 则转步骤五； 否则取消分配。Available= Available+ Requesti；Allocation= Allocation- Requesti；Needi= Needi+Requesti ； 进程 pi 等待。步骤五：确认分配，进程 pi 继续执行。 为了进行安全性检查，需要定义以下数据结构。 int Worki ：工作变量，记录可用资源。int Finishi ：工作变量，记录进程是否可以执行完

7、。1.4 安全性检测步骤一： Work=Available ； Finish=false ； 步骤二：寻找满足以下条件的 i ：Finishi=false； Needi Worki；如果不存在，则转步骤四。步骤三： Work= Work+Allocationi ； Finishi=true ； 转步骤二。步骤四：如果对于所有 i ，Finishi=true ，则系统处于安 全状态，否则系统处于不安全状态。1.5 安全检测流程图如图 1 所示。2 算法程序实现用C#语言编写主体程序如下：using System;using System.Collections.Generic;using Sys

8、tem.Text;namespace BankArithclass Processint need;/ 还需要的资源int allocation;/ 已经分配的资源int max;/ 总共需要的所有资源int length =0;/ 资源个数/ 总共需要的所有资源/ 已经分配的资源public Process(int max, int allocation)if (max.Length != allocation.Length)throw new Exception( 进程的所需资源与已分配资源个数 不相等 .);this.max = max;this.allocation = allocat

9、ion; length=max .Length ; need =new int length ;for (int i = 0; i/ 已经分配的资源/public int Allocationget return this.allocation;/ 总共需要的所有资源/public int Maxget return this.max;/ 还需要的资源/ public int Needget return this.need;/ 某时刻进程请求的资源/public int RequestgetRandom rd = new Random();int request = new intlengt

10、h;/bool hasPlus = false;/while (!hasPlus)/全为 0 的资源分配不进行/for (int i = 0; i 0)/ hasPlus = true;/break;return request;/ 正式给进程分配资源/ 分配到的各个资源数public void AssignResource(int resource)for (int i = 0; i ，因而可以断言当前出于安全状态。 假设现在进程 p2 发出新的资源申请， Request2=1 ，2，2，2 由于 Request2=1 , 2, 2, 2Need2=2 , 3, 5, 6，因而 请求合法。进一步 Request2=1 , 2, 2, 2Available=1 , 6, 2, 3，估该请求是可以满足的。假设将资源分配p2，则系统状态变为：Allocation Need AvailableA B C D A B C D A B C Dp0 0 0 3 2 0 0 1 2 0 4 0 1p1 1 0 0 0 1 7 5 0p2 2 5 7 6 1 1 3 4p3 0 3 3 2 0 6 5 2p4 0 0 1 4 0 6 5 6运行安全检测算法， Work=Available=0 ，4，0，1 ，Finishi=false，此时所有 N