銀行家算法課程設計

1、信息與計算科學信息與計算科學 操作系統(tǒng)原理操作系統(tǒng)原理 課程設計報告課程設計報告 題目： 銀行家算法程序設計 班級： 姓名： 專業(yè)： 銀行家算法程序設計 第 頁1 銀行家算法程序設計 目錄 1.1.緒論緒論.2 2.2.需求分析需求分析.2 2.1 功能需求.2 2.2 數(shù)據(jù)需求.2 3.3. 總體設計總體設計.2 3.1 功能模塊設.2 3.2 系統(tǒng)設計方案.3 3.3 開發(fā)工具.4 4.4. 詳細設計詳細設計.4 4.1 銀行家算法中的數(shù)據(jù)結構.4 4.2 銀行家算法.5 4.3 安全性算法.6 5.5. 調(diào)試與測試調(diào)試與測試.8 6.6. 結論結論.8 結束語結束語.8 參考文獻參考文獻

2、.9 附錄附錄 1 1用戶手冊用戶手冊.10 附錄附錄 2 2源程序清單源程序清單.12 銀行家算法程序設計 第 頁2 1.1.緒論緒論 20 世紀末，隨著計算機科學的發(fā)展，c 語言的應用越來越廣泛，很多程序都需要使 用 c 語言來編寫。c 語言使用方便快捷，它已經(jīng)成為計算機編程中不可缺少的一部分，而 且它也被用于各個方面。例如：政府部門，銀行，學校等等。 銀行家算法是判斷系統(tǒng)是否安全，并且允許其它進程來申請這里的資源，任何一個 進程來申請資源時，必須先登記該進程對資源的申請要求然后由系統(tǒng)檢查當前資源的狀 況，并用銀行家算法和安全性算法來檢查是否允許分配資源給進程。通過課程設計，加 深我們對利

3、用銀行家算法避免死鎖的理解。在設計中主要的難點是用語言編寫銀行家算 法和安全性算法，使系統(tǒng)資源分配能安全進行，避免系統(tǒng)死鎖。 2.2.需求分析需求分析 2.12.1 功能需求功能需求 1.添加進程的可用資源，最大資源，已分配資源； 2.判斷系統(tǒng)是否安全； 3.申請資源； 4.申請資源后如何分配； 5.進行安全檢查。 2.22.2 數(shù)據(jù)需求數(shù)據(jù)需求 主要數(shù)據(jù)包括：可用資源，最大資源，已分配資源，申請資源數(shù)。 3.3. 總體設計總體設計 3.13.1 功能模塊設功能模塊設 銀行家算法程序設計 第 頁3 對 資 源 進 行 分 配 銀行家算法 判 斷 是 否 安 全 輸 出 安 全 序 列 圖 1

4、功能模塊圖 3.23.2 系統(tǒng)設計方案系統(tǒng)設計方案 在程序中設計五個進程，分別為 p0,p1,p2,p3,p4。共享三類資源。在這個資源管理 系統(tǒng)中對進程的所需最大資源(max)、已分配給當前進程資源(allocation)和系統(tǒng)可用資 源(available)分別進行了初始化了值。進程可動態(tài)地申請資源和釋放資源，系統(tǒng)按各進 程的申請動態(tài)地分配資源。要求程序具有顯示和打印各進程的某一時刻的資源分配表和 安全序列，若分配不安全，則釋放分配的資源，防止使系統(tǒng)進入不安全狀態(tài)。顯示和打 印各進程依次要求申請的資源號以及為某進程分配資源后的有關資源數(shù)據(jù)。程序還可以 實現(xiàn)對系統(tǒng)的修改。如果修改系統(tǒng)可用資源

5、(available)，和進程分配資源。 程序具體的設計是：函數(shù) void showdata()用來顯示資源矩陣，包括系統(tǒng)可用資源數(shù) 目，進程對資源最大需求數(shù)，系統(tǒng)已分配給進程的資源數(shù)，進程還需求資源。通過以上 顯示，很直觀的觀察到資源分配和修改的過程。函數(shù) share()用來利用銀行家算法對某個 進程申請資源對進行判定。函數(shù) int setdata(int k)用來實現(xiàn)資源試探分配。主要執(zhí)行 銀行家算法程序設計 第 頁4 的步驟是 vailablej=availablej-requestj; allocationkj=allocationkj+requestj; needkj=needkj-

