銀行家算法實驗報告

1、操作系統(tǒng)原理課程設(shè)計銀行家算法指導(dǎo)老師： 周敏 唐洪英 楊宏雨 楊承玉 傅由甲 黃賢英 院 系： 計算機學(xué)院計算機科學(xué)與技術(shù)系 班 級： 0237-6 學(xué) 號： 2002370608 姓 名： 朱 應(yīng) 瑜 同 組 者： 陳 源 時 間： 2005/12/22-2005/12/28 目錄一、設(shè)計目的3二、設(shè)計內(nèi)容3三、銀行家算法的基本思想3（一）死鎖3（二）系統(tǒng)安全狀態(tài)4（三）銀行家算法避免死鎖41、銀行家算法中的數(shù)據(jù)結(jié)構(gòu)42、銀行家算法43、安全性算法5四、系統(tǒng)模塊間關(guān)系圖6五、系統(tǒng)子模塊結(jié)構(gòu)圖7六、輸入、輸出數(shù)據(jù)9七、源程序及系統(tǒng)文件使用說明12（一）源程序12（二）系統(tǒng)文件使用說明25八、

2、心得體會26九、參考文獻(xiàn)26銀行家算法一、 設(shè)計目的本課程設(shè)計是學(xué)習(xí)完計算機操作系統(tǒng)課程后，進(jìn)行的一次全面的綜合訓(xùn)練。通過這次課程設(shè)計，讓我們更好地掌握操作系統(tǒng)的原理及實現(xiàn)方法,加深對操作系統(tǒng)基礎(chǔ)理論和重要算法的理解，加強動手能力。二、 設(shè)計內(nèi)容編制銀行家算法通用程序，并檢測所給狀態(tài)的系統(tǒng)安全性。三、銀行家算法的基本思想（一）死鎖在多道程序系統(tǒng)中，雖可借助于多個進(jìn)程的并發(fā)執(zhí)行，來改善系統(tǒng)的資源利用率，提高系統(tǒng)的吞吐量，但可能發(fā)生一種危險死鎖。所謂死鎖，是指多個進(jìn)程在運行過程中因爭奪資源而造成的一種僵局，當(dāng)進(jìn)程處于這種僵持狀態(tài)時，若無外力作用，它們都將無法再向前推進(jìn)。產(chǎn)生死鎖的原因可歸結(jié)為如下兩

3、點：（1）競爭資源。（2）進(jìn)程間推進(jìn)順序非法。死鎖的發(fā)生必須具備下列四個必要條件：（1）互斥條件。（2）請求和保持條件。（3）不剝奪條件。（4）環(huán)路等待條件。（二）系統(tǒng)安全狀態(tài)避免死鎖的實質(zhì)在于：系統(tǒng)在進(jìn)行資源分配時，如何使系統(tǒng)不進(jìn)入不安全狀態(tài)。所謂安全狀態(tài)，是指系統(tǒng)能按某種進(jìn)程順序（P1，P2，Pn）（稱<P1，P2，Pn>序列為安全序列），來為每個進(jìn)程Pi分配其所需資源，直至滿足每個進(jìn)程對資源的最大需求，使每個進(jìn)程都可順利的完成。如果系統(tǒng)無法找到這樣一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)。（三）銀行家算法避免死鎖為實現(xiàn)銀行家算法，系統(tǒng)中必須設(shè)置若干數(shù)據(jù)結(jié)構(gòu)。1、銀行家算法中的數(shù)據(jù)

