1、操作系統實驗五實驗報告內容 （用二維數組實現銀行家算法）組長：賴建明組員：賴建明（34號） 何文成（26號） 莫善坤（9號） 李居林（13號） 黃小龍（23號） 高大旺（29號）一、 實驗題目與要求：1、用二維數組實現銀行家算法（避免死鎖）。二、總的設計思想及：1、設計思想：避免分配資源也稱作Banker(銀行家)算法。Banker算法的主要思想： 若進程Pi的申請超過了其申報的最大需求數，則報錯； 若進程Pi的申請超過了可用資源數，則Pi必須等待； 系統暫時為進程Pi分配其所需要的資源，修改資源分配狀態； 調用安全算法檢查系統當前狀態，若導致不安全狀態，則推遲這種分配。三、 數據結構與模塊說

2、明（功能與框圖）： 數據結構：安全性算法：（參考課本P102頁）Available：向量（一維數組），指出當前每種類型資源可用實例的總數量。Max：每個進程對每種資源類型實例的最大需求，它是 n x m 矩陣（二維數組）。Allocation：每個進程當前已分配的各種資源類型的實例數量，它是 n x m 矩陣（二維數組）。Need：每個進程還需要的剩余的資源，它是 n x m 矩陣（二維數組）need = max allocation。向量 Work ：是臨時的資源使用數組，它初始化為當前可用的資源數。向量 Finish： 是布爾型數組，每個進程一個單元并初始化為 false。模塊說明：安全性

3、算法流程圖Work=Available;Finish=falsefalse;Needi<=Work&&Finishi=falsetrueWork+=Availablei;Finishi=true;輸入錯誤請檢查后重新輸入!false所有進程的Finish=true否則true安全序列為:return ture資源分配失敗!資源分配成功!功能： 銀行家算法主要有兩部分：資源請求部分和安全檢測部分。對于資源請求部分，首先檢查進程的本次請求是否超過它的最初資源要求總量；如果本資源共享進程請求有效，下一步確定系統是否可以滿足進程的這次請求；如果不能滿足；掛起進程，如果可以滿足，調

4、用安全檢測算法。對于資源請求算法如下情況：1、 如果AllocationI,*+Rquest*<=NeedI,*,則轉（2），否則因進程i已起出其最大需求，系統出錯。2、 如果Request*<=Available*，則轉（3），否則進程i因沒有可用資源面等待。3、 假定系統可以分配給進程i所請求的資源，并按如下方式修改狀態：Allocationi,*=Allocationi,*+Request*;Available*=Avlaiable*-Request*;4、系統安全檢測算法。查看此時系統狀態是否安全。如果是安全的，就實際分配資源，滿足進程的此次請求；否則若新狀態不安全。則進程

