操作系統(tǒng)試驗報告-銀行家算法

操作系統(tǒng)實驗報告----銀行家算法班級：計算機03(7)班姓名：李君益學(xué)號：(61號)—提交日期：06.7.11指導(dǎo)老師：林穗一、設(shè)計題目加深了解有關(guān)資源申請、避免死鎖等概念，并體會和了解死鎖和避免死鎖的具體實施方法。要求編寫和調(diào)試一個系統(tǒng)動態(tài)分配資源的簡單模擬程序，觀察死鎖產(chǎn)生的條件，并采用銀行家算法，有效的防止和避免死鎖的發(fā)生。二、設(shè)計要求內(nèi)容：編制銀行家算法通用程序，并檢測思考題中所給狀態(tài)的安全性。要求：(1) 下列狀態(tài)是否安全？(三個進程共享12個同類資源)進程已分配資源數(shù)最大需求數(shù)114(狀態(tài)a)244358114246(狀態(tài)b)368(2) 考慮下列」系統(tǒng)狀態(tài)分配矩陣最大需求矩陣可用資源矩陣00120012152010001750135423560632065200140656問系統(tǒng)是否安全？若安全就給出所有的安全序列。若進程2請求(0420)，可否立即分配?三、設(shè)計分析關(guān)于操作系統(tǒng)的死鎖1、死鎖的產(chǎn)生計算機系統(tǒng)中有許多獨占資源，他們在任一時刻只能被一個進程使用，如磁帶機，繪圖儀等獨占型外圍設(shè)備，或進程表，臨界區(qū)等軟件資源。兩個進程同時向一臺打印機輸出將導(dǎo)致一片混亂，兩個進程同時進入臨界區(qū)將導(dǎo)致數(shù)據(jù)庫錯誤乃至程序崩潰。正因為這些原因，所有操作系統(tǒng)都具有授權(quán)一個進程獨立訪問某一辭源的能力。一個進程需要使用獨占型資源必須通過以下的次序：申請資源使用資源歸還資源若申請施資源不可用，則申請進程進入等待狀態(tài)。對于不同的獨占資源，進程等待的方式是有差別的，如申請打印機資源、臨界區(qū)資源時，申請失敗將一位這阻塞申請進程；而申請打開文件文件資源時，申請失敗將返回一個錯誤碼，由申請進程等待一段時間之后重試。只得指出的是，不同的操作系統(tǒng)對于同一種資源采取的等待方式也是有差異的。在許多應(yīng)用中，一個進程需要獨占訪問多個資源，而操作系統(tǒng)允許多個進程并發(fā)執(zhí)行共享系統(tǒng)資源時，此時可能會出現(xiàn)進程永遠(yuǎn)被阻塞的現(xiàn)象。這種現(xiàn)象稱為“死鎖”。2.死鎖的定義一組進程處于死鎖狀態(tài)是指：如果在一個進程集合中的每個進程都在等待只能由該集合中的其他一個進程才能引發(fā)的時間，則稱一組進程或系統(tǒng)此時發(fā)生了死鎖。3,死鎖的防止a.死鎖產(chǎn)生的條件：互斥條件占有和等待條件不剝奪條件循環(huán)等待條件以上三個條件是死鎖存在的必要條件，膽不是充分條件。第四個條件是錢嗩吶個條件同時存在時產(chǎn)生的結(jié)果，所以，這些條件并不完全獨立。但單獨考慮每個條件是有用的，只要能破壞這四個必要條件之一，死鎖就可以防止。匕實用死鎖防止方法靜態(tài)分配策略層次分配策略4,死鎖的避免破壞死鎖的四個條件之一能防止系統(tǒng)發(fā)生死鎖，但這會導(dǎo)致低效率的進程運行和資源使用率。死鎖的避免則相反，他允許系統(tǒng)中同時存在三個必要條件，如果能掌握并發(fā)進程中與每個進程有關(guān)的資源動態(tài)申請情況，做出明智和合理的選擇，仍然可以避免死鎖的發(fā)生。每當(dāng)在為申請者分配資源前先測試系統(tǒng)狀態(tài)，若把資源分配個申請者會產(chǎn)生死鎖的話，則拒絕分配，否則接受申請，為它分配資源。死鎖避免不是通過隊進程隨意強加一些規(guī)則，而是通過對每一次資源申請進行認(rèn)真的分析來判斷它是否能安全的分配。問題是：是否存在一種算法總能做出正確的選擇從而避免死鎖？

