操作系统课程设计银行家算法

1、银行家算法1. 课程设计的目的了解多道程序系统中，多个进程并发执行的资源分配，及死锁的产生原因、必要条件和处理死锁的基本方法，掌握预防死锁的方法，系统安全状态的基本概念，了解银行家算法，及资源在进程并发执行中的资源分配策略，并且理解死锁避免在当前计算机系统不常使用的原因。根据设计题目的要求，充分地分析和理解题目，叙述系统的要求，明确程序要求实现的功能以及限制条件。明白自己需要用代码实现的功能，清楚编写每部分代码的目的，做到有的放矢，有条理不遗漏的用代码实现银行家算法。2.设计方案论证2.1题目描述银行家算法是一种最有代表性的避免死锁的算法。在多道程序系统中，多个进程的并发执行来改善系统的资源利

2、用率，提高系统的吞吐量，但可能发生一种危险死锁。所谓死锁(Deadlock)，是指多个进程在运行过程中因争夺资源而造成的一种僵局（DeadlyEmbrace），当进程处于这种状态时，若无外力作用，他们都无法在向前推进。要预防死锁，有摒弃“请求和保持”条件，摒弃“不剥夺”条件，摒弃“环路等待”条件等方法。但是，在预防死锁的几种方法之中，都施加了较强的限制条件；而在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统状态分为安全状态和不安全状态，便可避免死锁的发生。要解释银行家算法，必须先解释操作系统安全状态和不安全状态。安全状态是指系统能按照某种进程顺序P1,P

