銀行家算法某實驗報告材料

1、計算機學院操作系統(tǒng)課程設計報告設計題目：銀行家算法的實現姓名：學號：班級： 06 網絡工程班完成日期： 2009 年 6 月 13 日設計題目銀行家算法的實現設計形式獨立完成設1 加深了解有關資源申請、避免死鎖等概念。Lm2 體會和了解死鎖和避免死鎖的具體實施方法。設1 死鎖的相關知識。計 預2 銀行家算法。備 知 識3 .系統(tǒng)安全性檢查。設計內容定 是 確 請 的 。 申 值 示 源 初<表資 及 請 其 。 示 申 宀疋 況 表 。的 決 情 請 況 源， 化 各ttsrfti請 對 提 某 , 申 程 統(tǒng) 次 序 源 進 系 每 程 資 計 定B制 一不 設 設 設 編 顯O1 2

2、 3 4 足 5滿到小組成口貝分工無銀行家算法分析、設計與實現、設計理論描述本設計的目的是通過編寫和調試一個系統(tǒng)動態(tài)分配資源的簡單模擬程序， 觀察死鎖產生的條件， 并采用適當的算法， 有效地防止和避免死鎖地發(fā)生。 要求 如下：（1 ） 模擬一個銀行家算法；（2 ） 初始化時讓系統(tǒng)擁有一定的資源；（3 ） 用鍵盤輸入的方式申請資源；（4 ） 如果預分配后，系統(tǒng)處于安全狀態(tài)，則修改系統(tǒng)的資源分配情況；（5 ） 如果預分配后，系統(tǒng)處于不安全狀態(tài)，則提示不能滿足請求， 設計的主要內容是模擬實現動態(tài)資源分配。 同時編寫和調試一個系統(tǒng)動態(tài) 資源的簡單模擬程序， 觀察死鎖產生的條件， 并使用適當的算法， 有

3、效的防止和 避免死鎖的發(fā)生。銀行家算法 . 顧名思義是來源于銀行的借貸業(yè)務，一定數量的本金要應多 個客戶的借貸周轉， 為了防止銀行加資金無法周轉而倒閉， 對每一筆貸款， 必須 考察其是否能限期歸還。 在操作系統(tǒng)中研究資源分配策略時也有類似問題， 系統(tǒng) 中有限的資源要供多個進程使用， 必須保證得到的資源的進程能在有限的時間內 歸還資源， 以供其他進程使用資源。 如果資源分配不得到就會發(fā)生進程循環(huán)等待 資源，則進程都無法繼續(xù)執(zhí)行下去的死鎖現象。把一個進程需要和已占有資源的情況記錄在進程控制中，假定進程控制塊 PCB 其中“狀態(tài)”有就緒態(tài)、等待態(tài)和完成態(tài)。當進程在處于等待態(tài)時，表示系統(tǒng)不能滿足該進程

4、當前的資源申請資源需求總量” 表示進程在整個執(zhí)行過程中總共要申請的資源量。 顯然， ，每個進程的資源需求總量不能超過系統(tǒng)擁有 的資源總數 , 銀行算法進行資源分配可以避免死鎖 .二、算法描述及數據結構模型1. 銀行家算法 :設進程 i 提出請求 Requestn ，則銀行家算法按如下規(guī)則進行判斷。(1) 如果 Requestn>Needi ，n ，則報錯返回。(2) 如果 Requestn>Available ，則進程 i 進入等待資源狀態(tài)，返回。(3) 假設進程 i 的申請已獲批準，于是修改系統(tǒng)狀態(tài)： Available=Available-Request Allocation=

5、Allocation+Request Need=Need-Request(4) 系統(tǒng)執(zhí)行安全性檢查，如安全，則分配成立；否則試探險性分配作廢，系統(tǒng) 恢復原狀，進程等待。2. 安全性檢查(1) 設置兩個工作向量 Work=Available ；FinishM=False(2) 從進程集合中找到一個滿足下述條件的進程，Finish i=FalseNeed<=Work如找到，執(zhí)行 (3) ；否則，執(zhí)行 (4)(3) 設進程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。Work=Work+AllocationFinish=TrueGO TO 2(4) 如所有的進程 FinishM=true ，則

