操作系統(tǒng)實(shí)驗(yàn)_銀行家算法

1、學(xué)號(hào)P71514032 專業(yè)計(jì)算機(jī)科學(xué)與技術(shù) 姓名 實(shí)驗(yàn)日期2017.11.9 教師簽字 成績(jī)實(shí)驗(yàn)報(bào)告【實(shí)驗(yàn)名稱】銀行家算法【實(shí)驗(yàn)?zāi)康摹空莆浙y行家算法，用銀行家算法模擬操作系統(tǒng)避免死鎖的方法【實(shí)驗(yàn)原理】銀行家算法又稱“資源分配拒絕”法，其基本思想是，系統(tǒng)中的所有進(jìn)程放入進(jìn)程集合，在安全狀態(tài)下系統(tǒng)受到進(jìn)程的請(qǐng)求后試探性的把資源分配給他，現(xiàn)在系統(tǒng)將剩下的資源和進(jìn)程集合中其他進(jìn)程還需要的資源數(shù)做比較，找出剩余資源能滿足最大需求量的進(jìn)程，從而保證進(jìn)程運(yùn)行完成后還回全部資源。這時(shí)系統(tǒng)將該進(jìn)程從進(jìn)程集合中將其清除。此時(shí)系統(tǒng)中的資源就更多了。反復(fù)執(zhí)行上面的步驟，最后檢查進(jìn)程的集合為空時(shí)就表明本次申請(qǐng)可行，系

2、統(tǒng)處于安全狀態(tài)，可以實(shí)施本次分配，否則，只要進(jìn)程集合非空，系統(tǒng)便處于不安全狀態(tài)，本次不能分配給他。請(qǐng)進(jìn)程等待用C語(yǔ)言編寫一個(gè)簡(jiǎn)單的銀行家算法模擬程序，用銀行家算法實(shí)現(xiàn)資源分配。程序能模擬多個(gè)進(jìn)程共享多種資源的情形。進(jìn)程可動(dòng)態(tài)地申請(qǐng)資源，系統(tǒng)按各進(jìn)程的申請(qǐng)動(dòng)態(tài)地分配資源。要求程序具有顯示和打印各進(jìn)程的某一時(shí)刻的資源分配表和安全序列；顯示和打印各進(jìn)程依次要求申請(qǐng)的資源數(shù)量以及為某進(jìn)程分配資源后的有關(guān)資源數(shù)據(jù)的情況【數(shù)據(jù)結(jié)構(gòu)和符號(hào)說(shuō)明】可利用資源向量Available最大需求矩陣Max分配矩陣Allocation需求矩陣Need工作向量Work標(biāo)記向量Finishchar name10010;/定義

3、最大100個(gè)進(jìn)程，每個(gè)大小為10int Max100100; /定義int Allocation100100;/可利用資源向量資源數(shù)int Need100100; /需求矩陣int avaiable100; /系統(tǒng)可利用資源int avaiable1100;int state100; /進(jìn)程狀態(tài)數(shù)組char name110010;/進(jìn)程名int bigger; ;/是否大于int N; /進(jìn)程數(shù)int n; /資源數(shù)int counter;函數(shù)：void Input()/輸入函數(shù)void Init()/初始化void output()/輸出安全序列或等待void insert_pcb()/請(qǐng)求

4、進(jìn)程或更新進(jìn)程void show()/顯示界面與選擇int CmpRequestAvailable(int Pos,int n)/比較Request和Available的大小int CmpRequestNeed(int Pos,int n)/比較Request和Need的大小void Reset(int n,int Pos)/更新request之后的Need，Allocation，Available的值void Banker()/銀行家算法【實(shí)驗(yàn)流程圖及算法實(shí)現(xiàn)】用C語(yǔ)言編寫一個(gè)簡(jiǎn)單的銀行家算法模擬程序，用銀行家算法實(shí)現(xiàn)資源分配。程序能模擬多個(gè)進(jìn)程共享多種資源的情形。進(jìn)程可動(dòng)態(tài)地申請(qǐng)資源，系統(tǒng)

5、按各進(jìn)程的申請(qǐng)動(dòng)態(tài)地分配資源。要求程序具有顯示和打印各進(jìn)程的某一時(shí)刻的資源分配表和安全序列；顯示和打印各進(jìn)程依次要求申請(qǐng)的資源數(shù)量以及為某進(jìn)程分配資源后的有關(guān)資源數(shù)據(jù)的情況【流程圖】代碼：#include<iostream>using namespace std;char name10010;定義最大100個(gè)進(jìn)程，每個(gè)大小為10int Max100100; /定義int Allocation100100;/可利用資源向量資源數(shù)int Need100100; /需求矩陣int avaiable100; /int state100; /進(jìn)程狀態(tài)數(shù)組int dayu; ;是否大于int