4、結(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個進(jìn)程中的每一個進(jìn)程對m類資源的最大需求。如果Maxi，j=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。（3）分配矩陣Allocation。這也是一個n*m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocationi，j=K，則表示進(jìn)程i當(dāng)前已

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

6、<= Availablej，便轉(zhuǎn)向步驟（3）；否則，表示尚無足夠資源，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ù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。3、安全性算法系統(tǒng)所執(zhí)行的安全性算法可描述

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

8、Allocationi，j； Finishi=true； go to step 2；（4）如果所有進(jìn)程的Finishi=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。四、系統(tǒng)模塊間關(guān)系圖五、系統(tǒng)子模塊結(jié)構(gòu)圖六、輸入、輸出數(shù)據(jù)執(zhí)行程序，輸入數(shù)據(jù)之前：現(xiàn)在請分別輸入對應(yīng)的進(jìn)程號、資源號和個數(shù)：現(xiàn)在請選擇1或2：選擇了1后：因為未通過安全性測試，不予以分配，所以一切數(shù)據(jù)均無變化。點擊了1后：現(xiàn)在又請分別輸入其它需要測試的進(jìn)程號、資源號和個數(shù)：現(xiàn)在請選擇1或2：選擇了1后：因為通過了安全性測試，并找到了一個安全序列，所以分配成功，有關(guān)數(shù)據(jù)均要發(fā)生變化。（請對照前后數(shù)據(jù)及所輸入的數(shù)據(jù)

9、進(jìn)行比較）l 資源類型1的可利用資源由4變成3；l 進(jìn)程2的資源類型1的已分配資源由2變成3；l 進(jìn)程2的資源類型1的已需求資源由1變成0；點擊了1后：七、源程序及系統(tǒng)文件使用說明（一）源程序#include "stdafx.h"#include<iostream.h>#include<fstream.h>#include<windows.h>#include<stdlib.h>#define MAX_PROCESS 32 /最大進(jìn)程數(shù)#define MAX_COURCE 64 /最大資源類別int MAX_FACT_PROC

10、ESS; /實際總進(jìn)程數(shù)int MAX_FACT_COURCE; /實際資源類別數(shù)int AvailableMAX_COURCE; /可利用資源向量int MaxMAX_PROCESSMAX_COURCE; /最大需求矩陣int AllocationMAX_PROCESSMAX_COURCE; /分配矩陣int NeedMAX_PROCESSMAX_COURCE; /需求矩陣int Request_PROCESS; /發(fā)出請求的進(jìn)程int Request_COURCE; /被請求資源類別int Request_COURCE_NEMBER; /請求資源數(shù)bool loop = true;stru

11、ct COMPint value;int num;int next;int flag=0;void Read_Initiate(void)/讀入初始化文檔 ifstream infile("Initiate.txt");if(!infile)cout<<"不能打開輸入文件:"<<"Initiate.txt"<<endl;exit(1);cout<<"開始讀入初始化文檔"<<endl;int ch;int ArrayMAX_PROCESS*MAX_COURC

12、E*2;int num=0;while(infile>>ch) /初始化文檔的第一個數(shù)字為長度Arraynum+=ch;num=0;MAX_FACT_COURCE=Arraynum+;for(int j=0;j<MAX_FACT_COURCE;j+)Availablej=Arraynum+;MAX_FACT_PROCESS=Arraynum+;for(int i=0;i<MAX_FACT_PROCESS;i+)for(int j=0;j<MAX_FACT_COURCE;j+)Maxij=Arraynum+;infile.close();void Write_Ini

13、tiate(void)/寫入初始化文檔(分配資源) ofstream outfile("Initiate.txt");if(!outfile)cout<<"不能打開初始化文檔："<<endl;exit(1);int ArrayMAX_PROCESS*MAX_COURCE*2;int num=0;Arraynum+=MAX_FACT_COURCE;for(int i=0;i<MAX_FACT_COURCE;i+)Arraynum+=Availablei;Arraynum+=MAX_FACT_PROCESS;for(i=0;i&

14、lt;MAX_FACT_PROCESS;i+)for(int j=0;j<MAX_FACT_COURCE;j+)Arraynum+=Maxij;num=0;outfile<<Arraynum+<<" "for(i=0;i<MAX_FACT_COURCE;i+)outfile<<Arraynum+<<" "outfile<<endl<<Arraynum+<<endl;for(i=0;i<MAX_FACT_PROCESS;i+)for(int j=0;j&l

15、t;MAX_FACT_COURCE;j+)outfile<<Arraynum+<<" "outfile<<endl;int m_delay=3000;Sleep(m_delay);outfile.close();cout<<"修改初始化文檔成功!"<<endl;void Allocated_list(void)/讀入已分配資源列表 ifstream infile("Allocated_list.txt");if(!infile)cout<<"不能打開輸入

16、文件:"<<"Allocated_list.txt"<<endl;exit(1);cout<<"開始讀入已分配資源列表"<<endl;int ch;int num=0;int ArrayMAX_PROCESS*MAX_COURCE;while(infile>>ch)Arraynum+=ch;num=0;for(int i=0;i<MAX_FACT_PROCESS;i+)for(int j=0;j<MAX_FACT_COURCE;j+)Allocationij=Arraynu

17、m+;infile.close();void Set_Need(void)/設(shè)置需求矩陣 cout<<"設(shè)置需求矩陣"<<endl;for(int i=0;i<MAX_FACT_PROCESS;i+)for(int j=0;j<MAX_FACT_COURCE;j+)Needij=Maxij-Allocationij;void Write_Allocation(void)/修改資源分配列表(資源分配) ofstream outfile("Allocated_list.txt");if(!outfile)cout<&

18、lt;"不能打開資源分配列表："<<endl;exit(1);for(int i=0;i<MAX_FACT_PROCESS;i+)for(int j=0;j<MAX_FACT_COURCE;j+)outfile<<Allocationij<<" "outfile<<endl;int m_delay=3000;Sleep(m_delay);cout<<"修改資源分配列表成功!"<<endl;outfile.close();void Allocate_So

19、urce(void)/開始分配(已通過掃描和安全性檢測) cout<<endl<<"開始給第"<<Request_PROCESS<<"個進(jìn)程分配第"<<Request_COURCE<<"類資源"<<Request_COURCE_NEMBER<<"個"<<endl;Write_Initiate();Write_Allocation();int m_delay=3000;Sleep(m_delay);cout&l

20、t;<endl<<"祝賀您，資源分配已成功!"<<endl;bool Test_Safty()/安全性檢測 cout<<endl<<"進(jìn)入安全性檢測!"<<endl;int WorkMAX_COURCE;for(int i=0;i<MAX_FACT_COURCE;i+)Worki=Availablei;bool FinishMAX_PROCESSMAX_COURCE;for(i=0;i<MAX_FACT_PROCESS;i+)for(int j=0;j<MAX_FACT_

21、COURCE;j+)Finishij=false;COMP Array32;for(i=0;i<MAX_FACT_PROCESS;i+)Arrayi.value=NeediRequest_COURCE-1; Arrayi.num=i;for(i=0;i<MAX_FACT_PROCESS;i+)for(int j=i+1;j<MAX_FACT_PROCESS;j+)if(Arrayi.value>=Arrayj.value)int t;t=Arrayj.value;Arrayj.value=Arrayi.value;Arrayi.value=t;t=Arrayj.num;

22、Arrayj.num=Arrayi.num;Arrayi.num=t;else continue;int m_delay=3000;Sleep(m_delay);if(FinishRequest_PROCESS-1Request_COURCE-1=false&&NeedRequest_PROCESS-1Request_COURCE-1<=WorkRequest_COURCE-1)WorkRequest_COURCE-1=WorkRequest_COURCE-1+AllocationRequest_PROCESS-1Request_COURCE-1;FinishReques

23、t_PROCESS-1Request_COURCE-1=true;elsecout<<"未通過安全性測試，不與以分配"<<endl;return false; for(i=0;i<MAX_FACT_PROCESS;i+) if(Arrayi.num=Request_PROCESS-1)continue;if(Arrayi.num!=Request_PROCESS-1&&FinishArrayi.numRequest_COURCE-1=false&&NeedArrayi.numRequest_COURCE-1<

24、;=WorkRequest_COURCE-1)WorkRequest_COURCE-1=WorkRequest_COURCE-1+AllocationArrayi.numRequest_COURCE-1; FinishArrayi.numRequest_COURCE-1=true;for(i=0;i<MAX_FACT_PROCESS;i+)if(FinishiRequest_COURCE-1=true)continue;elsecout<<"未通過安全性測試，不與以分配"<<endl;return false;cout<<endl&

25、lt;<"找到一個安全序列:"<<"P"<<Request_PROCESS<<"->"for(i=0;i<MAX_FACT_PROCESS;i+)if(Arrayi.num=Request_PROCESS)continue;elsecout<<"P"<<Arrayi.num<<"->"cout<<endl<<"已通過安全性測試!"<<endl;A

26、llocate_Source();return true;bool RUN(void) /執(zhí)行銀行家算法 cout<<"*"<<endl<<"點擊1執(zhí)行!"<<endl<<"點擊2退出!"<<endl<<"*"<<endl;cin>>flag;if(flag=2)loop = false;exit(0);if(flag=1)cout<<"開始掃描請求信息!"<<en

27、dl;int m_delay=3000;Sleep(m_delay);if(Request_COURCE_NEMBER>NeedRequest_PROCESS-1Request_COURCE-1)cout<<endl<<"第"<<Request_PROCESS<<"個進(jìn)程請求第"<<Request_COURCE<<"類資源"<<Request_COURCE_NEMBER<<"個"<<endl;cout&

28、lt;<"可是已超出該進(jìn)程尚需的該類資源的最大數(shù)量,所以不予以分配!"<<endl;return false;if(Request_COURCE_NEMBER>AvailableRequest_COURCE-1)cout<<endl<<"第"<<Request_PROCESS<<"個進(jìn)程請求第"<<Request_COURCE<<"類資源"<<Request_COURCE_NEMBER<<&quo

29、t;個"<<endl;cout<<"可是系統(tǒng)中尚無足夠的資源,所以進(jìn)入等待隊列!"<<endl;return false;elseAvailableRequest_COURCE-1=AvailableRequest_COURCE-1-Request_COURCE_NEMBER;AllocationRequest_PROCESS-1Request_COURCE-1=AllocationRequest_PROCESS-1Request_COURCE-1+Request_COURCE_NEMBER;NeedRequest_PROCES

30、S-1Request_COURCE-1=NeedRequest_PROCESS-1Request_COURCE-1-Request_COURCE_NEMBER;cout<<"掃描通過"<<endl;Sleep(m_delay);Test_Safty();else cout<<"輸入錯誤,請重新輸入!"<<endl;RUN();return true; void main(void)int tflag;int i;int j;char tch;while(loop)Read_Initiate();cout&l

31、t;<endl<<"資源個數(shù)："<<MAX_FACT_COURCE<<endl;cout<<"可利用資源"<<endl;cout<<"資源類型 "for(i=0;i<MAX_FACT_COURCE;i+)cout<<i+1<<" "cout<<endl;cout<<" "for(i=0;i<MAX_FACT_COURCE;i+)cout<<Avai

32、lablei<<" "cout<<endl<<"進(jìn)程個數(shù)："<<MAX_FACT_PROCESS<<endl;cout<<"資源類型 "for(i=0;i<MAX_FACT_COURCE;i+)cout<<i+1<<" "cout<<endl;for(i=0;i<MAX_FACT_PROCESS;i+)cout<<"P"<<i+1<<&quo

33、t;: "for(j=0;j<MAX_FACT_COURCE;j+)cout<<Maxij<<" "cout<<endl;int m_delay=3000;Sleep(m_delay);cout<<"讀入成功"<<endl<<endl;Allocated_list();cout<<"資源類型 "for(i=0;i<MAX_FACT_COURCE;i+)cout<<i+1<<" "cout

34、<<endl;for(i=0;i<MAX_FACT_PROCESS;i+)cout<<"P"<<i+1<<": "for(j=0;j<MAX_FACT_COURCE;j+)cout<<Allocationij<<" "cout<<endl;Sleep(m_delay);cout<<"讀入成功"<<endl<<endl;Set_Need();cout<<"資源類型

35、"for(i=0;i<MAX_FACT_COURCE;i+)cout<<i+1<<" "cout<<endl;for(i=0;i<MAX_FACT_PROCESS;i+)cout<<"P"<<i+1<<": "for(j=0;j<MAX_FACT_COURCE;j+)cout<<Needij<<" "cout<<endl;Sleep(m_delay);cout<<&qu

36、ot;設(shè)置成功"<<endl;cout<<endl<<"請輸入進(jìn)程號("<<"1"<<MAX_FACT_PROCESS<<"):"cin>>Request_PROCESS;cout<<endl<<"請輸入資源號("<<"1"<<MAX_FACT_COURCE<<"):"cin>>Request_COURCE;cout<<endl<<"請輸入個數(shù):"cin>>Request_COURCE_NEMBER;cout<<endl<<"第"<<Request_PROCESS<<"個進(jìn)程請求第"<&