銀行家算法要點(diǎn)

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

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

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

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

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

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

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

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

9、類資源的最大需求int Avaliable100=0;系統(tǒng)可用資源char name100=0;資源的名稱int Allocatio n100100=0;系統(tǒng)已分配資源int Need100100=0; 還需要資源int Request100=0;請(qǐng)求資源向量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進(jìn)程名 ;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) 進(jìn)行

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+)輸出運(yùn)行進(jìn)程數(shù)組couttempi;if(iM-1) cout;coutvve ndl;return 0;void share()利用銀行

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

14、錯(cuò)，不予分配!vvendl;ch= n;break;if(ch=y) cha ngdata(i);/根據(jù)進(jìn)程需求量變換資源showdata();/根據(jù)進(jìn)程需求量顯示變換后的資源safe();/根據(jù)進(jìn)程需求量進(jìn)行銀行家算法判斷void addresources()添加資源int n, flag;coutvv請(qǐng)輸入需要添加資源種類的數(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請(qǐng)輸入需要?jiǎng)h除的資源名稱：docinming;for(i=0;iN;i+)if(ming=n amei)flag=0;break;if(i=N)coutvv該資源名稱不存在，請(qǐng)重新輸入: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請(qǐng)輸入該作業(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*單處理機(jī)系統(tǒng)進(jìn)程調(diào)度實(shí)現(xiàn)*、n;N=n;for(i=0;i ming;n amei=ming;coutvv資源的數(shù)量:;cinnu mber;Avaliablei=nu mber;coutvve ndl;coutvv請(qǐng)輸入作業(yè)的數(shù)量:;cinm;M=m; coutvv請(qǐng)輸入各進(jìn)程的最大需求量(m*矩陣)Max:vendl; for(i=0;im;i+)for(j=0;j Maxij;doflag=0;coutvv請(qǐng)輸入各進(jìn)程已經(jīng)申請(qǐ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申請(qǐng)的資源大于最大需求量，請(qǐng)重新輸入!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請(qǐng)正確選擇功能號(hào)(0-5)!endl;break;return 1;作系統(tǒng)銀行家算法流程圖：初始化函數(shù)chushihua()開始輸入進(jìn)程的數(shù)量輸入資源種類數(shù)輸入個(gè)資源當(dāng)前可用資源數(shù)輸出提示：同意分配請(qǐng)求AVAILABLEi-=REQUE STi；ALLOCATIONi-=REQU ESTi;NEEDi+=REQUESTi退出程序，銀行家算法Bank()結(jié)束;安全性算法Safe()開始Work+=ALLOCATIONi; FINISHi=ture;安全，輸出安全序列Retur n ture ；5 運(yùn)行結(jié)果:T時(shí)