編程序模擬銀行家算法1(共25頁)

1、PAGE PAGE 4 需求分析 5武漢理工大學華夏(Huxi)學院課程設(shè)計報告書課程名稱： 操作系統(tǒng)(co zu x tn)原理 題 目： 編程序模擬(mn)銀行家算法 系 名： 信 息 工 程 系 專業(yè)班級： 計算機1111班 姓 名： 學 號： 10210411131 指導教師: 蘇 永 紅 2013 年 6 月 28 日課程設(shè)計任務(wù)書學生(xu sheng)姓名： 專業(yè)(zhuny)班級： 計算機1111班 指導(zhdo)教師： 蘇永紅 工作單位： 信息工程系 設(shè)計題目：編程序模擬銀行家算法初始條件：Linux操作系統(tǒng)，GCC編譯環(huán)境要求完成的主要任務(wù)：主要任務(wù)：銀行家算法是避免死鎖

2、的一種重要方法，本實驗要求用用c/c+語言在Linux操作系統(tǒng)環(huán)境下編寫和調(diào)試一個簡單的銀行家算法程序。加深了解有關(guān)資源申請、避免死鎖等概念，并體會和了解死鎖和避免死鎖的具體實施方法。思想：將一定數(shù)量的資金供多個用戶周轉(zhuǎn)使用，當用戶對資金的最大申請量不超過現(xiàn)存資金時可接納一個新客戶，客戶可以分期借款，但借款總數(shù)不能超過最大的申請量。銀行家對客戶的借款可以推遲支付，但是能夠使客戶在有限的時間內(nèi)得到借款，客戶得到所有的借款后能在有限的時間內(nèi)歸還。用銀行家算法分配資源時，測試進程對資源的最大需求量，若現(xiàn)存資源能滿足最大需求就滿足當前進程的申請，否則推遲分配，這樣能夠保證至少有一個進程可以得到所需的全

3、部資源而執(zhí)行到結(jié)束，然后歸還資源，若OS能保證所有進程在有限的時間內(nèi)得到所需資源則稱系統(tǒng)處于安全狀態(tài)。設(shè)計報告撰寫格式要求：1設(shè)計題目與要求 2 設(shè)計思想 3系統(tǒng)結(jié)構(gòu) 4 數(shù)據(jù)結(jié)構(gòu)的說明和模塊的算法流程圖 5 使用說明書（即用戶手冊）：內(nèi)容包含如何登錄、退出、讀、寫等操作說明6 運行結(jié)果和結(jié)果分析（其中包括實驗的檢查結(jié)果、程序的運行情況）7 自我評價與總結(jié) 8 附錄：程序清單，注意加注釋（包括關(guān)鍵字、方法、變量等），在每個模塊前加注釋； 時間安排 6月24日 布置課程設(shè)計任務(wù)；分配題目后，查閱資料、 準備程序； 6月 256月27 日上機調(diào)試程序、書寫課程設(shè)計報告；6月28 日 提交課程設(shè)計報

4、告及相關(guān)文檔。指 導 教 師 簽 字： 2013年 6月 28日系 主 任 簽 字： 2013年 6月 28日目錄(ml)1設(shè)計(shj)題目與要求41.1設(shè)計(shj)題目41.2要求完成的任務(wù)41.3主要任務(wù)41.4提示42設(shè)計思路52.1算法思路52.2銀行家算法53系統(tǒng)結(jié)構(gòu)53.1主要用到的數(shù)據(jù)結(jié)構(gòu)53.2程序模塊53.3各模塊間的調(diào)用關(guān)系64數(shù)據(jù)結(jié)構(gòu)的說明和模塊的算法流程圖64.1數(shù)據(jù)結(jié)構(gòu)說明64.1算法流程圖75使用說明96測試結(jié)果截圖106.1開始界面106.2輸出界面107自我評價與總結(jié)148參考文獻159附錄：程序清單16PAGE 151設(shè)計(shj)題目與要求11設(shè)計(sh

5、j)題目編程序模擬(mn)銀行家算法1.2要求完成的任務(wù)銀行家算法是避免死鎖的一種重要方法，本實驗要求用用c/c+語言在Linux操作系統(tǒng)環(huán)境下編寫和調(diào)試一個簡單的銀行家算法程序。加深了解有關(guān)資源申請、避免死鎖等概念，并體會和了解死鎖和避免死鎖的具體實施方法。1.3主要任務(wù)銀行家算法就是對每一個請求進行檢查，檢查如果滿足它是否會導致不安全狀態(tài)。若是，則不滿足該請求；否則便滿足。檢查狀態(tài)是否安全的方法是看他是否有足夠的資源滿足一個距最大需求最近的客戶。如果可以，則這筆投資認為是能夠收回的，然后接著檢查下一個距最大需求最近的客戶，如此反復(fù)下去。如果所有投資最終都被收回，則該狀態(tài)是安全的，最初的請求

