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

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

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

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

4、告及相關(guān)文檔。指 導(dǎo) 教 師 簽 字： 2013年 6月 28日系 主 任 簽 字： 2013年 6月 28日目錄(ml)1設(shè)計(jì)(shj)題目與要求41.1設(shè)計(jì)(shj)題目41.2要求完成的任務(wù)41.3主要任務(wù)41.4提示42設(shè)計(jì)思路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測(cè)試結(jié)果截圖106.1開始界面106.2輸出界面107自我評(píng)價(jià)與總結(jié)148參考文獻(xiàn)159附錄：程序清單16PAGE 151設(shè)計(jì)(shj)題目與要求11設(shè)計(jì)(sh

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

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

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

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

9、ty() /利用(lyng)安全性算法進(jìn)行安全性檢測(cè)public void changdata(int i) /進(jìn)行(jnxng)資源分配 void judge() /利用銀行家算法對(duì)申請(qǐng)資源(zyun)進(jìn)行判定33各模塊間的調(diào)用關(guān)系：主函數(shù)void main()要調(diào)用： printFrame()，print()，Safty()，judge()安全性檢測(cè)函數(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）進(jìn)行初始化輸入的函數(shù)（2）打印輸出的函數(shù)（3）利用安全性算

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

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

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

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

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

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

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

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

18、fine N 5 #define FALSE 0 #define TRUE 1 /*M個(gè)進(jìn)程(jnchng)對(duì)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個(gè)進(jìn)程對(duì)N類資源最大資源需求量*/ int ALLOCATIONMN=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0; /*M個(gè)進(jìn)程已經(jīng)得到N類資源的資源量 */ int NEEDMN=9,7,5,5,4,4,11,0,4,4,4,4,6,5,5; /*M個(gè)進(jìn)程還需要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(請(qǐng)您輸入想要申請(qǐng)資源(zyun)的進(jìn)程號(hào)（從0至); printf(%d,M-1); printf(，請(qǐng)您重新(chngxn)輸入!）:); scanf(%d,&i); if(i=M)printf(不好意思，

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

21、se if(RequestjAVAILABLEj) printf(進(jìn)程); printf(%d,i); printf(申請(qǐng)的資源數(shù)大于系統(tǒng)可用); printf(%d,j); printf(類資源的資源量!您所提出的申請(qǐng)不合理，出現(xiàn)錯(cuò)誤!請(qǐng)您重新選擇!n); /*printf(您所提出的申請(qǐng)不合理，出現(xiàn)錯(cuò)誤!請(qǐng)您重新選擇!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(請(qǐng)問是否繼續(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各進(jìn)程(jnchng)資源的最大需求量:endlendl; / for (i=0;iM;i+) / / cou

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

24、f( 進(jìn)程(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