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

PAGEPAGE9銀行家算法【開(kāi)發(fā)語(yǔ)言及實(shí)現(xiàn)平臺(tái)或?qū)嶒?yàn)環(huán)境】C++MicrosoftVisualStudio6.0【實(shí)驗(yàn)?zāi)康摹浚?）進(jìn)一步理解利用銀行家算法避免死鎖的問(wèn)題；（2）在了解和掌握銀行家算法的基礎(chǔ)上，編制銀行家算法通用程序，將調(diào)試結(jié)果顯示在計(jì)算機(jī)屏幕上，再檢測(cè)和筆算的一致性。（3）理解和掌握安全序列、安全性算法【實(shí)驗(yàn)要求】（1）了解和理解死鎖；（2）理解利用銀行家算法避免死鎖的原理；（3）會(huì)使用某種編程語(yǔ)言?！緦?shí)驗(yàn)原理】一、安全狀態(tài)指系統(tǒng)能按照某種順序如<P1,P2,…,Pn>(稱為<P1,P2,…,Pn>序列為安全序列)，為每個(gè)進(jìn)程分配所需的資源，直至最大需求，使得每個(gè)進(jìn)程都能順利完成。二、銀行家算法假設(shè)在進(jìn)程并發(fā)執(zhí)行時(shí)進(jìn)程i提出請(qǐng)求j類資源k個(gè)后，表示為Requesti[j]=k。系統(tǒng)按下述步驟進(jìn)行安全檢查：（1）如果Requesti≤Needi則繼續(xù)以下檢查，否則顯示需求申請(qǐng)超出最大需求值的錯(cuò)誤。（2）如果Requesti≤Available則繼續(xù)以下檢查，否則顯示系統(tǒng)無(wú)足夠資源，Pi阻塞等待。（3）系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：Available［j］∶=Available［j］-Requesti[j］;Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;Need［i,j］∶=Need［i,j］-Requesti［j］;（4）系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來(lái)的資源分配狀態(tài)，讓進(jìn)程Pi等待。三、安全性算法（1）設(shè)置兩個(gè)向量：①工作向量Work:它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有m個(gè)元素，在執(zhí)行安全算法開(kāi)始時(shí)，Work∶=Available;②Finish:它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開(kāi)始時(shí)先做Finish［i］∶=false;當(dāng)有足夠資源分配給進(jìn)程時(shí)，再令Finish［i］∶=true。（2）從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程：①Finish［i］=false;②Need［i,j］≤Work［j］；若找到，執(zhí)行步驟(3)，否則，執(zhí)行步驟(4)。（3）當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：Work［j］∶=Work［i］+Allocation［i,j］;Finish［i］∶=true;gotostep2;（4）如果所有進(jìn)程的Finish［i］=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。【實(shí)驗(yàn)步驟】 參考實(shí)驗(yàn)步驟如下：（1）參考圖1-1所示流程圖編寫(xiě)安全性算法。NNY所有finish都為true？輸出安全序列NYN存在Finish[i]=false&&Need[i][j]<=Available[j]初始化Work和FinishFinish[i]=true，Work[j]=Work[j]+Allocation[i][j]所有進(jìn)程都找完了？Y開(kāi)始圖1-1安全性算法流程圖輸出系統(tǒng)不安全（2）編寫(xiě)統(tǒng)一的輸出格式。 每次提出申請(qǐng)之后輸出申請(qǐng)成功與否的結(jié)果。如果成功還需要輸出變化前后的各種數(shù)據(jù)，并且輸出安全序列。（3）參考圖1-2所示流程圖編寫(xiě)銀行家算法。（4）編寫(xiě)主函數(shù)來(lái)循環(huán)調(diào)用銀行家算法。結(jié)束結(jié)束否是申請(qǐng)失敗。以上分配作廢，恢復(fù)原來(lái)的分配狀態(tài)：Available[j]=Available[j]+Requesti[j]Allocation[i][j]=Allocation[i][j]－Requesti[j]Need[i][j]=Need[i][j]+Requesti[j]NYNYRequesti[j]>Need[i][j]出錯(cuò)返回：return(error)Requesti[j]>Available[j]出錯(cuò)返回：(進(jìn)程阻塞)return(error)Available[j]=Available[j]–Requesti[j]Allocation[i][j]=Allocation[i][j]+Requesti[j]Need[i][j]=Need[i][j]–Requesti[j]假定分配：輸入初始參數(shù)（資源分配及請(qǐng)求情況）開(kāi)始假定分配之后，系統(tǒng)安全嗎？申請(qǐng)成功。輸出各種數(shù)據(jù)的變化圖1-2銀行家算法流程圖【參考代碼】#include<iostream>#include<string.h>#include<stdio.h>#defineFalse0#defineTrue1usingnamespacestd;intMax[100][100]={0};//各進(jìn)程所需各類資源的最大需求intAvaliable[100]={0};//系統(tǒng)可用資源charname[100]={0};//資源的名稱intAllocation[100][100]={0};//系統(tǒng)已分配資源intNeed[100][100]={0};//還需要資源intRequest[100]={0};//請(qǐng)求資源向量inttemp[100]={0};//存放安全序列intWork[100]={0};//存放系統(tǒng)可提供資源intM=100;//進(jìn)程的最大數(shù)為intN=100;//資源的最大數(shù)為voidshowdata()//顯示資源矩陣{ inti,j; cout<<"系統(tǒng)目前可用的資源[Avaliable]:"<<endl; for(i=0;i<N;i++)cout<<name[i]<<""; cout<<endl; for(j=0;j<N;j++)cout<<Avaliable[j]<<"";//輸出分配資源 cout<<endl; cout<<"MaxAllocationNeed"<<endl; cout<<"進(jìn)程名"; for(j=0;j<3;j++){ for(i=0;i<N;i++) cout<<name[i]<<""; cout<<""; } cout<<endl; for(i=0;i<M;i++){ cout<<""<<i<<""; for(j=0;j<N;j++) cout<<Max[i][j]<<""; cout<<""; for(j=0;j<N;j++) cout<<Allocation[i][j]<<""; cout<<""; for(j=0;j<N;j++) cout<<Need[i][j]<<""; cout<<endl; }}voidchangdata(inti)//進(jìn)行資源分配{ intj; for(j=0;j<N;j++){ Avaliable[j]=Avaliable[j]-Request[j]; Allocation[i][j]=Allocation[i][j]+Request[j]; Need[i][j]=Need[i][j]-Request[j]; } }voiddeletejob(inti){intj,count=0; for(j=0;j<N;j++){ if(Need[i][j]==0) { count++; } } if(count==N) { cout<<"!!!!!!!!!!!!!此作業(yè)需求的資源已經(jīng)分配完畢，自動(dòng)釋放!!!!!!!!!!!!"<<endl; for(j=0;j<N;j++) { Avaliable[j]=Avaliable[j]+Allocation[i][j]; } M--; }}intsafe()//安全性算法{ inti,k=0,m,apply,Finish[100]={0}; intj; for(i=0;i<N;i++) { Work[i]=Avaliable[i]; } for(i=0;i<M;i++){ apply=0; for(j=0;j<N;j++){ if(Finish[i]==False&&Need[i][j]<=Work[j]){ apply++; if(apply==N){ for(m=0;m<N;m++) Work[m]=Work[m]+Allocation[i][m];//變分配數(shù) Finish[i]=True; temp[k]=i; i=-1; k++; } } } } for(i=0;i<M;i++){ if(Finish[i]==False){ cout<<"系統(tǒng)不安全"<<endl;//不成功系統(tǒng)不安全 return-1; } }cout<<"系統(tǒng)是安全的!"<<endl;//如果安全，輸出成功cout<<"分配的序列:"; for(i=0;i<M;i++){//輸出運(yùn)行進(jìn)程數(shù)組 cout<<temp[i]; if(i<M-1)cout<<"->"; } cout<<endl; return0;}voidshare()//利用銀行家算法對(duì)申請(qǐng)資源對(duì)進(jìn)行判定{ charch; inti=0,j=0; ch='y'; cout<<"請(qǐng)輸入要求分配的資源進(jìn)程號(hào)(0-"<<M-1<<"):";cin>>i;//輸入須申請(qǐng)的資源號(hào) cout<<"請(qǐng)輸入進(jìn)程"<<i<<"申請(qǐng)的資源:"<<endl; for(j=0;j<N;j++) { cout<<name[j]<<":"; cin>>Request[j];//輸入需要申請(qǐng)的資源 }for(j=0;j<N;j++){ if(Request[j]>Need[i][j])//判斷申請(qǐng)是否大于需求，若大于則出錯(cuò) { cout<<"進(jìn)程"<<i<<"申請(qǐng)的資源大于它需要的資源"; cout<<"分配不合理，不予分配！"<<endl; ch='n'; break; } else{if(Request[j]>Avaliable[j])//判斷申請(qǐng)是否大于當(dāng)前資源，若大于則 {//出錯(cuò) cout<<"進(jìn)程"<<i<<"申請(qǐng)的資源大于系統(tǒng)現(xiàn)在可利用的資源"; cout<<"分配出錯(cuò)，不予分配!"<<endl; ch='n'; break; } }}if(ch=='y'){ changdata(i);//根據(jù)進(jìn)程需求量變換資源 deletejob(i); showdata();//根據(jù)進(jìn)程需求量顯示變換后的資源 safe();//根據(jù)進(jìn)程需求量進(jìn)行銀行家算法判斷}}voidaddprocess(){//添加作業(yè)intflag=M; M=M+1; cout<<"請(qǐng)輸入該作業(yè)的最大需求量[Max]"<<endl; for(inti=0;i<N;i++){ cout<<name[i]<<":"; cin>>Max[flag][i]; Need[flag][i]=Max[flag][i]-Allocation[flag][i]; } showdata(); safe();}intmain()//主函數(shù){inti,j,number,choice,m,n,flag;charming; cout<<"\t"<<endl; cout<<"\t||||"<<endl; cout<<"\t||銀行家算法的實(shí)現(xiàn)||"<<endl; cout<<"\t||||"<<endl; cout<<"\t||binbinwangbin||"<<endl; cout<<"\t||||"<<endl; cout<<"\t||||"<<endl; cout<<"\t"<<endl; cout<<"請(qǐng)首先輸入系統(tǒng)可供資源種類的數(shù)量:"; cin>>n; N=n; for(i=0;i<n;i++) { cout<<"資源"<<i+1<<"的名稱:"; cin>>ming; name[i]=ming; cout<<"資源的數(shù)量:"; cin>>number; Avaliable[i]=number; } cout<<endl; cout<<"請(qǐng)輸入作業(yè)的數(shù)量:"; cin>>m; M=m; cout<<"請(qǐng)輸入各進(jìn)程的最大需求量("<<m<<"*"<<n<<"矩陣)[Max]:"<<endl; for(i=0;i<m;i++) for(j=0;j<n;j++) cin>>Max[i][j]; do{ flag=0; cout<<"請(qǐng)輸入各進(jìn)程已經(jīng)申請(qǐng)的資源量("<<m<<"*"<<n<<"矩陣)[Allocation]:"<<endl; for(i=0;i<m;i++) f