6、可以批準。1.4提示將一定數(shù)量的資金供多個用戶周轉(zhuǎn)使用，當用戶對資金的最大申請量不超過現(xiàn)存資金時可接納一個新客戶，客戶可以分期借款，但借款總數(shù)不能超過最大的申請量。銀行家對客戶的借款可以推遲支付，但是能夠使客戶在有限的時間內(nèi)得到借款，客戶得到所有的借款后能在有限的時間內(nèi)歸還。用銀行家算法分配資源時，測試進程對資源的最大需求量，若現(xiàn)存資源能滿足最大需求就滿足當前進程的申請，否則推遲分配，這樣能夠保證至少有一個進程可以得到所需的全部資源而執(zhí)行到結(jié)束，然后歸還資源，若OS能保證所有進程在有限的時間內(nèi)得到所需資源則稱系統(tǒng)處于安全狀態(tài)。2 設(shè)計(shj)思想21算法(sun f)思路：先對用戶提出的請求

7、進行合法性檢查，即檢查請求是否大于需要的，是否大于可利用的。若請求合法，則進行預(yù)分配，對分配后的狀態(tài)調(diào)用安全性算法進行檢查。若安全，則分配；若不安全，則拒絕申請，恢復(fù)(huf)到原來的狀態(tài)，拒絕申請。22銀行家算法 ：我們可以把操作系統(tǒng)看做是銀行家，操作系統(tǒng)管理的資源相當于銀行家管理的資金，進程向操作系統(tǒng)請求資源相當于客戶向銀行家貸款。操作系統(tǒng)按銀行家制定的規(guī)則為進程分配資源，當進程首次申請資源時，要測試該進程尚需求的資源量，若是系統(tǒng)現(xiàn)存的資源可以滿足它尚需求的資源量，則按當前的申請量來分配資源，否則就推遲分配。當進程在執(zhí)行中繼續(xù)申請資源時，先測試該進程申請的資源量是否超過了它尚需的資源量。若

8、超過則拒絕分配，若沒有超過則再測試系統(tǒng)尚存的資源是否滿足該進程尚需的資源量，若滿足即可按當前的申請量來分配，若不滿足亦推遲分配。3 系統(tǒng)結(jié)構(gòu)31主要用到的數(shù)據(jù)結(jié)構(gòu)：最大需求矩陣Max已分配矩陣Allocation仍需求矩陣Need=Max-Allocation可利用資源向量Available申請各類資源向量Request工作向量 work , Finish32程序模塊： public static void main(String args) /系統(tǒng)的主函數(shù)public void printFrame() /初始化public void print() /打印輸出public void Saf

9、ty() /利用(lyng)安全性算法進行安全性檢測public void changdata(int i) /進行(jnxng)資源分配 void judge() /利用銀行家算法對申請資源(zyun)進行判定33各模塊間的調(diào)用關(guān)系：主函數(shù)void main()要調(diào)用： printFrame()，print()，Safty()，judge()安全性檢測函數(shù)Safty()要調(diào)用：print()銀行家算法函數(shù)judge()要調(diào)用print()、Safty()、和judge()本身4 數(shù)據(jù)結(jié)構(gòu)的說明和模塊的算法流程圖4.1數(shù)據(jù)結(jié)構(gòu)說明（1）進行初始化輸入的函數(shù)（2）打印輸出的函數(shù)（3）利用安全性算

