編程序模擬銀行家算法

1、武漢理工大學(xué)華夏學(xué)院課程設(shè)計報告書課程名稱： 操作系統(tǒng)原理 題 目： 編程序模擬銀行家算法 系 名： 信息工程系 專業(yè)班級： 軟件1121 姓 名： 鐘偉 學(xué) 號： 10212812120 指導(dǎo)教師: 蘇永紅 2014年 6 月 13 日武漢理工大學(xué)華夏學(xué)院信息工程系課 程 設(shè) 計 任 務(wù) 書課程名稱： 操作系統(tǒng)原理課程設(shè)計 指導(dǎo)教師： 蘇永紅 班級名稱： 軟件1121 開課系、教研室： 軟件與信息安全 一、課程設(shè)計目的與任務(wù)操作系統(tǒng)課程設(shè)計是操作系統(tǒng)原理課程的后續(xù)實踐課程，旨在通過一周的實踐訓(xùn)練，加深學(xué)生對理論課程中操作系統(tǒng)概念，原理和方法的理解，加強學(xué)生綜合運用操作系統(tǒng)原理、linux系統(tǒng)

2、、c語言程序設(shè)計技術(shù)進行實際問題處理的能力，進一步提高學(xué)生進行分析問題和解決問題的能力，包含系統(tǒng)分析、系統(tǒng)設(shè)計、系統(tǒng)實現(xiàn)和系統(tǒng)測試的能力。學(xué)生將在指導(dǎo)老師的指導(dǎo)下，完成從需求分析，系統(tǒng)設(shè)計，編碼到測試的全過程。二、課程設(shè)計的內(nèi)容與基本要求1、課程設(shè)計題目 編程序模擬銀行家算法2、課程設(shè)計內(nèi)容本課程設(shè)計要求在linux操作系統(tǒng)，gcc編譯環(huán)境下開發(fā)。銀行家算法是避免死鎖的一種重要方法，本實驗要求用用c/c+語言在linux操作系統(tǒng)環(huán)境下編寫和調(diào)試一個簡單的銀行家算法程序。加深了解有關(guān)資源申請、避免死鎖等概念，并體會和了解死鎖和避免死鎖的具體實施方法。思想：將一定數(shù)量的資金供多個用戶周轉(zhuǎn)使用，當(dāng)用

3、戶對資金的最大申請量不超過現(xiàn)存資金時可接納一個新客戶，客戶可以分期借款，但借款總數(shù)不能超過最大的申請量。銀行家對客戶的借款可以推遲支付，但是能夠使客戶在有限的時間內(nèi)得到借款，客戶得到所有的借款后能在有限的時間內(nèi)歸還。用銀行家算法分配資源時，測試進程對資源的最大需求量，若現(xiàn)存資源能滿足最大需求就滿足當(dāng)前進程的申請，否則推遲分配，這樣能夠保證至少有一個進程可以得到所需的全部資源而執(zhí)行到結(jié)束，然后歸還資源，若os能保證所有進程在有限的時間內(nèi)得到所需資源則稱系統(tǒng)處于安全狀態(tài)。 3、設(shè)計報告撰寫格式要求：1設(shè)計題目與要求 2 設(shè)計思想 3系統(tǒng)結(jié)構(gòu) 4 數(shù)據(jù)結(jié)構(gòu)的說明和模塊的算法流程圖 5 使用說明書（即

4、用戶手冊）：內(nèi)容包含如何登錄、退出、讀、寫等操作說明6 運行結(jié)果和結(jié)果分析（其中包括實驗的檢查結(jié)果、程序的運行情況）7 自我評價與總結(jié) 8 附錄：程序清單，注意加注釋（包括關(guān)鍵字、方法、變量等），在每個模塊前加注釋；三、課程設(shè)計步驟及時間進度和場地安排本課程設(shè)計將安排在第17周, 教育技術(shù)中心。具體安排如下：第一天，下發(fā)任務(wù)書，學(xué)生查閱資料第二天，系統(tǒng)設(shè)計和原型開發(fā)第三，四天 系統(tǒng)功能實現(xiàn)第五天，系統(tǒng)調(diào)試 測試 打包和驗收周次星期一星期二星期三星期四星期五第17周第1-8節(jié)第1-8節(jié)第1-8節(jié)第1-8節(jié)第1-8節(jié)地點現(xiàn)教241現(xiàn)教241現(xiàn)教241現(xiàn)教241現(xiàn)教241四、課程設(shè)計考核及評分標(biāo)準課

