2024年銀行家算法實(shí)驗(yàn)報(bào)告完整版

操作系統(tǒng)試驗(yàn)報(bào)告課題：銀行家算法專業(yè)：班級(jí)：學(xué)號(hào)：姓名：年月日目錄HYPERLINK一試驗(yàn)?zāi)繕?biāo) ……………………3HYPERLINK二試驗(yàn)內(nèi)容………3HYPERLINK三問題描述 ……………………3HYPERLINK四設(shè)計(jì)思緒 ………4HYPERLINK五詳細(xì)設(shè)計(jì) ……………………5HYPERLINK六運(yùn)行成果 …………………10HYPERLINK七心得體會(huì) ……………………16HYPERLINK八參考文獻(xiàn)………17HYPERLINK附源程序………17一、試驗(yàn)?zāi)繕?biāo)模擬實(shí)現(xiàn)銀行家算法，用銀行家算法實(shí)現(xiàn)資源分派。1．加深了解有關(guān)資源申請(qǐng)、防止死鎖等概念。2．體會(huì)和了解死鎖和防止死鎖的詳細(xì)實(shí)行措施。3、輸入：1.系統(tǒng)中各類資源表2.每個(gè)進(jìn)程需要各類資源總數(shù)系統(tǒng)分派給各個(gè)進(jìn)程各類資源數(shù)4、輸出：1.判斷T0時(shí)刻的安全性2.假如系統(tǒng)是安全的，任意給出某個(gè)進(jìn)程的一個(gè)資源祈求方式并判斷系統(tǒng)能否接收此祈求，假如能夠接收，其輸出所有安全序列，反之，不予分派。二、試驗(yàn)內(nèi)容1．設(shè)計(jì)進(jìn)程對(duì)各類資源最大申請(qǐng)表示及初值確實(shí)定。2．設(shè)定系統(tǒng)提供資源的初始情況。3．設(shè)定每次某個(gè)進(jìn)程對(duì)各類資源的申請(qǐng)表示。4．編制程序，依據(jù)銀行家算法，決定其資源申請(qǐng)是否得到滿足。5．顯示資源申請(qǐng)和分派時(shí)的變化情況。三、問題描述銀行家算法.顧名思義是起源于銀行的借貸業(yè)務(wù)，一定數(shù)量的本金要應(yīng)多個(gè)客戶的借貸周轉(zhuǎn)，為了預(yù)防銀行加資金無法周轉(zhuǎn)而倒閉，對(duì)每一筆貸款，必須考查其是否能限期償還。在操作系統(tǒng)中研究資源分派方略時(shí)也有類似問題，系統(tǒng)中有限的資源要供多個(gè)進(jìn)程使用，必須確保得到的資源的進(jìn)程能在有限的時(shí)間內(nèi)償還資源，以供其他進(jìn)程使用資源。假如資源分派不得到就會(huì)發(fā)生進(jìn)程循環(huán)等候資源，則進(jìn)程都無法繼續(xù)執(zhí)行下去的死鎖現(xiàn)象。在死鎖的防止中，銀行家算法把系統(tǒng)狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)一直處在安全狀態(tài)，便能夠防止發(fā)生死鎖。所謂安全狀態(tài)，是指系統(tǒng)能按某種次序?yàn)槊總€(gè)進(jìn)程分派所需資源，直到最大需求，使每一個(gè)進(jìn)程都能夠順利完成，即可找到一個(gè)安全資源分派序列。模擬實(shí)現(xiàn)這個(gè)工作過程。四、設(shè)計(jì)思緒我們能夠把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相稱于銀行家管理的資金，進(jìn)程向操作系統(tǒng)祈求分派資源相稱于用戶向銀行家貸款。操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分派資源，當(dāng)進(jìn)程初次申請(qǐng)資源時(shí)，要測(cè)試該進(jìn)程對(duì)資源的最大需求量，假如系統(tǒng)現(xiàn)存的資源能夠滿足它的最大需求量則按目前的申請(qǐng)量分派資源，否則就推遲分派。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請(qǐng)資源時(shí)，先測(cè)試該進(jìn)程已占用的資源數(shù)與本次申請(qǐng)的資源數(shù)之和是否超出了該進(jìn)程對(duì)資源的最大需求量。若超出則拒絕分派資源，若沒有超出則再測(cè)試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則按目前的申請(qǐng)量分派資源，否則也要推遲分派。銀行家算法是一個(gè)最具代表性的防止死鎖的算法。要解釋銀行家算法，必須先解釋操作系統(tǒng)的安全狀態(tài)和不安全狀態(tài)。安全狀態(tài)：假如存在一個(gè)由系統(tǒng)中所有進(jìn)程組成的安全序列P1，…，Pn，則系統(tǒng)處在安全狀態(tài)。安全狀態(tài)一定沒有死鎖發(fā)生。不安全狀態(tài)：不存在一個(gè)安全序列。不安全狀態(tài)不一定導(dǎo)致死鎖。安全序列：一個(gè)進(jìn)程序列{P1，…，Pn}是安全的，假如對(duì)于每個(gè)進(jìn)程Pi（0≤i≤n），它以后尚需要的資源量不超出系統(tǒng)目前剩余資源量與所有進(jìn)程Pj（j＜i）目前占有資源量之和。先對(duì)系統(tǒng)從源文獻(xiàn)中讀取的數(shù)據(jù)進(jìn)行安全性判斷，然后對(duì)用戶提出的祈求進(jìn)行合法性檢查，即檢查祈求的是小于需要的，小于系統(tǒng)可利用的資源。若祈求合法，則進(jìn)行試分派，最后對(duì)試分派狀態(tài)調(diào)用安全性算法進(jìn)行安全性檢查。若安全，則分派，否則，不分派，恢復(fù)本來狀態(tài)，拒絕申請(qǐng)。五、詳細(xì)設(shè)計(jì)1、初始化由用戶輸入數(shù)據(jù)，分別對(duì)可利用資源向量矩陣AVAILABLE、最大需求矩陣MAX、分派矩陣ALLOCATION、需求矩陣NEED賦值。

