操作系统课程设计的-模拟银行家算法-绝对独一无二(共14页).doc

精选优质文档-倾情为你奉上湖南工业大学课 程 设 计资 料 袋 计算机与通信 学院（系、部） 2011 2012 学年第 2 学期 课程名称 操作系统 指导教师 左新娥 职称 讲师 学生姓名 刘 耀 澳 专业班级 计算机科学与技术 学号 题 目 模拟银行家算法 成 绩 起止日期 2011 年 12月 19 日 2011 年 12月 24 日目 录 清 单序号材 料 名 称资料数量备 注1课程设计任务书12课程设计说明书13课程设计图纸张湖南工业大学课程设计任务书2011 2012 学年第 2 学期 计算机与通信 学院（系、部） 计算机科学与技术 专业 09-3 班级课程名称： 操作系统 设计题目： 模拟银行家算法 完成期限：自 2011 年 12 月 19 日至 2011 年 12 月 24 日共 1 周内容及任务一、课程设计目的通过设计和调试银行家算法通用程序，加深对死锁概念和死锁避免方法的了解。二、课程设计内容编制银行家算法程序，并检测所给状态的系统安全性。进度安排起止日期工作内容 2011-12-192011-12-20确定银行家算法所需的数据结构和算法分析2011-12-202011-12-21根据算法画出流程图，然后编码实现算法2011-12-222011-12-24 对程序的调试、修改、改进。编写设计说明书主要参考资料1 孟庆昌，牛欣源编著。操作系统（第二版）。电子工业出版社。2010-10.2 徐虹，何嘉，张钟澎编著。操作系统实验指导基于Linux内核（第二版）。清华大学出版社。2009-08.指导教师（签字）： 年 月 日系（教研室）主任（签字）： 年 月 日专心-专注-专业操作系统课程设计说明书模拟银行家算法起止日期： 2011 年 12 月 19 日 至 2011 年 12 月 24日学生姓名*班级计算机 09-3班学号*成绩指导教师(签字)计算机与通信 学院（部）2011年 12月 24日一、课程设计目的通过设计和调试银行家算法通用程序，加深对死锁概念和死锁避免方法的了解。二、课程设计内容编制银行家算法程序，并检测所给状态的系统安全性。三、算法的原理 银行家算法是一种最有代表性的避免死锁的算法。要解释银行家算法，必须先解释操作系统安全状态和不安全状态。 安全状态：如果存在一个由系统中所有进程构成的安全序列P1，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。 不安全状态:不存在一个安全序列。不安全状态不一定导致死锁。那么什么是安全序列呢？安全序列：一个进程序列P1，Pn是安全的，如果对于每一个进程Pi(1in），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i ) 我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。1）对用银行家算法来避免死锁的方法有较深入的了解，给出系统的初始状态，模拟避免死锁的动态过程。2）银行家算法中的数据结构（1）可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。Availablej=K，则表示系统中现有Rj类资源K个。（2）最大需求矩阵Max。这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi，j=K，则表示进程i需要Rj类资源的最大数目为K。（3）分配矩阵Allocation。这也是一个n*m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi，j=K，则表示进程i当前已分得Rj类资源的数目为K。（4）需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi，j=K，则表示进程i还需要Rj类资源K个，方能完成其任务。上述三个矩阵存在如下关系： Needi,j= Maxi，j- Allocationi，j3）银行家算法设Requesti 是进程Pi的请求向量，如果Requesti，j=K,表示进程需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：（1）如果Requesti，j<= Needi，j，便转向步骤（2）；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。（2）如果Requesti，j<= Availablej，便转向步骤（3）；否则，表示尚无足够资源，Pi须等待。（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Availablej= Availablej- Requesti，j； Allocationi，j= Allocationi，j+ Requesti，j； Needi，j= Needi，j- Requesti，j；（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。4）安全性算法系统所执行的安全性算法可描述如下：（1）设置两个向量：工作向量Work：它表示系统可提供给进程继续运行所需要的各类资源数目，它含有m个元素，在执行安全算发开始时，Work=Available；Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi=false；当有足够资源分配给进程时，再令Finishi=true。（2）从进程集合中找到一个能满足下述条件的进程：Finishi=false；Needi，j <= Workj；若找到，执行步骤（3），否则，执行步骤（4）。（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Workj= Worki+ Allocationi，j； Finishi=true； go to step 2；（4）如果所有进程的Finishi=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。5）银行家算法程序流程图如图3.1所示，银行家算法所用数据可参考ppt上的例子。四、数据流程图图一、银行家算法程序流程图五、源程序代码 源代码： #include<iostream>using namespace std;#define F 0#define T 1int main()int n,m,i,j;n=4;m=3; / 定义进程总数和资源类总数。int Available3; /可利用的各类的资源数。int Max43; /每个进程对每类资源的最大需求数。int Allocation43; /每个进程已分配的各类资源个数。int Need43; / 每个进程还需要每类资源的个数。/int Request43; / 每个进程对每类资源的申请的个数。int Work3; / 在安全性算法中表示可利用的资源个数。int Finish4; /在安全性算法中每个进程的完成情况。/int securityArithmetic(int *Work,int *Available,int *Finish,int Need3,int Allocation3,int n,int m); /安全性算法的子程序的声明。 /下面是输入资源分配表的情况。cout<<"input the Available: "<<endl;for(j=0;j<m;j+)cout<<"Available"<<j<<":"cin>>Availablej; cout<<endl; /输入每类资源可利用的个数。/下面是输入各类资源的已分配的、最大需求的、现在还需要的资源个数。cout<<"input the Allocation ,Max ,Need :"<<endl;for(i=0;i<n;i+)for(j=0;j<m;j+)cout<<"Allocation"<<i<<""<<j<<":" cin>>Allocationij;cout<<endl; /输入i号进程已分配的j类资源的个数cout<<"Max"<<i<<""<<j<<":" cin>>Maxij;cout<<endl;/输入i号进程对j类资源的最大需求个数。cout<<"Need"<<i<<""<<j<<":" cin>>Needij;cout<<endl; /输入i号进程还需要j类资源的个数。/下面是输入某个进程对每类资源的申请个数。int Request_Num=0;int thedoing;cout<<"读入请求分配资源的进程个数 Request_Num :"cin>>Request_Num; /输入申请资源的进程个数。cout<<endl;while(Request_Num!=0)int security=T; /设置一个标志变量，用于判断对i号进程的/申请预分配后系统是否是安全的。int b=1; /b也是判断标志变量，用于判断是否所有进程的Finishi=T.cout<<"读入 i 进程的资源请求：" cin>>i;thedoing=i; /输入请求资源的进程号。cout<<endl<<"输入请求的各类资源数目："for(j=0;j<m;j+)cout<<"输入第"<<j<<"类的个数：" cin>>Requestij; /输入i进程对各类资源的申请个数。/进程 i 的资源预分配int aa=1; /控制变量aa是用于判断是否能对i进程的申请进行预分配。for(j=0;j<m;j+)if (!(Requestij<=Needij && Requestij<=Availablej)aa=0;if(aa=1) /如果aa=1,即所申请的<所需要的，并且所申请的<可利用的。 /就可进行预分配。for(j=0;j<m;j+) /下面是进行预分配时所要改变的相关变量参数。 Availablej= Availablej- Requestij; Allocationij= Allocationij+ Requestij; Needij= Needij- Requestij;else /如果不能进行预分配，则退出循环，结束程序。 cout<<”警告：申请资源个数大于所需的或可利用的个数.”;return 0; / 调用安全性算法，返回一个控制变量，表明是否存在安全序列，是否有安全状态. b=securityArithmetic(Work,Available,Finish,Need,Allocation, n,m);/ /如果有安全序列，b=1，则该进程的此次请求分配可行。if(b=1)for(i=0;i<n;i+) Finishi=F; /如果b=1，则表明此次申请安全，并把/Finishi都置为 F .为下一个进程的申请做准备。else security=F;if(security=T) /判断当前进程申请各类资源后系统是否安全。cout<<"进程"<<thedoing<<"请求资源后：存在安全序列，是可行的。"<<endl;cout<<endl;else cout<<"进程"<<thedoing<<"请求资源后：不存在安全序列，是不可行的。"<<endl; /下面是如果当前进程申请资源后有死锁危险，则撤销之前的预分配。Availablej= Availablej+ Requestij; Allocationij= Allocationij- Requestij; Needij= Needij+ Requestij;Request_Num-; /申请的进程数量减一，进行下一个进程的资源预分配和系统安全性判断。return 0; /对每个申请资源的进程进行了银行家算法后，程序结束。/定义安全性算法子程序int securityArithmetic(int *Work,int *Available,int *Finish,int Need3,int Allocation3,int n,int m) int i,j;for(i=0;i<n;i+)Finishi=F;for(j=0;j<m;j+)Workj=Availablej;/下面的 a、b、c 都是控制标志变量。int b=1; int a=1; /标志某一进程目前还需要的各类资源<可利用的个数。 int c=0; /标志Finishc=T 的进程号。int d;for(d=0;d<n;d+) /for(i=0;i<n;i+)/找一个可执行完但还没执行完的进程 c 。a=1; for(j=0;j<m;j+)/判断i 进程的所需的所有的资源是否可利用的。 if(Needij<=Workj) c=i; else a=0;if(Finishc=F && a=1) /如果所需可用的，且Finish=F，则进程 / i 就释放其占有的资源。 for(j=0;j<m;j+) Workj=Workj+Allocationcj; Finishc=T; b=1; for(i=0;i<n;i+) /如果所有的进程都已经执行完,则b=1,表示执行此次/分配是安全的。 if(Finishi=T) ;/是否所有进程都能运行完成。 else b=0; return b; /返回标志目前系统是否安全的标志变量 b .六、程序运行结果显示 （1）、资源分配表情况 资源进程AllocationMaxNeedAvailableR0R1R2R0R1R2R0R1R2R0R1R20100322222112151161310222113141033002422420 （2）、运行结果1、输入可利用的资源数：Available。然后输入每个进程的 ：Allocation的资源个数。Max的资源个数。Need的资源个数。2、 当把资源分配表的情况输入完后，再输入要请求分配资源的进程的个数，这里我输入了2，表示有两个进程请求资源。再输入请求资源的进程号，然后再输入请求的各类资源的个数，但不能超过Available 中的个数。我的输入是： 1号进程，请求各类资源数为：1、0、2 。照理论是安全的。和运行结果一样的。然后再输入：0号进程，请求各类资源数为：0、1、1 。因为这时Available已经变成：0、1、0. 所以0号进程请求后就处于不安全状态了。七、总结 经过几天的自己动手练习，对操作系统的掌握又进了一步，收获了很多课堂上和书上未出现过的或老师未讲到的一些知识。在完成实验的过程中，进行了反复的修改和调试，这次实验，让我基本上明白了银行家算法的基本原理，加深了对课堂上知识的理解，也懂得了如何让银行家算法实现，但编程功底的原因使程序很是繁琐。银行家算法是这样的：1）当一个用户对资金的最大的需求量不超过银行家现有的资金时就可以接纳该用户。2）用户可以分期贷款，但贷款的总数不能超过最大需求量。3）当银行家现有的资金不能满足用户的尚需贷款时，对用户的贷款可推迟支付，但总能使用户在有限的时间里得到贷款。4）当用户得到所需的全部资金后，一定能在有限的时间里归还所有资金。我们把操作系统看作是银行家，操作系统管理的资源相当于是银行家管理的资金，则银行家算法就是：1）当一个进程首次申请资源时，测试该进程对资源的最大的需求量，如果不超过系统现存资源时就可以按他的当前申请量为其分配资源。 否则推迟分配。2）进程执行中继续申请资源时，测试该进程占用资源和本次申请资源总数有没有超过最大需求量。超过就不分配，没超过则再测试现存资源是否满足进程还需要的最大资源量，满足则按当前申请量分配，否则也推迟分配。总之，银行家算法要保证分配资源时系统现存资源一定能满足至少一个进程所需的全部资源。这样就可以保证所有进程都能在有限时间内得到需要的全部资源。这就是安全状态。参考文献1 庞丽萍.操作系统原理M. 武汉：华中科技大学出版社，20082 杨树青,王欢.Linux环境下C编程指南M. 北京：清华大学出版社，20073 陈维兴,林小茶. C+面对对象程序设计教程M. 北京：清华大学出版社，20044杨路明. C语言程序设计教程M. 北京：北京邮电大学出版社，2005