c++银行家算法总结.doc

《c++银行家算法总结.doc》由会员分享，可在线阅读，更多相关《c++银行家算法总结.doc（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品文档 仅供参考 学习与交流c+银行家算法总结【精品文档】第 16 页算法的实现 一、初始化由用户输入数据，分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵MAX、分配矩阵ALLOCATION、需求矩阵NEED赋值。二、银行家算法在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。设进程cusneed提出请求REQUEST i，则银行家算法按如下规则进行判断。(

2、1)如果REQUEST cusneed i= NEEDcusneedi，则转(2)；否则，出错。(2)如果REQUEST cusneed i= AVAILABLEcusneedi，则转(3)；否则，出错。(3)系统试探分配资源，修改相关数据： AVAILABLEi-=REQUESTcusneedi; ALLOCATIONcusneedi+=REQUESTcusneedi; NEEDcusneedi-=REQUESTcusneedi;(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。三、安全性检查算法运行安全性检查算法如下：1）Work = Availa

3、ble；Finish = false；2）寻找满足如下条件的i: Finishi=false并且NeediWorki； 如果不存在，则转步骤 4）；3）Work = Work + Allocationi；Finishi = true； 转步骤 2）；4）如果对于所有i，Finishi = true，则系统处于安全状态，否则处于不安全状态。 (1)设置两个工作向量Work=AVAILABLE;FINISH(2)从进程集合中找到一个满足下述条件的进程，FINISH=false;NEED=Work;如找到，执行(3)；否则，执行(4)(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。Work

4、+=ALLOCATION;Finish=true;GOTO 2(4)如所有的进程Finish= true，则表示安全；否则系统不安全。各算法流程图 #include using namespace std;#define MAXPROCESS50/*最大进程数*/ #define MAXRESOURCE100/*最大资源数*/ int AVAILABLEMAXRESOURCE; /*/ /* 可用资源数组 */ int MAXMAXPROCESSMAXRESOURCE; /*/ /* 最大需求矩阵 */ int ALLOCATIONMAXPROCESSMAXRESOURCE; /*/ /* 分

5、配矩阵 */ int NEEDMAXPROCESSMAXRESOURCE; /*/ /* 需求矩阵 */ int REQUESTMAXPROCESSMAXRESOURCE; /*/ /* 进程需要资源数 */ bool FINISHMAXPROCESS; /*/ /* 系统是否有足够的资源分配 */ int pMAXPROCESS; /*/ /* 记录序列 */ int m,n; /*/ /* m个进程,n个资源 */ void Init();bool Safe();void Bank();int main()Init();Safe();Bank();getchar(); / 给出系统拥有的每

6、种资源数，已经分配给每个进程的资源数，还有每个进程最多需要每种资源的个数，让你判断当前系统是不是安全的 void Init() /*/ /* 初始化算法 */ int i,j;cout m;cout n;cout 请输入每个进程最多所需的各资源数,按照 m x n 矩阵输入 endl; for (i = 0 ;i m;i + ) for (j = 0 ;j MAXij;cout 请输入每个进程已分配的各资源数,也按照 m x n 矩阵输入 endl; for (i = 0 ;i m;i + ) for (j = 0 ;j ALLOCATIONij;NEEDij = MAXij - ALLOCA

7、TIONij; if (NEEDij 0 ) cout 您输入的第 i + 1 个进程所拥有的第 j + 1 个资源数错误,请重新输入: endl;j - ; continue ; cout 请输入各个资源现有的数目: endl; for (i = 0 ;i AVAILABLEi; void Bank() /*/ /* 银行家算法 */ int i,cusneed; char again; while ( 1 ) Restart:cout 请输入要申请资源的进程号(注:第1个进程号为0,依次类推) cusneed;cout 请输入进程所请求的各资源的数量 endl; for (i = 0 ;i

8、 REQUESTcusneedi; for (i = 0 ;i NEEDcusneedi) cout 您输入的请求数超过进程的需求量!请重新输入! AVAILABLEi) cout 您输入的请求数超过系统有的资源数!请重新输入! endl; goto Restart; for (i = 0 ;i n;i + ) AVAILABLEi -= REQUESTcusneedi;ALLOCATIONcusneedi += REQUESTcusneedi;NEEDcusneedi -= REQUESTcusneedi; if (Safe() cout 同意分配请求! endl; else cout 您的

9、请求被拒绝! endl; for (i = 0 ;i n;i + ) AVAILABLEi += REQUESTcusneedi;ALLOCATIONcusneedi -= REQUESTcusneedi;NEEDcusneedi += REQUESTcusneedi; for (i = 0 ;i m;i + ) FINISHi = false ; cout 您还想再次请求分配吗?是请按y/Y,否请按其它键 again; if (again = y | again = Y ) continue ; break ; bool Safe() /*/ /* 安全性算法 */ int i,j,k,l

10、= 0 ; int WorkMAXRESOURCE; /*/ /* 工作数组 */ for (i = 0 ;i n;i + )Worki = AVAILABLEi; for (i = 0 ;i m;i + ) FINISHi = false ; for (i = 0 ;i m;i + ) if (FINISHi = true ) continue ; else for (j = 0 ;j Workj) break ; if (j = n) /*/ /* 那么你就需要看每个进程还需要每种资源多少，把它计算出来，然后看你剩下的可分配的资源数是不是可以达到其中一个进程的要求，如果可以，就分配给它，让

11、这个进程执行，执行结束后，这个进程释放资源，重新计算系统的可分配的资源 */ FINISHi = true ; for (k = 0 ;k n;k + ) Workk += ALLOCATIONik; pl + = i;i =- 1 ; else continue ; if (l = m) cout 系统是安全的 endl;cout 安全序列: endl; for (i = 0 ;i l;i + ) cout pi; if (i != l - 1 ) cout ; cout endl; return true ; cout 系统是不安全的 endl; return false ; 、银行算法是

12、怎样避免死锁的： 银行家算法是这样的：1）当一个用户对资金的最大的需求量不超过银行家现有的资金时就可以接纳该用户。2）用户可以分期贷款，但贷款的总数不能超过最大需求量。3）当银行家现有的资金不能满足用户的尚需贷款时，对用户的贷款可推迟支付，但总能使用户在有限的时间里得到贷款。4）当用户得到所需的全部资金后，一定能在有限的时间里归还所有资金。我们把操作系统看作是银行家，操作系统管理的资源相当于是银行家管理的资金，则银行家算法就是：1）当一个进程首次申请资源时，测试该进程对资源的最大的需求量，如果不超过系统现存资源时就可以按他的当前申请量为其分配资源。 否则推迟分配。2）进程执行中继续申请资源时，测试该进程占用资源和本次申请资源总数有没有超过最大需求量。超过就不分配，没超过则再测试现存资源是否满足进程还需要的最大资源量，满足则按当前申请量分配，否则也推迟分配。总之，银行家算法要保证分配资源时系统现存资源一定能满足至少一个进程所需的全部资源。这样就可以保证所有进程都能在有限时间内得到需要的全部资源。这就是安全状态。（银行家算法在操作系统的实践考试中可能会用到）