3、2,，Pn（称P1,P2,，Pn 序列为安全序列），来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺利完成。安全状态一定没有死锁发生。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。安全序列：一个进程序列P1，Pn是安全的，如果对于每一个进程Pi(1in），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和，则称此进程序列P1,P2,，Pn是安全的，称作安全序列。银行家算法：我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操

4、作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。2.2设计思路算法思路先对用户提出的请求进行合法性检查，即检查请求是否大于需要的，是否大于可利用的。若请求合法，则进行预分配，对分配后的状态调用安全性算法进行检查。若安全

5、，则分配；若不安全，则拒绝申请，恢复到原来的状态，拒绝申请。银行家算法中的数据结构（1）可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available j= K，则表示系统中现有R类资源K个（2）最大需求矩阵Max。这是一个n*m的矩阵，它定义了系统中n个进程对m类资源的最大需求。如果Maxi,j=K，则表示进程i需要R类资源的数目为K。（3）分配矩阵Allocation。这也是一个n*m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的

6、资源数。如果Allocation i,j=K，则表示进程i当前已分得R类资源的数目为K。（4）需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need i,j=K，则表示进程i还需要R类资源K个，才能完成其任务。上述矩阵存在关系：Needi,j= Maxi,jAllocationi,j2.2.3银行家算法设Requesti是进程Pi的请求向量，Requesti=K表示进程Pi需要K个j类资源。Pi发出资源请求后，按下列步骤进行检查：（1）如果requestijneedi,j，转向步骤（2）；否则认为错误，所需要的资源数已超过它所宣布的最大值。（2）如果requ

7、estijavailablej，转向步骤（3）；否则，表示尚无足够资源，Pi需等待。（3）系统尝试将资源分配给进程Pi，并修改下面数据结构中的数值：Availablej：=Availablej-Requestij；Allocationi,j：=Allocationi,j+ Requestij；Needi,j：=Needi,j- Requestij；（4）执行安全性算法，检查此次资源分配后，系统是否出于安全状态。若安全，才正式将资源分配给进程Pi，已完成本次分配；否则，将本次试探分配作废，恢复原来的资源分配状态，让Pi等待。2.1.4安全性检查算法（1）设置两个向量：工作向量work：表示系统可

8、提供给进程继续运行所需的各类资源数目，执行安全性算法开始时work：=available。finish标志：表示系统是否有足够的资源分配给进程，使之运行完成。初始化finishi:=false;有足够资源分配给进程时，令finishi：=true。（2）从进程集合中找到一个能满足下述条件的进程finishi=false; Needi,jworkj;找到执行步骤（3），否则执行步骤（4）。（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Workj：=worki+allocationi,j； Finishi：=true； Go to step ；（4）如果所有

9、进程的finishi=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。2.3设计方法2.3.1基本要求（1）可以输入某系统的资源以及T0时刻进程对资源的占用及需求情况的表项，以及T0时刻系统的可利用资源数。（2）对T0时刻的进行安全性检测，即检测在T0时刻该状态是否安全。（3）进程申请资源，用银行家算法对其进行检测，分为以下三种情况：A. 所申请的资源大于其所需资源，提示分配不合理不予分配并返回。B所申请的资源未大于其所需资源，但大于系统此时的可利用资源，提示分配不合理不予分配并返回。 C. 所申请的资源未大于其所需资源，亦未大于系统此时的可利用资源，预分配并进行安全性检查：

10、a. 预分配后系统是安全的，将该进程所申请的资源予以实际分配并打印后返回。 b. 与分配后系统进入不安全状态，提示系统不安全并返回。（4）对输入进行检查，即若输入不符合条件，应当报错并返回重新输入。2.3.2流程图：（1）银行家算法，如图1所示。输入进程号初始化Request数组REQUESTcusneedi>NEEDcusneedi REQUESTcusneedi>AVAILABLEiYN试分配changdata()NSafe()Put()输出内容 Y图1银行家算法流程图（2）安全性算法，如图2所示。初始化work数组，使Workj=Availablej; Finishi=fal

11、seFinishi=true Y NNeedij>Workj Y Napply+;appy=N Y YFinishi=trueWorkm+=Allocationimtempk=i;k+l=mY不安全Availablei=Availablei+Requesti;Allocationnumi=Allocationnumi-RequestjNeednumi=Neednumi+Requesti; N输出安全序列Return trueMaxnumi=Allocationnumi; Allocationnumi=0; Availablei = Availablei + Allocationnumi;

12、图2安全性算法流程图2.3.3调试结果（1）资源分配情况，如图3所示。图3资源分配情况（2）安全判断，如图4所示。图4安全判断（3）为1分配资源，如图5所示。图5为1分配资源（4）为4分配资源，如图6所示。图6为4分配资源（5）为0分配资源，如图7所示。图7为0分配资源3.设计体会通过本次课程设计，我收获很多，首先我对十大算法之一的银行家算法有了清楚的认识，认真分析了进程产生死锁的原因，了解为什么要进行死锁的避免，掌握银行家算法的数据结构，了解了算法的执行过程，加深了对银行家算法的理解。其次，我对编程有了个清楚的认识，编程就是将先现实中的规律模拟成电脑能运行的程序，方便我们的工作和学习生活。最

13、后，我也清楚认识到理论联系实际重要性，动手操作能力和编程逻辑思维能力的提高的重要性，对自己所编写的程序要学会调试，不断改进，向更加全面的方向考虑，同时也要考虑程序的可行性和健壮性。总而言之，我在编写程序方面有了更加深入的认识。不同的算法可以实现相同的功能，这是我从本次实验中深深体会到的，因而在今后的学习中遇到问题我会尝试着用的不同的方法来解决，有时候换个角度可以很方便的解决问题课程设计是我们对专业课程知识综合应用的实践训练，只有认真的进行课程设计，学会脚踏实地认真思考学习，课程设计是培养我们综合运用所学知识，发现、提出、分析和解决实际问题、锻炼实践能力的重要环节,是对我们实际能力的考察过程。4

14、.参考文献1 汤小丹，梁红兵，哲凤屏，汤子瀛.计算机操作系统.M 西安：西安电子科技大学出版社，2007. 150-2202 严蔚敏，吴伟民.数据结构. M 北京：清华大学出版社，2006. 14-993 赵莉，杨国梁，孙喁喁，徐飞.Java程序设计教程. M 西安：西安科技大学出版社，2009.25-994刘璟等.高级语言C+程序设计.M西安电子科技大学出版社,2009.66-102附录#include<iostream.h>#include<string.h>#define False 0#define True 1char name50=0;/资源名称int Ma

15、x5050=0;/进程所需各类资源的最大需求int Allocation5050=0;/系统已分配资源int Need5050=0;/进程需求资源int Available50=0;/系统可用资源向量int Request50=0;/进程请求资源向量int Work50=0;/存放系统可提供进程继续运行所需各类资源数目int temp50=0;/存放安全序列int b50=0;/系统各类资源总数int M=50;/进程的最大数目为50int N=50;/资源的最大数目为50void display() int i,j,number,m,n;char ming;int a50=0;cout<

16、;<"请输入系统中资源的种类:"cin>>n;N=n;for(i=0;i<n;i+) cout<<"资源"<<i+1<<"的名称和数量:"cin>>ming>>number;namei=ming;bi=number;cout<<"请输入进程的数量:"cin>>m;M=m;cout<<"请输入各进程的最大需求("<<m<<"*"<

17、<n<<"矩阵)Max:"<<endl;for(i=0;i<m;i+)for(j=0;j<n;j+)cin>>Maxij;cout<<"请输入各进程的已分配("<<m<<"*"<<n<<"矩阵)Allocation:"<<endl;for(i=0;i<m;i+)for(j=0;j<n;j+)cin>>Allocationij;Needij=Maxij-Allocati

18、onij;if(Needij<0)cout<<"您输入的第"<<i+1<<"个进程所拥有的第"<<j+1<<"个资源数错误,请重新输入:"<<endl;j-;continue;cout<<"目前可用的资源:"<<endl;for(i=0;i<N;i+)cout<<namei<<" "cout<<endl;for (j=0;j<N;j+)for(i=

19、0;i<M;i+)aj+=Allocationij;Availablej=bj-aj;for(i=0;i<N;i+)cout<<Availablei<<" "/输出分配资源cout<<endl;void print()/显示资源分配情况int i,j;cout<<" Max Allocation Need"<<endl;cout<<"进程名 "for(j=0;j<3;j+)for(i=0;i<N;i+)cout<<namei&l

20、t;<" "cout<<" "cout<<endl;for(i=0;i<M;i+)cout<<" "<<i<<" "for(j=0;j<N;j+)cout<<Maxij<<" "cout<<" "for(j=0;j<N;j+)cout<<Allocationij<<" "cout<<" &qu

21、ot;for(j=0;j<N;j+)cout<<Needij<<" "cout<<endl;int changdata(int i)/进行资源分配 int j;for (j=0;j<M;j+) Availablej=Availablej-Requestj; Allocationij=Allocationij+Requestj; Needij=Needij-Requestj;return 1;int safe(int num,int M,int N)/安全性算法对系统进行分析int i,j,k=0,m,apply,Finish5

22、=0;int flag;int flag1;for(j=0;j<M;j+) Workj=Availablej; for(flag=0;flag<M;flag+)for(i=0;i<M;i+)apply=0;for(j=0;j<N;j+)if (Finishi=False&&Needij<=Workj) apply+;if(apply=N)for(m=0;m<N;m+)Workm=Workm+Allocationim;/变分配数Finishi=True;tempk=i;k+;for(i=0;i<M;i+)if(Finishi=False)

23、cout<<"系统不安全"<<endl;/不成功系统不安全for(i = 0;i<N;i+) Availablei=Availablei+Requesti;Allocationnumi=Allocationnumi-Requesti; Neednumi=Neednumi+Requesti; return -1; cout<<"系统是安全的!"<<endl;/如果安全，输出成功 cout<<"分配的序列:"for(i=0;i<M;i+)/输出运行进程数组cout&l

24、t;<tempi;if(i<M-1) cout<<"->"cout<<endl;for(i = 0;i<N;i+)if(Maxnumi = Allocationnumi) flag1 = 1; elseflag1 = 0;break;if(flag1 = 1)for(i=0;i<N;i+)Availablei = Availablei + Allocationnumi;Allocationnumi = 0;return 0;void bank(int M,int N)/银行家算法对申请资源对进行判定char ch; int i=0,j=0; ch='y'cout<<"请输入要求分配的资源进程号(0-&