软件工程课程设计银行家算法

1、目 录一、设计目的1二、设计内容1三、设计原理1四、算法实现2五、流程图4六、源程序8七、运行示例及结果分析15八、心得体会19九、参考资料20银行家算法一、设计目的1）掌握死锁的产生的原因、产生死锁的必要条件和处理死锁的基本方法。2）了解多道程序系统中，多个进程并发执行的资源分配。3）掌握预防死锁的方法，系统安全状态的基本概念4）理解死锁避免在当前计算机系统不常使用的原因。5）掌握银行家算法，了解资源在进程并发执行中的资源分配策略。二、设计内容设计一个n个并发进程共享m个系统资源的系统。进程课动态申请资源和释放资源，系统按照进程的申请动态的分配资源。用银行家算法设计实现。三、设计原理我们可以

2、把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。 为保证资金的安全,银行家规定: (1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客; (2) 顾客可以分歧贷款,但贷款的总数不能超过最大需求量; (3) 当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款; (4) 当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金. 操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以

3、满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。四、算法实现（1） 初始化这组进程的最大资源请求和依次申请的资源序列。把各进程已占用和需求资源情况记录在进程控制块中。假定进程控制块的内容包括：进程名，状态，当前申请量，资源需求总量，已占资源量，能执行完标志。其中，进程的状态有：就绪、等待和完成。当系统不能满足进程的资源请求时，进程处于

4、等待态。资源需求总量表示进程运行过程中对资源的总的需求量。 已占资源量表示进程目前已经得到但还未归还的资源量。因此，进程在以后还需要的剩余资源量等于资源需要总量减去已占资源量。显然每个进程的资源需求总量不应超过系统拥有的资源总量。 （2） 银行家算法分配资源的原则是：当某个进程提出资源请求时，假定先分配资源给它，然后查找各进程的剩余请求，检查系统的剩余资源量是否由于进程的分配而导致系统死锁。若能，则让进程等待，否则，让进程的假分配变为真分配。 a) 查找各进程的剩余请求，检查系统的剩余资源量是否能满足其中一进程。如果能，则转b)。 b) 将资源分配给所选的进程，这样，该进程已获得资源最大请求，

5、最终能运行完成。标记这个进程为终止进程，并将其占有的全部资源归还给系统。 重复第a)步和第b)步，直到所有进程都标记为终止进程，或直到一个死锁发生。若所有进程都标记为终止进程，则系统的初始状态是安全的，否则为不安全的。若安全，则正式将资源分配给它，否则，假定的分配作废，让其等待。数据结构：#define MAXPROCESS 50 /*最大进程数*/#define MAXRESOURCE 100 /*最大资源数*/int AVAILABLEMAXRESOURCE; /*可用资源数组*/int MAXMAXPROCESSMAXRESOURCE; /*最大需求矩阵*/int ALLOCATIONM

6、AXPROCESSMAXRESOURCE; /*分配矩阵*/int NEEDMAXPROCESSMAXRESOURCE; /*需求矩阵*/int REQUESTMAXPROCESSMAXRESOURCE; /*进程需要资源数*/bool FINISHMAXPROCESS; /*系统是否有足够的资源分配*/int pMAXPROCESS; /*记录序列*/int WorkMAXRESOURCE; /*工作数组*/int m,n; /*m个进程,n个资源*/string showdata14=max ,allo,need,aval;/*绘制资源以及进程状态时使用*/string showdata2

7、5=work,need,allo,w+al,finish;/*绘制银行家算法过程时使用*/五、流程图1：主函数流程图：结束开始调用初始化函数(Init)图1主函数流程图安全性检测(Safe)银行家算法(Bank)安全YN2：初始化流程图结束返回Init()开始输入进程的数目m图2初始化流程图输入资源的种类n输入AVAILABLEi输入正确YN输入MAXij输入ALLOCATIONij 显示当前系统状态(iShow)提示错误，重新输入相应数据3：安全性检测流程图结束返回Safe()开始绘制结果表格头部(fShow)图3安全性检测流程图Worki=AVAILABLEi;FINISHi=false;

8、输出找到的安全序列，返回trueNEEDi=Work&FINISHi=falseYNWorki+=ALLOCATIONiFINISHi=true输出进程及资源变化结果系统不安全，返回false所有进程FINISHi=ture;YN4:银行家算法流程图结束返回Bank()开始输入请求资源的进程cusneed图4银行家算法流程图输入进程请求资源REQUESTcusneedi提示安全,允许请求REQUESTcusneedi=NEEDcusneediYNAVAILABLEi-=REQUESTcusneedi;ALLOCATIONcusneedi+=REQUESTcusneedi;NEEDcusneed

9、i-=REQUESTcusneedi;分配资源分配资源操作回滚，恢复到未分配REQUESTcusneedi= AVAILABLEiYNNSafe();继续分配？YN六、源程序#include #include #include using namespace std;#define MAXPROCESS 50 /*最大进程数*/#define MAXRESOURCE 100 /*最大资源数*/int AVAILABLEMAXRESOURCE; /*可用资源数组*/int MAXMAXPROCESSMAXRESOURCE; /*最大需求矩阵*/int ALLOCATIONMAXPROCESSMA

10、XRESOURCE; /*分配矩阵*/int NEEDMAXPROCESSMAXRESOURCE; /*需求矩阵*/int REQUESTMAXPROCESSMAXRESOURCE; /*进程需要资源数*/bool FINISHMAXPROCESS; /*系统是否有足够的资源分配*/int pMAXPROCESS; /*记录序列*/int WorkMAXRESOURCE; /*工作数组*/int m,n; /*m个进程,n个资源*/string showdata14=max ,allo,need,aval;/*输出表格用标题*/string showdata25=work,need,allo,

