1、操作系統課程設計報告題目： 銀行家算法的模擬實現 專業計算機科學與技術學生姓名姜雯班級計算機131學號1310704112指導教師韓 立 毛完成日期2015.7.10信 息 工 程 學 院目 錄1 概述21.1 設計目的21.2 設計內容21.3 設計要求22 設計原理22.1銀行家算法中的數據結構22.2 銀行家算法應用33 設計思路44 程序運行調試結果54.1程序初始化54.2檢測系統資源分配是否安全結果65 設計小結86 參考文獻8附錄 源程序代碼9題目：銀行家算法的模擬實現1 概述1.1 設計目的 1.進一步了解進程的并發執行。2.加強對進程死鎖的理解。3.是用銀行家算法完成死鎖檢測

2、。1.2 設計內容給出進程需求矩陣C、資源向量R以及一個進程的申請序列。使用進程啟動拒絕和資源分配拒絕（銀行家算法）模擬該進程組的執行情況。1.3 設計要求1.初始狀態沒有進程啟動；2.計算每次進程申請是否分配，如：計算出預分配后的狀態情況（安全狀態、不安全狀態），如果是安全狀態，輸出安全序列；3.每次進程申請被允許后，輸出資源分配矩陣A和可用資源向量V；4.每次申請情況應可單步查看，如：輸入一個空格，繼續下個申請。2 設計原理2.1 銀行家算法中的數據結構(1)、可利用資源向量Available，這是一個含有m個元素的數組，其中的每個元素代表一類可利用資源的數目， 其初始值是系統中所配置的該

3、類全部資源的數目，其數值隨該類資源的分配和回收而動態改變。如果Availablej=K，則表示系統中現有Rj類資源K個。（2）、最大需求矩陣Max，這是一個n*m的矩陣，它定義了系統中n個進程中的每一個進程對m類資源的最大需求。如果Maxi,j=K，則表示進程i需要Rj類資源的最大數目為K。（3）、分配矩陣Allocation。這也是一個n*m的矩陣，它定義了系統中每一類資源當前已分配給每一進程的資源數。如果Allocationi,j=K，則表示進程i當前已經分得Rj類資源的數目為K。（4）、需求矩陣Need。這也是一個n*m的矩陣，用以表示每個進程尚需要的各類資源數。如果Needi,j=K，

4、則表示進程i還需要Rj類資源K個，方能完成其任務。上述三個矩陣間存在以下關系：Needi,j=Maxi,j-Allocationi,j2.2 銀行家算法應用模擬實現Dijkstra的銀行家算法以避免死鎖的出現，分兩部分組成：一是銀行家算法(掃描)；二是安全性算法。(1) 銀行家算法(掃描) 設Requesti是進程Pi的請求向量，如果Requestij=K，表示進程Pi需要K個Ri類型的資源。當Pi發出資源請求后，系統按下述步驟進行檢查：如果Requestij<= Needi,j，便轉向步驟2；否則認為出錯，因為它所需的資源數已經超過了它所宣布的最大值。如果Requestij<=

5、Availablej，便轉向步驟3；否則表示尚無足夠資源，Pi需等待。系統試探著把資源分配給進程Pi，并修改下面數據結構中的數值。Availablej=Available-Requestij;Allocationi,j=Allocationi,j+Requestij;Needi,j=Needi,j-Requestj;系統執行安全性算法，檢查此次資源分配后，系統是否處于安全狀態。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復原來資源的分配狀態，讓進程Pi等待。(2)安全性算法系統所執行的安全性算法可描述如下：設置兩個向量：一個是工作向量Work；它表示系統可

6、提供給進程繼續運行所需要的各類資源的數目，它含有m個元素，在執行安全性算法開始時，work=Availalbe；另一個是 Finish：它表示系統是否有足夠的資源分配給進程，使之運行完成。開始時先做Finishi=false；當有足夠資源分配給進程時，再令Finishi=rue；從進程集合中找到一個能滿足下述條件的進程：一是Finishi=false；二是 Needi,j<=Workj；若找到，執行步驟，否則，執行步驟；當進程Pi獲得資源后，可順利執行，直至完成，并釋放出分配給它的資源，故應執行：Workj=Workj+Allocationi,j；Finishi=true；go to s

7、tep；如果所有進程的Finishi=true都滿足，則表示系統處于安全狀態，否則系統處于不安全狀態。3 設計思路1.進程一開始向系統提出最大需求量；2.進程每次提出新的需求(分期貸款)都統計是否超出它事先提出的最大需求量；3.若正常，則判斷該進程所需剩余剩余量(包括本次申請)是否超出系統所掌握的剩余資源量，若不超出，則分配，否則等待。銀行家算法流程如圖16-4所示：圖16-4 銀行家算法流程銀行家算法安全檢測流程如圖16-5所示：圖16-5 銀行家算法安全檢測流程4 程序運行調試結果4.1 程序初始化4.2檢測系統資源分配是否安全結果5 設計小結“銀行家算法的模擬實現”是本學期操作系統課程的