二,單種資源的銀行彖算法Dijkstra(1965)提出了一種能夠避免死鎖的調(diào)度方法，稱為一銀行家算法。它的模型基于一個小城鎮(zhèn)的銀行家，現(xiàn)將該算法描述如下：假定一個銀行家擁有資金，數(shù)量為笈，被Nj客戶共享。銀行家對客戶提出下列約束條件：每個客戶必須預(yù)先說明自己所要求的最大資金量；每個客戶每次提出部分資金量申請和獲得分配；如果銀行滿足了客戶對資金的最大需求量，那么，客戶在資金運作后，應(yīng)在有限時間內(nèi)歸還銀行。只要每個客戶遵守上述約束，銀行家將保證做到：若一個客戶所要求的最大資金量不超過笈，則銀行一定接納該客戶，并可處理他的資金需求；銀行在受到一個客戶的資金申請是，可能因資金不足而讓客戶等待，但保證在有限時間內(nèi)讓客戶獲得現(xiàn)金。在銀行彖算法中，客戶可看作進程，資金可看作資源，銀行家可看作操作系統(tǒng)名字已使用最大名字 已使 用Andy06Barbara05Marvin名字已使用最大名字 已使 用Andy06Barbara05Marvin04Suzanne07名字已使用最大Andy16Barbara15Marvin24Suzanne47Andy16Barbara25Marvin24Suzanne47最大可用：10安全可用：2 可用：1安全 不安全銀行家算法就是對每一個請求進行檢查，檢查這次資源申請是否會導(dǎo)致不安全狀態(tài)，若是，則不滿足該請求，否則便滿足。檢查狀態(tài)是否安全的方法是看他是否有足夠的資源滿足一個距最大需求最近的客戶，如此反復(fù)下去。如果所有投資都最終被收回，則該狀態(tài)是安全的，最初的請求可以批準(zhǔn)。三, 多種資源的銀行彖算法銀行彖算法可以被推廣用來處理系統(tǒng)中有任意數(shù)目的進程，任意種類的資源，并且每種資源有多個實例的情況。下圖示出了其工作原理：

進程磁帶機繪圖儀打印機cd-rom進程磁帶機繪圖儀打印機cd-rom進程磁帶機繪圖儀打印機cd-rom進程磁帶機繪圖儀打印機cd-romA3011B0100C1110D1101E0000A1100B0112C3100D0010E2110已分配的資源仍需要的資源已分配的資源檢查一個狀態(tài)是否安全的步驟如下：查找右邊矩陣是否有一行，其未被滿足的設(shè)備數(shù)均小于或等于向量A。如果找不到，則系統(tǒng)將死鎖，因為任何進程都無法運行結(jié)束。若找到這樣一行，則可以假設(shè)它獲得所需的資源并運行結(jié)束，將該進程標(biāo)記為結(jié)束，并將資源加到向量A上。重復(fù)以上兩步，知道所有的進程都標(biāo)記為結(jié)束。若達(dá)到所有進程結(jié)束，則狀態(tài)示安全的，否則將發(fā)生死鎖。如果在第一步中同時存在若干進程均符合條件，則不管挑選哪一個運行都沒有關(guān)系，因為，可用資源或者將增多，或者在最壞的情況下保持不變。圖中所示的狀態(tài)示安全的，進程B現(xiàn)在再申請一臺打印機，可以滿足它的請求，而且保持系統(tǒng)狀態(tài)仍然示安全的(進程口可以結(jié)束，然后是人或E,剩下的進程最后結(jié)束)。假設(shè)進程B獲得一臺打印機后，E試圖獲得最后的一臺打印機，若分配給￡,可用資源向量將減到1000,這時將導(dǎo)致死鎖，顯然E的請求不能立即滿足，必須延遲一段時間。該算法最早由Dijkstra于1965年發(fā)表。從那以后幾乎每本操作系統(tǒng)的專著都詳細(xì)的描述它，許多論文的內(nèi)容也圍繞該算法討論，其主要優(yōu)點是不需要死領(lǐng)預(yù)防中加上的種種限制，如資源剝奪或重新運行進程。但很少由作者指出該算法缺乏實用價值。因為，進程很難在運行前就知道其所需資源的最大量；而且系統(tǒng)中的進程必須是無關(guān)的，相互之間沒有同步要求；進程的個數(shù)和分配的資源數(shù)目應(yīng)該是固定的。這些要求往往事先難以滿足。1.實現(xiàn)原理.數(shù)據(jù)結(jié)構(gòu)假設(shè)有n個進程m類資源，則有如下數(shù)據(jù)結(jié)構(gòu)：MAX[n*m]n個進程對m類資源的最大需求量AVAILABLE[m]系統(tǒng)可用資源數(shù)ALLOCATION[n*m]n個進程已經(jīng)得到m類資源的資源量NEED[n*m]n個進程還需要m類資源的資源量.銀行家算法設(shè)進程I提出請求Request[m]，則銀行家算法按如下規(guī)則進行判斷。⑴如果Request[m]<=NEED[I，m]，則轉(zhuǎn)(2)；否則，出錯。(2)如果Request[m]<=AVAILABLE，則轉(zhuǎn)(3)；否則，出錯。⑶系統(tǒng)試探分配資源，修改相關(guān)數(shù)據(jù)：AVAILABLE=AVAILABLE-REQUESTALLOCATION=ALLOCATION+REQUESTNEED=NEED-REQUEST(4)系統(tǒng)執(zhí)行安全性檢查，如安全，則分配成立；否則試探險性分配作廢，系統(tǒng)恢復(fù)原狀，進程等待。3.安全性檢查(1)設(shè)置兩個工作向量WORK=AVAILABLE；FINISH[n]=FALSE(2)從進程集合中找到一個滿足下述條件的進程，F(xiàn)INISH[i]=FALSENEED<=WORK如找到，執(zhí)行(3)；否則，執(zhí)行(4)⑶設(shè)進程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。WORK=WORK+ALLOCATIONFINISH=TRUEGOTO2(4)如所有的進程Finish[n]=true,則表示安全；否則系統(tǒng)不安全。2、程序執(zhí)行過程