2、銀行家算法在防止死鎖的措施中，所施加的限制條件較弱，有也許取得令人滿意的系統(tǒng)性能。在該措施中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)一直都處在安全狀態(tài)，便能夠防止發(fā)生死鎖。銀行家算法的基本思想是分派資源之前,判斷系統(tǒng)是否是安全的;若是,才分派。設(shè)進(jìn)程cusneed提出祈求REQUEST[i]，則銀行家算法按如下規(guī)則進(jìn)行判斷。(1)假如REQUEST[cusneed][i]<=NEED[cusneed][i]，則轉(zhuǎn)(2)；否則，犯錯(cuò)。(2)假如REQUEST[cusneed][i]<=AVAILABLE[cusneed][i]，則轉(zhuǎn)(3)；否則，犯錯(cuò)。(3)系統(tǒng)試探分派資源，修改有關(guān)數(shù)據(jù)：AVAILABLE[i]-=REQUEST[cusneed][i];ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];NEED[cusneed][i]-=REQUEST[cusneed][i];(4)系統(tǒng)執(zhí)行安全性檢查，如安全，則分派成立；否則試探險(xiǎn)性分派作廢，系統(tǒng)恢復(fù)原狀，進(jìn)程等候。(5)對(duì)于某一進(jìn)程i，若對(duì)所有的j，有NEED[i][j]=0，則表此進(jìn)程資源分派完成，應(yīng)將占用資源釋放。3、安全性檢查算法(1)設(shè)置兩個(gè)工作向量Work=AVAILABLE;FINISH(2)從進(jìn)程集合中找到一個(gè)滿足下述條件的進(jìn)程，F(xiàn)INISH==false;NEED<=Work;如找到，執(zhí)行(3)；否則，執(zhí)行(4)(3)設(shè)進(jìn)程取得資源，可順利執(zhí)行，直至完成，從而釋放資源。Work+=ALLOCATION;Finish=true;GOTO2(4)如所有的進(jìn)程Finish=true，則表示安全；否則系統(tǒng)不安全。4、流程圖1、整體流程圖開始開始錄入祈求資源數(shù)REQUEST[i]>NEED[i]或者REQUEST[i]>AVAILABLE[i]報(bào)錯(cuò)，重新輸入AVAILABLE[i]-=REQUEST[i];