6、N;int n;void input () cout<<"輸入進(jìn)程個(gè)數(shù)"<<endl; cin>>N; cout<<"輸入資源個(gè)數(shù)"<<endl; cin>>n; cout<<"系統(tǒng)現(xiàn)有的各資源的個(gè)數(shù)"<<endl; for(int i=0; i<n; i+) cin>>avaiablei; for(int i=0; i<N; i+)/輸入 cout<<"輸入第"<<i&l

7、t;<"個(gè)進(jìn)程的名字"<<endl; cin>>namei; cout<<"輸入第"<<i<<"所需要各進(jìn)程的最大資源數(shù)"<<endl; for(int j=0; j<n; j+) cin>>Maxij; cout<<"輸入第"<<i<<"現(xiàn)在所擁有的資源個(gè)數(shù)"<<endl; for(int j=0; j<n; j+) cin>>All

8、ocationij; statei=0; for(int i=0; i<N; i+)for(int j=0; j<n; j+) /尋找需求矩陣 Needij=Maxij-Allocationij;void yinhangjia() int i,j,k; for( i=0; i<N; i+) for( j=0; j<N; j+) if(statej=1) continue; dayu=0; for( k=0; k<n; k+) if(avaiablek>=Needjk) dayu=1; else dayu=0; break; if(dayu=1)/判斷狀態(tài) s

9、tatej=1; cout<<namej<<endl; for(int m=0; m<n; m+) avaiablem+=Allocationjm; break; int main()input();/輸入yinhangjia();截圖：帶有resquest請(qǐng)求更新的銀行家算法：描述：1）如果Requesti 是進(jìn)程Pi的請(qǐng)求向量，如果Requesti，j=K,表示進(jìn)程Pi需要K個(gè)Rj類型的資源。當(dāng)發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查： 如果Requestij<= Needi,j，便轉(zhuǎn)向步驟2；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源

10、數(shù)已超過(guò)它所宣布的最大值。 2）如果Requestij<=Availablej,便轉(zhuǎn)向步驟3，否則，表示尚無(wú)足夠資源，進(jìn)程Pi須等待。3）系統(tǒng)試探著把資源分配給進(jìn)程，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值。4）系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)i，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來(lái)的資源分配狀態(tài)，讓進(jìn)程等待。流程圖：代碼：#include<iostream>#include<string.h>using namespace std;char name10010;/定義最大100個(gè)進(jìn)程，每個(gè)大小

11、為10int Max100100; /定義int Allocation100100;/可利用資源向量資源數(shù)int Need100100; /需求矩陣int avaiable100; /int avaiable1100;int state100; /進(jìn)程狀態(tài)數(shù)組char name110010;int bigger; ;/是否大于int N;int n;int counter;void input ()/輸入函數(shù) cout<<"輸入進(jìn)程個(gè)數(shù)"<<endl; cin>>N; cout<<"輸入資源個(gè)數(shù)"<&

12、lt;endl; cin>>n; cout<<"系統(tǒng)現(xiàn)有的各資源的個(gè)數(shù)"<<endl; for(int i=0; i<n; i+) cin>>avaiablei; avaiable1i=avaiablei; for(int i=0; i<N; i+)/輸入 cout<<"輸入第"<<i+1<<"個(gè)進(jìn)程的名字"<<endl; cin>>namei; cout<<"輸入第"<<

13、i+1<<"所需要各進(jìn)程的最大資源數(shù)"<<endl; for(int j=0; j<n; j+) cin>>Maxij; cout<<"輸入第"<<i+1<<"現(xiàn)在所擁有的資源個(gè)數(shù)"<<endl; for(int j=0; j<n; j+) cin>>Allocationij; statei=0; for(int i=0; i<N; i+) for(int j=0; j<n; j+) /尋找需求矩陣 Needij=M

14、axij-Allocationij;void Banker()/銀行家算法 int i,j,k; counter=0; for(i=0; i<N; i+) statei=0; for( i=0; i<N; i+)/循環(huán)次數(shù) for( j=0; j<N; j+)/每次從頭越查找 if(statej=1) continue; bigger=0; for( k=0; k<n; k+) if(avaiablek>=Needjk)/每一個(gè)大于需求 bigger =1; else bigger=0; break;/跳出需求循環(huán) if( bigger=1)/判斷狀態(tài)，此時(shí)該進(jìn)程

15、所有need<= avaiable statej=1; strcpy(name1counter+,namej); for(k=0; k<n; k+) avaiablek+=Allocationjk;/更新avaiable向量 break; void output()/輸出安全序列或等待 int i; if (counter=N) cout<<"安全序列為:" for(i=0; i<N-1; i+) cout<< name1i<<"-> " cout<< namei<<en

