操作系統(tǒng)課程設(shè)計(jì)的-模擬銀行家算法-絕對(duì)獨(dú)一無(wú)二

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專(zhuān)心-專(zhuān)注-專(zhuān)業(yè)專(zhuān)心-專(zhuān)注-專(zhuān)業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專(zhuān)心-專(zhuān)注-專(zhuān)業(yè)湖南工業(yè)大學(xué)課 程 設(shè) 計(jì)資 料 袋 計(jì)算機(jī)與通信 學(xué)院（系、部） 2011 2012 學(xué)年第 2 學(xué)期 課程名稱(chēng) 操作系統(tǒng) 指導(dǎo)教師 左新娥 職稱(chēng) 講師 學(xué)生姓名 劉 耀 澳 專(zhuān)業(yè)班級(jí) 計(jì)算機(jī)科學(xué)與技術(shù) 學(xué)號(hào) 題 目 模擬銀行家算法 成 績(jī) 起止日期 2011 年 12月 19 日 2011 年 12月 24 日目 錄 清 單序號(hào)材 料 名 稱(chēng)資料數(shù)量備 注1課程設(shè)計(jì)任務(wù)書(shū)12課程設(shè)計(jì)說(shuō)明書(shū)13課程設(shè)計(jì)圖紙張湖南工業(yè)大學(xué)課程設(shè)計(jì)任務(wù)書(shū)2011 2012 學(xué)年第 2 學(xué)

2、期 計(jì)算機(jī)與通信 學(xué)院（系、部） 計(jì)算機(jī)科學(xué)與技術(shù) 專(zhuān)業(yè) 09-3 班級(jí)課程名稱(chēng)： 操作系統(tǒng) 設(shè)計(jì)題目： 模擬銀行家算法 完成期限：自 2011 年 12 月 19 日至 2011 年 12 月 24 日共 1 周內(nèi)容及任務(wù)一、課程設(shè)計(jì)目的通過(guò)設(shè)計(jì)和調(diào)試銀行家算法通用程序，加深對(duì)死鎖概念和死鎖避免方法的了解。二、課程設(shè)計(jì)內(nèi)容編制銀行家算法程序，并檢測(cè)所給狀態(tài)的系統(tǒng)安全性。進(jìn)度安排起止日期工作內(nèi)容 2011-12-192011-12-20確定銀行家算法所需的數(shù)據(jù)結(jié)構(gòu)和算法分析2011-12-202011-12-21根據(jù)算法畫(huà)出流程圖，然后編碼實(shí)現(xiàn)算法2011-12-222011-12-24 對(duì)程

3、序的調(diào)試、修改、改進(jìn)。編寫(xiě)設(shè)計(jì)說(shuō)明書(shū)主要參考資料1 孟慶昌，牛欣源編著。操作系統(tǒng)（第二版）。電子工業(yè)出版社。2010-10.2 徐虹，何嘉，張鐘澎編著。操作系統(tǒng)實(shí)驗(yàn)指導(dǎo)基于Linux內(nèi)核（第二版）。清華大學(xué)出版社。2009-08.指導(dǎo)教師（簽字）： 年 月 日系（教研室）主任（簽字）： 年 月 日操作系統(tǒng)課程設(shè)計(jì)說(shuō)明書(shū)模擬銀行家算法起止日期： 2011 年 12 月 19 日 至 2011 年 12 月 24日學(xué)生姓名*班級(jí)計(jì)算機(jī) 09-3班學(xué)號(hào)*成績(jī)指導(dǎo)教師(簽字)計(jì)算機(jī)與通信 學(xué)院（部）2011年 12月 24日一、課程設(shè)計(jì)目的通過(guò)設(shè)計(jì)和調(diào)試銀行家算法通用程序，加深對(duì)死鎖概念和死鎖避免方法

