银行家算法避免死锁研究与实现

1、银行家算法避免死锁的研究与实现学 号： 姓 名： 专 业： 目 录1 死锁11.1 什么是死锁11.2 产生死锁的原因11.2.1 竞争系统资源11.2.2 进程的推进不当21.3 产生死锁的必要条件21.4 解决死锁的基本方法21.4.1 预防死锁21.4.2 避免死锁31.4.3 死锁检测31.4.4 死锁的恢复 42 银行家算法42.1 关于银行家算法43 程序实现73.1 程序说明73.2 程序源代码73.3 程序测试111 死锁1.1 什么是死锁在多道程序设计环境下，多个进程可能竞争一定数量的资源。一个进程申请资源，如果资源不可用，那么进入等待状态。如果所申请的资源被其他等待进程占有

2、，那么该等待进程有可能无法改变状态，这种情况称为死锁（deadlock）。设系统有一台打印机(R1)，一台读卡机(R2)，两进程共享这两台设备。用信号量S1表示R1是否可用，初值为1；用信号量S2表示R2是否可用，初值为1； 这两个进程在并发执行过程中，可能会发生如下的情况。 即P1占用R1，P2占用R2，同时P1和P2又分别申请R2和R1的资源。于是造成了死锁。1.2 产生死锁的原因1.2.1 竞争系统资源如循环图所示：系统中只有一台打印机R1和一台读卡机R2，可供进程P1和P2共享。R1、R2已经分别分配给P1、P2使用，当P1、P2在不释放资源R1、R2而又同时分别申请R2、R1（如图）

3、，形成环路，这样会产生死锁。1.2.2 进程的推进不当如前面的例子可知他只是可能发生死锁，也就是说进程的推进不同会导致不同的结果。1.3 产生死锁的必要条件互斥条件进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一进程所占用。占有并等待条件当进程因请求资源而阻塞时，对已获得的资源保持不放。非抢占条件进程已获得的资源在未使用完之前，不能剥夺，只能在使用完时由自己释放。循环等待条件在发生死锁时，必然存在一个进程-资源的环形链。1.4 解决死锁的基本方法1.4.1 预防死锁前面我们降到了死锁的必要条件，那么只要一个条件不满足的话，就不会发生死锁了。所以我们可以从必要条件的角度来预防死锁

4、。a.互斥条件对于非共享资源，必须有互斥条件。而共享资源是不会涉及死锁。所以通常不能通过否定互斥条件来预防死锁：有些资源本身是非共享的。b.占有并等待为了确保该条件不在系统内出现，必须保证：当一个进程申请一个资源时，它不能占有其他资源。资源一次性分配可以解决这个问题。实现这一分配有两种协议1. 每个进程在执行前申请并获得所有资源。2. 允许进程在没有资源时才可申请资源。两种协议的缺点：1.资源利用率不高2.可能发生饥饿（磁带用到一半被抢了）c.非抢占允许当前进程被其他进程抢过去。缺点：可能发生饥饿（磁带用到一般被抢了）d.循环等待条件确保此条件不成立的方法就是对所有资源类型进行完全排序，且要求

5、每个进程按递增顺序来申请资源。实现方法：资源有序分配法遵循两种协议：A. 每个进程只按递增顺序申请资源。（第一次可以申请多个，但之后申请编号必须比前面大）B. 进程申请编号比拥有资源编号小时必须先释放大编号资源。这样进程如果需要磁带机和绘图机，那进程必须先申请磁带机，再申请绘图机。如果再想申请打印机，则必须先释放绘图机。1.4.2 避免死锁通过前面介绍想必大家也看到了在预防死锁的过程中会严重系统性能。因此在避免死锁中我们不得不施加较弱的限制，从而获得比较满意的性能。由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算 资源分配的安全性。若此次分配不会导致系统进入

6、不安全状态，则将资源分配给进程；否则，进程等待。最具代表性的避免死锁的算法是银行家算法。一般来说，由于操作系统有并发，共享以及随机性等特点，通过预防和避免的手段达到排除死锁的目的是很困难的。这需要较大的系统开销，而且不能充分利用资源。为此，一种简便的方法是系统为进程分配资源时，不采取任何限制性措施，但是提供了检测和解脱死锁的手段：能发现死锁并从死锁状态中恢复出来。因此，在实际的操作系统中往往采用死锁的检测与恢复方法来排除死锁。 死锁检测与恢复是指系统设有专门的机构，当死锁发生时，该机构能够检测到死锁发生的位置和原因，并能通过外力破坏死锁发生的必要条件，从而使得并发进程从死锁状态中恢复出来。1.

7、一个用来检查系统状态从而确定是否出现了死锁算法。即死锁检测2.一个用来从死锁状态中恢复的算法。即恢复算法1.4.3 死锁检测首先可以通过画分配图来判断是否发生了死锁。但如何用算法来判断呢？死锁检测算法。算法使用的数据结构是如下这些： 占有矩阵A：n*m阶，其中n表示并发进程的个数，m表示系统的各类资源的个数，这个矩阵记录了每一个进程当前占有各个资源类中资源的个数。 申请矩阵R：n*m阶，其中n表示并发进程的个数，m表示系统的各类资源的个数，这个矩阵记录了每一个进程当前要完成工作需要申请的各个资源类中资源的个数。 空闲向量T：记录当前m个资源类中空闲资源的个数。 完成向量F：布尔型向量值为真（t

