銀行家算法要點

1、福建農(nóng)林女修東方禽院DONGFANG COLLEGE , FUJIAN AGRICULTURE AND FORESTRY UNIVERSITY筱計說鋼吊課程名稱：操作系統(tǒng)系別：計算機科學系年級專業(yè)：計算機科學與技術學 號:姓 名:任課教師：成績：2015 年 11 月 25 日目錄一、本選題課程設計的目的 3二、本選題課程設計的要求 3三、本選題課程設計報告內(nèi)容 31. 前言 32. 銀行家算法的環(huán)境 43. 系統(tǒng)技術分析 44. 算法描述及數(shù)據(jù)結(jié)構(gòu)模型 55. 運行結(jié)果： 18四、 總結(jié) 1920參考文獻銀行家算法一、本選題課程設計的目的了解掌握銀行家算法，學會模擬實現(xiàn)資源分配，同時有要求編

2、寫和調(diào)試一個 系統(tǒng)分配資源的簡單模擬程序，觀察死鎖產(chǎn)生的條件，并使用適當?shù)乃惴ǎ行?的防止和避免死鎖的發(fā)生二、本選題課程設計的要求（1）模擬一個銀行家算法；（2）初始化時讓系統(tǒng)擁有一定的資源；（3）用鍵盤輸入的方式申請資源；（4）如果預分配后，系統(tǒng)處于安全狀態(tài)，則修改系統(tǒng)的資源分配情況；（5）如果預分配后，系統(tǒng)處于不安全狀態(tài)，則提示不能滿足請求，三、本選題課程設計報告內(nèi)容1 前言Dijkstra （1965） 提出了一種能夠避免死鎖的調(diào)度算法，稱為銀行家算法。它的模型基于一個小城鎮(zhèn)的銀行家，他向一群客戶分別承諾了一定的貸款額 度，每個客戶都有一個貸款額度，銀行家知道不可能所有客戶同時都需要最

3、大貸 款額，所以他只保留一定單位的資金來為客戶服務， 而不是滿足所有客戶貸款需 求的最大單位。這里將客戶比作進程，貸款比作設備，銀行家比作系統(tǒng)?？蛻魝兏髯宰鲎约旱纳猓谀承r刻需要貸款。在某一時刻，客戶已獲得 的貸款和可用的最大數(shù)額貸款稱為與資源分配相關的系統(tǒng)狀態(tài)。一個狀態(tài)被稱為 是安全的，其條件是存在一個狀態(tài)序列能夠使所有的客戶均得到其所需的貸款。 如果忽然所有的客戶都申請，希望得到最大貸款額，而銀行家無法滿足其中任何 一個的要求，則發(fā)生死鎖。不安全狀態(tài)并不一定導致死鎖，因為客戶未必需要其 最大貸款額度，但銀行家不敢抱這種僥幸心理。銀行家算法就是對每一個請求進行檢查，檢查如果滿足它是否會導

4、致不安全 狀態(tài)。若是，則不滿足該請求；否則便滿足。檢查狀態(tài)是否安全的方法是看他是否有足夠的資源滿足一個距最大需求最 近的客戶。如果可以，則這筆投資認為是能夠收回的，然后接著檢查下一個距最 大需求最近的客戶，如此反復下去。如果所有投資最終都被收回，則該狀態(tài)是安 全的，最初的請求可以批準。2 銀行家算法的環(huán)境Window7系統(tǒng)下的Visual C+ 6.0 中運行3. 系統(tǒng)技術分析設計的主要內(nèi)容是模擬實現(xiàn)動態(tài)資源分配。同時編寫和調(diào)試一個系統(tǒng)動態(tài) 資源的簡單模擬程序，觀察死鎖產(chǎn)生的條件，并使用適當?shù)乃惴?，有效的防止?避免死鎖的發(fā)生。銀行家算法.顧名思義是來源于銀行的借貸業(yè)務，一定數(shù)量的本金要應多

5、個客戶的借貸周轉(zhuǎn)，為了防止銀行加資金無法周轉(zhuǎn)而倒閉， 對每一筆貸款，必須 考察其是否能限期歸還。在操作系統(tǒng)中研究資源分配策略時也有類似問題，系統(tǒng) 中有限的資源要供多個進程使用，必須保證得到的資源的進程能在有限的時間內(nèi) 歸還資源，以供其他進程使用資源。如果資源分配不得到就會發(fā)生進程循環(huán)等待 資源，則進程都無法繼續(xù)執(zhí)行下去的死鎖現(xiàn)象。把一個進程需要和已占有資源的情況記錄在進程控制中，假定進程控制塊 PCB其中“狀態(tài)”有就緒態(tài)、等待態(tài)和完成態(tài)。當進程在處于等待態(tài)時，表示系 統(tǒng)不能滿足該進程當前的資源申請?！百Y源需求總量”表示進程在整個執(zhí)行過程 中總共要申請的資源量。顯然，每個進程的資源需求總量不能超