四、程序代碼設(shè)計思路設(shè)計進程對各在資源最大申請表示及初值確定。設(shè)定系統(tǒng)提供資源初始狀態(tài)。設(shè)定每次某個進程對各類資源的申請表示。編制程序，依據(jù)銀行家算法，決定其申請是否得到滿足。主要數(shù)據(jù)結(jié)構(gòu)假設(shè)有M個進程N類資源，則有如下數(shù)據(jù)結(jié)構(gòu)：MAX[M*N]M個進程對N類資源的最大需求量AVAILABLE[N]系統(tǒng)可用資源數(shù)ALLOCATION[M*N]M個進程已經(jīng)得到N類資源的資源量NEED[M*N]M個進程還需要N類資源的資源量主要代碼結(jié)枸voidmain。voidinit()intfenpei()intshq()源程序#include<stdio.h>#include<conio.h>#include<iostream.h>typedefstructMax1(intm_a;intm_b;intm_c;intm_d;}Max;typedefstructAllocation1inta_a;inta_b;inta_c;inta_d;}Allocation;typedefstructNeedl(intn_a;intn_b;intn_c;intn_d;}Need;structAvailablel(intav_aintav_bintav_cintav_d}q;structpr(charname;Maxmax;Allocationallocation;Needneed;intfinishflag;}p[5];charna[5];//*****************************voidinitCy/讀入(printfC各進程的NEED：\n");FILE*fp;fp=fopen("",“r+”)；for(inti=0;i<5;i++)fscanf(fp,"%c,%d,%d,%d,%d,%d,%d,%d,%d\n",&p[i].name,&p[i].max.m_a,&p[i].max.m_b,&p[i].max.m_c,&p[i].max.m_d,&p[i].allocation.a_a,&p[i].allocation.a_b,&p[i].allocation.a_c,&p[i].allocation.a_d);p[i].need.n_a=p[i].max.m_a-p[i].allocation.a_a;p[i].need.n_b=p[i].max.m_b-p[i].allocation.a_b;p[i].need.n_c=p[i].max.m_c-p[i].allocation.a_c;p[i].need.n_d=p[i].max.m_d-p[i].allocation.a_d;printf("%c:%d,%d,%d,%d\n",p[i].name,p[i].need.n_a,p[i].need.n_b,p[i].need.n_c,p[i].need.n_d)；)fclose(fp);)mmm***intfenpeiOZ/分配(printf("Available:\n");printf("%d,%d,%d,%d\nH,q.av_a,q.av_b,q.av_c,q.av_d);intfinishcnt=0,k=0,count=0;for(intj=0;j<5;j++)p[j].finishflag=0;while(finishcnt<5)(for(inti=0;i<5;i++)(if(p[i].finishflag==0&&q.av_a>=p[i].need.n_a&&q.av_b>=p[i].need.n_b&&q.av_c>=p[i].need.n_c&&q.av_d>=p[i].need.n_d)(q.av_a+=p[i].allocation.a_a;q.av_b+=p[i].allocation.a_b;q.av_c+=p[i].allocation.a_c;q.av_d+=p[i].allocation.a_d;p[i].finishflag=1;finishcnt++;na[k++]=p[i].name;break;})count++;//禁止循環(huán)過多if(count>5)return0;}return1;//*****************************intshq()(intm,i,j,k,l;printf("請輸入進程號和請求資源！例如:題目要求：1 0420(進程號和資源之間3個空格)\n");scanf(”％d%d%d%d%d”,&m,&i,&j,&k,&l);if(i<=p[m].need.n_a&&j<=p[m].need.n_b&&k<=p[m].need.n_c&&l<=p[m].need.n_d)(if(i<=q.av_a&&j<=q.av_b&&k<=q.av_c&&l<=q.av_d)(p[m].allocation.a_a+=i;p[m].allocation.a_b+=j;p[m].allocation.a_c+=k;p[m].allocation.a_d+=l;p[m].need.n_a=p[m].max.m_a-p[m].allocation.a_a;p[m].need.n_b=p[m].max.m_b-p[m].allocation.a_b;p[m].need.n_c=p[m].max.m_c-p[m].allocation.a_c;p[m].need.n_d=p[m].max.m_d-p[m].allocation.a_d;printfC各進程的NEED:\n");for(intw=0;w<5;w++)printf("%c:%d,%d,%d,%d\n",p[w].name,p[w].need.n_a,p[w].need.n_b,p[w].need.n_c,p[w].need.n_d);return1;)elseprintf("Request>Available\n讓%心等待......\n",p[m].name);)elseprintf("Request>Need\n讓%?等待 \n",p[m].name);return0;)//*****************************voidmain()(intflag;charc;cout<<"\n\n\n\n\n\n\n\n\n\t ";for(inti=0;i<30;i++)cout<<"*";cout<<endl<<"\t"<<" 操作系統(tǒng) -\n"<<endl;cout<<endl<<"\t"<<" 銀行家算法 -\n"<<endl;cout<<endl<<"\t"<<" 姓名:李君益 \n"<<endl;cout<<endl<<"\t"<<" 學(xué)號: \n"<<endl;cout<<endl<<Rt"<<“ 日期:06.7.11 \n"<<endl;printf("\t ");for(i=0;i<30;i++)printf("*");printf("\n\n\n\n\n");getch();printf("\t 請確認(rèn)已經(jīng)在C”中正確輸入各進程的有關(guān)信息\n");getch();init();q.av_a=3;q.av_b=14;q.av_c=12;q.av_d=12;while(flag)(for(i=0;i<5;i++)(q.av_a-=p[i].allocation.a_a;q.av_b-=p[i].allocation.a_b;q.av_c-=p[i].allocation.a_c;q.av_d-=p[i].allocation.a_d;)if(fenpei())(printf(%n這樣配置資源是安全的\n");printf("其安全序列是：");for(intl=0;l<5;l++)printf("-->%c",na[l]);printf("\n");printf('*有進程發(fā)出Request請求向量嗎 (EnteryorY)\n");c=getch();if(c=='y'||c=='Y')(if(shq())continue;elsebreak;}elseflag=0;)else{flag=0;printf("不安全5");}

