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

操作系统-银行家算法 CopyRightNigHtMaRe2009年12月30日 操作系统-银行家算法课程设计报告姓 名： 赵明 学 号：070609313 班 级：07计科9班 专 业：计算机科学与技术 西安工业大学 计算机科学与信息学院目 录1 课程设计目的 12 课程设计的要求 13 课程设计题目描述 24 课程设计之银行家算法原理 25 源程序结构分析及代码实现 46 课程设计总结 25一、课程设计的目的操作系统是计算机系统的核心系统软件，它负责控制和管理整个系统的资源并组织用户协调使用这些资源，使计算机高效的工作。操作系统课程设计是操作系统理论课的必要补充，是复习和检验所学课程的重要手段，本课程设计的目的是综合应用学生所学知识，通过实验环节，加深学生对操作系统基本原理和工作过程的理解，提高学生独立分析问题、解决问题的能力，增强学生的动手能力。二、课程设计的要求1分析设计内容，给出解决方案（要说明设计实现的原理，采用的数据结构）。2画出程序的基本结构框图和流程图。3对程序的每一部分要有详细的设计分析说明。4源代码格式要规范。5设计合适的测试用例，对得到的运行结果要有分析。6设计中遇到的问题，设计的心得体会。7按期提交完整的程序代码、可执行程序和课程设计报告。三、课程设计题目描述 银行家算法是一种最有代表性的避免死锁的算法。要解释银行家算法，必须先解释操作系统安全状态和不安全状态。安全状态：如果存在一个由系统中所有进程构成的安全序列P1，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。不安全状态:不存在一个安全序列。不安全状态不一定导致死锁。那么什么是安全序列呢？安全序列：一个进程序列P1，Pn是安全的，如果对于每一个进程Pi(1in），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j i )当前占有资源量之和。银行家算法：我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。4、 课程设计之银行家算法原理1银行家算法的思路 先对用户提出的请求进行合法性检查，即检查请求的是不大于需要的，是否不大于可利用的。若请求合法，则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。2银行家算法中用到的主要数据结构可利用资源向量 int Availablej j为资源的种类。最大需求矩阵 int Maxij i为进程的数量。分配矩阵 int Allocationij 需求矩阵 int needij= Maxij- Allocationij申请各类资源数量 int Request ij i进程申请j资源的数量工作向量 int Workx int Finishy 3银行家算法bank()进程i发出请求申请k个j资源，Request ij=k (1)检查申请量是否不大于需求量：Request ij=needi,j,若条件不符重新输入，不允许申请大于需求量。(2)检查申请量是否小于系统中的可利用资源数量：Request ij=availablei,j，若条件不符就申请失败，阻塞该进程，用goto语句跳转到重新申请资源。(3)若以上两个条件都满足，则系统试探着将资源分配给申请的进程，并修改下面数据结构中的数值：Availablei,j= Availablei,j- Request ij；Allocationij= Allocationij+ Request ij；needij= needij- Request ij；(4)试分配后，执行安全性检查，调用safe()函数检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程；否则本次试探分配作废，恢复原来的资源分配状态，让该进程等待。(5)用dowhile 循环语句实现输入字符y/n判断是否继续进行资源申请。4安全性检查算法（safe()函数）(1)设置两个向量：工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，在执行安全性算法开始时，Work= Available。Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi=0；当有足够的资源分配给进程时，再令Finishi=1。(2)在进程中查找符合以下条件的进程：条件1：Finishi=0；条件2：needij=Workj若找到，则执行步骤(3)否则，执行步骤(4)(3)当进程获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Workj= Workj+ Allocationij；Finishi=1；goto step 2；(4)如果所有的Finishi=1都满足，则表示系统处于安全状态，否则，处于不安全状态。五、源程序结构分析及代码实现1程序结构程序共有以下五个部分：(1) .初始化chushihua()：用于程序开始进行初始化输入数据：进程数量、资源种类、各种资源可利用数量、各进程的各种资源已分配数量、各进程对各类资源最大需求数等。(2).当前安全性检查safe()：用于判断当前状态安全性，根据不同地方的调用提示处理不同。(3).银行家算法bank()：进行银行家算法模拟实现的模块，调用其他各个模块进行银行家算法模拟过程。(4).显示当前状态show()：显示当前资源分配详细情况，包括：各种资源的总数量(all)、系统目前各种资源可用的数量、各进程已经得到的资源数量、各进程还需要的资源量。(5).主程序main()逐个调用初始化、显示状态、安全性检查、银行家算法函数，使程序有序的进行。2数据结构程序使用的全局变量：const int x=10，y=10； /定义常量int Availablex; /各种资源可利用的数量int Allocationyy; /各进程当前已分配的资源数量int Maxyy; /各进程对各类资源的最大需求数int Needyy; /还需求矩阵int Requestx; /申请各类资源的数量int Workx; /工作向量，表系统可提供给进程运行所需各类资源数量int Finishy; /表系统是否有足够的资源分配给进程，0为否，1为是int py; /存储安全序列int i,j; /全局变量，主要用于循环语句中int n,m; /n为进程的数量,m为资源种类数int l=0,counter=0;3函数声明void chushihua(); /系统初始化函数void safe(); /安全性算法函数void bank(); /银行家算法函数void show (); /输出当前资源分配情况4主函数main()int main() cout /显示程序开始提示信息 chushihua(); /初始化函数调用coutendlendl; showdata(); /输出初始化后的状态 /=判断当前状态的安全性= safe(); /安全性算法函数调用 if (ln) coutn当前状态不安全，无法申请,程序退出!endl; coutendl; system(pause); sign(); /调用签名函数 return 0; / break; else int i; /局部变量 l=0;coutn安全的状态!endl; cout安全序列为: ; coutendl进程(p0); /输出安全序列，考虑显示格式，先输出第一个 for (i=1; in; i+) cout进程(pi); for (i=0; in; i+) Finishi=0; /所有进程置为未分配状态 coutendlendl; bank(); /银行家算法函数调用return 0; 5. 操作系统银行家算法流程图：初始化函数chushihua()开始AVAILABLEi-=REQUESTi;ALLOCATIONi+=REQUESTi;NEEDi-=REQUESTi; 输入进程的数量 输入资源种类数输入个资源当前可用资源数输入各进程当前已分配的资源数输入各进程对各类资源的最大需求输出提示：输入有误，请重新输入初始化函数chushihua()结束，银行家函数Bank()提出请求REQUESTiError;REQUESTi=NEEDiREQUESTi=AVAILABLEiError;Safe();输出提示：你的请求被拒！AVAILABLEi-=REQUESTi；ALLOCATIONi-=REQUESTi;NEEDi+=REQUESTi；输出提示：同意分配请求是否进行再次分配退出程序，银行家算法Bank()结束;安全性算法Safe()开始Work=AVAILABLE;FINISH=false；NEEDi=Work&FINISHi=false;Work+=ALLOCATIONi;FINISHi=ture;所有进程的FINISH=ture；输出提示：系统是不安全的安全，输出安全序列Return ture；安全算法safe()结束2. 源程序代码：#include #include #include using namespace std; #define TRUE 1 /定义 TRUE =1#define FALSE 0 /定义 FLASE=0void bank(vector,vectorvector ,vectorvector ,int ,int ); /声明bank（应行家算法）int safe(vector Available,vectorvector Need,vectorvector Allocation,int n,int m);/声明safe（）安全性算法void init();/*主函数main()*/void main()init();int safe(vector Available,vectorvector Need,vectorvector Allocation,int n,int m);/*初始化函数init()*/void init()int m; /m资源类数int n; /进程数cout输入资源类数m;vector Available(m); /动态申请数组Available可用资源向量 cout输入各类资源总数:endl;/*/ /* 下面的被刚掉的为在DOS下输入资源向量*/ /*未被刚掉的是从Available.txt文件中读入数据*/*/*/for (int i=0;im;i+)cout输入RiAvailablei;/*/FILE *fp;fp=fopen(Available.txt,r+);cout从Available.txt文件中读入数据，并输出endl;for(int i=0;im;i+)fscanf(fp,%d,&Availablei);coutAvailableit;fclose(fp);coutn输入进程数n;vectorvector Max(n, vector(m);/*/* 下面的被刚掉的为在DOS下输入资源向量*/*未被刚掉的是从Max.txt文件中读入数据*/*/*for ( i=0;in;i+)cout输入进程i的最大需求向量;for (int j=0;jm;j+)cout 输入需要RjMaxij;while (MaxijAvailablej)coutjMaxij;/*/fp=fopen(Max.txt,r+);cout从Max.txt文件中读入数据，并输出endl;for(i=0;in;i+) for (int j=0;jm;j+)fscanf(fp,%d,&Maxij);coutMaxij ;coutendl;fclose(fp);cout输入已分配的Allocationendl;vectorvector Allocation(n, vector(m);vectorvector Need(n, vector(m);/*/* 下面的被刚掉的为在DOS下输入资源向量*/*未被刚掉的是从Allocation.txt文件中读入数据*/*/*for ( i=0;in;i+)cout输入为进程i的分配向量;for (int j=0;jm;j+)cout 输入分配RjAllocationij;while(AllocationijMaxij)coutj+1Allocationij;Needij=Maxij-Allocationij;Availablej =Availablej-Allocationij;/*/fp=fopen(Allocation.txt,r+);coutAllocation.txt从文件中读入数据，并输出endl;for(i=0;in;i+)for (int j=0;jm;j+)fscanf(fp,%d,&Allocationij);Needij=Maxij-Allocationij; /在初始化Max时，同时初始化Need数组Availablej =Availablej-Allocationij; /在初始化Max时，同时修改Available数组coutAllocationij ;coutendl;fclose(fp);int safe(vector Available,vectorvector Need,vectorvector Allocation,int n,int m);cout此状态安全!endl;bank(Available,Need,Allocation,n,m);/调用银行家算法bank()函数/*银行家算法bank()函数*/void bank(vector Available,vectorvector Need,vectorvector Allocation,int n,int m)vector Request(m);int all=0;/定义变量all，如果all=0，表示进程已经运行完，如果all=1，表示还有进程没有运行完for (int i=0;in;i+)for(int j=0;jm;j+)all +=Needij;if (0=all)cout所有进程已经运行完，结束=1，表示还有进程没有运行完/循环直至all0,即找到一个未运行完的进程cout任选一个进程作为当前进程0-n-1jc;for (int j=0;jm;j+)all += Needjcj;if (0=all)cout此进程已经运行，重新输入endl;cout输入该进程的请求向量endl;for (i=0;iRequesti;while(RequestiNeedjci|RequestiAvailablei)cout请求向量无法满足endl;break; /系统试探着把资源分配给该进程/for (i=0;im;i+)Availablei=Availablei-Requesti;Allocationjci=Allocationjci+Requesti;Needjci=Needjci-Requesti;int bb=0;bb=safe(Available,Need,Allocation,n,m);/调用安全性算法，判断此次资源分配后，系统是否处安全状态if (1=bb)cout系统成功分配资源endl;elsecout系统未能成分配资源,收回预分配资源endl;for (i=0;im;i+)Availablei=Availablei+Requesti;Allocationjci=Allocationjci-Requesti;Needjci=Needjci+Requesti;cout您还想再次请求分配吗?是请按y/Y,否请按其它键again; if(again=y|again=Y) all=0;continue; break;/*安全性算法safe()函数*/int safe(vector Available,vectorvector Need,vectorvector Allocation,int n,int m)vector Work(m),Finish(n);/申请工作向量work，finishWork=Available;vector count(n); /记录安全序列int len=-1; /记录安全序列的进程个数，如果len=n，即表示所有的finish【i】=true，处于安全状态for(int i=0;im;i+)Finishi=FALSE; for (i=0;in;i+) int needed=1;for (int j=0;jm;j+)if(Needij=Workj)needed=needed*TRUE;else needed=needed*FALSE;if (Finishi=FALSE)&needed=1)for (j=0;jm;j+)Workj=Workj+Allocationij;Finishi=TRUE;len=len+1;countlen=i;i=-1;if (len