ALLOCATION[i]+=REQUEST[i];

NEED[i]-=REQUEST[i];初始化安全性檢查安全AVAILABLE[i]+=REQUEST[i];

ALLOCATION[i]-=REQUEST[i];

NEED[i]+=REQUEST[i];保持原分派進(jìn)程執(zhí)行完釋放資源繼續(xù)分派結(jié)束YESNOYESNOYESYESNONO2、判斷系統(tǒng)的安全性Safe（）六、運(yùn)行成果1、系統(tǒng)不安全的輸入（1）、本程序按下圖建立.txt源文獻(xiàn)，作為程序的初始化輸入（2）執(zhí)行程序，讀取源文獻(xiàn)，并判斷T0時(shí)刻所得成果:2.系統(tǒng)安全的輸入（1）、本程序按下圖建立.txt源文獻(xiàn)，作為程序的初始化輸入（2）執(zhí)行程序，讀取源文獻(xiàn)，并判斷T0時(shí)刻所得成果:（3）T0時(shí)刻的安全序列（4）不合理的分派輸入P1進(jìn)程Request（221）與輸入P2進(jìn)程Request（222）所得祈求成果：（5）合理的分派1.存在安全序列：調(diào)用Request（）函數(shù)，測(cè)試該函數(shù)的可行性，如輸入P1進(jìn)程Request（012），所得成果：2、不存在安全序列輸入P0進(jìn)程Request（020），所得成果:七、心得體會(huì)本次試驗(yàn)讓我對(duì)銀行家算法和死鎖都有了一定的了解。懂得了在資源一定的條件下為了讓多個(gè)進(jìn)程都能使用資源完成任務(wù)，防止死鎖的產(chǎn)生能夠從一開始就對(duì)系統(tǒng)進(jìn)行安全性檢查來判斷是否將資源分派給正在祈求的進(jìn)程。不過銀行家算法會(huì)加大系統(tǒng)的開銷。另外，存在如下疑問，在系統(tǒng)不分派進(jìn)程所祈求的資源的時(shí)候，是否會(huì)將此資源等候，直到擁有足夠的資源的時(shí)候再來運(yùn)行？進(jìn)程會(huì)祈求資源是指在執(zhí)行的過程中只有擁有了足夠數(shù)量的資源才能夠執(zhí)行下去，不過資源有限，進(jìn)程數(shù)又有足夠多，我們期望所有進(jìn)程都能夠在最短的時(shí)間內(nèi)執(zhí)行完。也許能夠這么了解。操作系統(tǒng)的基本特性就是并發(fā)和共享，系統(tǒng)允許多個(gè)進(jìn)程并發(fā)執(zhí)行，并且共享系統(tǒng)的軟、硬件資源。為了最大程度的利用計(jì)算機(jī)資源，操作系統(tǒng)應(yīng)采取動(dòng)態(tài)分派的方略，不過這么就輕易因資源不足、分派不當(dāng)而引起“死鎖”。本次課程設(shè)計(jì)就是用銀行家算法來防止“死鎖”。該算法就是一個(gè)資源分派過程，使分派序列不會(huì)產(chǎn)生死鎖。此算法的中心思想就是，每次分派后總存在著一個(gè)進(jìn)程，假如讓它單獨(dú)的運(yùn)行下去，必然能夠取得它所需要的所有資源，而它結(jié)束后能夠償還此類資源以滿足其他申請(qǐng)者的需要。另外，我懂得了在程序進(jìn)行編寫之前，先對(duì)程序的要求進(jìn)行分析，搞清楚程序所需要的功效，然后將每個(gè)功效提成一個(gè)功效模塊即調(diào)用函數(shù)來實(shí)現(xiàn)，無需過多的畫蛇添足。參考資料【1】《計(jì)算機(jī)操作系統(tǒng)》（第三版）湯小丹、梁紅兵、湯子瀛、哲鳳屏等西安電子科技大學(xué)出版社-05

