银行家算法(用C语言实现)课程设计报告

课程设计报告题目银行家算法程序设计课程名称操作系统课程设计院部名称信息技术学院专业计算机科学与技术班级学生姓名**学号**********课程设计地点课程设计学时20指导教师*********教务处制成绩1操作系统课程设计报告摘要Dijkstra提出的银行家算法，是最具代表性的避免死锁的算法。本文对如何用银行家算法来处理操作系统给进程分配资源做了详细的说明，包括需求分析、概要设计、详细设计、测试与分析、总结、源程序清单。首先做了需求分析，解释了什么是银行家算法，并指出它在资源分配中的重要作用。然后给出了银行家算法的概要设计，包括算法思路、步骤，以及要用到的主要数据结构、函数模块及其之间的调用关系等。在概要设计的基础上，又给出了详细的算法设计，实现概要设计中定义的所有函数,对每个函数写出核心算法，并画出了流程图。接着对编码进行了测试与分析（并在最后附上Java编写的程序代码）。最后对整个设计过程进行了总结。关键词：安全状态；安全序列；银行家算法；安全性算法；安全序列；流程图。2目录摘要…………………………………………………………………………………1目录…………………………………………………………………………………21.绪论…………………………………………………………………………………31.1前言……………………………………………………………………………31.2研究意义………………………………………………………………………41.3结构安排………………………………………………………………………42.需求分析……………………………………………………………………………52.1题目描述………………………………………………………………………52.2银行家算法……………………………………………………………………52.3基本要求………………………………………………………………………52.4目的……………………………………………………………………………63.概要设计……………………………………………………………………………73.1设备环境………………………………………………………………………73.2算法思路………………………………………………………………………73.3银行家算法步骤………………………………………………………………73.4安全性算法步骤………………………………………………………………83.5数据结构………………………………………………………………………93.6系统结构图……………………………………………………………………124.详细设计………………………………………………………………………134.1主要函数的核心代码………………………………………………………134.2程序流程图…………………………………………………………………135.测试………………………………………………………………………………165.1测试用例……………………………………………………………………165.2测试结果截图………………………………………………………………176.总结………………………………………………………………………………22参考文献……………………………………………………………………………24致谢…………………………………………………………………………………25附录…………………………………………………………………………………2631绪论1．1前言：Dijkstra(1965)提出了一种能够避免死锁的调度算法，称为银行家算法。它的模型基于一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，每个客户都有一个贷款额度，银行家知道不可能所有客户同时都需要最大贷款额，所以他只保留一定单位的资金来为客户服务，而不是满足所有客户贷款需求的最大单位。这里将客户比作进程，贷款比作设备，银行家比作系统。客户们各自做自己的生意，在某些时刻需要贷款。在某一时刻，客户已获得的贷款和可用的最大数额贷款称为与资源分配相关的系统状态。一个状态被称为是安全的，其条件是存在一个状态序列能够使所有的客户均得到其所需的贷款。如果忽然所有的客户都申请，希望得到最大贷款额，而银行家无法满足其中任何一个的要求，则发生死锁。不安全状态并不一定导致死锁，因为客户未必需要其最大贷款额度，但银行家不敢抱这种侥幸心理。银行家算法就是对每一个请求进行检查，检查如果满足它是否会导致不安全状态。若是，则不满足该请求；否则便满足。检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户。如果可以，则这笔投资认为是能够收回的，然后接着检查下一个距最大需求最近的客户，如此反复下去。如果所有投资最终都被收回，则该状态是安全的，最初的请求可以批准。41．2研究意义：在多道程序系统中，多个进程的并发执行来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险——死锁。所谓死锁(Deadlock)，是指多个进程在运行过程中因争夺资源而造成的一种僵局（DeadlyEmbrace），当进程处于这种状态时，若无外力作用，他们都无法在向前推进。要预防死锁，有摒弃“请求和保持”条件，摒弃“不剥夺”条件，摒弃“环路等待”条件等方法。但是，在预防死锁的几种方法之中，都施加了较强的限制条件；而在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统状态分为安全状态和不安全状态，便可避免死锁的发生。而最具代表性的避免死锁的算法，便是Dijkstra的银行家算法。利用银行家算法，我们可以来检测CPU为进程分配资源的情况，决定CPU是否响应某进程的的请求并为其分配资源，从而很好避免了死锁的产生。1．3结构安排：一、绪论：介绍了题目背景以及研究意义。二、需求分析：介绍了题目描述、银行家算法、以及基本要求和所需达到的目的。三、概要设计：介绍了基本的算法思路、步骤，以及数据结构和主要的函数模块及其调用关系。四、详细设计：介绍了主要函数及其核心代码，以及程序流程图。五、测试六、总结参考文献附录：原程序清单52需求分析2．1题目描述：银行家算法是一种最具有代表性的避免死锁的算法。所谓安全状态，是指系统能按照某种进程顺序{P1,P2,…，Pn}（称{P1,P2,…，Pn}序列为安全序列），来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺利完成。安全状态一定没有死锁发生。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。那么，什么是安全序列呢？如果对每一个进程Pi(1in)，它以后尚需要的资源量不超过系统当前可利用的资源量与所有的进程Pj(jn)所占有的资源量之和，则称此进程序列{P1,P2,…，Pn}是安全的，称作安全序列。2．2银行家算法：我们可以把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求资源相当于客户向银行家贷款。操作系统按银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程尚需求的资源量，若是系统现存的资源可以满足它尚需求的资源量，则按当前的申请量来分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程申请的资源量是否超过了它尚需的资源量。若超过则拒绝分配，若没超过则再测试系统尚存的资源是否满足该进程尚需的资源量，若满足即可按当前的申请量来分配，若不满足亦推迟分配。2．3基本要求：设计一n个并发进程共享m个系统资源的程序实现银行家算法。要求包括：（1）简单的初始化界面；6（2）系统资源的占用和剩余情况；（3）为进程分配资源，用银行家算法对其进行检测，分为以下三种情况：A.所申请的资源大于其所需资源，提示分配不合理不予分配并返回；B.所申请的资源未大于其所需资源，但大于系统此时的可利用资源，提示分配不合理不予分配并返回；C.所申请的资源未大于其所需资源，亦未大于系统此时的可利用资源，预分配并进行安全性检查：a.预分配后系统是安全的，将该进程所申请的资源予以实际分配并打印后返回；b.与分配后系统进入不安全状态，提示系统不安全并返回；（4）对输入进行检查，即若输入不符合条件，应当报错并返回重新输入；（5）撤销作业，释放资源。2．4目的：银行家算法是避免死锁的一种重要方法，本设计要求用C语言编写和调试一个简单的银行家算法程序。加深有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。通过设计这个算法，让学生能够对书本知识有更深的理解，在操作和其它方面有更高的提升，对程序设计的水平也有所提高。根据设计题目的要求，充分地分析和理解题目，叙述系统的要求，明确程序要求实现的功能以及限制条件。明白自己需要用代码实现的功能，清楚编写每部分代码的目的，做到有的放矢，有条理不遗漏的用代码实现银行家算法。73概要设计3．1设备环境：软件：windowsXP，MicrosoftOfficcWord2003,MicrosoftOfficcVisio2003，TurboC2.0硬件：CPU：2.00GHZ内存：0.99GB主频：2.00HZ3．2算法思路：先对用户提出的请求进行合法性检查，即检查请求是否大于需要的，是否大于可利用的。若请求合法，则进行预分配，对分配后的状态调用安全性算法进行检查。若安全，则分配；若不安全，则拒绝申请，恢复到原来的状态，拒绝申请。3．3银行家算法步骤（1）如果Requesti＜or=Need,则转向步骤(2)；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。（2）如果Request＜or=Available,则转向步骤（3）；否则，表示系统中尚无足够的资源，进程必须等待。（3）系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值：Available=Available-Request[i];Allocation=Allocation+Request;8Need=Need-Request;(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。3．4安全性算法步骤（1）设置两个向量①工作向量Work。它表示系统可提供进程继续运行所需要的各类资源数目，执行安全算法开始时，Work=Allocation;②标志向量Finish。它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finish[i]=0，当有足够资源分配给进程时，令Finish[i]=1。（2）从进程集合中找到一个能满足下述条件的进程：①Finish[i]=0②Needor=Work如找到，执行步骤（3）；否则，执行步骤（4）。（3）当进程P获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Work=Work+Allocation;Finish[i]=1;转向步骤（2）。（4）如果所有进程的Finish[i]=1,则表示系统处于安全状态；否则，系统处于不安全状态。93．5数据结构：3．5.1主要用到的数据结构：(1)工作向量(已分配矩阵)rdy[](2)仍需求矩阵nd[][]=max[][]-rdy[](3)可利用资源向量sys[](4)申请各类资源向量req[](5)等待向量wait[](6)标志向量zhuang[]3．5.2程序模块：main()//系统的主函数intpstart()//初始化voidinputpcb()//输入资源及进程voidcsh()//数据备份voidoutputpcb()//打印输出voidinputreq()//提出资源请求10intcanloc()//判断请求intchange(inta[10],intb)//假设满足请求后，修改资源个数intexchange(inta[10],intb)//请求不能满足，恢复资源个数intss(intri)//判断是否有安全序列intlocate()//利用安全性算法进行安全性检测voidagree()//资源分配后修改资源个数voidoutput()//输出安全序列voidback()//撤销作业，归还资源3．5.3各模块间的调用关系：主函数mai