银行家算法

山东理工大学计算机学院课程设计（操作系统与编译器内核设计）班级计科1004姓名邢贵洋学号1011051140指导教师菊传香二○一三年十一月二十二日课程设计任务书及成绩评定课题名称1.银行家算法的设计与实现Ⅰ、题目的目的和要求：（1）设计一个小型的死锁避免系统，在系统中体现银行家算法及安全性算法；（2）用户请求及系统当前的资源分配状态从键盘输入；（3）输出能够判断当前的系统状态是否是安全的？若安全，给出至少一个安全序列；若不安全，给出原因（4）某进程提出一个请求，该请求能够满足，但会使系统进入不安全状态（5）某进程提出一个请求，该请求不能满足Ⅱ、设计进度及完成情况日期内容11.11-11.15选取参考书，查阅有关文献资料，完成课程设计说明书内容1部分。完成课程设计说明书内容2-4部分11.16~11.17创建相关数据结构,录入源程序11.18~11.20调试程序并记录调试中的问题，完成课程设计说明书第5部分。11.21系统测试，演示设计成果，考核成绩。11.22整理课程设计说明书，上午11时，由学习委员交课程设计说明书(计算机科学系9#213或直接交给指导教师)Ⅲ、主要参考文献及资料[1]汤子赢等.计算机操作系统（第二版）.西安电子科技大学出版社,2006.8[2]冯耀霖等.操作系统，西安电子科技大学出版社.1992[3]张尧学等.计算机操作系统教程(第2版).清华大学出版社,2001.4[4]谭耀铭.操作系统.中国人民大学出版社,2003.4[5]AbrahamSilberschatz,PeterGalvin&GregGagne,AppliedOperatingSystemConcepts,HigherEducationPress,2002Ⅳ、成绩评定：设计成绩：（教师填写）指导老师：（签字）二○一三年十一月二十二日目录一、设计目的.............................................1二、设计内容.............................................1三、设计原理.............................................1四、算法实现.............................................2五、流程图...............................................4六、源程序...............................................8七、运行示例及结果分析..................................15八、心得体会............................................19-1-银行家算法一、设计目的1）掌握死锁的产生的原因、产生死锁的必要条件和处理死锁的基本方法。2）了解多道程序系统中，多个进程并发执行的资源分配。3）掌握预防死锁的方法，系统安全状态的基本概念4）理解死锁避免在当前计算机系统不常使用的原因。5）掌握银行家算法，了解资源在进程并发执行中的资源分配策略。二、设计内容设计一个n个并发进程共享m个系统资源的系统。进程课动态申请资源和释放资源，系统按照进程的申请动态的分配资源。用银行家算法设计实现。三、设计原理我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。为保证资金的安全,银行家规定:(1)当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客;(2)顾客可以分歧贷款,但贷款的总数不能超过最大需求量;(3)当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款;(4)当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金.操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求-2-量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。四、算法实现（1）初始化这组进程的最大资源请求和依次申请的资源序列。把各进程已占用和需求资源情况记录在进程控制块中。假定进程控制块的内容包括：进程名，状态，当前申请量，资源需求总量，已占资源量，能执行完标志。其中，进程的状态有：就绪、等待和完成。当系统不能满足进程的资源请求时，进程处于等待态。资源需求总量表示进程运行过程中对资源的总的需求量。已占资源量表示进程目前已经得到但还未归还的资源量。因此，进程在以后还需要的剩余资源量等于资源需要总量减去已占资源量。显然每个进程的资源需求总量不应超过系统拥有的资源总量。（2）银行家算法分配资源的原则是：当某个进程提出资源请求时，假定先分配资源给它，然后查找各进程的剩余请求，检查系统的剩余资源量是否由于进程的分配而导致系统死锁。若能，则让进程等待，否则，让进程的假分配变为真分配。a)查找各进程的剩余请求，检查系统的剩余资源量是否能满足其中一进程。如果能，则转b)。b)将资源分配给所选的进程，这样，该进程已获得资源最大请求，最终能运行完成。标记这个进程为终止进程，并将其占有的全部资源归还给系统。重复第a)步和第b)步，直到所有进程都标记为终止进程，或直到一个死锁发生。若所有进程都标记为终止进程，则系统的初始状态是安全的，否则为不安全的。若安全，则正式将资源分配给它，否则，假定的分配作废，让其等待。数据结构：#defineMAXPROCESS50/*最大进程数*/-3-#defineMAXRESOURCE100/*最大资源数*/intAVAILABLE[MAXRESOURCE];/*可用资源数组*/intMAX[MAXPROCESS][MAXRESOURCE];/*最大需求矩阵*/intALLOCATION[MAXPROCESS][MAXRESOURCE];/*分配矩阵*/intNEED[MAXPROCESS][MAXRESOURCE];/*需求矩阵*/intREQUEST[MAXPROCESS][MAXRESOURCE];/*进程需要资源数*/boolFINISH[MAXPROCESS];/*系统是否有足够的资源分配*/intp[MAXPROCESS];/*记录序列*/intWork[MAXRESOURCE];/*工作数组*/intm,n;/*m个进程,n个资源*/stringshowdata1[4]={max,allo,need,aval};/*绘制资源以及进程状态时使用*/stringshowdata2[5]={work,need,allo,w+al,finish};/*绘制银行家算法过程时使用*/-4-五、流程图1：主函数流程图：结束开始调用初始化函数(Init)图1主函数流程图安全性检测(Safe)银行家算法(Bank)安全YN-5-2：初始化流程图结束返回Init()开始输入进程的数目m图2初始化流程图输入资源的种类n输入AVAILABLE[i]输入正确YN输入MAX[i][j]输入ALLOCATION[i][j]显示当前系统状态(iShow)提示错误，重新输入相应数据-6-3：安全性检测流程图结束返回Safe()开始绘制结果表格头部(fShow)图3安全性检测流程图Work[i]=AVAILABLE[i];FINISH[i]=false;输出找到的安全序列，返回trueNEED[i]=Work&&FINISH[i]=falseYNWork[i]+=ALLOCATION[i]FINISH[i]=true输出进程及资源变化结果系统不安全，返回false所有进程FINISH[i]=ture;YN-7-4:银行家算法流程图结束返回Bank()开始输入请求资源的进程cusneed图4银行家算法流程图输入进程请求资源REQUEST[cusneed][i]提示安全,允许请求REQUEST[cusneed][i]=NEED[cusneed][i]YNAVAILABLE[i]-=REQUEST[cusneed][i];ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];NEED[cusneed][i]-=REQUEST[cusneed][i];分配资源分配资源操作回滚，恢复到未分配REQUEST[cusneed][i]=AVAILABLE[i]YNNSafe();继续分配？YN-8-六、源程序#includeiostream#includeiomanip#includestringusingnamespacestd;#defineMAXPROCESS50/*最大进程数*/#defineMAXRESOURCE100/*最大资源数*/intAVAILABLE[MAXRESOURCE];/*可用资源数组*/intMAX[MAXPROCESS][MAXRESOURCE];/*最大需求矩阵*/intALLOCATION[MAXPROCESS][MAXRESOURCE];/*分配矩阵*/intNEED[MAXPROCESS][MAXRESOURCE];/*需求矩阵*/intREQUEST[MAXPROCESS][MAXRESOURCE];/*进程需要资源数*/boolFINISH[MAXPROCESS];/*系统是否有足够的资源分配*/intp[MAXPROCESS];/*记录序列*/intWork[MAXRESOURCE];/*工作数组*/intm,n;/*m个进程,n个资源*/stringshowdata1[4]={max,allo,need,aval};/*输出表格用标题*/stringshowdata2[5]={work,need,allo,w+al,finish};/*输出表格用标题*/voidiShow(){intsize,size2;cout系统;for(intk=0;k4;k++){size=showdata1[k].length();size2=(n*3+5-size)/2;/*计算出字符前端的空格*/coutsetw(size2+size)showdata1[k]setw(size2);/*使得文字在资源标志ABC总宽度下剧中*/}coutendl;cout资源;for(intk=0;k4;k++){charsourcename='A';/*资源命名，从A开始*/cout;for(intkk=0;kkn;kk++){coutsourcename;-9-sourcename++;}cout;}coutendl;for(intii=0;iim;ii++){coutPii;/*输出进程名及状态*/for(intjj=0;jjn;jj++)coutsetw(3)MAX[ii][jj];cout;for(intjj=0;jjn;jj++)coutsetw(3)ALLOCATION[ii][jj];cout;for(intjj=0;jjn;jj++)coutsetw(3)NEED[ii][jj];cout;if(ii==0){for(intiii=0;iiin;iii++)coutsetw(3)AVAILABLE[iii];}coutendl;}}voidfShow()/*显示表格*/{cout系统;for(intk=0;k5;k++){intsize=showdata2[k].length();intsize2=(n*3+5-size)/