银行家算法课程设计

XPANTECHNOLOGICALUNIVERSITY操作系统课程设计报告题目：银行家算法安全性算法院（系）:计算机科学与工程专业:软件工程班级:130608班学生:姚骏川学号：8指导教师：姜虹2015年12月28目录摘要错误!未定义书签。1绪论错误!未定义书签。前吉错误!未定义书签。研究意义错误!未定义书签。2需求分析错误!未定义书签。題目描述错误!未定义书签。银行家算法错误!未定义书签。基本要求错误!未定义书签。/目的错误!未定义书签。3概要设计错误!未定义书签。算法思路：错误!未定义书签。银行家算法步骤错误!未定义书签。安全性算法步骤错误!未定义书签。3.4数据结构：错误!未定义书签。4详细设计错误!未定义书签。主要函数的核心代码：错误!未定义书签。系统主要过程流程图错误!未定义书签。银行家算法流程图错误!未定义书签。5测试与分析错误!未定义书签。测试数据错误!未定义书签。银行家算法的演示错误!未定义书签。分配资源由于大于可利用资源则失败错误!未定义书签。增加一个作业得到不安全序列错误!未定义书签。分配资源由于大于最大资源则失败"错误!未定义书签。£附录源程序清单错误!未定义书签。1绪论前言Dijkstra(1965)提出了一种能够避免死锁的调度算法，称为银行家算法。它的模型基于一个小城鎮的银行家，他向一群客户分别承诺了一定的贷款额度，每个客户都有一个贷款额度，银行家知道不可能所有客户同时都需要最大贷款额，所以他只保留一定单位的资金来为客户服务，而不是满足所有客户贷款需求的最大单位。这里将客户比作进程，贷款比作设备，银行家比作系统。客户们各自做自己的生意，在某些时刻需要贷款。在某一时刻，客户已获得的贷款和可用的最大数额贷款称为与资源分配相关的系统状态。一个状态被称为是安全的，其条件是存在一个状态序列能够使所有的客户均得到其所需的贷款。如果忽然所有的客户都申请，希望得到最大贷款额，而银行家无法满足其中任何一个的要求，则发生死锁。不安全状态并不一定导致死锁，因为客户未必需要其最大贷款额度，但银行家不敢抱这种侥幸心理。银行家算法就是对每一个请求进行检查，检查如果满足它是否会导致不安全状态。若是，则不满足该请求；否则便满足。检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户。如果可以，则这笔投资认为是能够收回的，然后接着检查下一个距最大需求最近的客户，如此反复下去。如果所有投资最终都被收回，则该状态是安全的，最初的请求可以批准。研究意义在多道程序系统中，多个进程的并发执行来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险一一死锁。所谓死锁(Deadlock),是指多个进程在运行过程中因争夺资源而造成的一种僵局(DeadlyEmbrace),当进程处于这种状态时，若无外力作用，他们都无法在向前推进。要预防死锁，有摒弃“请求和保持”条件，摒弃“不剥夺”条件，摒弃“环路等待”条件等方法。但是，在预防死锁的几种方法之中，都施加了较强的限制条件；而在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统状态分为安全状态和不安全状态，便可避免死锁的发生。而最具代表性的避免死锁的算法，便是Dijkstra的银行家算法。利用银行家算法，我们可以来检测CPU为进程分配资源的情况，决定CPU是否响应某进程的的请求并为其分配资源，从而很好避免了死锁的产生。2需求分析题目描述银行家算法是一种最具有代表性的避免死锁的算法。要解释银行家算法，必须先解释操作系统的安全状态和不安全状态。所谓安全状态，是指系统能按照某种进程顺序｛P1,P2,…，Pn｝(称｛P1,P2,…,Pn｝序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺利完成。安全状态一定没有死锁发生。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。那么，什么是安全序列呢如果对每一个进程Pi(l<i<n),它以后尚需要的资源量不超过系统当前可利用的资源量与所有的进程Pj(j<n)所占有的资源量之和，则称此进程序列｛P1,P2,…,Pn｝是安全的，称作安全序列。银行家算法我们可以把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求资源相当于客户向银行家贷款。操作系统按银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程尚需求的资源量，若是系统现存的资源可以满足它尚需求的资源量，则按当前的申请量来分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程申请的资源量是否超过了它尚需的资源量。若超过则拒绝分配，若没有超过则再测试系统尚存的资源是否满足该进程尚需的资源量，若满足即可按当前的申请量来分配，若不满足亦推迟分配。基本要求设计用来保存：可利用资源向量Available>最大需求矩阵Max.分配矩阵Allocation、需求矩阵Need。(2)编写银行家算法，安全性检测算法。要求在不安全时输出错误信息。(3)编写输岀函数，能对进程申请后的系统状态进行输出。目的根据设计题目的要求，充分地分析和理解题目，叙述系统的要求，明确程序要求实现的功能以及限制条件。明白自己需要用代码实现的功能，清楚编写每部分代码的目的，做到有的放矢，有条理不遗漏的用代码实现银行家算法。3概要设计算法思路：先对用户提出的请求进行合法性检查，即检查请求是否大于需要的，是否大于可利用的。若请求合法，则进行预分配，对分配后的状态调用安全性算法进行检查。若安全，则分配；若不安全，则拒绝申请，恢复到原来的状态，拒绝申请。银行家算法步骤⑴如果RequestiV二Need,则转向步骤(2)；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。如果Request<or=Ava订able,则转向步骤(3)；否则，表示系统中尚无足够的资源，进程必须等待。系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值：Available=Available-Request[i]；Allocation二Allocation+Request；Need=Need-Request；系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。安全性算法步骤设置两个向量①工作向量Worko它表示系统可提供进程继续运行所需要的各类资源数目，执行安全算法开始时，Work二Allocation；②布尔向量Finisho它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finish[i]=false,当有足够资源分配给进程时，令Finish[i]=tnje°从进程集合中找到一个能满足下述条件的进程：Finish[i]=falseNeed<=Work；如找到，执行步骤(3)；否则，执行步骤(4)。当进程P获得资源后，可顺利执行，直至完成，并释放出分配给它的资源,故应执行：Work=Work+A11ocation；Finish[i]=true；转向步骤(2)。如果所有进程的Finish"]二true,则表示系统处于安全状态；否则,系统处于不安全状态。3.4数据结构：3.4.1主要用到的数据结构：仃)最大需求矩阵Max[][]已分配矩阵Allocation]][]仍需求矩阵Need[][]=Max[][]-Allocation[][]可利用资源向量Available[]申请各类资源向量Request[]工作向量work[],Finish]]存放安全序列temp[]存放系统可提供资源work[]资源的名字name[]3・4・2程序模块：int