【2】《C++Primer中文版》（第4版）（美）StanleyB.Lippman

等著

李師賢等譯.人民郵電出版社,-03-01【3】《C++Primer習(xí)題解答》（第4版）蔣愛軍，李師賢，梅曉勇

著人民郵電出版社-02-01【4】《當(dāng)代操作系統(tǒng)》（原書第3版）塔嫩鮑姆（Tanenbaum.A.S），陳向群，馬洪兵

著機(jī)械工業(yè)出版社-07-01【5】《計(jì)算機(jī)操作系統(tǒng)教程》張堯?qū)W，史美林，張高清華大學(xué)出版社-10-01【6】《數(shù)據(jù)結(jié)構(gòu)（STL框架）》王曉東

著清華大學(xué)出版社-09-01【7】《計(jì)算機(jī)操作系統(tǒng)（第三版）》湯子瀛等西安電子科技大學(xué)出版社-05【8】《操作系統(tǒng)試驗(yàn)教程——基于windows和Linux》秦明等\o"清華大學(xué)"清華大學(xué)出版社-09-01

附：源程序#include<fstream.h>#include<stdio.h>#include<stdlib.h>#defineM10//最大進(jìn)程數(shù)#defineN3//系統(tǒng)所擁有的資源類型intMax[M][N];//進(jìn)程對(duì)各類資源的最大需求intAllocation[M][N];//系統(tǒng)已為進(jìn)程所分派的各類資源數(shù)intNeed[M][N];//運(yùn)行進(jìn)程尚需的各類資源數(shù)intWork[N];//運(yùn)行進(jìn)程時(shí)系統(tǒng)所擁有的資源數(shù)boolfinish[M];//表示系統(tǒng)是否有足夠的資源分派給進(jìn)程intAvailable[N];//系統(tǒng)可利用的資源數(shù)intn_pro=0;//進(jìn)程的數(shù)目intflag[M]={-1};//用于標(biāo)識(shí)安全序列intReadfile();//從磁盤讀文獻(xiàn)intSafe1(intflag[],intn,intt);//輸出所有安全狀態(tài)voidshow();intSafe();//判斷系統(tǒng)是否處在安全狀態(tài)intRequest();//祈求資源分派函數(shù)voidshow(){ printf("\t%-9s\t%-9s\t%-9s\n","MAX","Allocation","Need"); printf("\tABC\tABC\tABC\n"); for(inti=0;i<n_pro;i++) { printf("p%d\t%d%4d%4d\t",i,Max[i][0],Max[i][1],Max[i][2]); printf("%d%4d%4d\t",Allocation[i][0],Allocation[i][1],Allocation[i][2]); printf("%d%4d%4d\n",Need[i][0],Need[i][1],Need[i][2]); } printf("系統(tǒng)可利用資源數(shù):\n"); printf("\tA\tB\tC\n"); printf("\t%d\t%d\t%d\n",Available[0],Available[1],Available[2]);}intReadfile()//從磁盤讀文獻(xiàn){ inti=0,j=0;//i表進(jìn)程，j表資源 ifstreaminFile;//文獻(xiàn) inFile.open("test.txt");//打開輸入文獻(xiàn)，按照要求的格式提取線程等信息 for(j=0;j<N;j++) inFile>>Available[j]; inFile.get(); printf("系統(tǒng)最大資源數(shù):\n"); printf("\tA\tB\tC\n"); printf("\t%d\t%d\t%d\n",Available[0],Available[1],Available[2]); inFile>>n_pro; inFile.get(); printf("目前進(jìn)程的數(shù)目:%d\n",n_pro); while(i<n_pro)//提取進(jìn)程的有關(guān)資源信息 { for(j=0;j<N;j++) inFile>>Max[i][j]; for(j=0;j<N;j++) inFile>>Allocation[i][j]; for(j=0;j<N;j++) { Need[i][j]=Max[i][j]-Allocation[i][j]; Available[j]-=Allocation[i][j]; } i++; } for(j=0;j<N;j++) Work[j]=Available[j]; printf("顯示初始化資源分派表:\n"); show(); printf("\n"); return0;}intSafe()//判斷系統(tǒng)是否是安全的{ inttempn=n_pro; inti=0,j=0,t=0; for(i=0;i<n_pro;i++) finish[i]=false; while(tempn) { for(i=0;i<n_pro;i++) { if(!finish[i]) { inttp=0;//注釋部分用于調(diào)試程序// printf("%d\t%d%4d%4d\t",i,Work[0],Work[1],Work[2]);// printf("%d%4d%4d\n",Need[i][0],Need[i][1],Need[i][2]); tp=(Work[0]>=Need[i][0])&&(Work[1]>=Need[i][1])&&(Work[2]>=Need[i][2]); if(tp) { finish[i]=true; for(intj=0;j<N;j++) Work[j]+=Allocation[i][j]; flag[t]=i;// printf("%d\tflag[%d]=%d",i,t,flag[t]);system("pause");printf("\n");t++; break; } } } tempn--; } for(i=0;i<n_pro;i++) if(finish[i]==false){printf("系統(tǒng)不安全,不存在安全序列\(zhòng)n");return-1;} printf("系統(tǒng)是安全的,存在安全序列:\n"); for(j=0;j<N;j++) Work[j]=Available[j]; Safe1(flag,n_pro,0); printf("\n"); return0;}intSafe1(intflag[],intn,intt){ intp,i,j,k;//p為標(biāo)識(shí) inttemp[N];//暫時(shí)數(shù)組 for(i=0;i<n;i++) { inttp=0; tp=(Work[0]>=Need[i][0])&&(Work[1]>=Need[i][1])&&(Work[2]>=Need[i][2]); if(tp) { for(j=0;j<N;j++) Work[j]+=Allocation[i][j]; flag[t]=i; p=1; } elsecontinue; for(intj=0;j<t;j++) if(flag[t]==flag[j]) { for(j=0;j<N;j++) Work[j]-=Allocation[i][j]; p=0;break; } if(p==1) { if(t==n-1) { for(k=0;k<n;k++) printf("p%-5d",flag[k]); printf("\n"); } else { for(k=0;k<N;k++) temp[k]=Work[k]-Allocation[i][k]; Safe1(flag,n,t+1); for(k=0;k<N;k++) Work[k]=temp[k]; } } } return0;}intRequest()//進(jìn)程提出祈求后，判斷系統(tǒng)能否將資源分派給它{ intrq;//下標(biāo) intRequest[N]; printf("請(qǐng)輸入需要祈求的進(jìn)程號(hào)(0~4):"); scanf("%d",&rq); printf("請(qǐng)輸入需要祈求的資源數(shù)(ABC):"); scanf("%d%d%d",&Request[0],&Request[1],&Request[2]); if(Need[rq][0]<Request[0]||Need[rq][1]<Request[1]||Need[rq][2]<Request[2]) { printf("進(jìn)程p%d申請(qǐng)的資源不小于它所需要的資源\n分派不合理，不予分派\n\n",rq); return-1; } if(Available[0]<Request[0]||Available[1]<Request[1]||Available[2]<Request[2]) { printf("進(jìn)程p%d申請(qǐng)的資源不小于系統(tǒng)目前可利用的資源\n分派不合理，不予分派\n\n",rq); return-1; } for(intj=0;j<N;j++) { Available[j]-=Request[j]; Allocation[rq][j]+=Request[j]; Need[rq][j]-=Request[