操作系统原理课程设计银行家算法

课程设计课程名称操作系统原理课程设计题目编程序模拟银行家算法专业计算机网络班级姓名成绩指导教师2009年7月6日至2009年7月10日课程设计任务书设计题目：编程序模拟银行家算法设计目的1、银行家算法是避免死锁的一种重要方法，本实验要求用高级语言编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。2、提高学生的程序设计能力、提高算法设计质量与程序设计素质；设计任务（在规定的时间内完成下列任务）思想：将一定数量的资金供多个用户周转使用，当用户对资金的最大申请量不超过现存资金时可接纳一个新客户，客户可以分期借款，但借款总数不能超过最大的申请量。银行家对客户的借款可以推迟支付，但是能够使客户在有限的时间内得到借款，客户得到所有的借款后能在有限的时间内归还。用银行家算法分配资源时，测试进程对资源的最大需求量，若现存资源能满足最大需求就满足当前进程的申请，否则推迟分配，这样能够保证至少有一个进程可以得到所需的全部资源而执行到结束，然后归还资源，若OS能保证所有进程在有限的时间内得到所需资源则称系统处于安全状态。时间安排1月14日布置课程设计任务；分配题目后，查阅资料、准备程序；1月15～1月17日上机调试程序、书写课程设计报告；1月18日提交课程设计报告及相关文档。具体要求1.课程设计报告按统一通用格式书写，具体格式要求请在网络上查阅；2.每位学生应独立完成各自的任务且每天至少在设计室工作半天；指导教师签名：09年7月6日教研室主任（或责任教师）签名：09年7月10日1.需求分析本设计的目的是通过编写和调试一个系统动态分配资源的简单模拟程序，观察死锁产生的条件，并采用适当的算法，有效地防止和避免死锁地发生。集体要求如下：（1）模拟一个银行家算法；（2）初始化时让系统拥有一定的资源；（3）用键盘输入的方式申请资源；（4）如果预分配后，系统处于安全状态，则修改系统的资源分配情况；（5）如果预分配后，系统处于不安全状态，则提示不能满足请求，此次课程设计的主要内容时模拟实现动态资源分配。同时要求编写和调试一个系统动态资源的简单模拟程序，观察死锁产生的条件，并使用适当的算法，有效的防止和避免死锁的发生。银行家算法是避免死锁的一种重要方法，通过编写一个简单的银行家算法程序，加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。死锁的产生，必须同时满足四个条件，即一个资源每次只能由一个进程张勇；第二个为等待条件，即一个进程请求资源不能满足时，它必须等待，单它仍继续宝石已得到的所有其他资源；第三个为非剥夺条件，即在出现死锁的系统中一定有不可剥夺使用的资源；第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待它前一个进程所持有的资源。防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。通过这个算法可以用来解决生活中的实际问题。死锁会引起计算机工作僵死，因此操作系统中必须防止。本实验的目的在于让学生独立的使用高级语言编写和调试一个系统动态分配资源的简单模拟程序，了解死锁产生的条件和原因，并采用银行家算法有效地防止死锁的发生，以加深对课堂上所讲授的知识的理解。1.1设计原理：死锁产生的条件1．互斥控制，进程对其所要求的资源进行排他控制，一个资源仅能被一个进程独占。2．非剥夺控制，进程所获得的资源在未被释放之前，不能被其他进程剥夺，即使该进程处于阻塞状态，他所占用的资源野不能被其他进程使用，而其他进程只能等待该资源的释放；3．逐次请求，进程以随意的零星方式逐次取得资源，而不是集中性的一次请求，这样有利于提高资源的利用率；4.环路条件，在发生死锁时，必然存在一个进程——资源的环形链。不断有资源在等待被占用的资源；我们只要破坏以上四个条件之一，既可以预防死锁。银行家算法是避免死锁的方法中，施加的限制条件较弱的，有利于获得令人满意的系统性能的方法。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。Dijkstra(1965)年提出了一种能够避免死锁的调度方法，称为银行家算法，描述如下：假定一个银行家拥有资金，数量为Ё，被N个可户共享。银行家对可户提出下列约束条件：Ⅰ.每个客户必须预先说明自己所要求的最大资金量；Ⅱ.每个客户每次提出部分资金量申请和获得分配；Ⅲ.如果银行家满足了客户对资金的最大需求量，那么，客户在资金运作后，应在有限时间内全部归还银行。把一个进程需要和已占有资源的情况记录在进程控制中，假定进程控制块PCB其中“状态”有就绪态、等待态和完成态。当进程在处于等待态时，表示系统不能满足该进程当前的资源申请。“资源需求总量”表示进程在整个执行过程中总共要申请的资源量。显然，，每个进程的资源需求总量不能超过系统拥有的资源总数,银行算法进行资源分配可以避免死锁.1.2设计思想：假设在进程并发执行时进程i提出请求j类资源k个后，表示为Requesti[j]=k。系统按下述步骤进行安全检查：（1）如果Requesti≤Needi则继续以下检查，否则显示需求申请超出最大需求值的错误。（2）如果Requesti≤Available则继续以下检查，否则显示系统无足够资源，Pi阻塞等待。（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：Available［j］∶=Available［j］-Requesti［j］;Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;Need［i,j］∶=Need［i,j］-Requesti［j］;（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。（5）设置两个向量：①工作向量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都满足，则表示系统处于安全状态；否则，系统处于不安全状态。1.3程序结构：A.字符判断模块：判断输入的字符是否为数字，如果不是则提示出错并重新输入，主要处理输入为非数字时程序出现运行错误现象。此模块功能由数字判断函数（intshuzi(intsz);）实现。B.程序初始化模块：用于程序开始进行初始化输入数据：进程数量、资源种类、各种资源可利用数量、各进程的各种资源已分配数量、各进程对各类资源最大需求数等。此模块功能在系统初始化函数（voidchushihua();）中实现。C.当前安全性检查模块：用于判断当前状态安全性，根据不同地方的调用提示处理不同，在安全性算法函数（voidsafe();）中实现。D.银行家算法模块：进行银行家算法模拟实现的模块，调用其他各个模块进行银行家算法模拟过程，在银行家算法函数（voidbank();）中实现。E.显示分配模块：显示当前资源分配详细情况，包括：各种资源的总数量(all)、系统目前各种资源可用的数量、各进程已经得到的资源数量、各进程还需要的资源量，在显示分配情况函数（voidshowdata();）中实现。1.4程序流程图：图1银行家算法的流程图1.5数据结构：1.5.1定义全局变量银行家算法bank（）开始初始化Init（）提出请求request[i]Request[i]=need[i]eerorRequest[i]=available[i]Available[i]=available[i]-request[i]Allocation[i]=allocation[i]+request[i]Need[i]=need[i]-request[i]Safe()输出提问：同意分配请求是否再次进行分配eeror输出提示：你的请求被拒绝Available[i]=available[i]-request[i]Allocation[i]=allocation[i]+request[i]Need[i]=need[i]-request[i]退出程序银行家算法bank（）结束falsefalsetruetruefalsefalsetruetruefalseconstintx=50,y=100;//定义常量，便于修改intAvailable[x];//各种资源可利用的数量intAllocation[y][y];//各进程当前已分配的资源数量intMax[y][y];//各进程对各类资源的最大需求数intNeed[y][y];//还需求矩阵intRequest[x];//申请各类资源的数量intWork[x];//工作向量，表系统可提供给进程运行所需各类资源数量intFinish[y];//表系统是否有足够的资源分配给进程，0为否，1为是intp[y];//存储安全序列inti,j;//全局变量，主要用于循环语句中intn,m;//n为进程的数量,m为资源种类数intl=0,counter=0;1.5.2函数声明intshuzi(intsz);//数字判断函数，还可使用voidshuzi(int&sz);方式voidchushihua();//系统初始化函数voidsafe();//安全性算法函数voidbank();//银行家算法函数voidshowdata();//函数showdata,输出当前资源分配情况1.5.3主函数结构intmain(){system(color06f);//设置当前窗口的背景色和前景色cout……//显示程序开始提示信息chushihua();//初始化函数调用coutendlendl;showdata();//输出初始化后的状态safe();//安全性算法函数调用if(ln){cout\n当前状态不安全，无法申请,程序退出!!!!!endl;coutendl;system(pause);return0;//break;}else{inti;//局部变量l=0;cout\n安全的状态!!!endl;cout安全序列为:;coutendl进程(p[0]);//输出安全序列，考虑显示格式，先输出第一个for(i=1;in;i++){cout==进程(p[i]);}for(i=0;in;i++)Finish[i]=0;//所有进程置为未分配状态coutendlendl;}bank();//银行家算法函数调用return0;}1.5.4银行家算法：设Requesti是进程Pi的请求向量，如果Requesti[j]=K，表示进程Pi需要K个Ri类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：（1）如果Requesti[j]=Need[i,j]，便转向步骤2；否则认为出错，因为它所需的资源数已经超过了它所宣布的最大值。（2）如果Requesti[j]=Available[j]，便转向步骤3；否则表示尚无足够资源，Pi需等待。（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值。Available[j]=Available-Requesti[j];Allocation[i,j]=Allocation[i,j]+Requesti