操作系統(tǒng)課程設(shè)計報告銀行家算法的模擬實現(xiàn)

1、操作系統(tǒng)課程設(shè)計報告題目： 銀行家算法的模擬實現(xiàn) 專業(yè)計算機(jī)科學(xué)與技術(shù)學(xué)生姓名班級計算機(jī)131學(xué)號指導(dǎo)教師完成日期2015.7.10信 息 工 程 學(xué) 院15操作系統(tǒng)課程設(shè)計（2015）目 錄1 概述21.1 設(shè)計目的21.2 設(shè)計要求22 設(shè)計原理22.1 銀行家算法22.2 安全性算法33 概要設(shè)計33.1 功能結(jié)構(gòu)33.2 模塊劃分34 詳細(xì)設(shè)計44.1 初始化模塊設(shè)計44.2 銀行家算法模塊設(shè)計44.3 安全性檢查模塊設(shè)計55 測試與分析65.1 測試方案65.2 測試結(jié)果65.3 結(jié)果分析76 設(shè)計小結(jié)77 參考文獻(xiàn)8附錄 源程序代碼9題目：銀行家算法的模擬實現(xiàn)1 概述1.1 設(shè)計目

2、的a).進(jìn)一步了解進(jìn)程的并發(fā)執(zhí)行。b).加強(qiáng)對進(jìn)程死鎖的理解。c).是用銀行家算法完成死鎖檢測。1.2 設(shè)計要求a).初始狀態(tài)沒有進(jìn)程啟動；b).計算每次進(jìn)程申請是否分配，如：計算出預(yù)分配后的狀態(tài)情況（安全狀態(tài)、不安全狀態(tài)），如果是安全狀態(tài)，輸出安全序列；c).每次進(jìn)程申請被允許后，輸出資源分配矩陣a和可用資源向量v；d).每次申請情況應(yīng)可單步查看，如：輸入一個空格，繼續(xù)下個申請。2 設(shè)計原理2.1 銀行家算法設(shè)requesti是進(jìn)程pi的請求向量，如果requestij=k，表示進(jìn)程pi需要k個ri類型的資源。當(dāng)pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查：a)如果requestij= nee

3、di,j，便轉(zhuǎn)向步驟b)；否則認(rèn)為出錯，因為它所需的資源數(shù)已經(jīng)超過了它所宣布的最大值。b)如果requestij= availablej，便轉(zhuǎn)向步驟c)；否則表示尚無足夠資源，pi需等待。c)系統(tǒng)試探著把資源分配給進(jìn)程pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值。availablej=available-requestij;allocationi,j=allocationi,j+requestij;needi,j=needi,j-requestj; d)系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來資源

4、的分配狀態(tài)，讓進(jìn)程pi等待。2.2 安全性算法系統(tǒng)所執(zhí)行的安全性算法可描述如下：a)設(shè)置兩個向量：一個是工作向量work；它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運行所需要的各類資源的數(shù)目，它含有m個元素，在執(zhí)行安全性算法開始時，work=availalbe；另一個是 finish：它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運行完成。開始時先做finishi=false；當(dāng)有足夠資源分配給進(jìn)程時，再令finishi=rue；b)從進(jìn)程集合中找到一個能滿足下述條件的進(jìn)程：一是finishi=false；二是 needi,j=workj；若找到，執(zhí)行步驟c)，否則，執(zhí)行步驟d)；c)當(dāng)進(jìn)程pi獲得資源后，可順利

5、執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：workj=workj+allocationi,j；finishi=true；go to step b)；d)如果所有進(jìn)程的finishi=true都滿足，則表示系統(tǒng)處于安全狀態(tài)，否則系統(tǒng)處于不安全狀態(tài)。3 概要設(shè)計3.1 功能結(jié)構(gòu) 銀行家算法功能結(jié)構(gòu)圖如圖3-1所示： 圖3-13.2 模塊劃分 a)初始化 b)銀行家算法 c)安全性檢查4 詳細(xì)設(shè)計4.1 初始化模塊設(shè)計由用戶輸入數(shù)據(jù)，分別對運行的進(jìn)程數(shù)、總的資源種類數(shù)、總資源數(shù)、各進(jìn)程所需要的最大資源數(shù)量（max），已分配的資源數(shù)量（allowcation），可利用的資源數(shù)量（availab