10、法進行檢測的函數(shù)（4）進行資源分配的函數(shù)(5)利用行家算法進行判定的函數(shù)4.2算法(sun f)流程圖 1.系統(tǒng)主要(zhyo)算法流程圖YNN結(jié)束分配安全進行實際分配分配不安全不能分配有？設(shè)置該進程“能運行完”標志并假設(shè)它歸還全部資源找到系統(tǒng)剩余資源數(shù)與“能運行完”標志為0的進程尚需資源數(shù)比較，找出一個系統(tǒng)能滿足要求的進程對申請者預(yù)分配清除所有進程“能運行完”標志開始檢查是否有“能運行完”標志尚未設(shè)置的進程 2.銀行家算法(sun f)流程圖3.安全性算法(sun f)流程圖5使用(shyng)說明 該程序(chngx)是用c/c+語言在Linux操作系統(tǒng)環(huán)境下編寫和調(diào)試(dio sh)一個

11、簡單的銀行家算法程序并在終端(zhn dun)中運行。使用方法是,在終端輸入./a.out按下enter鍵后顯示出來，然后在編譯執(zhí)行程序后按照提示輸入進程數(shù)量和資源數(shù)，然后程序會自動判斷能否生成安全序列，使得資源得倒合理分配。結(jié)果輸出后還可以繼續(xù)選擇其他的例如增加、刪除、修改資源種類和數(shù)量的功能。按N數(shù)字鍵可以退出程序。按Y數(shù)字鍵可以退出程序。6測試結(jié)果截圖：6.1開始界面 圖1 輸入./a.out 6.2輸出結(jié)果圖2輸入(shr)./a.out后的界面圖3 輸入(shr)進程號和資源數(shù)后的界面 圖4 按Y鍵后繼續(xù)執(zhí)行的界面(jimin)圖5 按N鍵后的界面(jimin)圖6 申請(shnqn

12、g)不合理時的界面圖7分配(fnpi)成功的界面PAGE 267 自我(zw)評價與總結(jié)第一次課程設(shè)計的時候，老師要求我們寫文檔，需求分析啊，系統(tǒng)測試啊，項目管理啊等等，那時候覺得寫這么多沒用的紙上的東西干什么啊，而且又什么都不明白。現(xiàn)在又一次的寫文檔，突然才明白，有些東西，寫多了自然就會有經(jīng)驗(jngyn)，有收獲的。在本程序設(shè)計中，我深深的感受到一個程序的總體設(shè)計是多么的重要了，以前寫的小程序都是想到哪寫到哪，無論怎樣都能搞定，這次因為設(shè)計了圖形界面，雖然說程序也不是很大，但因為當初考慮的不周全，導致最后，不得不通過刪減程序功能，來達到完成任務(wù)的目的。在銀行家算法這個系統(tǒng)之中，所采用的數(shù)據(jù)

13、結(jié)構(gòu)應(yīng)是最基本的部分。銀行家算法的數(shù)據(jù)結(jié)構(gòu)我們采用了一維數(shù)組與二維數(shù)組來存儲(cn ch)，比如最大需求量Max、已分配資源數(shù)Allocation、仍需求資源數(shù)Need、以及系統(tǒng)可利用的資源數(shù)、申請各類資源等數(shù)組。數(shù)據(jù)結(jié)構(gòu)雖然重要但卻只是基礎(chǔ)，而最主要的用以實現(xiàn)系統(tǒng)功能的應(yīng)該有兩個部分，一是用銀行家算法來判斷，二是用安全性算法來檢測系統(tǒng)的安全性。在本程序代碼中，銀行家算法用judge( )函數(shù)來實現(xiàn)。首先，輸入欲申請資源的進程以及其所申請的資源數(shù)，存放在Request數(shù)組中。然后，判斷進程請求的資源數(shù)是否大于其所需的資源數(shù)，若大于則報錯并返回，若不大于則繼續(xù)判斷它是否大于系統(tǒng)在此時刻可利用的資

