操作系统课程设计报告-银行家算法的设计与实现(JAVA语言).doc

西安工业大学课程设计 操作系统课程设计报告题目：银行家算法的设计与实现院 （系）： 计算机科学与工程学院专 业： 信息对抗专业 班 级： 学 生： 学 号： 指导教师： 2011年 12月基于计算机操作系统银行家算法实现摘要此次课程设计的主要内容是模拟实现资源分配。同时要求编写和调试一个系统动态分配资源的简单模拟程序，观察死锁产生的条件，并使用适当的算法，有效的防止和避免死锁的发生具体用银行家算法实现资源分配。要求如下：(1) 设计一个3个并发进程共享3类不同资源的系统，进程可动态地申请资源和释放资源，系统按各进程的申请动态地分配资源。(2) 设计用银行家算法和随机分配算法，实现资源分配的两个资源分配程序，应具有显示或打印各进程依次要求申请的资源数以及依次分配资源的情况。(3) 确定一组各进程依次申请资源数的序列，在相同的情况下分别运行上述两种资源分配程序，观察运行结果。银行家算法是避免死锁的一种重要方法，本实验要求用高级语言编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。死锁的产生，必须同时满足四个条件，即一个资源每次只能由一个进程占用：第二个为等待条件，即一个进程请求资源不能满足时，它必须等待，但它仍继续保持已得到的所有其他资源：第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待它前一个进程所持有的资源。防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。通过这个算法可用解决生活中的实际问题,如银行贷款等.通过对这个算法的设计,让学生能够对书本知识有更深的理解,在操作和其它方面有更高的提升.关键词：死锁 ；安全状态 ；安全序列 ；银行家算法 ；安全性检查目录1 概述.(3)1.1设计目的.(3)1.2开发环境.(3)2 需求分析.(4)2.1死锁概念.(4)2.2死锁的结论.(4)2.3资源分类.(4)2.4产生死锁的必要条件.(4)2.5死锁的解决方案.(4) 2.5.1产生死锁的例子.(4) 2.5.2死锁预防.(5) 2.5.3安全状态与不安全状态.(5)3 数据结构分析设计.(6)3.1可利用资源向量矩阵available .(6)3.2最大需求矩阵max .(6)3.3分配矩阵allocation .(6)3.4需求矩阵need .(6)4 算法的实现.(7)4.1初始化.(7)4.2银行家算法.(7)4.3安全性检查算法.(7)4.4各算法流程图.(8)5 测试与实例分析.(10)6 心得体会.(14)7.参考文献与源程序清单(附录).(15)1 概述1.1设计目的银行家算法是一种最有代表性的避免死锁的算法。把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。 本次课程设计通过用JAVA语言编写和调试实现银行家算法的程序，达到进一步掌握银行家算法，理解系统产生死锁的原因以及系统避免死锁的方法，增强理论联系实际的能力的目的。1.2开发环境操作系统：Windows XP编译工具：Myeclipse8.6生成文件：.java源代码文件和.class编译文件2 需求分析2.1死锁概念死锁就是指多个进程在运行中因争夺资源而造成的一种僵局，当进程出于这种僵持状态时，若无外力作用，它们都将无法再向前推进。2.2死锁的结论产生死锁的原因是：竞争资源和进程间推进顺序不当。处理死锁的基本方法是：预防死锁避免思索检测死锁解除死锁2.3资源分类1.可剥夺性资源，某些进程在获得此类资源后，该资源可以再被其他进程或系统剥夺。CPU和内存均属于可剥夺性资源。2.不可剥夺性资源，当系统把这类资源分配给进程后，再不能强行回收，只能在进程用完后自动释放，如磁带机，打印机。3.非剥夺性资源，在系统中所配置的非剥夺性资源，由于它们的数量不能满足诸进程运行的需要，会使进程在运行构成中，因争夺这些资源而陷入僵局。4.临时性资源，它是指由一个进程产生，被另一个进程使用一短暂时间后便无用的资源，也称之为消耗性资源。2.4产生死锁的必要条件1.互斥条件：进程对它所分配到的资源进行排他性使用，即在一段时间内某资源由一个进程占有。如果此时还有其它进程请求该资源，则请求者只能等待，直至占有该资源的进程用毕释放。2.请求和保持条件：进程已经保持了至少一个资源，但又提出新的资源请求，而该资源又被其他进程占有，此时请求进程阻塞，但又对自己获得的其他资源保持不放。3.不剥夺条件：进程已经获得的资源，在未使用完之前，不能被剥夺，只有在使用完是由自己释放。4.环路等待条件：发生死锁时，必然存在一个进程-资源的环形链。2.5死锁的解决方案2.5.1产生死锁的例子该例子是由于进程推进顺序非法引发的死锁：进程P1 和P2并发执行，如果按顺序执行：P1：Request（R1）P1：Request（R2）P1：Release（R1）P1：Release（R2）P2：Request（R2）P2：Request（R1）P2：Release（R2）P2：Release（R1），两个进程可顺利完成。如果按曲线执行：P1 和P2将进入不安全区D，P1保持了资源R1，P2保持了R2，接下来P2将申请不到R1，P1申请不到R2，系统处于不安全状态，往前推进将发生死锁。 图3-152.5.2死锁预防预防死锁的方法是使产生死锁的四个必要条件中的2、3、4条件之一不能成立。即： 1、摒弃“请求和保持”条件。系统规定所有进程在开始运行之前，都必须一次性申请其在整个运行过程中所需的全部资源。使该进程再整个运行过程中不会提出资源请求，因而摒弃了请求条件。又由于进程在等待期间没有占有任何资源，所以也摒弃了保持条件。 2、摒弃“不剥夺”条件。系统规定，进程逐个提出对资源的要求，当一个已经保持了某些资源的进程，再提出新的资源请求而未被满足时，必须释放已经保持的所有资源，待以后需要是在再重新申请。 3、摒弃“环路等待”条件。系统规定所有资源按类型进行线性排队，并赋予不同的序号。所有进程对资源的请求都必须严格按资源序号递增的顺序提出。2.5.3安全状态与不安全状态在避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，令进程等待所谓安全状态是指，系统能按某种进程顺序（P1， P2， P3，Pn），来为每个进程分配所需资源，直至满足每个进程对资源的最大需求，是每个进曾都可以顺利完成。如果系统找不到这样一个序列，系统就处于不安全状态。虽然并非所有的不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进入死锁状态。只要系统处于安全状态，系统便可以避免进入不安全状态。因此，避免死锁的实质在于：系统在进行资源分配时，如何使系统不进入不安全状态安全序列：一个进程序列P1，Pn是安全的，如果对于每一个进程Pi(1in），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j i )当前占有资源量之和。 银行家算发就是用具避免死锁的一个有效方法3 数据结构分析设计3.1可利用资源向量矩阵available 这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果available j= K，则表示系统中现有R类资源K个3.2最大需求矩阵max 这是一个n*m的矩阵，用以表示每一个进程对m类资源的最大需求。如果maxi,j=K，则表示进程i需要R类资源的数目为K。3.3分配矩阵allocation 这也是一个n*m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果allocation i,j=K，则表示进程i当前已分得R类资源的数目为K。3.4需求矩阵need 这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果need i,j=K，则表示进程i还需要R类资源K个，才能完成其任务。上述矩阵存在下述关系：needi,j= maxi,j allocationi,j4 算法的实现4.1初始化1.创建available数组，用以存放系统中可用的资源数目； 2.创建max数组，用以存放各个进程对各类资源的最大需求数目； 3.创建allocation数组，用以存放各个进程已经分得的各类资源数目； 4.创建need数组，用以存放各个进程还需要的各类资源数目； 5.创建 allocation1；need1；available1，用以存放系统试分配 资源前系统资源分配情况；4.2银行家算法设Requesti是进程Pi的请求向量，Requesti=K表示进程Pi需要K个j类资源。Pi发出资源请求后，按下列步骤进行检查：1.如果requestijneedi,j，转向步骤； 否则报错，所需要的资源数已超过它所宣布的最大值；2.如果requestijavailablej，转向步骤； 否则报错，尚无足够资源Pi需等待；3.尝试将资源分配给进程Pi，并修改下面数据结构中的数值：availablej：=availablej-raquestij；allocationi,j：=allocationi,j+raquestij；needi,j：=needi,j-raquestij；4. 执行安全性算法，检查此次资源分配后，系统是否出于安全状态。若安全， 才正式将资源分配给进程Pi，已完成本次分配；否则，将本次试探分配作废， 恢复原来的资源分配状态，让Pi等待。4.3安全性检查算法1.设置两个向量： 一、工作向量work：表示系统可提供给进程继续运行所需的各类资源数目，执行安全性算法开始时work：=available； 二、finish标志：表示系统是否有足够的资源分配给进程，使之运行完成。初始化finishi:=false;有足够资源分配给进程时，令finishi：=true。2.从进程集合中找到一个能满足下述条件的进程 finishi=false;Needi,jworkj;找到执行步骤，否则执行步骤3.当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Workj：=worki+allocationi,j； Finishi：=true； Go to step ；4.如果所有进程的finishi=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。4.4各算法流程图1.初始化算法流程：2.银行家算法流程图：235 测试与实例分析1.下列状态是否安全？(四个进程共享12个同类资源) 资源进程MaxA B C AllocationA B C NeedA B C Available A B C P03 2 2 1 0 0 2 2 2 2 1 2 P16 1 3 4 1 12 0 2 P23 1 4 2 1 1 1 0 3 P3 4 2 2 0 0 2 4 2 0 利用银行家算法程序进行检测：（1） 打开程序：（2） 输入上述数据初始化数据后显示（3） 进行安全检测：经检查，系统为安全状态，存在安全序列：p1p2p3p02.考虑下列系统状态，系统是否安全？若安全就给出所有的安全序列。如果此时p0和p1均提出资源请求Request(1,0,1)，能否立即给予满足？解：继续执行银行家算法程序:（1）P0申请资源（1,0,1）：申请不成功，系统不为其分配资源：继续执行银行家算法程序:（2）P1申请资源（1,0,1）：申请成功，存在安全序列：p1p2p3p0；所以对p2来说能得到立即满足如果此刻P2继续请求资源Reques（1,0,1），则就有：系统将资源试分给P1，则可用资源数变为（1,1,1）；然后继续试分配给p0 Request(1,0,1)，它小于Avalable，可以分配，但分配后很明显找不到一个安全序列，发现系统处于不安全状态，不能分配给它，于是回收资源，系统的可用资源恢复到（1,1,1）。6 心得体会 通过一个周的课程设计，虽然理解起来很容易，但想用算法具体去实现它还是有一定的难度，虽然做起来比较吃力，但当我通过自己亲手做出来时，使我更加加深了对银行家算法的理解，掌握了银行家算法避免死锁的过程和方法，理解了死锁产生的原因和条件以及避免死锁的方法。并且还巩固了JAVA知识，掌握了用JAVA实现银行家算法的方法。 所编写程序基本实现了银行家算法的功能，并在其基础上考虑了输出显示格式的美观性，使界面尽可能友好。并且在编程时将主要的操作都封装在方法中，如输入进程和资源信息放在了一个构造方法public TheBanker() 中，进行安全性检测的方法Security_check()，进行申请资源的方法checkRequest()，打印当前各资源的方法print() 。这样使程序可读性增强，使程序更加清晰明了。当然由于JAVA学的也就是些基础，平时的不常联系使得我实际操作能力的很欠缺，我在编写和调试过程中遇到了许多的问题，通过网上查询资料、翻阅课本、向同学请教、多次调试等方法逐渐解决了大部分问题。这次课程设计非常有意义，它让我收获很多，不仅掌握了课本所学的知识，也巩固了JAVA的相关知识。7 参考文献与源程序清单1. 汤子瀛，哲凤屏，汤小丹. 计算机操作系统 .西安电子科技大学出版社，20062.(美)威尔顿，麦可匹克. Java入门经典(第3版). 施宏斌译. 北京：清华大学出版社，20093.(美)Bruce Eckel. Java编程思想. 陈昊鹏译. 北京：机械工业出版社，2007源程序清单：第一部分（第一个类）代码：import java.util.Scanner;public class TestBanker public static void main(String args) System.out.println(-操作系统银行家算法-);TheBanker tb = new TheBanker();boolean flag = true;while (flag) System.out.println(1.死锁避免，检验是否安全);System.out.println(2.死锁检测);System.out.println(3.退出！);System.out.println(-);System.out.println(请选择);Scanner input = new Scanner(System.in);int num = input.nextInt();switch (num) case 1:tb.Security_check();flag = true;break;case 2:tb.checkRequest();/死锁检测flag = true;break;case 3:System.out.println(谢谢使用,再见!);flag = false;break; 第二部分（第二个类）代码：import java.util.Scanner;public class TheBanker int m; /进程个数int n; /每个进程的资源个数int max; /最大需求矩阵int allocation; / 以分配的资源（已占有的资源）int need; / 需求的资源 int available; / 可利用的资源int p; / 记录安全序列boolean finish; / 标志一个进程是否完成？true 表示完成 false 表示未完成Scanner input = new Scanner(System.in);public TheBanker() System.out.println(请输入系统中的【进程数】:); m = input.nextInt(); System.out.println(请输入进程的【资源类型数】:); n = input.nextInt(); max = new intmn; allocation = new intmn; need = new intmn; available = new intn; finish = new booleanm; System.out.println(请输入一个+m+行+n+列的各进程的最大需求量：); for (int i=0;imax.length;i+) /依次输入进程的各个最大资源数 System.out.println(请输入第p(+(i+1)+)进程的Max：); for(int j=0;jmaxi.length;j+) maxij = input.nextInt(); System.out.println(请输入一个+m+行+n+列的各进程的各占有量：); for (int i=0;iallocation.length;i+) /依次输入进程的各个占有资源数 System.out.println(请输入第p(+(i+1)+)进程中的Alloction：); for (int j=0;jallocationi.length;j+) allocationij = input.nextInt(); for (int i=0;ineed.length;i+) /计算出各个进程需求的资源数 for(int j=0;jneedi.length;j+) needij = maxij - allocationij; System.out.println(请输入可用资源数Avallable：); /输入进程的可用资源数 for (int i=0;in;i+) availablei = input.nextInt(); System.out.println(初始化结果为下表：); print();/显示列表 public void print() System.out.println(-); System.out.println(tMaxtAllocationtNeedtAvalable); System.out.println(tA B CtA B CttA B CtA B C); for (int i=0;im;i+) System.out.print(P(+i+): ); System.out.print( ); for (int j=0;jn;j+) System.out.print(maxij+ ); System.out.print(t); for (int j=0;jn;j+) System.out.print(allocationij+ ); System.out.print(tt); for (int j=0;jn;j+) System.out.print(needij+ ); System.out.print(t); if (i=0) for (int j=0;jn;j+) System.out.print(availablej+ ); System.out.println(); System.out.println(-); /-检验系统是否处于安全性状态-public boolean Security_check() int work = new intn;for (int i=0;in;i+) worki = availablei;/ 把available的值赋给workfinish = new booleanm;for (int i = 0; i m; i+) / 开始把进程全部置未分配状态 都为false；finishi = false;int num = 0;/ 对每个进程都要把所有资源都进行比较int num1 = 0;int count = 0;/ 记录可以分配的序列int count1 = 0;/ 记录所有序列是否分配p = new intm;/ 找到安全序列while (num1m) for (int i=0;im;i+) if (finishi = false) / 判断finish的状态，如果为true说明刚才已经找到，不需要重复。for (int j=0;jn;j+) if (needij = workj) / 比较一个进程的各种资源是否满足条件num+;if (num = n) / 如果一个进程所有资源都满足条件needwork,则找到了一个进程满足for (int k=0;kn;k+) workk = workk + allocationik;finishi = true;/ 找到一个进程满足pcount+ = i;/ 记录找到的是第几个进程num = 0;/ 必须把它清零，重新来找下个资源种类的每种是否都满足条件num1+;/ 记录有多少个序列；for (int i=0;im;i+) if (finishi = true) count1+;/ 检测是否所有的进程最后都是true,if (count1 = m) / 如果序列里面总数等于总共有多少程序，就找到了安全的序列。并且输出。反之没有找到System.out.println(存在一个安全序列，安全序列为:);for (int i=0;i); else System.out.println(P+pi);System.out.prin