6、le）賦值。如圖5-1所示，代碼如下。 int i,j,p=0,q=0;char c;int requestm,allocation1mm,need1mm,available1m;printf(*n);printf(* 銀行家算法的設(shè)計與實現(xiàn) *n); printf(*n);printf(請輸入進(jìn)程總數(shù):n);scanf(%d,&no1);printf(請輸入資源種類數(shù):n);scanf(%d,&no2); printf(請輸入max矩陣:n);for(i=0;ino1;i+)for(j=0;jno2;j+)scanf(%d,&maxij); /輸入已知進(jìn)程最大資源需求量printf(請輸入a

7、llocation矩陣:n);for(i=0;ino1;i+)for(j=0;jno2;j+)scanf(%d,&allocationij); /輸入已知的進(jìn)程已分配的資源數(shù) for(i=0;ino1;i+)for(j=0;jno2;j+)needij=maxij-allocationij; /根據(jù)輸入的兩個數(shù)組計算出need矩陣的值 printf(請輸入available矩陣n);for(i=0;ino2;i+)scanf(%d,&availablei); /輸入已知的可用資源數(shù)4.2 銀行家算法模塊設(shè)計設(shè)requesti是進(jìn)程pi的請求向量，如果requestij=k，表示進(jìn)程pi需要k個

8、ri類型的資源。當(dāng)pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查：a)如果requestij= needi,j，便轉(zhuǎn)向步驟b)；否則認(rèn)為出錯，因為它所需的資源數(shù)已經(jīng)超過了它所宣布的最大值。b)如果requestij= availablej，便轉(zhuǎn)向步驟c)；否則表示尚無足夠資源，pi需等待。c)系統(tǒng)試探著把資源分配給進(jìn)程pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值。availablej=available-requestij;allocationi,j=allocationi,j+requestij;needi,j=needi,j-requestj;d)系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀

9、態(tài)。若安全，才正式將資源分配給進(jìn)程pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來資源的分配狀態(tài)，讓進(jìn)程pi等待。如圖5-3,5-4,5-5,5-6所示，代碼如下。 q=0; p=0; printf(n請輸入請求資源的進(jìn)程號(04)：n); for(j=0;j=no1)printf(輸入錯誤，請重新輸入：n);continue; else break; printf(n請輸入該進(jìn)程所請求的資源數(shù)requestj:n); for(j=0;jno2;j+)scanf(%d,&requestj); for(j=0;jneedij) p=1; /判斷請求是否超過該進(jìn)程所需要的資源數(shù) if(p

10、)printf(請求資源超過該進(jìn)程資源需求量，請求失??！n); else for(j=0;javailablej) q=1; /判斷請求是否超過可用資源數(shù)if(q) printf(沒有做夠的資源分配，請求失??！n);else /請求滿足條件for(j=0;jno2;j+) available1j=availablej; allocation1ij=allocationij;need1ij=needij; /保存原已分配的資源數(shù)，仍需要的資源數(shù)和可用的資源數(shù)availablej=availablej-requestj; allocationij+=requestj;needij=needij-r

11、equestj; /系統(tǒng)嘗試把資源分配給請求的進(jìn)程print();check(); /檢測分配后的安全性if(r=0) /如果分配后系統(tǒng)不安全for(j=0;jno2;j+)availablej=available1j; allocationij=allocation1ij;needij=need1ij; /還原已分配的資源數(shù)，仍需要的資源數(shù)和可用的資源數(shù)printf(返回分配前資源數(shù)n);print();4.3 安全性檢查模塊設(shè)計系統(tǒng)所執(zhí)行的安全性算法可描述如下：a)設(shè)置兩個向量：一個是工作向量work；它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運行所需要的各類資源的數(shù)目，它含有m個元素，在執(zhí)行安全性算法開

