銀行家算法實驗報告13551

1、操作系統(tǒng)實驗報告課題：銀行家算法專 業(yè)：班 級：學 號：姓 名：年 月 日目錄一實驗目的錯誤!未定義書簽。二實驗容3三問題描述 3四設計思路 4五詳細設計 5六運行結果 10七心得體會 16八參考文獻 17附源程序 17實驗目的模擬實現(xiàn)銀行家算法，用銀行家算法實現(xiàn)資源分配。1加深了解有關資源申請、避免死鎖等概念。2體會和了解死鎖和避免死鎖的具體實施方法。3、輸入：1. 系統(tǒng)中各類資源表2. 每個進程需要各類資源總數(shù) 系統(tǒng)分配給各個進程各類資源數(shù)4、輸出：1. 判斷 T0 時刻的安全性 2.如果系統(tǒng)是安全的，任意給出某個進程的一 個資源請求方式并判斷系統(tǒng)能否接受此請求， 如果可以接受， 其輸出全

2、 部安全序列，反之，不予分配。、實驗容1設計進程對各類資源最大申請表示及初值的確定。 2設定系統(tǒng)提供資源的初始狀況。3設定每次某個進程對各類資源的申請表示。 4編制程序，依據銀行家算法，決定其資源申請是否得到滿足。 5顯示資源申請和分配時的變化情況。三、問題描述銀行家算法 . 顧名思義是來源于銀行的借貸業(yè)務，一定數(shù)量的本金要應多 個客戶的借貸周轉， 為了防止銀行加資金無法周轉而倒閉， 對每一筆貸款， 必須 考察其是否能限期歸還。 在操作系統(tǒng)中研究資源分配策略時也有類似問題， 系統(tǒng) 中有限的資源要供多個進程使用， 必須保證得到的資源的進程能在有限的時間歸 還資源，以供其他進程使用資源。 如果資源

3、分配不得到就會發(fā)生進程循環(huán)等待資 源，則進程都無法繼續(xù)執(zhí)行下去的死鎖現(xiàn)象。在死鎖的避免中， 銀行家算法把系統(tǒng)狀態(tài)分為安全狀態(tài)和不安全狀態(tài)， 只要 能使系統(tǒng)始終處于安全狀態(tài)， 便可以避免發(fā)生死鎖。 所謂安全狀態(tài)， 是指系統(tǒng)能 按某種順序為每個進程分配所需資源， 直到最大需求， 使每一個進程都可以順利 完成，即可找到一個安全資源分配序列。模擬實現(xiàn)這個工作過程四、設計思路我們可以把操作系統(tǒng)看作是銀行家， 操作系統(tǒng)管理的資源相當于銀行家 管理的資金，進程向操作系統(tǒng)請求分配資源相當于用戶向銀行家貸款。操 作系統(tǒng)按照銀行家制定的規(guī)則為進程分配資源，當進程首次申請資源時， 要測試該進程對資源的最大需求量，如

4、果系統(tǒng)現(xiàn)存的資源可以滿足它的最 大需求量則按當前的申請量分配資源，否則就推遲分配。當進程在執(zhí)行中 繼續(xù)申請資源時，先測試該進程已占用的資源數(shù)與本次申請的資源數(shù)之和 是否超過了該進程對資源的最大需求量。若超過則拒絕分配資源，若沒有 超過則再測試系統(tǒng)現(xiàn)存的資源能否滿足該進程尚需的最大資源量，若能滿 足則按當前的申請量分配資源，否則也要推遲分配。銀行家算法是一種最具代表性的避免死鎖的算法。要解釋銀行家算法， 必須先解釋操作系統(tǒng)的安全狀態(tài)和不安全狀態(tài)。 安全狀態(tài)： 如果存在一個由系統(tǒng) 中所有進程構成的安全序列Pl,，Pn,則系統(tǒng)處于安全狀態(tài)。安全狀態(tài)一定沒 有死鎖發(fā)生。不安全狀態(tài)：不存在一個安全序列。