6、requestj; 函數(shù) panduan()用來實現(xiàn)安全性算法，對分配后的資源進行計算，若分配資源后，系 統(tǒng)是安全的，則資源完成本次分配。若不安全將本次的試探分配作廢，調(diào)用 backdata() 函數(shù)恢復原來的資源分配狀態(tài)。 3.33.3 開發(fā)工具開發(fā)工具 該程序是采用 c 程序設計完成的，vc6.0 的編譯環(huán)境。 4.4. 詳細設計詳細設計 4.14.1 銀行家算法中的數(shù)據(jù)結構銀行家算法中的數(shù)據(jù)結構 1.可利用資源向量 available 是個含有 3 個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目。如果 availablej=k，則表示系統(tǒng)中現(xiàn)有 rj 類資源 k 個。 2.最大需

7、求矩陣 max 這是一個 53 的矩陣，它定義了系統(tǒng)中 5 個進程中的每一個進程對 3 類資源的最大 需求。如果 maxi,j=k，則表示進程 i 需要 rj 類資源的最大數(shù)目為 k。 3.分配矩陣 allocation 這也是一個 53 的矩陣，它定義了系統(tǒng)中每一類資源當前已分配給每一進程的資源 數(shù)。如果 allocationi,j=k，則表示進程 i 當前已分得 rj 類資源的數(shù)目為 k。 4.需求矩陣 need 這也是一個 53 的矩陣，用以表示每一個進程尚需的各類資源數(shù)。如果 needi,j=k，則表示進程 i 還需要 rj 類資源 k 個，方能完成其任務。 needi,j=maxi,

8、j-allocationi,j 銀行家算法程序設計 第 頁5 初始化函數(shù)showdata()開始 輸入各可用資源 輸入已分配資源 輸入每個進程最多所需資源 初始化函數(shù)showdata()結束 圖 2 賦值 4.24.2 銀行家算法銀行家算法 設 requesti 是進程 pi 的請求向量，如果 requestij=k，表示進程 pi 需要 k 個 rj 類型的資源。當 pi 發(fā)出資源請求后，系統(tǒng)按下述步驟進行檢查： 如果 requestijneedi,j ，便轉向步驟 2；否則認為出錯，因為它所需要的 資源數(shù)已超過它所宣布最大值。 1.如果 requestijavailablej ，便轉向步驟

9、(3)；否則， 表示尚無足夠資 源，pi 須等待。 銀行家算法程序設計 第 頁6 2.系統(tǒng)試探著把資源分配給進程 pi，并修改下面數(shù)據(jù)結構中的數(shù)值： availablej=availablej-requestij; allocationi,j=allocationi,j+requestij; needi,j=needi,j-requestij; 3.系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全， 才正式將資源分配給進程 pi，以完成本次分配；否則， 將本次的試探分配作廢，恢復原 來的資源分配狀態(tài)，讓進程 pi 等待。 4.34.3 安全性算法安全性算法 1.設置兩個向量

10、： 工作向量 work: 它表示系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目，它含有 m 個元素，在執(zhí)行安全算法開始時，work=available; 工作向量 finish: 它表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。開始 時先做 finishi=false; 當有足夠資源分配給進程時， 再令 finishi =true。 2.從進程集合中找到一個能滿足下述條件的進程： finishi=false; needi,jworkj ；若找到，執(zhí)行 (3)，否則，執(zhí)行 (4) 3.當進程 pi 獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應 執(zhí)行： workj=worki+a

11、llocationi,j; finishi=true; go to step 2; 4.如果所有進程的 finishi=true 都滿足， 則表示系統(tǒng)處于安全狀態(tài)；否則， 系統(tǒng)處于不安全狀態(tài) 銀行家算法程序設計 第 頁7 開始 初始化showdata() 判斷 needijworkj？ tempi=truetempi=false 是 否 workj=workj+allocatio nij; 5個進程是否 判斷完畢？ 否 輸出安全序列 顯示分配 結束 是 不安全 圖 3 安全性判斷 銀行家算法程序設計 第 頁8 5.5. 調(diào)試調(diào)試與測試與測試 1.在執(zhí)行程序時，有時分配空間能夠造成死鎖也會分配資

12、源。通過細心地查找發(fā)現(xiàn) 了其中的邏輯錯誤，并加以改正。 2.在使用循環(huán)語句：while 時由于循環(huán)條件的值沒有改變，所以形成了死循環(huán)。通過 耐心的檢查發(fā)現(xiàn)了這一錯誤，然后將其改正。 3.在執(zhí)行程序時，有時分配資源數(shù)大于總資源數(shù)時仍能分配。通過調(diào)試找到其中的錯 誤并改正。 4.在使用選擇語句 if 時，經(jīng)常出現(xiàn)邏輯錯誤。通過老師的指導，改正了錯誤。 6.6. 結論結論 這次操作系統(tǒng)實驗基本上已經(jīng)達到了預期的目的：能夠實現(xiàn)銀行家算法。雖然程序 已經(jīng)可以使用了，但是它還是有一些需要改進的地方。例如：不能同時對 2 個進程進行 分配，不能自行輸入進程數(shù)量和進程種類。 實驗主要是銀行家算法部分： 1.如