12、始時，work=availalbe；另一個是 finish：它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運行完成。開始時先做finishi=false；當(dāng)有足夠資源分配給進(jìn)程時，再令finishi=true；b)從進(jìn)程集合中找到一個能滿足下述條件的進(jìn)程：一是finishi=false；二是 needi,j=workj；若找到，執(zhí)行步驟c)，否則，執(zhí)行步驟d)；c)當(dāng)進(jìn)程pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：workj=workj+allocationi,j；finishi=true；go to step b)；d)如果所有進(jìn)程的finishi=true都滿足，則

13、表示系統(tǒng)處于安全狀態(tài)，否則系統(tǒng)處于不安全狀態(tài)。void check() /安全算法函數(shù)int k,f,v=0,i,j;int workm,am;bool finishm;r=1;for(i=0;ino1;i+)finishi=false; / 初始化進(jìn)程均沒得到足夠資源數(shù)并完成for(i=0;ino2;i+) worki=availablei;/worki表示可提供進(jìn)程繼續(xù)運行的各類資源數(shù)k=no1;dofor(i=0;ino1;i+)if(finishi=false)f=1;for(j=0;jworkj)f=0;if(f=1) /找到還沒有完成且需求數(shù)小于可提供進(jìn)程繼續(xù)運行的資源數(shù)的進(jìn)程fi

14、nishi=true;av+=i; /記錄安全序列號for(j=0;j0);f=1;for(i=0;ino1;i+) /判斷是否所有的進(jìn)程都完成if(finishi=false) f=0;break;if(f=0) /若有進(jìn)程沒完成，則為不安全狀態(tài)printf(系統(tǒng)處在不安全狀態(tài)！);r=0;elseprintf(n系統(tǒng)當(dāng)前為安全狀態(tài)，安全序列為：n);for(i=0;ino1;i+)printf(p%d ,ai); /輸出安全序列5 測試與分析5.1 測試方案假定系統(tǒng)中有五個進(jìn)程：p0，p1，p2，p3，p4和三種類型的資源a，b，c，每一種資源的數(shù)量分別為10、5、7，輸入相應(yīng)數(shù)據(jù)。5.2

15、 測試結(jié)果 程序初始化如圖5-1所示： 圖5-1t0時刻的資源分配情況如圖5-2所示： 圖5-2p1請求資源以及分配情況圖如圖5-3所示： 圖5-3p4請求資源以及分配情況圖如圖5-4所示： 圖5-4p0請求資源以及分配情況圖如圖5-5，5-6所示： 圖5-5 圖5-65.3 結(jié)果分析圖示為初始化函數(shù)執(zhí)行的結(jié)果，輸入相應(yīng)數(shù)據(jù)，得到一個安全狀態(tài)，然后對安全狀態(tài)進(jìn)行檢測，如果不是安全狀態(tài)，重新初始化。驗證了各種安全與不安全申請。6 設(shè)計小結(jié) 一周的課程設(shè)計結(jié)束了。在這一周里，我做一個模擬銀行家算法。我覺得在著手設(shè)計前設(shè)計的思路是很重要的。只有思路清晰才能進(jìn)行下一階段的設(shè)計。這樣才能完成整個程序的設(shè)