5、等待，對所申請的資源暫不予分配，并且把資源分配狀態恢復到（3）之前的情況。資源請求的主要代碼如下： bool request(int pid,int *r,int n) int i;int sl4; if(compare(Needpid,r,n)=true && compare(Available,r,n) subtract(Available,r,N); add(Allocationpid,r,N); subtract(Needpid,r,N); if(safe(sl) cout<<"安全序列為:"<<endl; for(i=0;i

6、<M;i+) printf("p%d",sli); cout<<endl; return true; else add(Available,r,N); subtract(Allocationpid,r,N); add(Needpid,r,N); return false; else return false; void print(int *a,int n) int i; for(i=0;i<n;i+) cout<<" "<<ai; cout<<endl;對于安全算法情況如下：（1） 設長度為的

7、工作向量：Work=(w1,w2 ,wm)和長度為n的工作向量Finish=(F1,F2,Fn),并令Work*=Available*;Finishi=false;（2） 查找這樣的進程i使其滿足：Finishi=false;Needi,*<=work*（3） 令：Work*=Work*+Allocationi,*;Finishi=true;（4） 如果對于所有i，Finishi=ture則系統處于安全狀態；否則系統處于不安全狀態。安全檢查的主要算法如下： bool safe(int *sl) int i; int count=0; /*記錄finishi = true 的個數*/ in

8、t n=0; int workN; bool finishM;assign(work,Available,N);for(i=0;i<M;i+) finishi=false; n=M; while(n-) for(i=0;i<M;i+) if(count>=M) return true; if(finishi=false&&compare(work,Needi,N) add(work,Allocationi,N); finishi=true; slcount=i; count+; if(count>=M) return true; else return

9、false; 四、源程序#include <stdio.h>#include <stdlib.h>#include <conio.h>#include<iostream.h>#define M 4 /*進程數*/#define N 3 /*資源數*/int AvailableN = 1,1,2; /系統可用資源向量int MaxMN = 3,2,2, 6,1,3, 3,1,4, 4,2,2, ; /最大需求向量int AllocationMN = 1,0,0, 5,1,1, 2,1,1, 0,0,2, ; /資源已分配向量int NeedMN =

10、 2,2,2, 1,0,2, 1,0,3, 4,2,0, ; /需求向量/比較兩個一維數組,判斷 a >= b ?bool compare(int *a,int *b,int n) int i=0; for(i=0;i<n;i+) if(ai<bi) return false; return true;/一維數組加法/a = a + bvoid add(int *a,int *b,int n) int i=0; for(i=0;i< n;i+) ai+=bi; /一維數組減法/a = a - bvoid subtract(int *a,int *b,int n) int

11、 i=0; for(i=0;i<n;i+) ai-=bi; /將數組b的值賦給a，n為數組的大小void assign(int *a,int *b,int n) int i=0; for(i=0;i<n;i+) ai=bi; /sl 記錄安全序列bool safe(int *sl) int i; int count=0; /*記錄finishi = true 的個數*/ int n=0; int workN; bool finishM; /work = av; assign(work,Available,N); /初始化標記 finish for(i=0;i<M;i+) fi

12、nishi=false; /n為進程的個數/循環最多執行n次 n=M; while(n-) for(i=0;i<M;i+) /判斷是否安全 if(count>=M) /全部進程都可安全執行（finish = true） return true; /判斷能否滿足進程i的要求 /work >= Needi ? if(finishi=false&&compare(work,Needi,N) /分配，待進程完成后再釋放 add(work,Allocationi,N); finishi=true; /記錄安全路徑 slcount=i; /能滿足的進程數+1 count+

13、; if(count>=M) return true; else return false; /請求分配/pid進程，r請求向量，n資源個數bool request(int pid,int *r,int n) int i; /記錄安全路徑 int sl4; if(compare(Needpid,r,n)=true && compare(Available,r,n) /嘗試分配資源 subtract(Available,r,N); add(Allocationpid,r,N); subtract(Needpid,r,N); /判斷是否是安全狀態 if(safe(sl) /打

14、印安全路徑 cout<<"安全序列為:"<<endl; for(i=0;i<M;i+) printf("p%d",sli); cout<<endl; /可以分配 return true; else /不分配 /恢復到分配前的狀態 add(Available,r,N); subtract(Allocationpid,r,N); add(Needpid,r,N); return false; else /error return false; /打印一維數組void print(int *a,int n) int i

15、; for(i=0;i<n;i+) cout<<" "<<ai; cout<<endl;/顯示系統信息void init() int i; cout<<"該系統共有進程4個,"<<'n'<<"其對資源的需求和分配情況分別是:"<<endl; for(i=0;i<M;i+) cout<<"進程"<<i<<"資源最大需求:" print(Maxi,N);

16、 cout<<endl; for(i=0;i<M;i+) cout<<"進程"<<i<<"已經分配資源:" print(Allocationi,N); cout<<endl; cout<<"系統可用資源數量:"<<'n'<<'t'<<endl; print(Available,N);/輸入void input(int *r,int n,int *id) char ch; cout<&l

17、t;"請輸入進程的id(0 3):"<<endl; ch=getche(); *id=ch-0x30; cout<<"n請輸入對0類資源的申請數量:"<<endl; ch=getche(); r0=ch-0x30;cout<<"n請輸入對1類資源的申請數量:"<<endl; ch=getche(); r1=ch-0x30; cout<<"n請輸入對2類資源的申請數量:"<<endl; ch=getche(); r2=ch-0x30;

18、 printf("n您輸入的是：Request%d(%d,%d,%d)n",*id,r0,r1,r2);/檢查輸入bool check(int id,int r1,int r2,int r3) if(id>3|id<0|r1<0|r2<0|r3<0) return false; else return true; int main() /進程id int id; /控制字符 int r3; char es; char control; /顯示開始信息 init(); /輸入申請信息 input(r,N,&id); /檢查輸入 if(check(id,r0,r1,r2) = false) cout<<"輸入錯誤請檢查后重新輸入!"<<endl; /continue; /執行 if(request(id,r,N) cout<<"資源分配成功!"<<endl; else cout<<"資源分配失敗!"<<endl; /顯示當前系統資源和進程情況 cout<<"系統可用資源:"<<endl; print(Available,N); cout&l