13、果 request=need,便轉向步驟 2；否則認為出錯，因為它所需要的資源數(shù)已超 過它所宣布的最大值。 2.如果 request=available,便轉向步驟 3；否則，表示尚無足夠資源，需要等待。 3.系統(tǒng)試探分配請求的資源進程。 4.系統(tǒng)執(zhí)行安全性算法。 結束語結束語 近兩周的操作系統(tǒng)實驗結束了，從開始選擇題目到作品的完成，再到設計報告的完 成，每一步對我來說都是新的嘗試與挑戰(zhàn)，在老師的細心指導和嚴格要求下我順利的完 成的任務，做出了理想的程序。雖然這是我第三次做課設，但是我對操作系統(tǒng)的實驗還 是不了解。通過老師的耐心指導我的 c 語言水平有所提高，并且完全明白了銀行家算法。 雖然課

14、程設計占用了我大量的時間，但是卻讓我復習了一下過去所學到的知識，我認為 銀行家算法程序設計 第 頁9 還是值得的。 在做這次課程設計過程中不但使我學到了很多 c 語言方面的知識，而且我也領悟到 了一些真理。我感到不論做什么事只有真正用心去做，才能克服種種困難，其實有些時 候困難本身并不可怕，真正可怕的是面對困難我們?nèi)鄙俚臎Q心和信心。光學不做是沒有 意義的，只有實踐才能學好，要想學好一門科目就要經(jīng)常做一些練習。希望這次的經(jīng)歷 能讓我在今后的學習. 工作和生活中不斷成長與進步。 參考文獻參考文獻 1譚浩強.c 程序設計（第三版）. 北京：清華大學版社，2005 2湯子灜.哲鳳屏. 湯小丹.計算機操

15、作系統(tǒng)（第三版）. 西安：電子科技大學出版社，2007 銀行家算法程序設計 第 頁10 附錄附錄 1 1用戶手冊用戶手冊 1.輸入可利用資源： 2.輸入需要申請資源的進程號：系統(tǒng)不安全 銀行家算法程序設計 第 頁11 3.輸入需要申請資源的進程號：系統(tǒng)安全并輸出安全序列 4.輸入申請資源錯誤 銀行家算法程序設計 第 頁12 附錄附錄 2 2源程序清單源程序清單 #include int available3,allocation53,max100100;/已有資源量 int need100100,work50,finish5,work53;/需求 int request3=0,0,0; int

16、 i,j,n,m,l=0,flag=0,temp5=0,1,2,3,4; void showdata() int i,j; for(i=1;i5;i+) for(j=0;j3;j+) worktemp0j=availablej; worktempij=worktempi-1j+allocationtempi-1j; cout 系統(tǒng)可用的資源數(shù)為:endlendl; cout 資源: a: available0; cout b: available1; cout c: available2; coutendlendl; cout work need allocation work+allocat

17、ionendl; cout資源 a b c a b c a b c a b cendl; for (i=0;i5;i+) cout進程 ptempi:; for (j=0;j3;j+)cout worktempij; coutt; for (j=0;j3;j+)cout needtempij; coutt; for (j=0;j3;j+)cout allocationtempij; coutt; for (j=0;j3;j+)cout worktempij+allocationtempij; coutendl; cout- -endlendl; void setdata(int k) int

18、j; 銀行家算法程序設計 第 頁13 for (j=0;j3;j+) availablej=availablej-requestj; allocationkj=allocationkj+requestj; needkj=needkj-requestj; void backdata(int k) int j; for (j=0;j3;j+) availablej=availablej+requestj; allocationkj=allocationkj-requestj; needkj=needkj+requestj; int panduan(int t) int h=0; int i=t;

19、while(i5) flag=0; if (finishi=0) for (j=0; j=needij) flag=flag+1; if(flag=m) finishi=1; for (j=0; jm;j+) workj=workj+allocationij; l=l+1; temph=i; h+; i=0; 銀行家算法程序設計 第 頁14 elsei+; return l; void main() int k=0,r=0; cout輸入各種資源可利用的數(shù)量 available3: endl; for (j=0; javailablej; workj=availablej; coutn 請輸入各進程當前已分配的資源數(shù)量 allocation53: endl; coutn 請嚴格按照(53)的距陣輸入:endl; for (i=0; i5; i+) for (j=0; jallocationij; finishi=0; c