5、程設(shè)計考核將綜合考慮學(xué)生考勤和參與度，系統(tǒng)設(shè)計方案正確性，系統(tǒng)設(shè)計和開發(fā)效果以及課程設(shè)計報告書的質(zhì)量。具體評分標(biāo)準如下：設(shè)置六個評分點（1）設(shè)計方案正確，具有可行性、創(chuàng)新性； 25分（2）系統(tǒng)開發(fā)效果較好； 25分（3）態(tài)度認真、刻苦鉆研、遵守紀律； 10分（4）設(shè)計報告規(guī)范、課程設(shè)計報告質(zhì)量高、參考文獻充分 20分（5）課程設(shè)計答辯概念清晰，內(nèi)容正確 10分（6）課程設(shè)計期間的課堂考勤、答疑與統(tǒng)籌考慮。 10分 按上述六項分別記分后求和，總分按五級記分法記載最后成績。優(yōu)秀（10090分），良好（8089分），中等（7079分），及格（6069分），不及格（059分）目錄1設(shè)計題目與要求51.

6、1設(shè)計題目51.2實驗要求52 設(shè)計思想54數(shù)據(jù)結(jié)構(gòu)的說明和模塊的算法流程圖64.1死鎖避免:64.1.1破壞“不可剝奪”條件64.1.2破壞“請求和保持”條件64.1.3破壞“循環(huán)等待”條件64.2安全狀態(tài)與不安全狀態(tài)64.3數(shù)據(jù)結(jié)構(gòu)：64.4安全性檢查算法74.5程序流程圖85 使用說明書96運行結(jié)果和結(jié)果分析96.1輸入96.2輸出106.3結(jié)果分析117自我評價與總結(jié)118附錄：12源程序清單121設(shè)計題目與要求1.1設(shè)計題目 編程序模擬銀行家算法1.2實驗要求 本實驗要求用用c/c+語言在linux操作系統(tǒng)環(huán)境下編寫和調(diào)試一個簡單的銀行家算法程序。加深了解有關(guān)資源申請、避免死鎖等概念

7、，并體會和了解死鎖和避免死鎖的具體實施方法。2 設(shè)計思想將一定數(shù)量的資金供多個用戶周轉(zhuǎn)使用，當(dāng)用戶對資金的最大申請量不現(xiàn)存資金時可接納一個新客戶，客戶可以分期借款，但借款總數(shù)不能超過最大的申請量。銀行家對客戶的借款可以推遲支付，但是能夠使客戶在有限的時間內(nèi)得到借款，客戶得到所有的借款后能在有限的時間內(nèi)歸還。用銀行家算法分配資源時，測試進程對資源的最大需求量，若現(xiàn)存資源能滿足最大需求就滿足當(dāng)前進程的申請，否則推遲分配，這樣能夠保證至少有一個進程可以得到所需的全部資源而執(zhí)行到結(jié)束，然后歸還資源，若os能保證所有進程在有限的時間內(nèi)得到所需資源則稱系統(tǒng)處于安全狀態(tài)。3實驗環(huán)境系統(tǒng)平臺：linux開發(fā)語

8、言：c 開發(fā)工具：pc機一臺4數(shù)據(jù)結(jié)構(gòu)的說明和模塊的算法流程圖4.1死鎖避免: 定義:：系統(tǒng)設(shè)計時確定資源分配算法，保證不發(fā)生死鎖。具體的做法是破壞產(chǎn)生死鎖的四個必要條件之一 4.1.1破壞“不可剝奪”條件 在允許進程動態(tài)申請資源前提下規(guī)定，一個進程在申請新的資源不能立即 得到滿足而變?yōu)榈却隣顟B(tài)之前，必須釋放已占有的全部資源，若需要再重新申請 4.1.2破壞“請求和保持”條件 要求每個進程在運行前必須一次性申請它所要求的所有資源，且僅當(dāng)該進 程所要資源均可滿足時才給予一次性分配 4.1.3破壞“循環(huán)等待”條件 采用資源有序分配法： 把系統(tǒng)中所有資源編號，進程在申請資源時必須嚴格按資源編號的遞增