16、dl<<endl; else cout<<"不存在安全序列,插入失敗"<<endl;void insert_pcb()/請(qǐng)求進(jìn)程或更新進(jìn)程 char name110; int choose; int add100; cout<<"1、增加新的進(jìn)程"<<endl; cout<<"2、對(duì)原有進(jìn)程增加資源申請(qǐng)"<<endl; cin>>choose; if(choose=1) int bigger=0; cout<<"輸入插

17、入進(jìn)程的名字"<<endl; cin>>nameN; cout<<"輸入該進(jìn)程擁有的資源個(gè)數(shù)"<<endl; for(int j=0; j<n; j+) cin>>AllocationNj; stateN=0; cout<<"輸入該所需要各資源最大數(shù)目"<<endl; for(int j=0; j<n; j+) cin>>MaxNj; NeedNj=MaxNj-AllocationNj; stateN=0; for( int k=0; k

18、<n; k+) if(avaiablek>=NeedNk)/每一個(gè)大于需求 bigger =1; else bigger=0; break;/跳出需求循環(huán) if(bigger=1) cout<<"插入成功"<<endl; N=N+1; Banker(); output(); else cout<<"插入失敗，進(jìn)程等待！"<<endl; else int pos;/找到需更新進(jìn)程的位置 cout<<"輸入原有進(jìn)程的名字"<<endl; cin>&g

19、t;name110; for(int i=0; i<N; i+) if(!strcmp(name1,namei) pos=i; break; cout<<"輸入該進(jìn)程還需要的各資源數(shù)"<<endl; for(int j=0; j<n; j+) cin>>addj; for( int k=0; k<n; k+) if(avaiablek>=addk)/每一個(gè)大于需求 bigger =1; else bigger=0; break;/跳出需求循環(huán) if(bigger=1) cout<<"插入成功&

20、quot;<<endl; for(int m=0; m<n; m+) Maxposm+=addm; Needposm+=addm; avaiablem=avaiable1m; Banker(); output(); else cout<<"插入失敗，進(jìn)程等待！"<<endl; void show()/顯示界面與選擇 int i,j; cout<<endl<<"*最大需求矩陣*"<<endl; cout<<"進(jìn)程名t" for(i=0; i<

21、n; i+) cout<<"max"<<i<<""<<"t" cout<<endl; for(i=0; i<N; i+) cout<<namei<<"t" for(j=0; j<n; j+) cout<<Maxij<<"t" cout<<endl; cout<<"*"<<endl<<endl; cout<

22、<"*各進(jìn)程已有資源數(shù)*"<<endl; cout<<"進(jìn)程名t" for(i=0; i<n; i+) cout<<"Allocation"<<i<<""<<"t" cout<<endl; for(i=0; i<N; i+) cout<<namei<<"tt" for(j=0; j<n; j+) cout<<Allocationij&

23、lt;<"tt" cout<<endl; cout<<"*"<<endl<<endl; cout<<"*各進(jìn)程需求資源數(shù)*"<<endl; cout<<"進(jìn)程名t" for(i=0; i<n; i+) cout<<" Need"<<i<<""<<"t" cout<<endl; for(i=0; i<

24、;N; i+) cout<<namei<<"tt" for(j=0; j<n; j+) cout<< Needij<<"tt" cout<<endl; cout<<"*"<<endl<<endl;int main() int select; cout<<"銀行家算法"<<endl; cout<<"初始化"<<endl; input();/輸入 sh

25、ow(); Banker(); output(); do cout<<"1、更新"<<endl; cout<<"2、查看各進(jìn)程的信息"<<endl; cout<<"3、結(jié)束"<<endl; cin>>select; if(select=3) break; else if(select=1) insert_pcb(); else show(); while(1);截圖：輸入資源種類數(shù)目，輸入最大需求矩陣，輸入分配矩陣，輸入可用資源數(shù)目，得到安全序列對(duì)進(jìn)程P1進(jìn)行請(qǐng)求，此時(shí)會(huì)形成一個(gè)新的安全序列,p1進(jìn)程的need和max發(fā)生相應(yīng)的變化。繼續(xù)修改進(jìn)程4，插入各需求3 3 0，不存在安全序列，此時(shí)需要等待。請(qǐng)求一個(gè)新進(jìn)程，所需求的最大資源為3 3 4，現(xiàn)有為2 2 3，形成新的安全序列。查看各進(jìn)程信息，并輸出安全序列。再請(qǐng)求一個(gè)新的大進(jìn)程，此時(shí)資源不足，需要等待。資源數(shù)為4：更新P1進(jìn)程，程序阻塞，進(jìn)程等待。請(qǐng)求一個(gè)新進(jìn)程，P5。插入成功，