五、執(zhí)行結(jié)果和結(jié)果分析1.程序運行還是介面如下:2單資源狀態(tài)a情況下列狀態(tài)是否安全？（三個進程共享12個同類資源）進程已分配資源數(shù)最大需求數(shù)進程已分配資源數(shù)4 （狀態(tài)a）4在文件里面輸入以上內(nèi)容，點擊單資源狀態(tài)a.exe運行，顯示如下:經(jīng)過驗證狀態(tài)a情況是安全的

3單資源狀態(tài)b情況下列狀態(tài)是否安全？（三個進程共享12個同類資源）（狀態(tài)b）在文件里面輸入以上內(nèi)容，點擊單資源狀態(tài)b.exe運行，顯示如下:經(jīng)過驗證狀態(tài)b情況是不安全的最大需求矩陣0012最大需求矩陣00121750235606520656可用資源矩陣15204考慮下列系統(tǒng)狀態(tài)分配矩陣00121000135406320014問系統(tǒng)是否安全？若安全就給出所有的安全序列。若進程2請求(0420),可否立即分配?在文件里面輸入以上內(nèi)容，點擊多資源狀態(tài).exe運行，顯示如下:

SC:\DotunientsandButting式君益\桌面\李君益\銀行家、多資源狀喜、多費蠹狀喜學(xué)號:3i03酗5119日期:06.7.U同進程的meed：卜:見見見后b：0r同進程的meed：卜:見見見后b：0r7,5,0L：：ir0r0r2d：0r0r2r0,：0,6,4,2Hva.ila.ble：1,5,2,0請確認(rèn)已經(jīng)在“input.tmQ，中正確輸入若進程的各進程的血電a：0,0,l,2b：lJ.7J.5J.0ciSj-Sj-Ej-G自Kjallocation：a：0,0,l,2b：l,0,0,0c=1,3,5,4d-0,61r31r2e=0,0,l,4蟀隹耶篁貨源是安全的出Reqiw"請求向量嗎？？？CEnteryof￥>其女全序列是！ 一>a->c--出Reqiw"請求向量嗎？？？CEnteryof￥>按題目要求進程2申請資源04