操作系统课程设计银行家算法样本.docx

操作系统课程设计题目：银行家算法设计与实现院、 系： 计算机信息与技术系 学科专业： 计算机科学与技术 学 号： B10060123 学生姓名： 徐飞 指引教师 ： 姜虹 06月目录一、绪论1二、需求分析22.1银行家算法的描述22.2银行家算法模拟系统流程图32.3模拟系统用况分析42.4模拟系统用况规约42.4.1用况名称：创建进程42.4.2用况名称：执行进程5三、总体设计73.1系统的分层模型73.2系统部署73.3系统的静态模型8四、详细设计94.1交互层设计94.2交互逻辑层设计94.3控制层设计114.3进程层设计124.4资源层设计12五、系统实现145.1交互层的实现145.2交互逻辑层的实现155.3控制层的实现185.3进程层的实现215.4资源层的实现22六、测试与分析246.1系统资源初始化测试246.2系统资源初始状态的设置246.3进程初始化测试246.4进程初始化设置256.5执行进程测试25课程设计总结26参考文献27附录A28一、绪论在具备多道程序并发执行能力系统中，系统资源运用率、进程执行效率都大幅增长，但也许发生“死锁”危险。所谓死锁，是指各种进程因竞争资源而导致一种僵局，若无外力作用，这些进程都将永远不能再向前推动。而死锁产生因素有两点：竞争资源和进程推动顺序不合法。为了避免死锁，使得进程执行可以顺利完毕，引入银行家算法进行解决。银行家算法是具备代表性避免死锁算法，由于该算法能用于银行系统钞票贷款发放而得名。银行家算法包括三个方面内容：1) 相应数据构造。2) 银行家算法。3) 安全性算法。其中相应数据构造定义了银行家算法中需要使用若干数据构造，银行家算法操作数据构造觉得安全性算法提供检测现场，安全性算法则是检测现场与否出于安全态。系统安全状态是指可以按照某种顺序，来为每个进程分派其所需资源，直至最大需求，使每个进程都可顺序完毕。若系统不存在这样一种安全序列，则称系统出于不安全状态。二、需求分析问题描述：银行家算法是避免死锁有效办法，为了验证银行家算法可以避免死锁，需要编写程序模仿银行家算法并加以验证。2.1银行家算法描述银行家算法所涉及数据构造：1) 可运用资源向量Avaliable它是一种vector向量，可被初始化任意长度，其中每一种元素代表一类可运用资源数目。其值随着该类资源分派和回收而动态变化。2) 最大需求矩阵Max这是一种nm矩阵，她定义了系统中n个进程中每一种进程对m类资源最大需求。3) 分派矩阵Allocation这是一种nm矩阵，她定义了系统中每一类资源当前已分派给每一进程资源数。4) 需求矩阵Need它是一种nm矩阵，用以表达每一种进程尚需各类资源数。以上三个矩阵间存在下述关系：Need=Max-Allocation银行家算法：设Request是某一进程祈求向量。当进程发出祈求后，系统按下列环节进行检查：1) 如果RequestNeed，则转向环节2；否则以为出错，由于她所需要资源数已超过她所宣布最大值。2) 如果RequestAvaliable，则转向环节3；否则表达系统中尚无足够资源，进程必要等待。3) 系统进行试分派：Avaliable=Avaliable-RequestAllocation=Allocation=RequestNeed=Need-Request4)系统执行安全性检查，若系统处在安全态，则正式将资源分派给进程；若处在不安全态，则将本次分派作废，回滚到分派前状态，并告知进程等待。安全性算法：1)设立两个工作向量工作向量Work。她表达系统可提供应进程继续运营所需要各类资源数目，她具有m个元素，执行安全性算法开始时，Work=Avaliable。Finish。她表达系统与否有足够资源分派给进程，使之运营完毕，初始状态为Finishi=false；当有足够资源分派给进程时，Finishi=true。2)从进程集合中找到一种能满足下列条件进程： Finishi=false NeedWork如找到，执行环节3，否则，执行环节43)当某一进程获得资源后，可顺利执行，直至完毕，并释放出分派给她资源，故应执行：Work= Work+ AllocationFinishi=trueGo to step 24)如果所有进程Finishitrue，则表达系统处在安全状态；否则系统处在不安全状态。2.2银行家算法模仿系统流程图银行家算法模仿系统流程图如图2.1所示图 2.1 系统流程图2.3模仿系统用况分析银行家算法模仿系统用况图如图2.2所示图 2.2 模仿系统用况图2.4模仿系统用况规约2.4.1用况名称：创立进程1.简要阐明该用况描述顾客如何通过使用模仿系统进行创立进程工作。2.事件流2.1基本流1.数据合法性检查顾客选取“创立进程”选项，系统对顾客输入合法性进行检查。2.提示顾客输入创立进程个数顾客输入进程个数。3.数据合法性检查对顾客输入数据进行合法性检查4.初始化进程所需资源量提示顾客输入进程所需资源量。5.数据合法性检查对顾客输入数据进行合法性检查2.2备选流备选流一：在基本流环节1中，规则检查不通过，提示输入数据不合法，请重新输入。备选流二：在基本流环节3中，规则检查不通过，提示输入数据不合法，请重新输入。备选流三：在基本流环节5中，规则检查不通过，提示输入数据不合法，请重新输入。3.用例场景3.1成功场景成功初始化进程信息：基本流。3.2失败场景数据合法性检查不通过：备选流一。数据合法性检查不通过：备选流二。数据合法性检查不通过：备选流三。4.特殊需求无5.前置条件顾客已初始化系统。6.后置条件显示安全序列。显示各数据构造信息。显示输入数据有误，请重新输入。显示系统初始状态处在不安全态，进程创立失败，并退出系统。7.扩展点无2.4.2用况名称：执行进程1.简要阐明该用况描述管理员如何使用执行进程功能测试银行家算法。2.事件流2.1基本流1.数据合法性检查顾客选取“执行进程”选项，系统对顾客输入合法性进行检查。2.提示顾客需要执行进程编号顾客输入进程号。3.数据合法性检查对顾客输入数据进行合法性检查4.输入进程祈求向量顾客按照提示输入祈求向量。5.数据合法性检查检查顾客输入数据合法性。6.返回安全序列和各数据构造系统解决进程祈求向量，并返回安全序列和数据构造。2.2备选流备选流一：在基本流环节1中，规则检查不通过，提示输入数据不合法，请重新输入。备选流二：在基本流环节3中，规则检查不通过，提示输入数据不合法，请重新输入。备选流三：在基本流环节5中，规则检查不通过，提示输入数据不合法，请重新输入。备选流四：在基本流环节6中，规则检查不通过，提示输入祈求向量有问题，请进程等待。3.用例场景3.1成功场景进程成功被分派资源：基本流。3.2失败场景数据合法性检查不通过：备选流一。数据合法性检查不通过：备选流二。数据合法性检查不通过：备选流三。数据不满足系统规定：备选流四。4.特殊需求无5.前置条件顾客已创立进程。6.后置条件显示安全序列。显示各数据构造信息。显示输入数据有误，请重新输入。显示系统资源局限性进程需要等待。显示系统处在不安全态，进程需要等待。7.扩展点无三、总体设计3.1系统分层模型图3.1 系统分层模型图系统分层模型如图3.1所示。交互层：重要功能是为了与顾客进行交互，涉及系统初始化，创立各种进程，置进程祈求向量。交互逻辑层：负责将顾客交互信息与控制层互换。进程层：重要功能是为了创立进程，并交给控制层进行管理。控制层：负责管理进程与资源，是整个系统核心某些，银行家算法与安全性算法均在这一层中。资源层：重要负责管理各种资源向量或矩阵。3.2系统布置系统被布置在控制台运营。之因此选取控制台是由于可以让咱们开发模仿系统时候更加专注于业务，而不是花太多精力在非业务功能上。3.3系统静态模型图3.2 系统静态模型图模仿系统共有3个类、4中新数据类型（其中4种新数据类型用衍形加以定义）。1)_Resource类掌管全局资源，各种数据构造都在其中定义，目是要把操作与数据分离，便于程序设计以及维护。其中M是资源种类数，Available是可运用资源向量，Max是最大需求矩阵，Allocation是分派矩阵，Need是需求矩阵。2)_Process类是进程类，用来实例化进程。其中Request是需求向量。可用_Process来实例化任意个进程，从而使程序扩展性、安全性以及构造都得到极大提高。3)_Control类负责对系统既有资源以及进程进行控制。其中add_Process办法负责将进程添加到控制类中，run_Process办法就是银行家算法，而safeChecked办法就是系统安全性算法。四、详细设计4.1交互层设计由于系统是被布置在控制台上，因此交互层实现比较简朴。交互层界面显示如图4.1所示。图4.1 模仿系统选取菜单4.2交互逻辑层设计交互逻辑层作用是将顾客输入信息与控制层进行协作。vector create(_Resource &r,_Control &c)（创立进程）设计如图4.2所示。图4.2 create函数流程图void run(vector &p,_Resource &r,_Control &c)（执行进程）设计如图4.3所示。图4.3 run函数流程图void out(vector &p,_Resource &r,_Control &c) 设计如图4.4所示。图4.4 out函数流程图4.3控制层设计_Control类设计。1) void add_Process(_Process &p,_Resource &r)办法设计如图4.5所示。图4.5 add_Process办法流程图2) int run_Process(_Process &p,int n,_Resource &r)（银行家算法）设计如图4.6所示。图4.6 银行家算法流程图3) bool safeChecked(_Resource &r_2)（安全性算法）设计如图4.7所示图4.7 安全性算法流程图4.3进程层设计类_Process设计void init(_Resource &r)办法设计如图4.8所示。图4.8 init办法流程图4.4资源层设计类_Resource设计void init()办法设计如图4.9所示。图4.9 init办法流程图五、系统实现系统实现采用C+语言，并使用Microsoft Visual Studio 作为平台进行实现。5.1交互层实现交互层被直接设计成main函数：int main()_Resource r;r.init();_Control c(r);vector p;bool is=false;while(true)int x;coutendl;cout1.创立进程endl;cout2.执行一种进程endl;cout3.退出x;if(cin.fail()cout您输入数据不合法，请重新输入！endl;cin.clear();cin.sync();continue;elseif(x=0)cout您输入数据不合法，请重新输入！endl;cin.clear();cin.sync();continue;cin.clear();cin.sync();break;switch(x)case 1:p=create(r,c),is=true;break;case 2:if(is)run(p,r,c);elsecout您尚未创立进程！endl;break;case 3:exit(0);default:cout输入数据不合法，请重新输入！endl;/输出各矩阵状态out(p,r,c);return 0;5.2交互逻辑层实现1.vector create(_Resource &r,_Control &c)（创立进程）实现。vector create(_Resource &r,_Control &c)cout请输入需要创立进程数目：i;if(cin.fail()cout您输入数据不合法，请重新输入！endl;cin.clear();cin.sync();continue;elseif(i=0)cout您输入数据不合法，请重新输入！endl;cin.clear();cin.sync();continue;cin.clear();cin.sync();break;vector p;/进程初始化_Process aaa;for(int j=0;ji;j+)p.push_back(aaa);int x=0;for(vector:iterator iter=p.begin();iter!=p.end();iter+)coutPx初始化endl;(*iter).init(r);x+;/添加进程for(vector:size_type index=0;index!=p.size();index+)c.add_Process(pindex,r);/初始安全态检查if(c.safeChecked(r);elsecout系统初始状态不安全！endl;system(pause);exit(0);return p;2.void run(vector &p,_Resource &r,_Control &c)（执行进程）实现void run(vector &p,_Resource &r,_Control &c)int i;cout请输入需要执行进程号：i;if(cin.fail()cout您输入数据不合法，请重新输入！endl;cin.clear();cin.sync();continue;elseif(i0)cout您输入数据不合法，请重新输入！endl;cin.clear();cin.sync();continue;cin.clear();cin.sync();break;cout初始化第i个进程祈求向量：endl;/置进程资源祈求向量for(vector:size_type sz=0;sz!=pi.Request.size();sz+)cout请输入祈求向量第sz个值：k;if(cin.fail()cout您输入数据不合法，请重新输入！endl;cin.clear();cin.sync();continue;elseif(k=0)cout您输入数据不合法，请重新输入！endl;cin.clear();cin.sync();continue;cin.clear();cin.sync();break;pi.Requestsz=k;c.run_Process(pi,i,r);3.void out(vector &p,_Resource &r,_Control &c) 实现。void out(vector &p,_Resource &r,_Control &c)/输出Available矩阵coutAvailable:endl;for(vector:size_type sz=0;sz!=r.Available.size();sz+)coutr.Availablesz ;coutendl;/输出Max矩阵coutMax:endl;for(vector:size_type i=0;ir.Max.size();i+)for(vector:size_type sz=0;szr.Maxi.size();sz+)coutr.Maxisz ;coutendl;/Allocation矩阵coutAllocation:endl;for(vector:size_type i=0;ir.Allocation.size();i+)for(vector:size_type sz=0;szr.Allocationi.size();sz+)coutr.Allocationisz ;coutendl;/输出需求矩阵coutNeed:endl;for(vector:size_type i=0;ir.Need.size();i+)for(vector:size_type sz=0;szr.Needi.size();sz+)coutr.Needisz ;coutendl;5.3控制层实现_Control类实现。1.void add_Process(_Process &p,_Resource &r)办法实现。void add_Process(_Process &p,_Resource &r)N+;/进程数加1/置最大需求矩阵Max_row mr;for(vector:iterator iter=p.Request.begin();iter!=p.Request.end();iter+)mr.push_back(*iter);r.Max.push_back(mr);/置分派矩阵Allocation_row ar;for(int i=0;ir.getM();i+)ar.push_back(0);r.Allocation.push_back(ar);/置需求矩阵Need_row nr;for(vector:iterator iter=p.Request.begin();iter!=p.Request.end();iter+)nr.push_back(*iter);r.Need.push_back(nr);2.int run_Process(_Process &p,int n,_Resource &r)（银行家算法）设计如图4.6所示。int run_Process(_Process &p,int n,_Resource &r)/先判断Request=Needbool temp_1=true;for(vector:size_type index=0;index!=p.Request.size();index+)if(p.Requestindexr.Neednindex)cout祈求出错！由于进程所需要资源数已超过它所宣布最大值。endl;return 1;/再判断Request=Availablefor(vector:size_type index=0;index!=p.Request.size();index+)if(p.Requestindexr.Availableindex)cout系统中尚无足够资源，Pn必要等待！endl;return 2;/进行试分派_Resource r_1=r;vector:iterator iter_2=r_1.Available.begin();vector:iterator iter_3=r_1.Allocationn.begin();vector:iterator iter_4=r_1.Needn.begin();for(vector:iterator iter_1=p.Request.begin();iter_1!=p.Request.end();iter_1+)/Available:=Available-Request*iter_2=*iter_2-*iter_1;/Allocation:=Allocation+Request*iter_3=*iter_3+*iter_1;/Need:=Need-Request*iter_4=*iter_4-*iter_1;/迭代器移向下一种元素iter_2+;iter_3+;iter_4+;/执行安全性检查if(safeChecked(r_1)r=r_1;/判断此进程与否获得所有资源，若获得，则让其执行完毕后释放bool temp=true;for(int i=0;ir.getM();i+)if(r.Needni!=0)temp=false;break;if(temp)/置最大需求矩阵for(int i=0;ir.getM();i+)r.Maxni=0;/且置可运用资源向量for(int i=0;ir.getM();i+)r.Availablei+=r.Allocationni;r.Allocationni=0;cout进程Pn执行完毕，已释放资源！endl;return 0;elsecout系统不处在安全态，Pn进程需要等待endl;return 3;3.bool safeChecked(_Resource &r_2)（安全性算法）实现。bool _Control:safeChecked(_Resource &r_2)vector Work;/初始化工作向量for(vector:iterator iter=r_2.Available.begin();iter!=r_2.Available.end();iter+)Work.push_back(*iter);vector Finish;for(vector:iterator iter=r_2.Need.begin();iter!=r_2.Need.end();iter+)Finish.push_back(false);/找出Finishi=false且Need=Work项step2:for(vector:size_type i=0;i!=r_2.Need.size();i+)if(!Finishi)bool temp=false;for(vector:size_type index=0;index!=Work.size();index+)if(r_2.Neediindex=Workindex)temp=true;elsetemp=false;break;if(temp)vector:iterator iter_2=r_2.Allocationi.begin();for(vector:iterator iter_1=Work.begin();iter_1!=Work.end();iter_1+)*iter_1=*iter_1+*iter_2;iter_2+;coutPi ;Finishi=true;goto step2;/本来不应当使用goto语句，但由于在此使用goto语句更显以便，故破例用之/判断所有进程Finish与否都为true，是则返回true，否则返回falsefor(vector:size_type index=0;index!=Finish.size();index+)if(Finishindex);elsereturn false;return true;5.3进程层实现类_Process设计void init(_Resource &r)办法实现。void init(_Resource &r)for(int i=0;ir.getM();i+)int temp;while(true)/*输入数据合法性检查*/cout请输入第i+1类资源需求量：temp;if(cin.fail()cout您输入数据不合法，请重新输入！endl;cin.clear();cin.sync();continue;elseif(temp=0)cout您输入数据不合法，请重新输入！endl;cin.clear();cin.sync();continue;cin.clear();cin.sync();break;Request.push_back(temp);5.4资源层实现类_Resource设计void init()办法实现。void _Resource:init()while(true)/*输入数据合法性检查*/cout请初始化系统资源种类数：M;if(cin.fail()cout您输入数据不合法，请重新输入！endl;cin.clear();cin.sync();continue;elseif(M=0)cout您输入数据不合法，请重新输入！endl;cin.clear();cin.sync();continue;cin.clear();cin.sync();break;for(int i=0;iM;i+)int temp;while(true)/*输入数据合法性检查*/cout请初始化系统中第i+1类资源数目：temp;if(cin.fail()cout您输入数据不合法，请重新输入！endl;cin.clear();cin.sync();continue;elseif(temp=0)cout您输入数据不合法，请重新输入！endl;cin.clear();cin.sync();continue;cin.clear();cin.sync();break;Available.push_back(temp);六、测试与分析本测试均采用黑盒测试6.1系统资源初始化测试测试用例预期成果实际成果请输入资源种类数：任意非数字字符1.应提示“输入数据不和法，请重新输入！”请输入资源种类数：负整数1.应提示“输入数据不和法，请重新输入！”6.2系统资源初始状态设立Available=7,5,3详细设立如图6.1所示。图6.1 初始资源设立6.3进程初始化测试测试用例预期成果实际成果请输入你所需要创立进程数：31.不应提示错误信息初始化各类资源需求量P0Request=4,4,4P1Request=1,1,1P2Request=1,1,11. 应提示“系统初始状态不安全！”2. 提示“按任意键退出系统”6.4进程初始化设立P0Request=1,2,3P1Request=1,2,2P2Request=1,2,26.5执行进程测试测试用例预期成果实际成果请输入你所需要执行进程号：0并置Request=4,4,41.应提示祈求出错信息，所需资源超过其所宣布最大值请输入你所需要执行进程号：1并置Request=1,1,11. 应直接输出安全序列2. 输出各数据构造现状请输入你所需要执行进程号：0并置Request=1,2,31. 应提示系统资源局限性，P0进程需等待2. 输出各数据构造现状请输入你所需要执行进程号：0并置Request=1,2,21. 应提示系统处在不安全态，P0进程需等待2. 输出各数据构造现状请输入你所需要执行进程号：1并置Request=0,1,11. 输出安全序列2. 提示进程P1执行完毕并释放资源3. 输出各数据构造现状课程设计总结在这次课程设计中，我发现大多数状况下咱们在做一种项目时，并不是一开始就具备完毕这项项目所有知识。这就规定咱们学会如何去迅速学会做项目所需要所有知识。遇到有些不会解决，我会上网去查，查某些对象、容器用法，如vector等容器。此前我对这些对象或容器用法并不是太熟悉，但当前我不但掌握了她们用法，更重要是我学会了如何去学习，然后迅速地应用到我所需要项目当中。在做这个银行家算法模仿系统时，我把它当作了一种产品去做，因此每个细节考虑虽不完全，但也周到。但这并不能阐明什么，由于诸多软件都是通过升级方式来弥补自身缺陷，我银行家算法模仿系统也是如此。在使用之中发现问题后再去积极修改问题，使得软件越来越完善。并且只有这样才是软件开发必经之路，由于没有什么事物毕生下来就是完美，都是在通过追求卓越过程中完善自己，继而达到巅峰。在这次课程设计中我还领悟了一种重大问题：在开发一种软件过程中，把整个系统框架精确描述出来是非常重要。由于咱们背面编码式样在整个系统框架基本之上进行，如果系统框架在搭建时候浮现了模块冲突，那会影响整个软件开发进度，最后就会引起软件危机。而这是咱们所不但愿看到。因此，在软件开发之前，一定要详细讨论整个系统框架，保证合理状况下再进行下一步工作，严格把开