6、過系統(tǒng)擁有的 資源總數(shù)，銀行算法進行資源分配可以避免死鎖.4. 算法描述及數(shù)據(jù)結(jié)構(gòu)模型銀行家算法：設進程i提出請求Requestn，則銀行家算法按如下規(guī)則進行判斷。如果RequestnNeedi ， n，則報錯返回。如果RequestnAvailable，則進程i進入等待資源狀態(tài)，返回。(3) 假設進程i的申請已獲批準，于是修改系統(tǒng)狀態(tài)：Available=Available-RequestAllocatio n= Allocatio n+RequestNeed=Need-Request(4) 系統(tǒng)執(zhí)行安全性檢查，如安全，則分配成立；否則試探險性分配作廢，系統(tǒng) 恢復原狀，進程等待。安全性檢查(

7、1) 設置兩個工作向量 Work=Available ； FinishM=False(2) 從進程集合中找到一個滿足下述條件的進程，F(xiàn)i nish i=FalseNeed=Work如找到，執(zhí)行；否則，執(zhí)行(4)(3) 設進程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。Work=Work+Allocati onFini sh=TrueGO TO 2如所有的進程FinishM=true ，則表示安全；否則系統(tǒng)不安全。數(shù)據(jù)結(jié)構(gòu)#defi ne False 0#defi ne True 1int Max100100=0;各進程所需各類資源的最大需求int Avaliable100=0;系統(tǒng)可用資源c

8、har name100=0;資源的名稱int Allocatio n 100100=0;系統(tǒng)已分配資源int Need100100=0; 還需要資源int Request100=0;請求資源向量int temp100=0;存放安全序列int Work100=0;存放系統(tǒng)可提供資源int M=100; 作業(yè)的最大數(shù)為100int N=100; 資源的最大數(shù)為100void showdata()顯示資源矩陣源程序代碼實現(xiàn)#i nclude#i ncludevstri ng.h#i nclude#defi ne False 0#defi ne True 1int Max100100=0;各進程所需各

9、類資源的最大需求int Avaliable100=0;系統(tǒng)可用資源char name100=0;資源的名稱int Allocatio n100100=0;系統(tǒng)已分配資源int Need100100=0; 還需要資源int Request100=0;請求資源向量int temp100=0;存放安全序列int Work100=0;存放系統(tǒng)可提供資源int M=100; 作業(yè)的最大數(shù)為100int N=100; 資源的最大數(shù)為100void showdata()顯示資源矩陣int i,j;cout系統(tǒng)目前可用的資源Avaliable:endl;for(i=0;iN;i+)cout n amei;co

10、ute ndl;for (j=0;jN;j+)coutAvaliablej ;/輸出分配資源coute ndl;coutMaxAllocatio nNeede ndl;coutvv進程名 ;for(j=0;j3;j+)for(i=0;iN;i+)cout n amei;cout;coute ndl;for(i=0;iM;i+)cout i;for(j=0;jN;j+)coutMaxijvv;cout;for(j=0;jN;j+)coutAllocatio nij;cout;for(j=0;jN;j+)coutNeedij;coute ndl;in t cha ngdata(i nt i) 進行

11、資源分配int j;for (j=O;jM;j+) Avaliablej=Avaliablej-Requestj;Allocatio nij=Allocatio n ij+Requestj;Needij=Needij-Requestj;return 1;int safe()安全性算法int i,k=O,m,apply,Fi ni sh100=0;int j;int flag=0;Work0=Avaliable0;Work1=Avaliable1;Work2=Avaliable2;for(i=0;iM;i+)apply=0;for(j=0;jN;j+)if (Fi ni shi=False&Ne

12、edijv=Workj) apply+;if(apply=N)for(m=0;mN;m+)變分配數(shù)Workm=Workm+Allocatio n im;Fini shi=True;tempk=i;i=-1;k+;flag+;for(i=0;iM;i+)if(Fi ni shi=False)coutvv系統(tǒng)不安全endl;不成功系統(tǒng)不安全return -1;coutvv系統(tǒng)是安全的!endl;如果安全，輸出成功cout分配的序列：；for(i=0;iM;i+)輸出運行進程數(shù)組couttempi;if(iM-1) cout;coutvve ndl;return 0;void share()利用銀行