6、表示安全；否則系統(tǒng)不安全3. 數據結構#define False 0#define True 1int Max100100=0;/ 各進程所需各類資源的最大需求int Avaliable100=0;/ 系統(tǒng)可用資源char name100=0;/ 資源的名稱int Allocation100100=0;/系統(tǒng)已分配資源int Need100100=0;/ 還需要資源int Request100=0;/ 請求資源向量int temp100=0;/ 存放安全序列int Work100=0;/ 存放系統(tǒng)可提供資源int M=100;/ 作業(yè)的最大數為 100int N=100;/ 資源的最大數為 1

7、00void showdata()/ 顯示資源矩陣三、源代碼#include<iostream.h>#include<string.h> #include<stdio.h>#define False 0 #define True 1int Max100100=0;/ 各進程所需各類資源的最大需求int Avaliable100=0;/ 系統(tǒng)可用資源char name100=0;/ 資源的名稱int Allocation100100=0;/ 系統(tǒng)已分配資源int Need100100=0;/ 還需要資源int Request100=0;/ 請求資源向量int

8、temp100=0;/ 存放安全序列int Work100=0;/ 存放系統(tǒng)可提供資源int M=100;/ 作業(yè)的最大數為 100int N=100;/ 資源的最大數為 100void showdata()/ 顯示資源矩陣int i,j;cout<<" 系統(tǒng)目前可用的資源 Avaliable:"<<endl; for(i=0;i<N;i+)cout<<namei<<" "cout<<endl;for (j=0;j<N;j+)cout<<Avaliablej<<

9、;" "/ 輸出分配資源cout<<endl;cout<<"MaxAllocationNeed"<<endl;cout<<" 進程名 "for(j=0;j<3;j+)for(i=0;i<N;i+)cout<<namei<<" "cout<<" "cout<<endl;for(i=0;i<M;i+)cout<<" "<<i<<&q

10、uot;for(j=0;j<N;j+)cout<<Maxij<<" " cout<<" " for(j=0;j<N;j+)cout<<Allocationij<<" "cout<<" "for(j=0;j<N;j+)cout<<Needi j<<" " cout<<endl;int changdata(int i)/ 進行資源分配int j;for (j=0;j<M

11、;j+) Avaliablej=Avaliablej-Requestj;Allocationij=Allocationij+Requestj;Needij=Needij-Requestj;return 1;int safe()/ 安全性算法int i,k=0,m,apply,Finish100=0;int j;int flag=0;Work0=Avaliable0;Work1=Avaliable1;Work2=Avaliable2;for(i=0;i<M;i+)apply=0;for(j=0;j<N;j+)if (Finishi=False&&Needij<=

12、Workj)apply+;if(apply=N)for(m=0;m<N;m+)Workm=Workm+Allocationim;/ 變分配數Finishi=True;tempk=i;i=-1;k+;flag+;for(i=0;i<M;i+)if(Finishi=False)cout<<" 系統(tǒng)不安全 "<<endl;/ 不成功系統(tǒng)不安全return -1;cout<<" 系統(tǒng)是安全的 !"<<endl;/ 如果安全，輸出成功cout<<" 分配的序列 :"for(

13、i=0;i<M;i+)/ 輸出運行進程數組cout<<tempi;if(i<M-1) cout<<"->"cout<<endl;return 0;void share()/ 利用銀行家算法對申請資源對進行判定char ch;int i=0,j=0;ch='y'cout<<" 請輸入要求分配的資源進程號 (0-"<<M-1<<"):"cin>>i;/ 輸入須申請的資源號cout<<" 請輸入進程 &

14、quot;<<i<<" 申請的資源 :"<<endl;for(j=0;j<N;j+)cout<<namej<<":"cin>>Requestj;/ 輸入需要申請的資源for (j=0;j<N;j+) if(Requestj>Needij)/ 判斷申請是否大于需求，若大于則出錯cout<<" 進程 "<<i<<" 申請的資源大于它需要的資源cout<<" 分配不合理，不予分配！ &

