银行家算法设计报告(共21页).doc

精选优质文档-倾情为你奉上基于银行家算法的研究摘要1研究的目的和意义加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。死锁的产生，必须同时满足四个条件，即一个资源每次只能由一个进程占用：第二个为等待条件，即一个进程请求资源不能满足时，它必须等待，但它仍继续保持已得到的所有其他资源：第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待它前一个进程所持有的资源。防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。通过这个算法可用解决生活中的实际问题,如银行贷款等.2研究的内容及方法 银行家算法是最有代表性的避免死锁的算法，由于该算法能用于银行系统现金贷款的发放而得名。其实现思想是：允许进程动态地申请资源，系统在每次实施资源分配之前，先计算资源分配的安全性，若此次资源分配安全（即资源分配后，系统能按某种顺序来为每个进程分配其所需的资源，直至最大需求，使每个进程都可以顺利地完成），便将资源分配给进程，否则不分配资源，让进程等待。 关键词：银行家算法 安全 死锁目录 摘要i 1绪论1 1.1前言11.2本文主要研究内容1 2需求分析22.1死锁的概念22.2关于死锁的一些概念22.3资源分类22.4产生死锁的必要条件22.5死锁预防32.6银行家算法33概要设计43.1设计思路43.2 数据结构43.3主要函数说明54详细设计64.1算法描述64.1.1银行家算法64.1.2 安全性检查算法74.2函数的实现过程74.3程序流程图95测试结果106结果分析127总结13源程序清单14专心-专注-专业1绪论1.1前言银行家算法是避免死锁的一种重要方法。 操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。银行家算法确实能保证系统时时刻刻都处于安全状态，但它要不断检测每个进程对各类资源的占用和申请情况，需花费较多的时间。 现在的大部分系统都没有采用这个算法，也没有任何关于死锁的检查。 1.2 本文主要研究内容（1）设计银行家算法，能够检测系统某一时刻是否安全，输出安全序列。（2）实现安全性检测算法。即在某一进程在某时刻提出Request时，检测系统是否能够满足该进程的请求，并得到一个安全序列，若能够得到一个安全序列，则系统能够满足它的请求，同意分配资源。若不能够满足，则回到请求前状态。（3）对于此次课程设计通过需求分析、概要设计、详细设计、测试与分析、总结、源程序清单等模块进行全面分析，以加深对死锁概念的理解，以及银行家算法避免死锁的过程。能够利用银行家算法，有效避免死锁的发生，或检测死锁的存在。2需求分析2.1死锁的概念所谓死锁: 是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。 由于资源占用是互斥的，当某个进程提出申请资源后，使得有关进程在无外力协助下，永远分配不到必需的资源而无法继续运行，这就产生了一种特殊现象死锁。2.2关于死锁的一些结论1) 参与死锁的进程最少是两个（两个以上进程才会出现死锁）2) 参与死锁的进程至少有两个已经占有资源3) 参与死锁的所有进程都在等待资源4) 参与死锁的进程是当前系统中所有进程的子集注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。 2.3资源分类1) 可剥夺资源2) 不可剥夺资源 2.4产生死锁的必要条件1、互斥条件（Mutual exclusion）一个资源每次只能被一个进程使用。2、请求与保持条件（占有等待）（Hold and wait）一个进程因请求资源而阻塞时，对已获得的资源保持不放。3、不剥夺条件（不可抢占）（No pre-emption）进程已获得的资源，在未使用完之前，不能强行剥夺。4、循环等待条件（Circular wait）若干进程之间形成一种头尾相接的循环等待资源关系。这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之一不满足，就不会发生死锁。2.5死锁预防理解了死锁的原因，尤其是产生死锁的四个必要条件，就可以最大可能地避免、预防和解除死锁。所以，在系统设计、进程调度等方面注意如何不让这四个必要条件成立，如何确定资源的合理分配算法，避免进程永久占据系统资源。此外，也要防止进程在处于等待状态的情况下占用资源,在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配 。因此，对资源的分配要给予合理的规划。2.6银行家算法我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。3概要设计3.1设计思路第一部分:银行家算法(扫描)1如果Request<=Need,则转向2;否则,出错2如果Request<=Available,则转向3,否则等待3系统试探分配请求的资源给进程4系统执行安全性算法 第二部分:安全性算法1.设置两个向量(1).工作向量:Work=Available(表示系统可提供给进程继续运行所需要的各类资源数目)(2).Finish:表示系统是否有足够资源分配给进程(True:有;False:没有).初始化为False2.若Finishi=False&&Need<=Work,则执行3;否则执行4(I为资源类别)3.进程P获得第i类资源,则顺利执行直至完成!并释放资源:Work=Work+Allocation;Finishi=true;转24.  若所有进程的Finishi=true,则表示系统安全;否则,不安全!3.2 数据结构1可利用资源向量矩阵AVAILABLE。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果AVAILABLE j= K，则表示系统中现有R类资源K个2最大需求矩阵MAX。这是一个n*m的矩阵，用以表示每一个进程对m类资源的最大需求。如果MAX i,j=K，则表示进程i需要R类资源的数目为K。3分配矩阵ALLOCATION。这也是一个n*m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果ALLOCATION i,j=K，则表示进程i当前已分得R类资源的数目为K。4需求矩阵NEED。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果NEED i,j=K，则表示进程i还需要R类资源K个，才能完成其任务。 上述矩阵存在下述关系：NEED i,j= MAXi,j ALLOCATIONi,j3.3主要函数说明a: void xx(int shu10,int i,int m) /输出各数组资源b: void input(int max10,int allocation10,int need10,int available,int n,int m) /输出资源分配情况c: int sec(int work,int need10,int allocation10,int n,int m)/安全性算法,检查系统是否处于安全状态d: void main() /主函数4详细设计4.1算法描述4.1.1银行家算法在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。设进程cusneed提出请求REQUEST i，则银行家算法按如下规则进行判断。(1)如果REQUEST cusneed i<= NEEDcusneedi，则转(2)；否则，出错。(2)如果REQUEST cusneed i<= AVAILABLEcusneedi，则转(3)；否则，出错。(3)系统试探分配资源，修改相关数据：         AVAILABLEi-=REQUESTcusneedi;         ALLOCATIONcusneedi+=REQUESTcusneedi;         NEEDcusneedi-=REQUESTcusneedi;(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。4.1.2 安全性检查算法(1)设置两个工作向量Work=AVAILABLE;FINISH(2)从进程集合中找到一个满足下述条件的进程，FINISH=false;NEED<=Work;如找到，执行(3)；否则，执行(4)(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。Work+=ALLOCATION;Finish=true;GOTO 2(4)如所有的进程Finish= true，则表示安全；否则系统不安全4.2函数的实现过程1主函数(main)的实现：输入已知条件，利用安全检测函数检测已知的进程分配情况是否为安全状况。如果为安全，则输入需请求资源的进程号和所需资源数，否则结束主函数。reqi为进程i的请求向量。进行银行家算法：(1):如果reqij>needij则认为出错，输出请求的资源数超过它所需的最大数; 否则执行(2); (2):如果reqij>availableij则输出尚无足够的资源;否则执行(3)(3):系统试探着把资源分配给进程i，并修改下面数据结构中的数值： availablej:=availablej-reqij;llocationij:=allocationij+reqij;needij:=needij-reqij;并且保存修改前的数值。(4):系统执行安全性算法。如果不安全则还原(3)中保存的availablej，allocationij, needij的值.最后输入是否要继续，如继续则转至前面的输入请求资源的进程号，否则退出。2安全检测函数(check): (1)设置两个向量work和finish : work:=available,表示系统可提供给进程继续运行所需的各类资源数目；finish表示系统是否有足够的资源分配给进程，使之完成。开始时先做finishi:=false;当有足够资源分配给进程时，再令finishi:=true。(2)从进程集合中找到一个能满足下述条件的进程：a:  finishi=false; b: needij<=workj; 若找到，执行(3)，否则，执行(4)。(3):当进程i获得资源后，可顺利执行，直到完成，并释放出分配给它的资源，故应执行：workj:=workj+allocationi,j;finishi:=true;av+=i;    （ 记录安全序列）go to step 2;(4):如果所有进程的finishi=true都满足，则表示系统处于安全状态，输出安全序列；否则，系统处于不安全状态。3.输出函数(print): 利用循环体输出各进程号，已分配的资源数，仍需要的资源数，剩余的可用资源数。4.3程序流程图开始输入资源类型数分别输入各类型资源的总数输入系统中进程数分别输入每个进程各类型资源的最大需求数（Max）分别输入每个进程已分得的各类型资源数（Allocation）检查当前系统是否处于安全状态YN输入发出请求的进程序号输入该进程请求的各类型资源数（Request）检查当前系统是否处于安全状态Y是否继续？Y资源不足以分配，进入等待！N结束request>needY请求的资源数超过其所需的资源数，ERROR！N5测试结果 6结果分析1. Available是一个长度为m的向量，它表示每类资源可用的数量。Available j=k，表示rj类资源可用的数量为k。2.Max是一个n×m矩阵，它表示每个进程对资源的最大需求。Max i，j=k，表示进程pi至多可以申请k个rj类资源单位。3. Allocation是一个n×m矩阵，它表示当前分给每个进程的资源数目。Allocation i，j=k，表示进程pi当前分到k个rj类资源。4. Need是一个n×m矩阵，它表示每个进程还缺少多少资源。Needi，j=k，表示进程pi尚需k个rj类资源才能完成其任务。显然Needi，j= Max i，j- Allocation i，j。 当输入进程数与资源数，以及各进程所需的资源和已分配资源之后，系统就会寻找安全序列，若能找到一个安全序列，则结果表明当前系统安全，若找不到则当前系统不安全。若某时刻有某进程提出资源申请，若满足条件Requesti<=Needi;Request<=Available;则试分配，试分配后再检测安全性。当不能满足该进程的要求时，系统收回为该进程分配的资源，回到申请资源前的状态，并显示不能为该进程分配资源。若有进程再次提出资源申请，应从分配前的状态开始。7总结在本次课程设计中遇到不少问题。但都一一解决了。问题如下：1) 越界错误，定义错误，死循环和一些语法错误，后来改正了2) 在检测了系统是安全的之后，进程提出申请，并且能够满足时，没有显示当前状态的Alocation 矩阵Need矩阵Available矩阵的信息，通过改正调用函数进行显示3) 在检测了系统能产生安全序列，当前是安全的之后，首次提出Request应该分配的资源是最初输入时的资源，因此在初始化Alocation，Need，Available三个矩阵时应该多定义三个矩阵将数据复制一份存在新定义的矩阵中。4) 程序在运行过程中有时会出现乱码，比如是定义时对于输入输出的格式控制的不到位。5) 通过这次课程设计，对银行家算法在一定基础上有了更深刻的理解，自己也学到了很多东西，比如编程中比较常见的错误，应该引起重视和注意。源程序清单#include<iostream>using namespace std;#define KG " " /空格/输出各数组资源void xx(int shu10,int i,int m)int j;for(j=0;j<m;j+) cout<<shuij<<' ' cout<<KG;/输出资源分配情况void input(int max10,int allocation10,int need10,int available,int n,int m)int i,j;cout<<"此时系统资源分配情况如下："<<endl;cout<<"-"<<endl;cout<<"进程序号-Max-Allocation-Need-Available-"<<endl;cout<<"-"<<endl;for(i=0;i<n;i+) cout<<KG<<i<<KG; xx(max,i,m); xx(allocation,i,m); xx(need,i,m); if(!i) for(j=0;j<m;j+) cout<<availablej<<' ' cout<<endl;cout<<"-"<<endl;/安全性算法,检查系统是否处于安全状态int sec(int work,int need10,int allocation10,int n,int m)int i,j,k,t;int finish10,xl10; /xl:安全序列cout<<endl<<"对系统进行安全性分析如下："<<endl;cout<<"-"<<endl;cout<<"进程序号-Max-Allocation-Need-Available-Finish-"<<endl;cout<<"-"<<endl;for(i=0;i<n;i+) finishi=0;for(i=0,k=0,t=0;i<n;) if(!finishi) for(j=0;j<m;j+) if(needij>workj) break; if(j=m) cout<<KG<<i<<KG; for(j=0;j<m;j+) cout<<workj<<' ' cout<<KG; xx(need,i,m); xx(allocation,i,m); cout<<KG; for(j=0;j<m;j+) workj=workj+allocationij; cout<<workj<<' ' finishi=1; cout<<KG<<KG<<"true"<<endl; xlk=i; k+; i+; if(i=n) if(k=t) cout<<"-"<<endl; return 0; else if(i!=k) i=0; t=k; else cout<<"-"<<endl; cout<<"找到安全序列(可能不止一个) " for(i=0;i<n;i+) cout<<xli<<" " cout<<""<<endl; return 1; cout<<"-"<<endl;return 0;/主函数void main()int m,n,i,j,k;char c='Y'int available10,max1010,need1010,allocation1010,request10,work10;cout<<"输入系统中的资源类型数："<<endl;cin>>m;cout<<"分别输入各类型资源的总数："<<endl;for(i=0;i<m;i+) cin>>availablei;cout<<"输入系统中的进程个数："<<endl;cin>>n;cout<<"分别输入每个进程各类型资源的最大需求数（Max）："<<endl;for(i=0;i<n;i+) for(j=0;j<m;j+) cin>>maxij;cout<<"分别输入每个进程已分得的各类型资源数（Allocation）："<<endl;for(i=0;i<n;i+) for(j=0;j<m;j+) cin>>allocationij; needij=maxij-allocationij; workj=availablej=availablej-allocationij; if(!sec(work,need,allocation,n,m) /进行安全性算法 cout<<"系统当前处于不安全状态！"<<endl; return;else cout<<"系统当前处于安全状态！"<<endl; /模拟系统初始化完成input(max,allocation,need,available,n,m);while(c='Y'|c='y') cout<<endl<<"输入发出请求的进程序号："<<endl; cin>>k; cout<<"输入进程"<<k<<"所请求的各类型资源数（Request）："<<endl; for(j=0;j<m;j+) cin>>requestj; for(j=0;j<m;j+) if(requestj>needkj) cout<<"请求的资源数超过其所需的资源数，ERROR！"<<endl; break; if(requestj>availablej) cout<<"系统没有足够资源进行分配，进程进入等待！"<<endl; break; if(j=m) for(j=0;j<m;j+) workj=availablej=availablej-requestj; allocationkj=allocationkj+requestj; needkj=needkj-requestj; cout<<endl<<"进行资源试探性分配"<<endl; input(max,allocation,need,available,n,m); if(!sec(work,need,allocation,n,m) cout<<"系统可能进入不安全状态，资源分配失败！"<<endl; for(j=0;j<m;j+) needkj=needkj+requestj; allocationkj=allocationkj-requestj; availablej=availablej+requestj; else cout<<"资源可分配，分配成功！"<<endl; input(max,allocation,need,available,n,m); cout<<endl<<"是否要继续？（Y/N）："<<endl; cin>>c;