13、家算法對申請資源對進行判定char ch;int i=0,j=0;ch=y;coutvv請輸入要求分配的資源進程號(0-vvM-1 i; 輸入須申請的資源號coutvv請輸入進程vvivv 申請的資源:endl;for(j=0;jN;j+)coutv n amejRequestj;/ 輸入需要申請的資源for (j=0;jNeedij)/判斷申請是否大于需求，若大于則出錯coutvv進程vvivv申請的資源大于它需要的資源;cout分配不合理，不予分配！Avaliablej)判斷申請是否大于當前資源，若大于則/出錯coutvv進程vvivv申請的資源大于系統(tǒng)現(xiàn)在可利用的資源;coutvv分配出

14、錯，不予分配!vvendl;ch= n;break;if(ch=y) cha ngdata(i);/根據(jù)進程需求量變換資源showdata();/根據(jù)進程需求量顯示變換后的資源safe();/根據(jù)進程需求量進行銀行家算法判斷void addresources()添加資源int n, flag;coutvv請輸入需要添加資源種類的數(shù)量cinn;flag=N;N=N+n;for(i nt i=0;in ameflag;cout數(shù)量:;cin Avaliableflag+;showdata();safe();void delresources()刪除資源char ming;int i,flag=1;

15、coutvv請輸入需要刪除的資源名稱：docinming;for(i=0;iN;i+)if(ming=n amei)flag=0;break;if(i=N)coutvv該資源名稱不存在，請重新輸入:while(flag);for(i nt j=i；jN-1;j+)n amej=n amej+1;Avaliablej=Avaliablej+1;N=N-1;showdata();safe();void cha ngeresources()修改資源函數(shù)cout系統(tǒng)目前可用的資源Avaliable:endl;for(i nt i=0;iN;i+)cout n ameivv:vAvaliableivve

16、 ndl;cout輸入系統(tǒng)可用資源Avaliable:Avaliable0Avaliable1Avaliable2;coutvv經(jīng)修改后的系統(tǒng)可用資源為endl;for (i nt k=0;kN;k+)cout n amek:Avaliableke ndl; showdata();safe();void addprocess()添加作業(yè)int flag=M;M=M+1;coutvv請輸入該作業(yè)的最打需求量Maxvendl; for(i nt i=0;iN;i+)cout n ameiMaxflagi;Needflagi=Maxflagi-Allocatio nflagi;showdata();

17、safe();int mai n()主函數(shù) int i,j, nu mber,choice, m,n, flag;char ming;coutvv*單處理機系統(tǒng)進程調(diào)度實現(xiàn)*、n;N=n;for(i=0;i ming;n amei=ming;coutvv資源的數(shù)量:;cinnu mber;Avaliablei=nu mber;coutvve ndl;coutvv請輸入作業(yè)的數(shù)量:;cinm;M=m; coutvv請輸入各進程的最大需求量(m*矩陣)Max:vendl; for(i=0;im;i+)for(j=0;j Maxij;doflag=0;coutvv請輸入各進程已經(jīng)申請的資源量(m*矩

18、陣)Allocati on :e ndl;for(i=0;im;i+)for(j=0;j Allocati on ij;if(Allocati on ijMaxij)flag=1;Needij=Maxij-Allocatio n ij;if(flag)coutvv申請的資源大于最大需求量，請重新輸入!n;while(flag);showdata(); 顯示各種資源safe();用銀行家算法判定系統(tǒng)是否安全while(choice)coutvv*銀行家算法演示 *endl;coutvv1:增加資源vve ndl;coutvv2:刪除資源vve ndl;coutvv3:修改資源vve ndl;co

19、utvv4:分配資源vve ndl;cout5:增加作業(yè)e ndl;cout0:離開e ndl;coutv*v choice;switch(choice)case 1: addresources();break;case 2: delresources();break;case 3: cha ngeresources();break;case 4: share();break;case 5: addprocess();break;case 0: choice=0;break;default: coutvv請正確選擇功能號(0-5)!endl;break;return 1;作系統(tǒng)銀行家算法流程圖：初始化函數(shù)chushihua()開始輸入進程的數(shù)量輸入資源種類數(shù)輸入個資源當前可用資源數(shù)輸出提示：同意分配請求AVAILABLEi-=REQUE STi；ALLOCATIONi-=REQU ESTi;NEEDi+=REQUESTi退出程序，銀行家算法Bank()結(jié)束;安全性算法Safe()開始Work+=ALLOCATIONi; FINISHi=ture;安全，輸出安全序列Retur n ture ；5 運行結(jié)果:T時