15、quot;<<endl;ch='n'break;else if(Requestj>Avaliablej)/ 判斷申請是否大于當前資源，若大于則 / 出錯cout<<" 進程 "<<i<<" 申請的資源大于系統(tǒng)現在可利用的資源 "cout<<" 分配出錯，不予分配 !"<<endl;ch='n'break;if(ch='y') changdata(i);/ 根據進程需求量變換資源showdata();/ 根據進程

16、需求量顯示變換后的資源safe();/ 根據進程需求量進行銀行家算法判斷void addresources()/ 添加資源int n,flag;cout<<" 請輸入需要添加資源種類的數量cin>>n;flag=N;N=N+n;for(int i=0;i<n;i+)cout<<" 名稱 :"cin>>nameflag;cout<<" 數量 :"cin>>Avaliableflag+;showdata();safe();void delresources()/ 刪除資源

17、char ming;int i,flag=1;cout<<" 請輸入需要刪除的資源名稱：docin>>ming;for(i=0;i<N;i+)if(ming=namei)flag=0;break;if(i=N)cout<<" 該資源名稱不存在，請重新輸入： " while(flag);for(int j=i;j<N-1;j+)namej=namej+1;Avaliablej=Avaliablej+1;N=N-1; showdata(); safe();void changeresources()/ 修改資源函數cou

18、t<<" 系統(tǒng)目前可用的資源 Avaliable:"<<endl; for(int i=0;i<N;i+) cout<<namei<<":"<<Avaliablei<<endl;cout<<" 輸入系統(tǒng)可用資源 Avaliable:"<<endl; cin>>Avaliable0>>Avaliable1>>Avaliable2; cout<<" 經修改后的系統(tǒng)可用資源為 &qu

19、ot;<<endl;for (int k=0;k<N;k+) cout<<namek<<":"<<Avaliablek<<endl;showdata();safe();void addprocess()/ 添加作業(yè)int flag=M;M=M+1;cout<<" 請輸入該作業(yè)的最打需求量 Max"<<endl;for(int i=0;i<N;i+)cout<<namei<<":"cin>>Maxflagi

20、;Needflagi=Maxflagi-Allocationflagi;showdata();safe();int main()/ 主函數int i,j,number,choice,m,n,flag;char ming;cout<<"* 單 處 理 機 系 統(tǒng) 進 程 調 度 實 現*、'<<endl;cout<<" 請首先輸入系統(tǒng)可供資源種類的數量cin>>n;N=n;for(i=0;i<n;i+)coutvv"資源"<<i+1<<"的名稱:"ci

21、n>>ming;namei=ming;cout<<" 資源的數量 :"cin>>number;Avaliablei=number;cout<<endl;cout<<" 請輸入作業(yè)的數量cin>>m;M=m;cout<<" 請 輸 入 各 進 程 的 最 大 需 求 量 ("<<m<<"*"<<n<<" 矩 陣)Max:"«e ndl;for(i=0;i<m;i

22、+)for(j=0;j<n;j+)cin>>Maxij;doflag=0;cout<<" 請 輸 入 各 進 程 已 經 申 請 的 資 源 量 ("<<m<<"*"<<n<<" 陣)Allocati on :"<<e ndl;for(i=0;i<m;i+)for(j=0;j<n;j+)cin>>Allocationij;if(Allocationij>Maxij)flag=1;Needij=Maxij-Alloca

23、tionij;if(flag)cout<<" 申請的資源大于最大需求量，請重新輸入 !n"while(flag);showdata();/ 顯示各種資源safe();/ 用銀行家算法判定系統(tǒng)是否安全while(choice)cout<<"*銀行家算法演示*"cout<<"1:增加資源"<<endl;cout<<"2:刪除資源"<<endl;cout<<"3:修改資源"<<endl;cout<<"4:分配資源"<<endl;cout<<"5:增加作業(yè)"<<endl;cout<<"0:離開"<<endl;<<endl;cout<<".*"<<endl;cout<<"