操作系统课程设计(银行家算法).docx

操作系统课程设计题目：银行家算法的设计与实现院、 系： 计算机信息与技术系 学科专业： 计算机科学与技术 学 号： B10060123 学生姓名： 徐飞 指导教师 ： 姜虹 ×××2012年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) 安全性算法。其中相应的数据结构定义了银行家算法中需要使用的若干数据结构，银行家算法操作数据结构以为安全性算法提供检测现场，安全性算法则是检测现场是否出于安全态。系统的安全状态是指能够按照某种顺序，来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成。若系统不存在这样一个安全序列，则称系统出于不安全状态。39二、需求分析问题描述：银行家算法是避免死锁的有效办法，为了验证银行家算法可以避免死锁，需要编写程序模拟银行家算法并加以验证。2.1银行家算法的描述银行家算法所涉及的数据结构：1) 可利用资源向量Avaliable它是一个vector向量，可被初始化任意长度，其中每一个元素代表一类可利用资源的数目。其值随着该类资源的分配和回收而动态的改变。2) 最大需求矩阵Max这是一个n×m的矩阵，他定义了系统中n个进程中的每一个进程对m类资源的最大需求。3) 分配矩阵Allocation这是一个n×m的矩阵，他定义了系统中每一类资源当前已分配给每一进程的资源数。4) 需求矩阵Need它是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。以上三个矩阵间存在下述关系：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<_Process> create(_Resource &r,_Control &c)（创建进程）的设计如图4.2所示。图4.2 create函数流程图void run(vector<_Process> &p,_Resource &r,_Control &c)（执行进程）的设计如图4.3所示。图4.3 run函数流程图void out(vector<_Process> &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 2010作为平台进行实现。5.1交互层的实现交互层被直接设计成main函数：int main()_Resource r;r.init();_Control c(r);vector<_Process> p;bool is=false;while(true)int x;cout<<endl;cout<<"1.创建进程"<<endl;cout<<"2.执行一个进程"<<endl;cout<<"3.退出"<<endl;while(true) /*输入数据合法性检查*/cin>>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<_Process> create(_Resource &r,_Control &c)（创建进程）的实现。vector<_Process> create(_Resource &r,_Control &c)cout<<"请输入需要创建的进程数目："<<endl;int i;while(true) /*输入数据合法性检查*/cin>>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<_Process> p;/进程初始化_Process aaa;for(int j=0;j<i;j+)p.push_back(aaa);int x=0;for(vector<_Process>:iterator iter=p.begin();iter!=p.end();iter+)cout<<"P"<<x<<"初始化"<<endl;(*iter).init(r);x+;/添加进程for(vector<_Process>: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<_Process> &p,_Resource &r,_Control &c)（执行进程）的实现void run(vector<_Process> &p,_Resource &r,_Control &c)int i;cout<<"请输入需要执行的进程号："<<endl;while(true) /*输入数据合法性检查*/cin>>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;cout<<"初始化第"<<i<<"个进程的请求向量："<<endl;/置进程的资源请求向量for(vector<int>:size_type sz=0;sz!=pi.Request.size();sz+)cout<<"请输入请求向量的第"<<sz<<"个值："<<endl; int k;while(true)/*输入数据合法性检查*/cin>>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<_Process> &p,_Resource &r,_Control &c) 的实现。void out(vector<_Process> &p,_Resource &r,_Control &c)/输出Available矩阵cout<<"Available:"<<endl;for(vector<int>:size_type sz=0;sz!=r.Available.size();sz+)cout<<r.Availablesz<<" "cout<<endl;/输出Max矩阵cout<<"Max:"<<endl;for(vector<Max_row>:size_type i=0;i<r.Max.size();i+)for(vector<int>:size_type sz=0;sz<r.Maxi.size();sz+)cout<<r.Maxisz<<" "cout<<endl;/Allocation矩阵cout<<"Allocation:"<<endl;for(vector<Allocation_row>:size_type i=0;i<r.Allocation.size();i+)for(vector<int>:size_type sz=0;sz<r.Allocationi.size();sz+)cout<<r.Allocationisz<<" "cout<<endl;/输出需求矩阵cout<<"Need:"<<endl;for(vector<Need_row>:size_type i=0;i<r.Need.size();i+)for(vector<int>:size_type sz=0;sz<r.Needi.size();sz+)cout<<r.Needisz<<" "cout<<endl;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<int>: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;i<r.getM();i+)ar.push_back(0);r.Allocation.push_back(ar);/置需求矩阵Need_row nr;for(vector<int>: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<int>:size_type index=0;index!=p.Request.size();index+)if(p.Requestindex>r.Neednindex)cout<<"请求出错！因为进程所需要的资源数已超过它所宣布的最大值。"<<endl;return 1;/再判断Request<=Availablefor(vector<int>:size_type index=0;index!=p.Request.size();index+)if(p.Requestindex>r.Availableindex)cout<<"系统中尚无足够的资源，P"<<n<<"必须等待！"<<endl;return 2;/进行试分配_Resource r_1=r;vector<int>:iterator iter_2=r_1.Available.begin();vector<int>:iterator iter_3=r_1.Allocationn.begin();vector<int>:iterator iter_4=r_1.Needn.begin();for(vector<int>: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;i<r.getM();i+)if(r.Needni!=0)temp=false;break;if(temp)/置最大需求矩阵for(int i=0;i<r.getM();i+)r.Maxni=0;/且置可利用资源向量for(int i=0;i<r.getM();i+)r.Availablei+=r.Allocationni;r.Allocationni=0;cout<<"进程P"<<n<<"执行完毕，已释放资源！"<<endl;return 0;elsecout<<"系统不处于安全态，P"<<n<<"进程需要等待"<<endl;return 3;3.bool safeChecked(_Resource &r_2)（安全性算法）的实现。bool _Control:safeChecked(_Resource &r_2)vector<int> Work;/初始化工作向量for(vector<int>:iterator iter=r_2.Available.begin();iter!=r_2.Available.end();iter+)Work.push_back(*iter);vector<bool> Finish;for(vector<Need_row>:iterator iter=r_2.Need.begin();iter!=r_2.Need.end();iter+)Finish.push_back(false);/找出Finishi=false且Need<=Work的项step2:for(vector<int>:size_type i=0;i!=r_2.Need.size();i+)if(!Finishi)bool temp=false;for(vector<int>:size_type index=0;index!=Work.size();index+)if(r_2.Neediindex<=Workindex)temp=true;elsetemp=false;break;if(temp)vector<int>:iterator iter_2=r_2.Allocationi.begin();for(vector<int>:iterator iter_1=Work.begin();iter_1!=Work.end();iter_1+)*iter_1=*iter_1+*iter_2;iter_2+;cout<<"P"<<i<<" "Finishi=true;goto step2;/本来不应该使用goto语句，但由于在此使用goto语句更显方便，故破例用之/判断所有进程Finish是否都为true，是则返回true，否则返回falsefor(vector<bool>: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;i<r.getM();i+)int temp;while(true)/*输入数据合法性检查*/cout<<"请输入第"<<i+1<<"类资源的需求量："<<endl;cin>>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<<"请初始化系统资源种类数："<<endl;cin>>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;i<M;i+)int temp;while(true)/*输入数据合法性检查*/cout<<"请初始化系统中第"<<i+1<<"类资源的数目："<<endl;cin>>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.不应提示错误信息初始化各类资源需求量P0的Request=4,4,4P1的Request=1,1,1P2的Request=1,1,11. 应提示“系统初始状态不安全！”2. 提示“按任意键退出系统”6.4进程初始化设置P0的Request=1,2,3P1的Request=1,2,2P2的Request=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等容器。以前我对这些对象或容器的用法并不是太熟悉，但现在我不仅掌握了他们的使用方法，更重要的是我学会了如何去学习，然后快速地应用到我所需要的项目当中。在做这个银行家算法模拟系统时，我把它当作了一个产品去做，所以每个细节考虑的虽不完全，但也周到。但这并不能说明什么，因为很多软件都是通过升级的方式来弥补自身的缺陷，我的银行家算法模拟系统也是如此。在使用之中发现问题后再去积极的修改问题，使得软件越来越完善。而且只有这样才是软件开发必经之路，因为没有什么事物一生下来就是完美的，都是在通过追求卓越的过程中完