银行家算法实验报告.doc

操作系统原理课程设计——银行家算法指导老师:周敏唐洪英杨宏雨杨承玉傅由甲黄贤英院系:计算机学院计算机科学与技术系班级:0237-6学号:姓名:朱应瑜同组者:陈源时间:2005/12/22---2005/12/28目录一、 设计目的 3二、 设计内容 3三、银行家算法的基本思想 3(一)死锁 3(二)系统安全状态 4(三)银行家算法避免死锁 41、银行家算法中的数据结构 42、银行家算法 43、安全性算法 5四、系统模块间关系图 6五、系统子模块结构图 7六、输入、输出数据 9七、源程序及系统文件使用说明 12(一)源程序 12(二)系统文件使用说明 25八、心得体会 26九、参考文献 26银行家算法设计目的本课程设计是学习完《计算机操作系统》课程后,进行的一次全面的综合训练。通过这次课程设计,让我们更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解,加强动手能力。设计内容编制银行家算法通用程序,并检测所给状态的系统安全性。三、银行家算法的基本思想(一)死锁在多道程序系统中,虽可借助于多个进程的并发执行,来改善系统的资源利用率,提高系统的吞吐量,但可能发生一种危险——死锁。所谓死锁,是指多个进程在运行过程中因争夺资源而造成的一种僵局,当进程处于这种僵持状态时,若无外力作用,它们都将无法再向前推进。产生死锁的原因可归结为如下两点:(1)竞争资源。(2)进程间推进顺序非法。死锁的发生必须具备下列四个必要条件:(1)互斥条件。(2)请求和保持条件。(3)不剥夺条件。(4)环路等待条件。(二)系统安全状态避免死锁的实质在于:系统在进行资源分配时,如何使系统不进入不安全状态。所谓安全状态,是指系统能按某种进程顺序(P1,P2,……,Pn)(称<P1,P2,……,Pn>序列为安全序列),来为每个进程Pi分配其所需资源,直至满足每个进程对资源的最大需求,使每个进程都可顺利的完成。如果系统无法找到这样一个安全序列,则称系统处于不安全状态。(三)银行家算法避免死锁为实现银行家算法,系统中必须设置若干数据结构。1、银行家算法中的数据结构(1)可利用资源向量Available。这是一个含有m个元素的数组,其中的每一个元素代表一类可利用的资源数目,其初始值是系统中所配置的该类全部可用资源的数目,其数值随该类资源的分配和回收而动态地改变。Available[j]=K,则表示系统中现有Rj类资源K个。(2)最大需求矩阵Max。这是一个n*m的矩阵,它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K。(3)分配矩阵Allocation。这也是一个n*m的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K,则表示进程i当前已分得Rj类资源的数目为K。(4)需求矩阵Need。这也是一个n*m的矩阵,用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K,则表示进程i还需要Rj类资源K个,方能完成其任务。上述三个矩阵存在如下关系:Need[i,j]=Max[i,j]-Allocation[i,j]2、银行家算法设Request[i]是进程Pi的请求向量,如果Request[i,j]=K,表示进程需要K个Rj类型的资源。当Pi发出资源请求后,系统按下述步骤进行检查:(1)如果Request[i,j]<=Need[i,j],便转向步骤(2);否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。(2)如果Request[i,j]<=Available[j],便转向步骤(3);否则,表示尚无足够资源,Pi须等待。(3)系统试探着把资源分配给进程Pi,并修改下面数据结构中的数值:Available[j]=Available[j]-Request[i,j];Allocation[i,j]=Allocation[i,j]+Request[i,j];Need[i,j]=Need[i,j]-Request[i,j];(4)系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配;否则,将本次的试探分配作废,恢复原来的资源分配状态,让进程Pi等待。3、安全性算法系统所执行的安全性算法可描述如下:(1)设置两个向量:①工作向量Work:它表示系统可提供给进程继续运行所需要的各类资源数目,它含有m个元素,在执行安全算发开始时,Work=Available;②Finish:它表示系统是否有足够的资源分配给进程,使之运行完成。开始时先做Finish[i]=false;当有足够资源分配给进程时,再令Finish[i]=true。(2)从进程集合中找到一个能满足下述条件的进程:①Fi