5、不安全狀態(tài)不一定導致死鎖。安全序列：一個進程序列Pl,，Pn是安全的，如果對于每個進程 Pi (0< i < n),它以后尚需要的資源量不超過系統(tǒng)當前剩余資源量與所有進程 Pj (j v i )當前占有資源量之和。先對系統(tǒng)從源文件中讀取的數(shù)據進行安全性判斷，然后對用戶提出的請 求進行合法性檢查，即檢查請求的是不大于需要的，不大于系統(tǒng)可利用的資源。若請求合法，則進行試分配，最后對試分配狀態(tài)調用安全性算法進行安全性檢查。若安全，則分配，否則，不分配，恢復原來狀態(tài)，拒絕申請五、詳細設計1、初始化由用戶輸入數(shù)據，分別對可利用資源向量矩陣AVAILABLE最大需求矩陣MAX分配矩陣ALLOC

6、ATION需求矩陣NEED武值。2、銀行家算法在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統(tǒng) 性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終 都處于安全狀態(tài)，便可以避免發(fā)生死鎖。銀行家算法的基本思想是分配資源之前， 判斷系統(tǒng)是否是安全的；若是,才分配。設進程cusneed提出請求REQUEST，則銀行家算法按如下規(guī)則進行判斷。 如果 REQUEST cusneed i<= NEEDcusneedi，則轉(2);否則, 出錯。(2) 如果 REQUEST cusneed iv= AVAILABLEcusneedi，則轉(3);否貝U,出錯。(3)

7、 系統(tǒng)試探分配資源，修改相關數(shù)據：AVAILABLEi-=REQUESTcus needi;ALLOCATIONcus needi+=REQUESTcus needi;NEEDcus needi-=REQUESTcus needi;(4) 系統(tǒng)執(zhí)行安全性檢查，如安全，則分配成立；否則試探險性分配作廢,系統(tǒng)恢復原狀，進程等待。(5) 對于某一進程i，若對所有的j，有NEEDij=0，則表此進程資源分配完 畢，應將占用資源釋放。3、安全性檢查算法(1) 設置兩個工作向量 Work=AVAILABLE;FINISH(2) 從進程集合中找到一個滿足下述條件的進程，F(xiàn)INISH=false;NEED&l

8、t;=Work;如找到，執(zhí)行；否則，執(zhí)行(3) 設進程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。Work+=ALLOCATION;Fin ish=true;GOTO 2如所有的進程Finish= true ，則表示安全；否則系統(tǒng)不安全4、流程圖1、整體流程圖開始2、判斷系統(tǒng)的安全性Safe ()六、運行結果1、系統(tǒng)不安全的輸入（ 1）、本程序按下圖建立 .txt 源文件，作為程序的初始化輸入2）執(zhí)行程序，讀取源文件，并判斷 T0 時刻所得結果 :2. 系統(tǒng)安全的輸入（ 1）、本程序按下圖建立 .txt 源文件，作為程序的初始化輸入2）執(zhí)行程序，讀取源文件，并判斷 T0 時刻所得結果 :3)

9、T0 時刻的安全序列(4)不合理的分配輸入P1進程Request (2 2 1)與輸入P2進程Request (2 2 2)所得請求 結果：（5）合理的分配1.存在安全序列：調用Request （）函數(shù)，測試該函數(shù)的可行性，如輸入 P1進程Request 0 1 2），所得結果：2、不存在安全序列輸入 P0 進程 Request（0 2 0），所得結果 :七、心得體會本次實驗讓我對銀行家算法和死鎖都有了一定的理解。知道了在資源一 定的條件下為了讓多個進程都能使用資源完成任務，避免死鎖的產生可以從 一開始就對系統(tǒng)進行安全性檢查來判斷是否將資源分配給正在請求的進程。 但是銀行家算法會加大系統(tǒng)的開銷