9、次 、序進行，否則操作系統(tǒng)不予分配。4.2安全狀態(tài)與不安全狀態(tài) 安全狀態(tài)： 如果存在一個由系統(tǒng)中所有進程構(gòu)成的安全序列p1，pn，則系統(tǒng)處于安全狀態(tài)。一個進程序列p1，pn是安全的，如果對于每一個進程pi(1in），它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與所有進程pj (j i )當(dāng)前占有資源量之和，系統(tǒng)處于安全狀態(tài) (安全狀態(tài)一定是沒有死鎖發(fā)生的) 不安全狀態(tài):不存在一個安全序列，不安全狀態(tài)一定導(dǎo)致死鎖。4.3數(shù)據(jù)結(jié)構(gòu)：（1）可利用資源向量available是個含有m個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目。如果availablej=k，則表示系統(tǒng)中現(xiàn)有rj類資源k個。（

10、2）最大需求矩陣max這是一個nm的矩陣，它定義了系統(tǒng)中n個進程中的每一個進程對m類資源的最大需求。如果maxi,j=k，則表示進程i需要rj類資源的最大數(shù)目為k。（3）分配矩陣allocation這也是一個nm的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進程的資源數(shù)。如果allocationi,j=k，則表示進程i當(dāng)前已分得rj類資源的 數(shù)目為k。（4）需求矩陣need。這也是一個nm的矩陣，用以表示每一個進程尚需的各類資源數(shù)。如果needi,j=k，則表示進程i還需要rj類資源k個，方能完成其任務(wù)。needi,j=maxi,j-allocationi,j4.4安全性檢查算法4.4.1設(shè)

11、置兩個工作向量work=available;finish4.4.2從進程集合中找到一個滿足下述條件的進程，finish=false;need=work;如找到，執(zhí)行(3)；否則，執(zhí)行(4)4.4.3設(shè)進程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。work+=allocation;finish=true;goto 24.4.4如所有的進程finish= true，則表示安全；否則系統(tǒng)不安全。4.5程序流程圖5 使用說明書 5.1首先在終端中使用vi編輯器建立c的源文件5.2然后使用gcc編輯器編譯生成可執(zhí)行文件5.3使用命令./當(dāng)前名字，來執(zhí)行6運行結(jié)果和結(jié)果分析 6.1輸入6.2輸出6.3

12、結(jié)果分析這次的設(shè)計數(shù)據(jù)是通過一道實際的題目來體現(xiàn)銀行家算法避免死鎖的問題，先用銀行家算法給其中一個進程分配資源，看它所請求的資源是否大于它的需求量，才和系統(tǒng)所能給的資源相比較.讓進程形成一個安全隊列,看系統(tǒng)是否安全.再利用安全性算法檢查此時系統(tǒng)是否安全。 7自我評價與總結(jié)在本次實驗中我們使用了liunx變成環(huán)境，讓我們更加系統(tǒng)深入的了解了liunx，gcc編程思路和思想，同時讓我更加深刻的了解銀行家算法,了解死鎖的避免和預(yù)防，對操作系統(tǒng)對資源的申請和釋放有了更加深刻的理解，同時在編程過程中積極的向老師同學(xué)請教問題與他們一起探討在系統(tǒng)中存在的問題和漏洞。深入了解了銀行家算法的資源申請和資源分配的

13、過程及原則。保證系統(tǒng)處于安全狀態(tài)。 經(jīng)過本周的課程設(shè)計，我對操作系統(tǒng)的掌握又進了一步，收獲了很多知識。 ，終于我了由于對 c 語言不夠熟練，在試驗過程中，進行了反復(fù)的修改和調(diào)試，解銀行家算法的基本原理，并且在此次的課程設(shè)計中我又復(fù)習(xí)了一下 c 語言，加深了對它的了解，而且在課程設(shè)計的過程中我們同樣學(xué)會了如何簡單的操作與使用 linux 操作系統(tǒng)，學(xué)習(xí)到了許多 linux 操作系統(tǒng)中常用的一些密令。 這次的設(shè)計數(shù)據(jù)是通過一道實際的題目來體現(xiàn)銀行家算法避免死鎖的問題，先用銀行家算法給其中一個進程分配資源，看它所請求的資源是否大于它的需求量，才和系統(tǒng)所能給的資源相比較.讓進程形成一個安全隊列看系統(tǒng)是

14、否安全.再利用安全性算法檢查此時系統(tǒng)是否安全。 操作系統(tǒng)的基本特征是并發(fā)與共享。系統(tǒng)允許多個進程并發(fā)執(zhí)行，并且共享系統(tǒng)的軟、硬件資源。為了最大限度的利用計算機系統(tǒng)的資源，操作系統(tǒng)應(yīng)采用動態(tài)分配的策略，但是這樣就容易因資源不足，分配不當(dāng)而引起“死鎖”。而我本次課程設(shè)計就是得用銀行家算法來避免“死鎖”。銀行家算法就是一個分配資源的過程，使分配的序列不會產(chǎn)生死鎖。此算法的中心思想是：按該法分配資源時，每次分配后總存在著一個進程，如果讓它單獨運行下去，必然可以獲得它所需要的全部資源，也就是說，它能結(jié)束，而它結(jié)束后可以歸還這類資源以滿足其他申請者的需要。 通過這次實驗，我體會到銀行家算法的重要性，銀行家

15、算法是避免死鎖的主要方法，其思路在很多方面都非常值得我來學(xué)習(xí)借鑒。通過這次實踐，我知道，要做一個課程設(shè)計，如果知識面只是停留在書本上，是不可能把課成設(shè)計完全地做好。在課程設(shè)計中，很多c語言的知識都忘了，每次的課程設(shè)計中都能將以前的知識順便再復(fù)習(xí)一遍，課程設(shè)計是給了我們一個機會去動手和主動復(fù)習(xí)，同時也是提醒我們應(yīng)該注重平時的積累。從課程設(shè)計以后還是要多多的動手，在實踐中體會理論知識，才能吸取經(jīng)驗教訓(xùn)。經(jīng)過這次實驗訓(xùn)練，我對這門課程有了更好的了解。8附錄：源程序清單#include#include#include#define false 0#define true 1int max100100=

16、0;/各進程所需各類資源的最大需求int avaliable100=0;/系統(tǒng)可用資源char name100=0;/資源的名稱int allocation100100=0;/系統(tǒng)已分配資源int need100100=0;/還需要資源int request100=0;/請求資源向量int temp100=0;/存放安全序列int work100=0;/存放系統(tǒng)可提供資源int p100=0;int q100100=0;int z100100=0;int m=100;/作業(yè)的最大數(shù)為100int n=100;/資源的最大數(shù)為100int gg=1;void showdata()/顯示資源矩陣

17、int i,j; coutendl此時刻的資源分配情況為：endl; cout max allocation need avaliableendl; cout進程名 ; for(j=0;j4;j+) for(i=0;in;i+) coutnamei ; cout ; coutendl; for(i=0;im;i+) cout i ; for(j=0;jn;j+) coutmaxij ; cout ; for(j=0;jn;j+) coutallocationij ; cout ; for(j=0;jn;j+) coutneedij ;if(i=0) cout ; for (j=0;jn;j+)

18、 coutavaliablej ;/輸出分配資源 coutendl; int changdata(int i)/進行資源分配 int j;for (j=0;jm;j+) /pj=avaliablej; avaliablej=avaliablej-requestj; /qij=allocationij; allocationij=allocationij+requestj; /zij=needij; needij=needij-requestj;return 1;int safe()/安全性算法int i,d,k=0,m,h,s,apply,finish100=0;int j;int flag=

19、0;for(i=0;in;i+)worki=avaliablei;coutendl 安全性檢查 endl;cout work need allocation work+allocation finishendl;cout進程名 ;for(h=0;h4;h+) for(s=0;sn;s+) coutnames ; cout ; coutendl;for(i=0;im;i+) apply=0; for(j=0;jn;j+) if (finishi=false&needij=workj) apply+; if(apply=n) cout i ; for(d=0;dn;d+) coutworkd ;

20、cout ;for(d=0;dn;d+)coutneedid ; cout ;for(d=0;dn;d+)coutallocationid ; cout ; for(m=0;mn;m+) workm=workm+allocationim; coutworkm ; /變分配數(shù) finishi=true; tempk=i;cout ; couttrue ; coutendl;i=-1; k+; flag+; for(i=0;im;i+) if(finishi=false) for(j=0;jn;j+)avaliablej=avaliablej+requestj; allocationij=allo

21、cationij-requestj; needij=needij+requestj; coutendl系統(tǒng)進入不安全狀態(tài)！此時系統(tǒng)不分配資源！endl;/不成功系統(tǒng)不安全 return 0; coutendl此時系統(tǒng)是安全的!endl;/如果安全，輸出成功 cout安全序列為:;for(i=0;im;i+)/輸出運行進程數(shù)組 couttempi; if(im-1) cout; coutendl; return 0;void share()/利用銀行家算法對申請資源對進行判定char ch;int i=0,j=0;ch=y;coutendl請輸入要求分配的資源進程號(0-m-1i;/輸入須申請的

22、資源號coutendl請輸入進程 i 申請的資源:endl;for(j=0;jn;j+) coutnamejrequestj;/輸入需要申請的資源 for (j=0;jneedij)/判斷申請是否大于需求，若大于則出錯 coutendl進程 i申請的資源大于它需要的資源; cout 分配不合理，不予分配！avaliablej)/判斷申請是否大于當(dāng)前資源，若大于則 /出錯 coutendl進程i申請的資源大于系統(tǒng)現(xiàn)在可利用的資源; cout 分配出錯，不予分配!endl; ch=n; break; if(ch=y) changdata(i);/根據(jù)進程需求量變換資源 showdata();/根據(jù)進程需求量顯示變換后的資源 safe();/根據(jù)進程需求量進行銀行家算法判斷 int main()/主函數(shù) int t=1,i,j,number,choice,m,n,flag;char ming;cout*銀行家算法的設(shè)計與實現(xiàn)*endl;coutendln;n=n;for(i=0;in;i+) cout資源i+1ming; namei=ming; coutnumber; avaliablei=n