操作系统课程设计的-模拟银行家算法-绝对独一无二

湖南工业大学课程设计资料袋计算机与通信学院（系、部）2011~2012学年第2学期课程名称操作系统指导教师左新娥职称讲师学生姓名刘耀澳专业班级计算机科学与技术学号09408100327题目模拟银行家算法成绩起止日期2011年12月19日～2011年12月24日目录清单序号材料名称资料数量备注1课程设计任务书12课程设计说明书13课程设计图纸张湖南工业大学课程设计任务书22011—2012学年第2学期计算机与通信学院（系、部）计算机科学与技术专业09-3班级课程名称：操作系统设计题目：模拟银行家算法完成期限：自2011年12月19日至2011年12月24日共1周内容及任务一、课程设计目的通过设计和调试银行家算法通用程序，加深对死锁概念和死锁避免方法的了解。二、课程设计内容编制银行家算法程序，并检测所给状态的系统安全性。进度安排起止日期工作内容2011-12-19~2011-12-20确定银行家算法所需的数据结构和算法分析2011-12-20~2011-12-21根据算法画出流程图，然后编码实现算法2011-12-22~2011-12-24对程序的调试、修改、改进。编写设计说明书主要参考资料[1]孟庆昌，牛欣源——编著。操作系统（第二版）。电子工业出版社。2010-10.[2]徐虹，何嘉，张钟澎——编著。操作系统实验指导——基于Linux内核（第二版）。清华大学出版社。2009-08.指导教师（签字）：年月日系（教研室）主任（签字）：年月日操作系统课程设计说明书模拟银行家算法起止日期：2011年12月19日至2011年12月24日学生姓名****班级计算机09-3班学号***********成绩指导教师(签字)计算机与通信学院（部）2011年12月24日计算机与通信学院课程设计4一、课程设计目的通过设计和调试银行家算法通用程序，加深对死锁概念和死锁避免方法的了解。二、课程设计内容编制银行家算法程序，并检测所给状态的系统安全性。三、算法的原理银行家算法是一种最有代表性的避免死锁的算法。要解释银行家算法，必须先解释操作系统安全状态和不安全状态。安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。不安全状态:不存在一个安全序列。不安全状态不一定导致死锁。那么什么是安全序列呢？安全序列：一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj(ji)我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。1）对用银行家算法来避免死锁的方法有较深入的了解，给出系统的初始状态，模拟避免死锁的动态过程。2）银行家算法中的数据结构计算机与通信学院课程设计5（1）可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。Available[j]=K，则表示系统中现有Rj类资源K个。（2）最大需求矩阵Max。这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i，j]=K，则表示进程i需要Rj类资源的最大数目为K。（3）分配矩阵Allocation。这也是一个n*m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i，j]=K，则表示进程i当前已分得Rj类资源的数目为K。（4）需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i，j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。上述三个矩阵存在如下关系：Need[i,j]=Max[i，j]-Allocation[i，j]3）银行家算法设Request[i]是进程Pi的请求向量，如果Request[i，j]=K,表示进程需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：（1）如果Request[i，j]=Need[i，j]，便转向步骤（2）；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。（2）如果Request[i，j]=Available[j]，便转向步骤（3）；否则，表示尚无足够资源，Pi须等待。（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：Available[j]=Available[j]-Request[i，j]；Allocation[i，j]=Allocation[i，j]+Request[i，j]；Need[i，j]=Need[i，j]-Request[i，j]；（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。4）安全性算法系统所执行的安全性算法可描述如下：（1）设置两个向量：①工作向量Work：它表示系统可提供给进程继续运行计算机与通信学院课程设计6所需要的各类资源数目，它含有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都满足，则表示系统处于安全状态；否则，系统处于不安全状态。5）银行家算法程序流程图如图3.1所示，银行家算法所用数据可参考ppt上的例子。四、数据流程图计算机与通信学院课程设计7图一、银行家算法程序流程图五、源程序代码源代码：#includeiostreamusingnamespacestd;#defineF0#defineT1计算机与通信学院课程设计8intmain(){intn,m,i,j;n=4;m=3;////定义进程总数和资源类总数。intAvailable[3];///可利用的各类的资源数。intMax[4][3];////每个进程对每类资源的最大需求数。intAllocation[4][3];/////每个进程已分配的各类资源个数。。intNeed[4][3];/////每个进程还需要每类资源的个数。////////////////intRequest[4][3];/////每个进程对每类资源的申请的个数。intWork[3];////////在安全性算法中表示可利用的资源个数。intFinish[4];////在安全性算法中每个进程的完成情况。///////////intsecurityArithmetic(int*Work,int*Available,int*Finish,intNeed[][3],intAllocation[][3],intn,intm);////安全性算法的子程序的声明。///////////下面是输入资源分配表的情况。coutinputtheAvailable:endl;for(j=0;jm;j++){coutAvailable[j]:;cinAvailable[j];coutendl;///输入每类资源可利用的个数。}/////下面是输入各类资源的已分配的、最大需求的、现在还需要的资源个数。coutinputtheAllocation,Max,Need:endl;for(i=0;in;i++){for(j=0;jm;j++){coutAllocation[i][j]:;cinAllocation[i][j];coutendl;///输入i号进程已分配的j类资源的个数coutMax[i][j]:;cinMax[i][j];coutendl;///输入i号进程对j类资源的最大需求个数。coutNeed[i][j]:;cinNeed[i][j];coutendl;///输入i号进程还需要j类资源的个数。}}/////////////////////////下面是输入某个进程对每类资源的申请个数。。intRequest_Num=0;intthedoing;cout读入请求分配资源的进程个数Request_Num:;cinRequest_Num;///输入申请资源的进程个数。计算机与通信学院课程设计9coutendl;while(Request_Num!=0){intsecurity=T;///设置一个标志变量，用于判断对i号进程的/////申请预分配后系统是否是安全的。。intb=1;///b也是判断标志变量，用于判断是否所有进程的Finish[i]=T.cout读入i进程的资源请求：;cini;thedoing=i;////输入请求资源的进程号。。coutendl输入请求的各类资源数目：;for(j=0;jm;j++){cout输入第j类的个数：;cinRequest[i][j];///输入i进程对各类资源的申请个数。}/////////////////进程i的资源预分配intaa=1;///控制变量aa是用于判断是否能对i进程的申请进行预分配。for(j=0;jm;j++){if(!(Request[i][j]=Need[i][j]&&Request[i][j]=Available[j])){aa=0;}}if(aa=1)///如果aa=1,即所申请的所需要的，并且所申请的可利用的。{////就可进行预分配。for(j=0;jm;j++){////下面是进行预分配时所要改变的相关变量参数。Available[j]=Available[j]-Request[i][j];Allocation[i][j]=Allocation[i][j]+Request[i][j];Need[i][j]=Need[i][j]-Request[i][j];}}else////如果不能进行预分配，则退出循环，结束程序。{cout”警告：申请资源个数大于所需的或可利用的个数..”;return0;}/////////////////////调用安全性算法，返回一个控制变量，表明是否存在安全序列，是否有安全状态.b=securityArithmetic(Work,Available,Finish,Need,Allocation,n,m);/////////////////////////////////////////如果有安全序列，b==1，则该进程的此次请求分配可行。if(b==1)计算机与通信学院课程设计10{for(i=0;in;i++)Finish[i]=F;///如果b==1，则表明此次申请安全，并把///Finish[i]都置为F.为下一个进程的申请做准备。}els