银行家算法实验报告

第1页共26页操作系统原理课程设计——银行家算法指导老师：周敏唐洪英杨宏雨杨承玉傅由甲黄贤英院系：计算机学院计算机科学与技术系班级：0237-6学号：2002370608姓名：朱应瑜同组者：陈源时间：2005/12/22---2005/12/28第2页共26页目录一、设计目的.....................................................................................................................3二、设计内容.....................................................................................................................3三、银行家算法的基本思想...........................................................................................3（一）死锁...............................................................................................................................3（二）系统安全状态...............................................................................................................4（三）银行家算法避免死锁...................................................................................................41、银行家算法中的数据结构.........................................................................................42、银行家算法.................................................................................................................43、安全性算法.................................................................................................................5四、系统模块间关系图.....................................................................................................6五、系统子模块结构图.....................................................................................................7六、输入、输出数据...........................................................................................................9七、源程序及系统文件使用说明..............................................................................12（一）源程序.........................................................................................................................12（二）系统文件使用说明.....................................................................................................25八、心得体会.........................................................................................................................26九、参考文献.........................................................................................................................26第3页共26页银行家算法一、设计目的本课程设计是学习完《计算机操作系统》课程后，进行的一次全面的综合训练。通过这次课程设计，让我们更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强动手能力。二、设计内容编制银行家算法通用程序，并检测所给状态的系统安全性。三、银行家算法的基本思想（一）死锁在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险——死锁。所谓死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。产生死锁的原因可归结为如下两点：（1）竞争资源。（2）进程间推进顺序非法。死锁的发生必须具备下列四个必要条件：（1）互斥条件。（2）请求和保持条件。（3）不剥夺条件。（4）环路等待条件。第4页共26页（二）系统安全状态避免死锁的实质在于：系统在进行资源分配时，如何使系统不进入不安全状态。所谓安全状态，是指系统能按某种进程顺序（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发出资源请求后，系统按下述步骤进行检查：第5页共26页（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）从进程集合中找到一个能满足下述条件的进程：①Finish[i]=false；②Need[i，j]=Work[j]；若找到，执行步骤（3），否则，执行步骤（4）。（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Work[j]=Work[i]+Allocation[i，j]；Finish[i]=true；gotostep2；（4）如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。第6页共26页四、系统模块间关系图开始loop=trueloopRead_Initiate()输出系统现有资源和进程最大需求Allocated_list()输出进程已分配资源Set_Need()输出进程需求资源输入需求RUN()继续否YNloop=falseY结束N第7页共26页五、系统子模块结构图打开文件结束读取资源个数-MAX_FACT_COURCE读取资源-Available读取进程个数-MAX_FACT_PROCESS进程最大需求-Max关闭文件Read_Initiate()Allocated_list()打开文件读取已分配资源-Allocation关闭文件结束第8页共26页Set_NeedNeed=Max-Allocation结束Request_COURCE_NEMBERNeedRequest_COURCE_NEMBERAvailableAvailable=Available-Request_COURCE_NEMBERAllocation=Allocation+Request_COURCE_NEMBERNeed=Need-Request_COURCE_NEMBERTest_Safty()结束RUNwork=availablefinish=falseNeed=work分配资源运行后释放处于安全状态YNTest_Safty()第9页共26页六、输入、输出数据执行程序，输入数据之前：现在请分别输入对应的进程号、资源号和个数：现在请选择1或2：选择了1后：第10页共26页因为未通过安全性测试，不予以分配，所以一切数据均无变化。点击了1后：现在又请分别输入其它需要测试的进程号、资源号和个数：现在请选择1或2：第11页共26页选择了1后：因为通过了安全性测试，并找到了一个安全序列，所以分配成功，有关数据均要发生变化。（请对照前后数据及所输入的数据进行比较）资源类型1的可利用资源由4变成3；进程2的资源类型1的已分配资源由2变成3；进程2的资源类型1的已需求资源由1变成0；点击了1后：第12页共26页七、源程序及系统文件使用说明（一）源程序#includestdafx.h#includeiostream.h#in