4、的了解。二、課程設(shè)計(jì)內(nèi)容編制銀行家算法程序，并檢測(cè)所給狀態(tài)的系統(tǒng)安全性。三、算法的原理 銀行家算法是一種最有代表性的避免死鎖的算法。要解釋銀行家算法，必須先解釋操作系統(tǒng)安全狀態(tài)和不安全狀態(tài)。 安全狀態(tài)：如果存在一個(gè)由系統(tǒng)中所有進(jìn)程構(gòu)成的安全序列P1，Pn，則系統(tǒng)處于安全狀態(tài)。安全狀態(tài)一定是沒(méi)有死鎖發(fā)生。 不安全狀態(tài):不存在一個(gè)安全序列。不安全狀態(tài)不一定導(dǎo)致死鎖。那么什么是安全序列呢？安全序列：一個(gè)進(jìn)程序列P1，Pn是安全的，如果對(duì)于每一個(gè)進(jìn)程Pi(1in），它以后尚需要的資源量不超過(guò)系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程Pj (j i ) 我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管

5、理的資金，進(jìn)程向操作系統(tǒng)請(qǐng)求分配資源相當(dāng)于用戶向銀行家貸款。操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請(qǐng)資源時(shí)，要測(cè)試該進(jìn)程對(duì)資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請(qǐng)量分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請(qǐng)資源時(shí)，先測(cè)試該進(jìn)程已占用的資源數(shù)與本次申請(qǐng)的資源數(shù)之和是否超過(guò)了該進(jìn)程對(duì)資源的最大需求量。若超過(guò)則拒絕分配資源，若沒(méi)有超過(guò)則再測(cè)試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請(qǐng)量分配資源，否則也要推遲分配。1）對(duì)用銀行家算法來(lái)避免死鎖的方法有較深入的了解，給出系統(tǒng)的初始狀態(tài)，模擬避免死鎖的動(dòng)態(tài)過(guò)程。2）銀行家算法

6、中的數(shù)據(jù)結(jié)構(gòu)（1）可利用資源向量Available。這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類(lèi)可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類(lèi)全部可用資源的數(shù)目，其數(shù)值隨該類(lèi)資源的分配和回收而動(dòng)態(tài)地改變。Availablej=K，則表示系統(tǒng)中現(xiàn)有Rj類(lèi)資源K個(gè)。（2）最大需求矩陣Max。這是一個(gè)n*m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類(lèi)資源的最大需求。如果Maxi，j=K，則表示進(jìn)程i需要Rj類(lèi)資源的最大數(shù)目為K。（3）分配矩陣Allocation。這也是一個(gè)n*m的矩陣，它定義了系統(tǒng)中每一類(lèi)資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocationi，j=K，則表示進(jìn)程

7、i當(dāng)前已分得Rj類(lèi)資源的數(shù)目為K。（4）需求矩陣Need。這也是一個(gè)n*m的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類(lèi)資源數(shù)。如果Needi，j=K，則表示進(jìn)程i還需要Rj類(lèi)資源K個(gè)，方能完成其任務(wù)。上述三個(gè)矩陣存在如下關(guān)系： Needi,j= Maxi，j- Allocationi，j3）銀行家算法設(shè)Requesti 是進(jìn)程Pi的請(qǐng)求向量，如果Requesti，j=K,表示進(jìn)程需要K個(gè)Rj類(lèi)型的資源。當(dāng)Pi發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查：（1）如果Requesti，j= Needi，j，便轉(zhuǎn)向步驟（2）；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過(guò)它所宣布的最大值。（2）如果Requesti，j

8、= Availablej，便轉(zhuǎn)向步驟（3）；否則，表示尚無(wú)足夠資源，Pi須等待。（3）系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Availablej= Availablej- Requesti，j； Allocationi，j= Allocationi，j+ Requesti，j； Needi，j= Needi，j- Requesti，j；（4）系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來(lái)的資源分配狀態(tài)，讓進(jìn)程Pi等待。4）安全性算法系統(tǒng)所執(zhí)行的安全性算法可描述如下：（

9、1）設(shè)置兩個(gè)向量：工作向量Work：它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需要的各類(lèi)資源數(shù)目，它含有m個(gè)元素，在執(zhí)行安全算發(fā)開(kāi)始時(shí)，Work=Available；Finish：它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開(kāi)始時(shí)先做Finishi=false；當(dāng)有足夠資源分配給進(jìn)程時(shí)，再令Finishi=true。（2）從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程：Finishi=false；Needi，j = Workj；若找到，執(zhí)行步驟（3），否則，執(zhí)行步驟（4）。（3）當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行： Workj= Worki+ Allocati

10、oni，j； Finishi=true； go to step 2；（4）如果所有進(jìn)程的Finishi=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。5）銀行家算法程序流程圖如圖3.1所示，銀行家算法所用數(shù)據(jù)可參考ppt上的例子。四、數(shù)據(jù)流程圖圖一、銀行家算法程序流程圖五、源程序代碼 源代碼： #includeusing namespace std;#define F 0#define T 1int main()int n,m,i,j;n=4;m=3; / 定義進(jìn)程總數(shù)和資源類(lèi)總數(shù)。int Available3; /可利用的各類(lèi)的資源數(shù)。int Max43; /每個(gè)進(jìn)程對(duì)每

11、類(lèi)資源的最大需求數(shù)。int Allocation43; /每個(gè)進(jìn)程已分配的各類(lèi)資源個(gè)數(shù)。int Need43; / 每個(gè)進(jìn)程還需要每類(lèi)資源的個(gè)數(shù)。/int Request43; / 每個(gè)進(jìn)程對(duì)每類(lèi)資源的申請(qǐng)的個(gè)數(shù)。int Work3; / 在安全性算法中表示可利用的資源個(gè)數(shù)。int Finish4; /在安全性算法中每個(gè)進(jìn)程的完成情況。/int securityArithmetic(int *Work,int *Available,int *Finish,int Need3,int Allocation3,int n,int m); /安全性算法的子程序的聲明。 /下面是輸入資源分配表的情況。

12、coutinput the Available: endl;for(j=0;jm;j+)coutAvailablejAvailablej; coutendl; /輸入每類(lèi)資源可利用的個(gè)數(shù)。/下面是輸入各類(lèi)資源的已分配的、最大需求的、現(xiàn)在還需要的資源個(gè)數(shù)。coutinput the Allocation ,Max ,Need :endl;for(i=0;in;i+)for(j=0;jm;j+)coutAllocationijAllocationij;coutendl; /輸入i號(hào)進(jìn)程已分配的j類(lèi)資源的個(gè)數(shù)coutMaxijMaxij;coutendl;/輸入i號(hào)進(jìn)程對(duì)j類(lèi)資源的最大需求個(gè)數(shù)。co

13、utNeedijNeedij;coutendl; /輸入i號(hào)進(jìn)程還需要j類(lèi)資源的個(gè)數(shù)。/下面是輸入某個(gè)進(jìn)程對(duì)每類(lèi)資源的申請(qǐng)個(gè)數(shù)。int Request_Num=0;int thedoing;coutRequest_Num; /輸入申請(qǐng)資源的進(jìn)程個(gè)數(shù)。coutendl;while(Request_Num!=0)int security=T; /設(shè)置一個(gè)標(biāo)志變量，用于判斷對(duì)i號(hào)進(jìn)程的/申請(qǐng)預(yù)分配后系統(tǒng)是否是安全的。int b=1; /b也是判斷標(biāo)志變量，用于判斷是否所有進(jìn)程的Finishi=T.couti;thedoing=i; /輸入請(qǐng)求資源的進(jìn)程號(hào)。coutendl輸入請(qǐng)求的各類(lèi)資源數(shù)目：;f

14、or(j=0;jm;j+)cout輸入第jRequestij; /輸入i進(jìn)程對(duì)各類(lèi)資源的申請(qǐng)個(gè)數(shù)。/進(jìn)程 i 的資源預(yù)分配int aa=1; /控制變量aa是用于判斷是否能對(duì)i進(jìn)程的申請(qǐng)進(jìn)行預(yù)分配。for(j=0;jm;j+)if (!(Requestij=Needij & Requestij=Availablej)aa=0;if(aa=1) /如果aa=1,即所申請(qǐng)的所需要的，并且所申請(qǐng)的可利用的。 /就可進(jìn)行預(yù)分配。for(j=0;jm;j+) /下面是進(jìn)行預(yù)分配時(shí)所要改變的相關(guān)變量參數(shù)。 Availablej= Availablej- Requestij; Allocationij= A

15、llocationij+ Requestij; Needij= Needij- Requestij;else /如果不能進(jìn)行預(yù)分配，則退出循環(huán)，結(jié)束程序。 cout”警告：申請(qǐng)資源個(gè)數(shù)大于所需的或可利用的個(gè)數(shù).”;return 0; / 調(diào)用安全性算法，返回一個(gè)控制變量，表明是否存在安全序列，是否有安全狀態(tài). b=securityArithmetic(Work,Available,Finish,Need,Allocation, n,m);/ /如果有安全序列，b=1，則該進(jìn)程的此次請(qǐng)求分配可行。if(b=1)for(i=0;in;i+) Finishi=F; /如果b=1，則表明此次申請(qǐng)安全，

16、并把/Finishi都置為 F .為下一個(gè)進(jìn)程的申請(qǐng)做準(zhǔn)備。else security=F;if(security=T) /判斷當(dāng)前進(jìn)程申請(qǐng)各類(lèi)資源后系統(tǒng)是否安全。cout進(jìn)程thedoing請(qǐng)求資源后：存在安全序列，是可行的。endl;coutendl;else cout進(jìn)程thedoing請(qǐng)求資源后：不存在安全序列，是不可行的。endl; /下面是如果當(dāng)前進(jìn)程申請(qǐng)資源后有死鎖危險(xiǎn)，則撤銷(xiāo)之前的預(yù)分配。Availablej= Availablej+ Requestij; Allocationij= Allocationij- Requestij; Needij= Needij+ Reques

17、tij;Request_Num-; /申請(qǐng)的進(jìn)程數(shù)量減一，進(jìn)行下一個(gè)進(jìn)程的資源預(yù)分配和系統(tǒng)安全性判斷。return 0; /對(duì)每個(gè)申請(qǐng)資源的進(jìn)程進(jìn)行了銀行家算法后，程序結(jié)束。/定義安全性算法子程序int securityArithmetic(int *Work,int *Available,int *Finish,int Need3,int Allocation3,int n,int m) int i,j;for(i=0;in;i+)Finishi=F;for(j=0;jm;j+)Workj=Availablej;/下面的 a、b、c 都是控制標(biāo)志變量。int b=1; int a=1; /標(biāo)

18、志某一進(jìn)程目前還需要的各類(lèi)資源可利用的個(gè)數(shù)。 int c=0; /標(biāo)志Finishc=T 的進(jìn)程號(hào)。int d;for(d=0;dn;d+) /for(i=0;in;i+)/找一個(gè)可執(zhí)行完但還沒(méi)執(zhí)行完的進(jìn)程 c 。a=1; for(j=0;jm;j+)/判斷i 進(jìn)程的所需的所有的資源是否可利用的。 if(Needij=Workj) c=i; else a=0;if(Finishc=F & a=1) /如果所需可用的，且Finish=F，則進(jìn)程 / i 就釋放其占有的資源。 for(j=0;jm;j+) Workj=Workj+Allocationcj; Finishc=T; b=1; for(

19、i=0;in;i+) /如果所有的進(jìn)程都已經(jīng)執(zhí)行完,則b=1,表示執(zhí)行此次/分配是安全的。 if(Finishi=T) ;/是否所有進(jìn)程都能運(yùn)行完成。 else b=0; return b; /返回標(biāo)志目前系統(tǒng)是否安全的標(biāo)志變量 b .六、程序運(yùn)行結(jié)果顯示 （1）、資源分配表情況 資源進(jìn)程AllocationMaxNeedAvailableR0R1R2R0R1R2R0R1R2R0R1R20100322222112151161310222113141033002422420 （2）、運(yùn)行結(jié)果1、輸入可利用的資源數(shù)：Available。然后輸入每個(gè)進(jìn)程的 ：Allocation的資源個(gè)數(shù)。Max的

20、資源個(gè)數(shù)。Need的資源個(gè)數(shù)。2、 當(dāng)把資源分配表的情況輸入完后，再輸入要請(qǐng)求分配資源的進(jìn)程的個(gè)數(shù)，這里我輸入了2，表示有兩個(gè)進(jìn)程請(qǐng)求資源。再輸入請(qǐng)求資源的進(jìn)程號(hào)，然后再輸入請(qǐng)求的各類(lèi)資源的個(gè)數(shù)，但不能超過(guò)Available 中的個(gè)數(shù)。我的輸入是： 1號(hào)進(jìn)程，請(qǐng)求各類(lèi)資源數(shù)為：1、0、2 。照理論是安全的。和運(yùn)行結(jié)果一樣的。然后再輸入：0號(hào)進(jìn)程，請(qǐng)求各類(lèi)資源數(shù)為：0、1、1 。因?yàn)檫@時(shí)Available已經(jīng)變成：0、1、0. 所以0號(hào)進(jìn)程請(qǐng)求后就處于不安全狀態(tài)了。七、總結(jié) 經(jīng)過(guò)幾天的自己動(dòng)手練習(xí)，對(duì)操作系統(tǒng)的掌握又進(jìn)了一步，收獲了很多課堂上和書(shū)上未出現(xiàn)過(guò)的或老師未講到的一些知識(shí)。在完成實(shí)驗(yàn)的過(guò)程中，進(jìn)行了反復(fù)的修改和調(diào)試，這次實(shí)驗(yàn)