16、計，完成整個文報告的書寫。 課程設(shè)計這幾天學(xué)到的東西還真不少。以前不清楚的現(xiàn)在都暴露出來了。以前認(rèn)為學(xué)了沒用的東西現(xiàn)在也用到了。這次的課程設(shè)計使我進(jìn)一步了解了調(diào)度與死鎖的問題。以及有關(guān)資源申請的問題、避免死鎖的具體實施方法。深入了解了銀行家算法的資源申請和資源分配的過程及原則。保證系統(tǒng)處于安全狀態(tài)。7 參考文獻(xiàn)1 韓立毛，李先鋒. 計算機(jī)操作系統(tǒng)實踐教程m，南京：南京大學(xué)出版社，2011.10.2 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)m，北京：清華大學(xué)出版社，1997.4.3 張堯?qū)W，史美林. 計算機(jī)操作系統(tǒng)教程m，北京：清華大學(xué)出版社，2000.8.4 孫靜宇. 計算機(jī)操作系統(tǒng)課程設(shè)計指導(dǎo)書m，山西：

17、太原理工出版社，2006.4.附錄 源程序代碼#include #include #include # define m 50 int no1; /進(jìn)程數(shù)int no2; /資源數(shù)int r;int allocationmm,needmm,availablem,maxmm; char name1m,name2m; /定義全局變量void main()void check();void print();int i,j,p=0,q=0;char c;int requestm,allocation1mm,need1mm,available1m;printf(*n);printf(* 銀行家算法的設(shè)計

18、與實現(xiàn) *n); printf(*n);printf(請輸入進(jìn)程總數(shù):n);scanf(%d,&no1);printf(請輸入資源種類數(shù):n);scanf(%d,&no2); printf(請輸入max矩陣:n);for(i=0;ino1;i+)for(j=0;jno2;j+)scanf(%d,&maxij); /輸入已知進(jìn)程最大資源需求量printf(請輸入allocation矩陣:n);for(i=0;ino1;i+)for(j=0;jno2;j+)scanf(%d,&allocationij); /輸入已知的進(jìn)程已分配的資源數(shù) for(i=0;ino1;i+)for(j=0;jno2;j

19、+)needij=maxij-allocationij; /根據(jù)輸入的兩個數(shù)組計算出need矩陣的值 printf(請輸入available矩陣n);for(i=0;ino2;i+)scanf(%d,&availablei); /輸入已知的可用資源數(shù)print(); /輸出已知條件check(); /檢測t0時刻已知條件的安全狀態(tài)if(r=1) /如果安全則執(zhí)行以下代碼do q=0; p=0;printf(n請輸入請求資源的進(jìn)程號(04)：n);for(j=0;j=no1)printf(輸入錯誤，請重新輸入：n); continue; else break;printf(n請輸入該進(jìn)程所請求的

20、資源數(shù)requestj:n);for(j=0;jno2;j+)scanf(%d,&requestj);for(j=0;jneedij) p=1; /判斷請求是否超過該進(jìn)程所需要的資源數(shù)if(p)printf(請求資源超過該進(jìn)程資源需求量，請求失??！n);elsefor(j=0;javailablej) q=1; /判斷請求是否超過可用資源數(shù)if(q) printf(沒有做夠的資源分配，請求失敗！n);else /請求滿足條件for(j=0;jno2;j+) available1j=availablej; allocation1ij=allocationij;need1ij=needij; /保

21、存原已分配的資源數(shù)，仍需要的資源數(shù)和可用的資源數(shù)availablej=availablej-requestj; allocationij+=requestj;needij=needij-requestj; /系統(tǒng)嘗試把資源分配給請求的進(jìn)程print();check(); /檢測分配后的安全性if(r=0) /如果分配后系統(tǒng)不安全for(j=0;jno2;j+)availablej=available1j; allocationij=allocation1ij; needij=need1ij; /還原已分配的資源數(shù)，仍需要的資源數(shù)和可用的資源數(shù)printf(返回分配前資源數(shù)n);print();printf(n你還要繼續(xù)分配嗎？y or n ?n); /判斷是否繼續(xù)進(jìn)行資源分配c=getche();while(c=y|c=y);void check() /安全算法函數(shù)int k,f,v=0,i,j;int workm,am;bool finishm;r=1;for(i=0;ino1;i+)finishi=false; / 初始化進(jìn)程均沒得到足夠資源數(shù)并完成for(i=0;ino2;i+) worki=available