11、w+al,finish;/*输出表格用标题*/void iShow()int size,size2;cout系统;for(int k=0;k4;k+)size=showdata1k.length();size2=(n*3+5-size)/2; /*计算出字符前端的空格*/coutsetw(size2+size)showdata1ksetw(size2) ;/*使得文字在资源标志ABC总宽度下剧中*/coutendl;cout资源;for(k=0;k4;k+)char sourcename=A; /*资源命名，从A开始*/cout ;for(int kk=0;kkn;kk+)cout sourc

12、ename;sourcename+;cout ;coutendl;for(int ii=0;iim;ii+)coutPii ;/*输出进程名及状态*/for(int jj=0;jjn;jj+)coutsetw(3)MAXiijj;cout ;for(jj=0;jjn;jj+)coutsetw(3)ALLOCATIONiijj;cout ;for(jj=0;jjn;jj+)coutsetw(3)NEEDiijj;cout ;if(ii=0)for(int iii=0;iiin;iii+)coutsetw(3)AVAILABLEiii;cout endl;void fShow()/*显示表格*/c

13、out系统;for(int k=0;k5;k+)int size=showdata2k.length();int size2=(n*3+5-size)/2;coutsetw(size2+size)showdata2ksetw(size2) ;coutendl;cout资源;for(k=0;k4;k+)char sourcename=A;cout ;for(int kk=0;kkn;kk+)coutsetw(3)sourcename;sourcename+;cout ;coutendl;void Init() /*初始化算法*/ int i,j; coutm; coutn; cout请输入每个进

14、程最多所需的各资源数,按照mxn矩阵输入endl; for(i=0;im;i+) for(j=0;jMAXij; cout请输入每个进程已分配的各资源数,也按照mxn矩阵输入endl; for(i=0;im;i+) for(j=0;jALLOCATIONij; NEEDij=MAXij-ALLOCATIONij; if(NEEDij0) cout您输入的第i+1个进程所拥有的第j+1个资源数错误,请重新输入:endl; j-; continue; cout请输入各个资源现有的数目:endl; for(i=0;iAVAILABLEi; iShow();bool Safe() /*安全性算法*/f

15、Show(); int i,j,k,l=0; for(i=0;in;i+) Worki=AVAILABLEi; for(i=0;im;i+) FINISHi=false; for(i=0;im;i+) if(FINISHi=true) continue; else for(j=0;jWorkj) break; if(j=n) FINISHi=true;coutPi ;for(k=0;kn;k+)coutsetw(3)Workk;cout ;for(k=0;kn;k+)coutsetw(3)NEEDik;cout ;for(k=0;kn;k+)coutsetw(3)ALLOCATIONik;co

16、ut ;for(k=0;kn;k+)coutsetw(3)Workk+ALLOCATIONik;cout ;coutsetw(3)trueendl; for(k=0;kn;k+) Workk+=ALLOCATIONik; pl+=i; i=-1; /*再次由进程从小到大遍历*/ else continue; if(l=m) /*进程记录p的数量等于资源总量，全部进程均已经满足*/ cout系统是安全的endl; cout安全序列:endl; for(i=0;il;i+) coutpi; if(i!=l-1) cout; coutendl; return true; coutn无法继续找到可满足

17、的进程!endl; cout系统是不安全的endl; return false; void Bank() /*银行家算法*/ int i,cusneed; /*cusneed为进程*/ char again; while(1) coutcusneed; coutn请输入进程所请求的各资源的数量endl; for(i=0;iREQUESTcusneedi; for(i=0;iNEEDcusneedi) cout您输入的请求数超过进程的需求量!请重新输入!AVAILABLEi) cout您输入的请求数超过系统有的资源数!请重新输入!endl; continue; for(i=0;in;i+)/*先

18、分配资源*/ AVAILABLEi-=REQUESTcusneedi; ALLOCATIONcusneedi+=REQUESTcusneedi; NEEDcusneedi-=REQUESTcusneedi; if(Safe() cout同意分配请求!endl; else cout您的请求被拒绝!endl; for(i=0;in;i+)/*资源分配后不安全，回滚分配资源操作*/ AVAILABLEi+=REQUESTcusneedi; ALLOCATIONcusneedi-=REQUESTcusneedi; NEEDcusneedi+=REQUESTcusneedi; for(i=0;im;i+

19、) FINISHi=false; cout您还想再次请求分配吗?是请按y/Y,否请按其它键again; if(again=y|again=Y) continue; break; void main() while(true) Init(); if(Safe() break; /*如果初始化安全，跳出while循环*/ cout当前系统不安全，请重新初始化系统; Bank();七、运行示例及结果分析结果分析：图1为初始化函数段执行的结果，输入相应数据如下后：请输入进程的数目:5请输入资源的种类:3请输入每个进程最多所需的各资源数,按照3x5矩阵输入7 5 33 2 29 0 22 2 24 3

20、3请输入每个进程已分配的各资源数,也按照3x5矩阵输入0 1 02 0 03 0 22 1 10 0 2请输入各个资源现有的数目:332得到一个安全状态，然后对安全状态进行检测，如果不是安全状态，重新初始化。验证了各种安全与不安全申请。八、心得体会在设计“银行家算法的模拟实现”程序的过程中，我遇到过许多问题，可是也学到了很多东西。本程序的设计实现主要是用C+语言实现，通过对程序算法的设计优化、输出显示的格式设计、输入过程中的异常处理等一些设计过程中的问题的考虑解决，在C+学习上也有了很大的进步。本来想要动态分配列表空间来完成数据功能，但是动态分配后，指针位置作为二维数组时计算相当麻烦，放弃了动态分配的算法，而是以全局函数来完成算法所需要的数据结构，牺牲了