8、rue）或假（false），记录当前n个并发进程能否进行完。为真即能进行完，为假则不能进行完。 临时向量W：开始时W：=T。算法步骤： （1）W：=T， 对于所有的i=1，2，.，n， 如果Ai=0，则Fi：=true；否则，Fi：=false （2）找满足下面条件的下标i： Fi：=false并且Ri=W 如果不存在满足上面的条件i，则转到步骤（4）。 （3）W：=W+Ai Fi：=true 转到步骤（2） （4）如果存在i，Fi：=false，则系统处于死锁状态，且Pi进程参与了死锁。什麽时候进行死锁的检测取决于死锁发生的频率。如果死锁发生的频率高，那麽死锁检测的频率也要相应提高，这样一方

9、面可以提高系统资源的利用率，一方面可以避免更多的进程卷入死锁。如果进程申请资源不能满足就立刻进行检测，那麽每当死锁形成时即能被发现，这和死锁避免的算法相近，只是系统的开销较大。为了减小死锁检测带来的系统开销，一般采取每隔一段时间进行一次死锁检测，或者在CPU的利用率降低到某一数值时，进行死锁的检测。1.4.4 死锁的恢复 一旦在死锁检测时发现了死锁，就要消除死锁，使系统从死锁状态中恢复过来。 （1）最简单，最常用的方法就是进行系统的重新启动，不过这种方法代价很大，它意味着在这之前所有的进程已经完成的计算工作都将付之东流，包括参与死锁的那些进程，以及未参与死锁的进程。 （2）撤消进程，剥夺资源。

10、终止参与死锁的进程，收回它们占有的资源，从而解除死锁。这时又分两种情况：一次性撤消参与死锁的全部进程，剥夺全部资源；或者逐步撤消参与死锁的进程，逐步收回死锁进程占有的资源。一般来说，选择逐步撤消的进程时要按照一定的原则进行，目的是撤消那些代价最小的进程，比如按进程的优先级确定进程的代价；考虑进程运行时的代价和与此进程相关的外部作业的代价等因素。此外，还有进程回退策略，即让参与死锁的进程回退到没有发生死锁前某一点处，并由此点处继续执行，以求再次执行时不再发生死锁。虽然这是个较理想的办法，但是操作起来系统开销极大，要有堆栈这样的机构记录进程的每一步变化，以便今后的回退，有时这是无法做到的。 2 银

11、行家算法2.1 关于银行家算法银行家算法（Bankers Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格迪杰在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的斯特拉分配策略为基础，判断并保证系统的安全运行。2.2 安全序列讲银行家算法之前，我们首先引入安全序列的定义：所谓系统是安全的，是指系统中的所有进程能够按照某一种次序分配资源，并且依次地运行完毕，这种进程序列P1，P2，.，Pn就是安全序列。如果存在这样一个安全序列，则系统是安全的；如果系统不存在这样一个安全序列，则系统是不安全的。安全序列P1，P2，.，Pn是这样组成的：若对于每一