14、源數(shù)，同樣，如果大于則報錯并反回，如果不大于則調(diào)用changedata( )函數(shù)來進行預(yù)分配，之后再調(diào)用安全型算法safty檢查。最后，無論此次分配是否成功，我們都可以選擇繼續(xù)分配或者退出系統(tǒng)。安全性檢測我們是用safty( )函數(shù)來實現(xiàn)的。首先，F(xiàn)inish為布爾型，默認是False，即該進程未完成。而Work即該系統(tǒng)中可以用來工作的資源數(shù)最開始為系統(tǒng)最初可以用的資源數(shù)。然后，我們從第一個進程開始判斷該進程未完成且其所需求的資源量不大于該系統(tǒng)中可以用來工作的資源量這個條件是否成立，即Finish=False且Need=Work是否成立。成立的話則將當前在工作的資源量與該進程已分配的資源量相加

15、，存放于當前可用來工作的資源量當中，即Work=Work+Allocation，并將Finish的值改為True。否則便將此進程的優(yōu)先級減一，排在隊位，然后開始往后循環(huán)。待所有的進程循環(huán)完畢，我們再次判斷是否還存在進程的Finish=False，如果仍存在，則說明系統(tǒng)沒有安全序列，處于不安全狀態(tài)，不可以進行分配；否則，系統(tǒng)處于安全狀態(tài)，將預(yù)分配變?yōu)閷嶋H分配，求出安全序列并且將實際分配后的資源分配情況打印輸出。除此之外，在程序當中，我們也得強調(diào)一下對輸入的合法性的判斷。比如，我們輸入的欲申請資源的進程號沒有在系統(tǒng)已存在的進程當中，或者進程號定義為整型，但是卻錯輸成字母等情況，我們需要對這些情況進

16、行(jnxng)判斷，讓程序報錯返回而并非因錯誤而中斷。這樣的情況處理起來比較麻煩，相當于對每次輸入針對各種不同的情況都得做判斷。我也沒有涵蓋全部的輸入，僅僅只是對輸入的進程號不在已存在進程當中、以及輸入的操作選擇不存在兩種情況分別作了判斷，并且針對第二種情況設(shè)定了五次輸入錯誤的話(dehu)系統(tǒng)關(guān)閉的功能。而因為對于某些比如(br)進程號本來設(shè)定就是整型，因此對輸入的是字母的判別因比較復(fù)雜而未能加上?？傊?，銀行家算法是避免死鎖的主要方法，其思路在很多方面都非常值得我們來學習借鑒。8.參考文獻湯小丹，梁紅兵，哲鳳屏，湯子瀛.計算機操作系統(tǒng). 西安：西安電子科技大學出版社，2007.嚴蔚敏，吳偉

17、民.數(shù)據(jù)結(jié)構(gòu). 北京：清華大學出版社，2006.趙莉，楊國梁，孫喁喁，徐飛. Java程序設(shè)計教程. 西安：西安科技大學出版社，2009. HYPERLINK /view/32d7df73f242336c1eb95efa.html /view/32d7df73f242336c1eb95efa.html (百度文庫：銀行家算法報告) HYPERLINK /default.asp?id=204 /default.asp?id=204 （志文工作室： 銀行家算法模擬實現(xiàn)）9. 附錄(fl)：程序清單#include string.h #include #include #define M 7 #de