10、。此外，存在以下疑問，在系統(tǒng)不分配進程所請求的資源的時候， 是否會 將此資源等待，直到擁有足夠的資源的時候再來運行？進程會請求資源是指 在執(zhí)行的過程中只有擁有了足夠數(shù)量的資源才可以執(zhí)行下去，但是資源有 限，進程數(shù)又有足夠多，我們期望所有進程都可以在最短的時間執(zhí)行完。也許可以這樣理解。操作系統(tǒng)的基本特征就是并發(fā)和共享， 系統(tǒng)允許多個進程并發(fā)執(zhí)行，并 且共享系統(tǒng)的軟、硬件資源。為了最大限度的利用計算機資源， 操作系統(tǒng)應 采用動態(tài)分配的策略，但是這樣就容易因資源不足、分配不當而引起“死鎖”。 本次課程設計就是用銀行家算法來避免“死鎖”。該算法就是一個資源分配 過程，使分配序列不會產生死鎖。此算法的中

11、心思想就是，每次分配后總存 在著一個進程，如果讓它單獨的運行下去，必然可以獲得它所需要的全部資 源，而它結束后可以歸還這類資源以滿足其他申請者的需要。另外，我知道了在程序進行編寫之前，先對程序的要求進行分析，弄清 楚程序所需要的功能，然后將每個功能分成一個功能模塊即調用函數(shù)來實 現(xiàn)，無需過多的畫蛇添足。八、參考資料【1】計算機操作系統(tǒng)（第三版）湯小丹、梁紅兵、湯子瀛、哲鳳 屏等電子科技大學2007-05【2C+Primer 中文版（第 4 版）（美）Stanley B. Lippman 等著 師賢 等 譯.人民郵電，2006-03-01【3C+ Primer習題解答（第4版） 愛軍，師賢，梅曉

12、勇 著 人民郵電 2007-02-01【4現(xiàn)代操作系統(tǒng)（原書第3版）塔嫩鮑姆 （）, 向群，馬洪兵著機械工業(yè)2009-07-01【5計算機操作系統(tǒng)教程堯學，史美林，高清華大學2006-10-01【6數(shù)據結構（STL框架）王曉東著清華大學2009-09-01【7計算機操作系統(tǒng)（第三版）湯子瀛等電子科技大學2007-05【8操作系統(tǒng)實驗教程基于windows和Linux明等 清華大學 2010-09-01附：源程序#in clude<fstream.h>#i nclude<stdio.h> #in clude<stdlib.h>#define M 10 /最大進

13、程數(shù)#define N 3 /系統(tǒng)所擁有的資源類型int MaxMN;/ 進程對各類資源的最大需求int AllocationMN;/ 系統(tǒng)已為進程所分配的各類資源數(shù)int NeedMN;/ 運行進程尚需的各類資源數(shù)int WorkN;/ 運行進程時系統(tǒng)所擁有的資源數(shù)bool finishM;/ 表示系統(tǒng)是否有足夠的資源分配給進程int AvailableN;/ 系統(tǒng)可利用的資源數(shù)int n_pro=0;/ 進程的數(shù)目int flagM=-1;/ 用于標記安全序列int Readfile();/ 從磁盤讀文件int Safe1(int flag,int n,int t);/ 輸出所有安全狀態(tài)v

