實(shí)驗(yàn)二(銀行家算法)

實(shí)驗(yàn)二死鎖的防止――銀行家算法實(shí)驗(yàn)?zāi)康恼莆账梨i產(chǎn)生的原因。掌握銀行家算法。能使用高級(jí)語(yǔ)言模擬實(shí)現(xiàn)銀行家算法。相關(guān)數(shù)據(jù)結(jié)構(gòu)可利用資源向量Available，它是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源的數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源數(shù)目。其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。如果Available[j]=k，標(biāo)是系統(tǒng)中現(xiàn)有j類資源k個(gè)。最大需求矩陣Max，這是一個(gè)n×m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Max[i][j]=k，表示進(jìn)程i需要j類資源的最大數(shù)目為k。分配矩陣Allocation，這是一個(gè)n×m的矩陣，它定義了系統(tǒng)中的每類資源當(dāng)前分配到每一個(gè)進(jìn)程的資源數(shù)。如果Allocation[i][j]=k，表示進(jìn)程i當(dāng)前已經(jīng)分到j(luò)類資源的數(shù)目為k個(gè)。Allocation[i]表示進(jìn)程i的分配向量。需求矩陣Need，這是一個(gè)n×m的矩陣，用以表示每個(gè)進(jìn)程還需要的各類資源的數(shù)目。如果Need[i][j]=k，表示進(jìn)程i還需要j類資源k個(gè)，才能完成其任務(wù)。Need[i]表示進(jìn)程i的需求向量。上述三個(gè)矩陣間存在關(guān)系：Need[i][j]=Max[i][j]-Allocation[i][j]；銀行家算法Request是進(jìn)程i的請(qǐng)求向量。Request[j]=k表示進(jìn)程i請(qǐng)求分配j類資源k個(gè)。當(dāng)進(jìn)程i發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查：如果Request≤Need[i]，那么轉(zhuǎn)向步驟2；否那么，認(rèn)為出錯(cuò)，因?yàn)樗?qǐng)求的資源數(shù)已超過(guò)它當(dāng)前的最大需求量。如果Request≤Available，那么轉(zhuǎn)向步驟3；否那么，表示系統(tǒng)中尚無(wú)足夠的資源滿足進(jìn)程i的申請(qǐng)，進(jìn)程i必須等待。系統(tǒng)試探性地把資源分配給進(jìn)程i，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：Available=Available-RequestAllocation[i]=Allocation[i]+RequestNeed[i]=Need[i]-Request系統(tǒng)執(zhí)行平安性算法，檢查此次資源分配后，系統(tǒng)是否處于平安狀態(tài)。如果平安才正式將資源分配給進(jìn)程i，以完本錢次分配；否那么，將試探分配作廢，恢復(fù)原來(lái)的資源分配狀態(tài)，讓進(jìn)程i等待。平安性算法設(shè)置兩個(gè)向量。Work：它表示系統(tǒng)可提供應(yīng)進(jìn)程繼續(xù)運(yùn)行的各類資源數(shù)目，它包含m個(gè)元素，開(kāi)始執(zhí)行平安性算法時(shí)，Work=Available。Finish：它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成，開(kāi)始Finish[i]=false；當(dāng)有足夠資源分配給進(jìn)程i時(shí)，令Finish[i]=true；從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程。Finish[i]==false；Need[i]≤work；如找到那么執(zhí)行步驟3；否那么，執(zhí)行步驟4；當(dāng)進(jìn)程i獲得資源后，可順利執(zhí)行直到完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行Work=work+Allocation[i]Finish[i]=true；轉(zhuǎn)向步驟2；假設(shè)所有進(jìn)程的Finish[i]都為true，那么表示系統(tǒng)處于平安狀態(tài)；否那么，系統(tǒng)處于不平安狀態(tài)。實(shí)驗(yàn)內(nèi)容設(shè)計(jì)有n個(gè)進(jìn)程共享m個(gè)系統(tǒng)資源的系統(tǒng)，進(jìn)程可動(dòng)態(tài)的申請(qǐng)和釋放資源，系統(tǒng)按各進(jìn)程的申請(qǐng)動(dòng)態(tài)的分配資源。系統(tǒng)能顯示各個(gè)進(jìn)程申請(qǐng)和釋放資源，以及系統(tǒng)動(dòng)態(tài)分配資源的過(guò)程，便于用戶觀察和分析；程序框架已經(jīng)給出〔見(jiàn)附件〕，要求將平安性測(cè)試算法補(bǔ)充完整。當(dāng)前資源狀態(tài)圖總的資源向量E=〔1057〕空閑的資源向量C=(357)已分配尚需ABCABCP0010743P1200122P2302600P3211011P40024312．補(bǔ)充完整的平安性算法//平安性檢測(cè)//返回值：0：未通過(guò)平安性測(cè)試；1：通過(guò)平安性測(cè)試intTest_Safty(){//〔請(qǐng)寫出平安性測(cè)試算法的代碼〕 cout<<endl<<"進(jìn)入平安性檢測(cè)！"<<endl; inti,j; intWork[MAX_RESOURCE];//定義工作向量 for(i=0;i<RESOURCE_NUM;i++) { Work[i]=Available[i]; } boolFinish[MAX_PROCESS];//定義布爾向量 for(i=0;i<PROCESS_NUM;i++) Finish[i]=false; intsafe[MAX_RESOURCE];//用于保存平安序列 boolfound=false;//判斷在一輪查找中是否找到符合條件的進(jìn)程 intFinishCount=0;//找到滿足跳進(jìn)的進(jìn)程IDE數(shù)目while(FinishCount<5){ for(i=0;i<PROCESS_NUM;i++){if(Finish[i]==true)//檢查是否滿足條件Finish[i]==falsecontinue; boolHasResource=true; for(j=0;j<RESOURCE_NUM;j++)//檢查是否滿足條件Need[i]<=Work if(Need[i][j]>Work[j]) HasResource=false; if(HasResource) { for(j=0;j<RESOURCE_NUM;j++) Work[j]=Work[j]+Allocation[i][j]; Finish[i]=true; safe[FinishCount]=i; FinishCount++; found=true; } } if(found) { found=false;}elsebreak;}for(i=0;i<PROCESS_NUM;i++)//判斷是否所有進(jìn)程滿足Finish[i]==true{ if(Finish[i]==true) continue; else { cout<<"未通過(guò)平安性測(cè)試，不分配"<<endl; return0;}}cout<<'\n'<<"找到一個(gè)平安序列:";for(i=0;i<PROCESS_NUM;i++)//打印平安序列??{ cout<<"P"<<safe[i]; if(i!=PROCESS_NUM-1) cout<<"--->";}cout<<'\n'<<"已通過(guò)平安性測(cè)試!"<<endl;return1;}3：截圖4：體會(huì)：本次實(shí)驗(yàn)銀行家算法是對(duì)死鎖的防止很好表達(dá)，充分說(shuō)明了能否設(shè)計(jì)一個(gè)好的資源分派算法是從源頭上防止死鎖的發(fā)生的重要之處。