18、fine N 5 #define FALSE 0 #define TRUE 1 /*M個進程(jnchng)對N類資源最大資源需求量*/ int MAXMN=9,7,5,5,4,4,11,0,4,4,4,4,6,5,5; /*系統(tǒng)(xtng)可用資源數(shù)*/ int AVAILABLEN=12,7,9; /*M個進程對N類資源最大資源需求量*/ int ALLOCATIONMN=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0; /*M個進程已經(jīng)得到N類資源的資源量 */ int NEEDMN=9,7,5,5,4,4,11,0,4,4,4,4,6,5,5; /*M個進程還需要N類資源的

19、資源量*/ int RequestN=0,0,0; int main() int i=0,j=0; char flag=Y; void showdata(); void changdata(int); void rstordata(int); int chkerr(int); showdata(); while(flag=Y|flag=y) i=-1; while(i=M) printf(請您輸入想要申請資源(zyun)的進程號（從0至); printf(%d,M-1); printf(，請您重新(chngxn)輸入!）:); scanf(%d,&i); if(i=M)printf(不好意思，

20、你所輸入的進程號不存在(cnzi)，請重新輸入!n); printf(請您輸入進程號); printf(%d,i); printf(申請的資源數(shù)n); for (j=0;jNEEDij) printf(進程(jnchng); printf(%d,i); printf(申請的資源(zyun)數(shù)大于進程); printf(%d,i); printf(如果(rgu)還需要); printf(%d,j); printf(類資源的資源量!您所提出的申請的不合理，出現(xiàn)錯誤!請您重新選擇!n); /*printf(您所提出的申請的不合理，出現(xiàn)錯誤!請您重新選擇!n);*/ flag=N; break; el

21、se if(RequestjAVAILABLEj) printf(進程); printf(%d,i); printf(申請的資源數(shù)大于系統(tǒng)可用); printf(%d,j); printf(類資源的資源量!您所提出的申請不合理，出現(xiàn)錯誤!請您重新選擇!n); /*printf(您所提出的申請不合理，出現(xiàn)錯誤!請您重新選擇!n);*/ flag=N; break; if(flag=Y|flag=y) changdata(i); if(chkerr(i) rstordata(i); showdata(); else showdata(); else showdata(); printf(n); p

22、rintf(請問是否繼續(xù)(jx)銀行家算法演示,按Y或y鍵繼續(xù),按N或n鍵退出演示: ); scanf(%c,&flag); void showdata() int i,j; printf(注意！系統(tǒng)(xtng)可用的資源數(shù)為:n); printf( ); for (j=0;jN;j+) printf( 資源(zyun); printf(%d,j); printf(:); printf(%d,AVAILABLEj); /*printf(n);*/ /* coutendl; / cout各進程(jnchng)資源的最大需求量:endlendl; / for (i=0;iM;i+) / / cou

23、t進程(jnchng)i:; / for (j=0;jN;j+)cout 資源(zyun)j: MAXij; / coutendl; */ printf(n); printf(各進程還需要的資源量:n); for (i=0;iM;i+) printf( 進程); printf(%d,i); printf(:); for (j=0;jN;j+) printf(資源); printf(%d,j); printf(:); printf(%d,NEEDij); /*printf(n);*/ printf(n); printf(各進程已經(jīng)得到的資源量: n); for (i=0;iM;i+) print

24、f( 進程(jnchng); printf(%d,i); /*printf(:n);*/ for (j=0;jN;j+) printf(資源(zyun); printf(%d,j); printf(:); printf(%d,ALLOCATIONij); /*printf(n);*/ printf(n); void changdata(int k) int j; for (j=0;jN;j+) AVAILABLEj=AVAILABLEj-Requestj; ALLOCATIONkj=ALLOCATIONkj+Requestj; NEEDkj=NEEDkj-Requestj; ; void rstordata(int k) int j; for (j=0;jN;j+) AVAILABLEj=AVAILABLEj+Requestj; ALLOCATIONkj=ALLOCATIONkj-Requestj; NEEDkj=NEEDkj+Requestj; int chkerr(int s) int WORK,FINISHM,tempM; int i,j,k=0; for(i=0;iM;i+)FINISHi=FALSE; for(j=0;jN;j+) WORK=AVAILABLEj; i=s; whi