main()3.4资源分配情况如下表:源情况MaxABCAllocationABCNeedABCAvailableABCP0753010743332P1322200122P2092302600P3222211011P4433002431结果截图:图图图图]2、・wCsXOodxwexrtra*nd£<1**<::1>«.4>\0\/%向\>立^4£杉（>十|**2、1><21>11^\乞・豪淀42・食？原丄心.匕称=«债涯的数丘=3濒源2的各J尔::B施源砸熬呈二3送源丁備■今尔=C资源的薮呈沙喬齡篦斟皇韻董矣而求呈<5-3矩阵>【gJ=753322V02222话侖入卷进程己纟圣申话的资源呈矩阵>"】：ld“"002075301074J1322200122290230260032222110114433WW2431充疑參全的Y进程名分配的存列=1->3->0->2->4Mcx«ncNeed«nCH1locrtCion«nc002系统目前可用的谶源LagJLJLcbJLuJ=dJBC332银行家算法的演示进行资源的分配，为进程1分配了（1,0,2）,进行安全算法得到如下的结果。Max辺程名aBCAllocationaBC0Max辺程名aBCAllocationaBC0753fl1R13223022902302322221144.33002泳统還安缶的？分配的序列：1->3->0>2->4C：2索统目前可用的资源[nvaliablc]:aBC230NeedaBC74302060S01149丄分配资源由于大于可利用资源则失败。增加一个作业得到不安全序列O请•迭择功尙官号：5请输入该徉业的展大需求呈况二&»=系统目前可用=■DCi3007530X07-43X32N3N2M290230260O32222X1RX1-443302431.5666000666进程茗NeedBCMaxBCA1locjmI;IoneBC分配资源由于大于最大资源则失败。6总结操作系统的基本特征是并发与共享。系统允许多个进程并发执行，并且共享系统的软、硬件资源。为了最大限度的利用计算机系统的资源，操作系统应采用动态分配的策略，但是这样就容易因资源不足，分配不当而引起''死锁”。而我本次课程设计就是得用银行家算法来避免"死锁”。银行家算法就是一个分配资源的过程，使分配的序列不会产生死锁。此算法的中心思想是：按该法分配资源时，每次分配后总存在着一个进程，如果让它单独运行下去，必然可以获得它所需要的全部资源，也就是说，它能结束，而它结束后可以归还这类资源以满足其他申请者的需要。在程序当中，我们也得强调一下对输入的合法性的判断。比如，我们输入的欲申请资源的进程号没有在系统已存在的进程当中，或者进程号定义为整型，但是却错输成字母等情况，我们需要对这些情况进行判断，让程序报错返回而并非因错误而中断。这样的情况处理起来比较麻烦，相当于对每次输入针对各种不同的情况都得做判断。我也没有涵盖全部的输入，仅仅只是对输入的进程号不在已存在进程当中、以及输入的操作选择不存在两种情况分别作了判断，并且针对第二种情况设定了五次输入错误的话系统关闭的功能。而因为对于某些一一比如进程号一一本来设定就是整型，因此对输入的是字母的判别因比较复杂而未能加上。总之，银行家算法是避免死锁的主要方法，其思路在很多方面都非常值得我们来学习借鉴。参考文献汤小丹，梁红兵，哲凤屏，汤子瀛•计算机操作系统.西安：西安电子科技大学出版社，2007.严蔚敏，吴伟民•数据结构.北京：清华大学出版社，2006.附录源程序清单#include<>#include<>#include<>#defineFalse0#defineTrue1intMax[100][100]二{0}；//各进程所需各类资源的最大需求intAvaliable[100]={0}；//系统可用资源charname[100]={0}；//资源的名称intAllocation[100][100]={0}；//系统已分配资源intNeed[100][100]={0}；//还需要资源intRequest11001=;0：;//请求资源向量inttempt100]={0}；//存放安全序列intWork[100]={0};//存放系统可提供资源intM二100；//作业的最大数为100intN二100；//资源的最大数为100voidshowdata（）//显示资源矩阵{inti,j;cout«w系统目前可用的资源[Available]:M«endl；for（i=0；i<N；i++）cout<<name[i]<<'rH；cout«endl；for（j=0；j<N；j++）cout«Avaliable[j]«"'r；//输出分配资源cout«endl；cout«wMaxAllocationNeed"<〈endl；cout«H进程名“；for（j=0；j<3；j++）{for（i=0；i<N；i++）cout<<name[i]<<w"；TOC\o"1-5"\h\zcout«H“；}cout«endl；for（i=0；i<M；i++）{cout«ww«i«H“；for（j=0；j<N；j++）cout«Max[i][j]«'rH；cout<<'rw；for（j=0；j<N；j++）cout«Allocation[i][j]«"”;cout<<'rw；for（j=0；j<N；j++）cout<<Need[i][j]<<w'r；cout<<endl；}}intchangdata（inti）//进行资源分配{intj;for（j=0；j<M；j++）{Ava1iab1e[j]=Ava1iab1e[j]-Request[j]；Allocation[i][j]=Allocation[i][j]+Request[j]；Need[i][j]=Need[i][j]-Request[j]；}return1；}intsafe（）//安全性算法{inti,k=0,m,a,Finish[100]={0}；intj;intflag二0；Work[0|=Avaliable|0]；Work[l]=Avaliable[l]；Work[2]=Avaliable[2]；for（i=0；i<M；i++）{a=0；for（j=0；j<N；j++）{if（Finish[i]==False&&Need[i][j]<=Work[j]）{a++；if（a==N）{for（m=0；m<N；m++）Work[m]=Work[m]+Allocation[i][m]；//变分配数Finish[i]=True；temp[k]=i；i二T;k++；flag++；}}}}for（i=0；i<M；i++）{if（Finish[i]—False）{cout«M系统不安全H<<encll；//不成功系统不安全return-1；}cout«H系统是安全的!w«endl；//如果安全，输出成功cout«,r分配的序列："；for(i=0；i<M；i++){//输出运行进程数组cout<<temp[i]；if(i<M-l)cout«M->M；}cout«endl；return0；}voidshare()//利用银行家算法对申请资源对进行判定{charch；inti=0,j=0；ch='y';cout«H请输入要求分配的资源进程号(0-w«M-l«H)：H；cin»i；//输入须申请的资源号cout«w请输入进程w«i«w申请的资源:,r«endl；for(j=0；j<N；j++){cout«name[j]<〈"："；cin>>Request[j]；//输入需要申请的资源}for(j=0；j<N；j++){if(Request[j]>Need[i][j])//判断申请是否大于需求，若大于则出错{cout«M进程申请的资源大于它需要的资源”；cout«"分配不合理，不予分配Iw«endl；ch二'n'；break；}else{if(Request[j]>Avaliable[j])//判断申请是否大于当前资源，若大于则{〃出错cout«M进程,,«i«w申请的资源大于系统现在可利用的资源"；cout«'r分配出错，不予分配!'r«endl；ch=,n'；break；if(ch='y'){changdata(i)；//根据进程需求量变换资源showdata()；//根据进程需求量显示变换后的资源safeO；//根据进程需求量进行银行家算法判断}}voidaddresources(){//添加资源intn,flag；cout«H请输入需要添加资源种类的数量："；cin>>n；flag=N；N二N+n；for(inti=0；i<n；i++){cout«M名称："；cin>>name[flag]；cout«w数量："；cin>>Avaliable[flag++]；}showdata()；safe()；}voiddelresourcesO{//删除资源charming；inti,flag=l；cout«H请输入需要刪除的资源名称："；do{cin>>】ning；for(i=0；i<N；i++)if(ming二二name[i]){flag=0；break；}if(i=N)cout«H该资源名称不存在，请重新输入："；}while(flag)；for(intj=i；j<NT；j++){name[j]=name[j+1]；Avaliable[j]=Avaliable[j+l]；}N二N-l；showdata()；safe()；}voidchangeresources(){//修改资源函数cout«'*系统目前可用的资源[Available]:K<<endl；for(inti=0；i<N；i++)cout<<name[i]«'r：M«Avaliable[i]«endl；cout«w输入系统可用资源[Available]:"<<endl；cin>>Avaliable[O]>>Avaliable[l]»Avaliable[2]；cout«w经修改后的系统可用资源为H«endl；for(intk=0；k<N；k++)cout<<name[k]«H：w«Avaliable[k]<<endl；showdata()；safe()；}voidaddprocess(){〃添加作业intflag=M；M=M+1；cout«,r请输入该作业的最大需求量[Max],，«endl；for(inti=0；i<N；i++){cout<〈name[i]<〈"："；cin»Max[flag][i]；Need[flag][i]二Max[flag][订-Allocation[flag][i]；}showdata()；safe()；}intmain()//主函数{inti,j,number,choice,m,n,flaycharming；cout«*******************资源管理系统的设计与实现*****************"<<endl；cout«H请首先输入系统可供资源种类的数量：”；cin>>n；N二n；for(i=0；i<n；i++){cout«'r资源W«i+1«N的名称："；cin>>ming；name[i]=ming；cout«w资源的数量："；cin>>number；Avaliab