14、oid show();int Safe();判斷系統(tǒng)是否處于安全狀態(tài)int Request。;/請求資源分配函數(shù)void show()printf(" t%-9st%-9st%-9sn","MAX","Allocation","Need");printf(" tA B CtA B CtA B Cn");for(int i=0;i<n_pro;i+)printf("p%dt%d%4d%4dt",i,Maxi0,Maxi1,Maxi2);printf("%d%4d

15、%4dt",Allocationi0,Allocationi1,Allocationi2);printf("%d%4d%4dn",Needi0,Needi1,Needi2);printf(" 系統(tǒng)可利用資源數(shù) :n");printf(" tAtBtCn"); printf("t%dt%dt%dn",Available0,Available1,Available2);int Readfile()/ 從磁盤讀文件int i=0,j=0;/i 表進程， j 表資源ifstream inFile; / 文件inF

16、ile.open("test.txt"); / 打開輸入文件，按照規(guī)定的格式提取線程等信息 for(j=0;j<N;j+)inFile >> Availablej;inFile.get();printf(" 系統(tǒng)最大資源數(shù) :n");printf(" tAtBtCn"); printf("t%dt%dt%dn",Available0,Available1,Available2);inFile >> n_pro;inFile.get();printf(" 當前進程的數(shù)目 :%d

17、n",n_pro); while(i<n_pro) / 提取進程的相關資源信息 for(j=0;j<N;j+)inFile >> Maxij;for(j=0;j<N;j+)inFile >> Allocationij;for(j=0;j<N;j+)Needij = Maxij - Allocationij;Availablej -= Allocationij;i+; for(j=0;j<N;j+)Workj = Availablej;printf(" 顯示初始化資源分配表 :n"); show();printf

18、("n");return 0;int Safe()判斷系統(tǒng)是否是安全的int tempn=n_pro;int i=0,j=0,t=0;for(i=0;i<n_pro;i+) finishi=false;while(tempn)for(i=0;i<n_pro;i+)if(!finishi)int tp=0;/注釋部分用于調試程序/printf("%dt%d%4d%4dt",i,Work0,Work1,Work2);/printf("%d%4d%4dn",Needi0,Needi1,Needi2);&&tp=(

19、Work0>=Needi0) && (Work1>=Needi1)(Work2>=Needi2);if(tp)finishi=true;for(int j=0;j<N;j+)Workj += Allocationij;flagt=i;/ printf("%dtflag%d=%d",i,t,flagt);system("pause");printf("n");t+;break;tempn-;for(i=0;i<n_pro;i+)if(finishi = false)printf("

20、 系統(tǒng)不安全 , 不存在安全序列 n");return -1;printf(" 系統(tǒng)是安全的 ,存在安全序列 :n");for(j=0;j<N;j+)Workj = Availablej;Safe1(flag,n_pro,0);printf("n");return 0;int Safe1(int flag,int n,int t)int p,i,j,k; /p 為標記int tempN;/ 臨時數(shù)組for(i=0;i<n;i+)int tp=0;&&tp=(Work0>=Needi0) && (

21、Work1>=Needi1) (Work2>=Needi2);if(tp)for(j=0;j<N;j+)Workj += Allocationij;flagt=i;p=1;else continue;for(int j=0;j<t;j+)if(flagt=flagj)for(j=0;j<N;j+)Workj -= Allocationij;p=0;break;if(p=1)if(t=n-1)for(k=0;k<n;k+)printf("p%-5d",flagk);printf("n");elsefor(k=0;k<

22、;N;k+)tempk = Workk - Allocationik;Safe1(flag,n,t+1);for(k=0;k<N;k+)Workk =tempk;return 0;int Request。/進程提出請求后，判斷系統(tǒng)能否將資源分配給它int rq; 下標int RequestN;printf("請輸入需要請求的進程號(04):");scanf("%d",&rq);printf("請輸入需要請求的資源數(shù)(A B C):");scanf("%d%d%d",&Request0,&

23、;Request1,&Request2);if(Needrq0 < Request0 | Needrq1 < Request1 | Needrq2 < Request2)printf("進程p%d申請的資源大于它所需要的資源n分配不合理，不予分 配 nn",rq);return -1;if(Available0 < Request0 | Available1 < Request1 | Available2 <Request2)printf("進程p%d申請的資源大于系統(tǒng)現(xiàn)在可利用的資源n分配不合理， 不予分配 nn",rq);return -1;for(int j=0;j<N;j+)Availablej -= Requestj;Allocationrq