操作系統(tǒng)課程設計的-模擬銀行家算法-絕對獨一無二

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

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

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

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

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

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

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

8、= Availablej，便轉(zhuǎn)向步驟（3）；否則，表示尚無足夠資源，Pi須等待。（3）系統(tǒng)試探著把資源分配給進程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)。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復原來的資源分配狀態(tài)，讓進程Pi等待。4）安全性算法系統(tǒng)所執(zhí)行的安全性算法可描述如下：（

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

10、oni，j； Finishi=true； go to step 2；（4）如果所有進程的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; / 定義進程總數(shù)和資源類總數(shù)。int Available3; /可利用的各類的資源數(shù)。int Max43; /每個進程對每

11、類資源的最大需求數(shù)。int Allocation43; /每個進程已分配的各類資源個數(shù)。int Need43; / 每個進程還需要每類資源的個數(shù)。/int Request43; / 每個進程對每類資源的申請的個數(shù)。int Work3; / 在安全性算法中表示可利用的資源個數(shù)。int Finish4; /在安全性算法中每個進程的完成情況。/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; /輸入每類資源可利用的個數(shù)。/下面是輸入各類資源的已分配的、最大需求的、現(xiàn)在還需要的資源個數(shù)。coutinput the Allocation ,Max ,Need :endl;for(i=0;in;i+)for(j=0;jm;j+)coutAllocationijAllocationij;coutendl; /輸入i號進程已分配的j類資源的個數(shù)coutMaxijMaxij;coutendl;/輸入i號進程對j類資源的最大需求個數(shù)。co

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

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

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

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

17、tij;Request_Num-; /申請的進程數(shù)量減一，進行下一個進程的資源預分配和系統(tǒng)安全性判斷。return 0; /對每個申請資源的進程進行了銀行家算法后，程序結(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 都是控制標志變量。int b=1; int a=1; /標

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

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

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