8、課程設計。在設計此程序的過程中我們遇到過許多問題也學到了很多東西。通過這周的課程設計，我加深了對銀行家算法的理解，掌握了銀行家算法避免死鎖的過程和方法，理解了死鎖產生的原因和條件以及避免死鎖的方法。所編寫程序基本實現了銀行家算法的功能，并在其基礎上考慮了輸出顯示格式的美觀性，使界面盡可能友好。并且在編程時將主要的操作都封裝在函數中，這樣使程序可讀性增強，使程序更加清晰明了。在算法的數據結構設計上考慮了很長時間。在程序設計中先后參考了很多網絡資料也參考了一些別人寫的的程序綜合這些算法思想和自己的思路對程序做了很好的設計方式對一些算法的優越性等也作了一些考慮。當然，在編寫和調試過程中我遇到了許多的

9、問題，通過網上查詢資料、翻閱課本、向同學請教、多次調試等方法逐漸解決了大部分問題。讓我收獲很多，相信在今后的生活中也有一定幫助。6 參考文獻1 韓立毛，李先鋒. 計算機操作系統實踐教程M，南京：南京大學出版社，2011.10.2 嚴蔚敏，吳偉民. 數據結構M，北京：清華大學出版社，1997.43 張堯學，史美林. 計算機操作系統教程M，北京：清華大學出版社，2000.8.4 孫靜宇. 計算機操作系統課程設計指導書M，山西：太原理工出版社，2006.4.附錄 源程序代碼#include <stdio.h>#include <stdlib.h>#include <co

10、nio.h> # define m 50int no1; /進程數int no2; /資源數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("* 銀行家算法的設計與實現 *n"); printf(&

11、quot;*n");printf("請輸入進程總數:n");scanf("%d",&no1);printf("請輸入資源種類數:n");scanf("%d",&no2); printf("請輸入Max矩陣:n");for(i=0;i<no1;i+)for(j=0;j<no2;j+)scanf("%d",&maxij); /輸入已知進程最大資源需求量printf("請輸入Allocation矩陣:n");for(

12、i=0;i<no1;i+)for(j=0;j<no2;j+)scanf("%d",&allocationij); /輸入已知的進程已分配的資源數 for(i=0;i<no1;i+)for(j=0;j<no2;j+)needij=maxij-allocationij; /根據輸入的兩個數組計算出need矩陣的值 printf("請輸入Available矩陣n");for(i=0;i<no2;i+)scanf("%d",&availablei); /輸入已知的可用資源數print(); /輸出

13、已知條件check(); /檢測T0時刻已知條件的安全狀態if(r=1) /如果安全則執行以下代碼do q=0; p=0;printf("n請輸入請求資源的進程號(04)：n");for(j=0;j<=10;j+)scanf("%d",&i);if(i>=no1)printf("輸入錯誤，請重新輸入：n"); continue; else break;printf("n請輸入該進程所請求的資源數requestj:n");for(j=0;j<no2;j+)scanf("%d&quo

14、t;,&requestj);for(j=0;j<no2;j+)if(requestj>needij) p=1; /判斷請求是否超過該進程所需要的資源數if(p)printf("請求資源超過該進程資源需求量，請求失敗！n");elsefor(j=0;j<no2;j+)if(requestj>availablej) q=1; /判斷請求是否超過可用資源數if(q) printf("沒有做夠的資源分配，請求失敗！n");else /請求滿足條件for(j=0;j<no2;j+) available1j=availablej

15、; allocation1ij=allocationij;need1ij=needij; /保存原已分配的資源數，仍需要的資源數和可用的資源數availablej=availablej-requestj; allocationij+=requestj;needij=needij-requestj; /系統嘗試把資源分配給請求的進程print();check(); /檢測分配后的安全性if(r=0) /如果分配后系統不安全for(j=0;j<no2;j+)availablej=available1j; allocationij=allocation1ij; needij=need1ij;

16、/還原已分配的資源數，仍需要的資源數和可用的資源數printf("返回分配前資源數n");print();printf("n你還要繼續分配嗎？Y or N ?n"); /判斷是否繼續進行資源分配c=getche();while(c='y'|c='Y');void check() /安全算法函數int k,f,v=0,i,j;int workm,am;bool finishm;r=1;for(i=0;i<no1;i+)finishi=false; / 初始化進程均沒得到足夠資源數并完成for(i=0;i<no2;

17、i+) worki=availablei;/worki表示可提供進程繼續運行的各類資源數k=no1;dofor(i=0;i<no1;i+)if(finishi=false)f=1;for(j=0;j<no2;j+)if(needij>workj)f=0;if(f=1) /找到還沒有完成且需求數小于可提供進程繼續運行的資源數的進程finishi=true;av+=i; /記錄安全序列號for(j=0;j<no2;j+)workj+=allocationij; /釋放該進程已分配的資源k-; /每完成一個進程分配，未完成的進程數就減1while(k>0);f=1;fo

18、r(i=0;i<no1;i+) /判斷是否所有的進程都完成if(finishi=false) f=0;break;if(f=0) /若有進程沒完成，則為不安全狀態printf("系統處在不安全狀態！");r=0;elseprintf("n系統當前為安全狀態，安全序列為：n");for(i=0;i<no1;i+)printf("p%d ",ai); /輸出安全序列void print() /輸出函數int i,j;printf("n");printf("*此時刻資源分配情況*n");printf("進程名/號 | Max | Allocation | Need |n"); for (i = 0; i < no1; i+)printf(" p%d/%d ",i,i); for (j = 0; j < no2; j+) printf("%d ",maxij);for