12、个进程Pi，它需要的附加资源可以被系统中当前可用资源加上所有进程Pj当前占有资源之和所满足，则P1，P2，.，Pn为一个安全序列，这时系统处于安全状态，不会进入死锁状态。 虽然存在安全序列时一定不会有死锁发生，但是系统进入不安全状态（四个死锁的必要条件同时发生）也未必会产生死锁。当然，产生死锁后，系统一定处于不安全状态。2.3 算法原理我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。为保证资金的安全，银行家规定：(1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客；(2) 顾客可以分期贷款，但贷款

13、的总数不能超过最大需求量；(3) 当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款；(4) 当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金.操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。2.4 银行家算法设进程i提出请求Reque

14、stj，则银行家算法按如下规则进行判断。(1) 如果RequestjNeedi,j，则转向（2），否则认为出错。(2) 如果RequestjAvailablej，则转向（3）；否则表示尚无足够资源，Pi需等待。(3) 假设进程i的申请已获批准，于是修改系统状态：Availablej=Availablej-RequestiAllocationi,j=Allocationi,j+RequestjNeedi,j=Needi,j-Requestj(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。算法流程图2.5 安全性检查算法（1)设置两个工作向量Work=A

15、VAILABLE;FINISH(2)从进程集合中找到一个满足下述条件的进程，FINISH=false;NEED=Work;如找到，执行（3)；否则，执行（4)(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。Work=Work+ALLOCATION;Finish=true;GOTO 2(4)如所有的进程Finish= true，则表示安全；否则系统不安全。3 程序实现3.1 程序说明操作系统: windows 7 64位开发工具: MyEcplise开发语言: javaJdk版本: 1.7相关字段和方法:Int MAX 进程所需最大资源数Int AVAILABLE 系统初始资源Int

16、NEED 每进程需的资源Int M 进程数Int N 资源数showdate(): 显示进程及资源分配情况方法.chkerr(int s): 安全查检方法3.2 程序源代码package test;import javax.swing.JOptionPane;public class Test2 / 每个进程所需要的最大资源数public static int MAX = 6, 5, 3 , 3, 2, 1 , 9, 0, 2 , 2, 2, 2 , 4, 3, 3 ;/ 系统拥有的初始资源数public static int AVAILABLE = 9, 6, 8 ;/ 系统已给每个进程分配

17、的资源数public static int ALLOCATION = 0, 0, 0 , 0, 0, 0 , 0, 0, 0 , 0, 0, 0 , 0, 0, 0 ;/ 每个进程还需要的资源数public static int NEED = 6, 5, 3 , 3, 2, 1 , 9, 0, 2 , 2, 2, 2 , 4, 3, 3 ;/ 每次申请的资源数public static int Request = 0, 0, 0 ;/ 进程数与资源数public static int M = 5, N = 3;int FALSE = 0;int TRUE = 1;public static v

18、oid main(String args) int i = 0, j = 0;int flag = 1;Test2 bank = new Test2();bank.showdata();while (flag = 1) i = -1;while (i = M) String str = JOptionPane.showInputDialog(请输入需申请资源的进程号（从0到+ (M - 1) + ，否则重输入!）);i = Integer.parseInt(str);if (i = M)System.out.println(输入的进程号不存在，重新输入!n);System.out.print(

19、请输入进程 + i + 申请的资源数n);for (j = 0; j NEEDij) System.out.print(进程 + i + 申请的资源数大于进程 + i + 还需要 + j+ 类资源的资源量!申请不合理，出错!请重新选择!n);flag = 0;break; else if (Requestj AVAILABLEj) System.out.print(进程 + i + 申请的资源数大于系统可用 + j+ 类资源的资源量!申请不合理，出错!请重新选择!n);flag = 0;break;if (flag = 1) bank.changdata(i);int chkerr = ban

20、k.chkerr(i);if (chkerr = 1) bank.rstordata(i);bank.showdata(); else bank.showdata();int check = bank.check0(i);if (check = 1) System.out.print(进程 + i + 已经完成，系统将其所占用资源释放n);bank.free(i); else bank.showdata();System.out.println(n);String str = JOptionPane.showInputDialog(是否继续银行家算法演示,按1键继续,按0键退出演示);flag

21、 = Integer.parseInt(str);public void showdata() int i, j;System.out.print(系统可用的资源数为:n);for (j = 0; j N; j+) System.out.print(资源 + j + : + AVAILABLEj + );System.out.println();System.out.println(n各进程还需要的资源量:);for (i = 0; i M; i+) System.out.print(进程 + i + : );for (j = 0; j N; j+) System.out.print(资源 +

22、 j + : + NEEDij + );System.out.print(n);System.out.print(n各进程已经得到的资源量: n);for (i = 0; i M; i+) System.out.print(进程);System.out.print(i);for (j = 0; j N; j+) System.out.print(资源 + j + : + ALLOCATIONij + );System.out.print(n);/ 分配资源，并重新更新各种状态public void changdata(int k) int j;for (j = 0; j N; j+) AVAI

23、LABLEj = AVAILABLEj - Requestj;ALLOCATIONkj = ALLOCATIONkj + Requestj;NEEDkj = NEEDkj - Requestj;/ 回收资源，并重新更新各种状态public void rstordata(int k) int j;for (j = 0; j N; j+) AVAILABLEj = AVAILABLEj + Requestj;ALLOCATIONkj = ALLOCATIONkj - Requestj;NEEDkj = NEEDkj + Requestj;/ 释放资源public void free(int k)

24、for (int j = 0; j N; j+) AVAILABLEj = AVAILABLEj + ALLOCATIONkj;System.out.print(释放 + k + 号进程的 + j + 资源!n);public int check0(int k) int j, n = 0;for (j = 0; j N; j+) if (NEEDkj = 0)n+;if (n = 3)return 1;elsereturn 0;/ 检查安全性函数public int chkerr(int s) int WORK;int FINISH = new intM, temp = new intM;/

25、保存临时的安全进程序列int i, j, k = 0;for (i = 0; i M; i+)FINISHi = FALSE;for (j = 0; j N; j+) WORK = AVAILABLEj; / 第j个资源可用数i = s;/ 判断第i个进程是否满足条件while (i M) if (FINISHi = FALSE & NEEDij = WORK) WORK = WORK + ALLOCATIONij;FINISHi = TRUE;tempk = i;k+;i = 0; else i+;for (i = 0; i M; i+)if (FINISHi = FALSE) System.out.print(n系统不安全! 本次资源申请不成功!n);return 1;System.out.print(n经安全性检查，系统安全，本次分配成功。n);System.out.print(本次安全序列：);for (i = 0; i );System.out.print(进程 + tempM - 1);System.out.println(n);return 0;3.3 程序测试系统可用的资源数为:资源0:9 资源1:6 资源2:8 各进程还需要的资源量:进程0: 资源0:6 资源1:5 资源2:3 进程1: 资源0