2024年銀行家算法設(shè)計實驗報告

銀行家算法設(shè)計試驗報告一．題目分析銀行家算法：我們能夠把操作系統(tǒng)看做是銀行家，操作系統(tǒng)管理的資源相稱于銀行家管理的資金，進程向操作系統(tǒng)祈求資源相稱于客戶向銀行家貸款。操作系統(tǒng)按銀行家制定的規(guī)則為進程分派資源，當進程初次申請資源時，要測試該進程尚需求的資源量，若是系統(tǒng)現(xiàn)存的資源能夠滿足它尚需求的資源量，則按目前的申請量來分派資源，否則就推遲分派。當進程在執(zhí)行中繼續(xù)申請資源時，先測試該進程申請的資源量是否超出了它尚需的資源量。若超出則拒絕分派，若沒有超出則再測試系統(tǒng)尚存的資源是否滿足該進程尚需的資源量，若滿足即可按目前的申請量來分派，若不滿足亦推遲分派。2.基本要求：（1）能夠輸入某系統(tǒng)的資源以及T0時刻進程對資源的占用及需求情況的表項，以及T0時刻系統(tǒng)的可利用資源數(shù)。（2）對T0時刻的進行安全性檢測，即檢測在T0時刻該狀態(tài)是否安全。（3）進程申請資源，用銀行家算法對其進行檢測，分為如下三種情況：A.所申請的資源不小于其所需資源，提示分派不合理不予分派并返回B.所申請的資源未不小于其所需資源，但不小于系統(tǒng)此時的可利用資源，提示分派不合理不予分派并返回。C.所申請的資源未不小于其所需資源，亦未不小于系統(tǒng)此時的可利用資源，預(yù)分派并進行安全性檢查：a.預(yù)分派后系統(tǒng)是安全的，將該進程所申請的資源予以實際分派并打印后返回。b.與分派后系統(tǒng)進入不安全狀態(tài)，提示系統(tǒng)不安全并返回。（4）對輸入進行檢查，即若輸入不符合條件，應(yīng)當報錯并返回重新輸入。3.目標：依照設(shè)計題目標要求，充足地分析和了解題目，論述系統(tǒng)的要求，明確程序要求實現(xiàn)的功效以及限制條件。明白自己需要用代碼實現(xiàn)的功效，清楚編寫每部分代碼的目標，做到有的放矢，有條理不遺漏的用代碼實現(xiàn)銀行家算法。二.概要設(shè)計1.算法思緒：先對用戶提出的祈求進行合法性檢查，即檢查祈求是否不小于需要的，是否不小于可利用的。若祈求合法，則進行預(yù)分派，對分派后的狀態(tài)調(diào)用安全性算法進行檢查。若安全，則分派；若不安全，則拒絕申請，恢復(fù)到本來的狀態(tài)，拒絕申請。2.安全性算法步驟（1）設(shè)置兩個變量①剩余資源變量盤p[]。它表示系統(tǒng)可提供進程繼續(xù)運行所需要的各類資源數(shù)目，執(zhí)行安全算法開始時，p[N]=S[N]②標識數(shù)組C[]。它表示系統(tǒng)是否有足夠的資源分派給進程，使之運行完成，開始時先做C[i]=’F’，當有足夠資源分派給進程時，令C[i]=’T’。（2）從進程集合中找到一個能滿足下述條件的進程：①C[i]=’F’②Q[][]<=p[]如找到，執(zhí)行步驟（3）；否則，執(zhí)行步驟（4）。（3）當進程T取得資源后，可順利執(zhí)行，直至完成，并釋放出分派給它的資源，故應(yīng)執(zhí)行：p[]=p[]+R[][];C[i]=’T’;轉(zhuǎn)向步驟（2）。（4）假如所有進程的C[i]=’T’,則表示系統(tǒng)處在安全狀態(tài)；否則，系統(tǒng)處在不安全狀態(tài)。3.進程祈求算法步驟（1）假如Request[][]＜=Q[],則轉(zhuǎn)向步驟(2)；否則，以為犯錯，因為它所需要的資源數(shù)已超出它所宣布的最大值。（2）假如Request[][]＜=p[][],則轉(zhuǎn)向步驟（3）；否則，表示系統(tǒng)中尚無足夠的資源，進程必須等候。（3）系統(tǒng)試探把要求的資源分派給進程Tt(t從1開始),并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：

p[j]=p[j]-Request[t-1][j];

R[t-1][j]=R[t-1][j]+Request[t-1][j];

Q[t-1][j]=Q[t-1][j]-Request[t-1][j];(4)系統(tǒng)執(zhí)行安全性算法，檢查本次資源分派后，系統(tǒng)是否處在安全狀態(tài)。4.重要用到的數(shù)據(jù)結(jié)構(gòu)：最大需求矩陣Max[N][N]已分派矩陣R[N][N]仍需求矩陣Q[N][N]=Max[N][N]-R[N][N]可利用資源向量p[N]申請各類資源向量Request[N]工作向量work[],C[N](7)各類資源總數(shù)S[N];5.程序模塊：voidmain()系統(tǒng)的主函數(shù)，用來顯示資源的分派情況和提示信息，同時用Main函數(shù)來調(diào)用其他子程序。intcheck();安全性檢查函數(shù)，用來檢查是否有安全序列，假如存在則返回一個‘1’給主函數(shù)，否則返回‘0’。intjudge();進程祈求函數(shù)，用來進行資源祈求，分為手動的和隨機申請。同時對申請的資源進行判斷，檢查申請是否有效，假如有效則返回一個‘1’給主函數(shù)，否則返回‘0’。三．流程圖1.銀行家算法Main()函數(shù)流程圖2.安全性檢查算法check()函數(shù)流程圖調(diào)用check()函調(diào)用check()函數(shù)p[]=S[]C[]=’F’Q[i][j]<=p[j]C[i]=’F’?p[j]=p[j]+R[i][j]C[i]=’T’YN所有進程的C[i]==’T’?l=m?YN輸出安全序列，并打印出目前資源分派情況輸出提示：系統(tǒng)不安全調(diào)用結(jié)束j=n?YN進程祈求算法judge()函數(shù)流程圖四．運行成果及闡明輸入進程總數(shù)，資源總類，每類資源總數(shù)；然后輸入已分派矩陣，最大需求矩陣，系統(tǒng)會求出尚需矩陣并且在屏幕上輸出；然后系統(tǒng)調(diào)用check（）安全檢查函數(shù)進行安全檢查，會在屏幕上輸出系統(tǒng)是否安全，若安全，則會輸出安全序列；接著系統(tǒng)調(diào)用judge（）祈求分派函數(shù)，屏幕上提示輸入要申請資源的序列號和要申請的各類資源數(shù)，輸入以后，系統(tǒng)會進行判斷要申請的資源數(shù)是否小于剩余資源數(shù)，是否小于或等于最大需求數(shù)，若都小于，系統(tǒng)會進行安全檢查，若安全，系統(tǒng)就會進行資源分派。運行成果如下：五、總結(jié)通過這次的課程設(shè)計，我了解掌握了銀行家算法，學會模擬實現(xiàn)資源分派，同時通過編寫和調(diào)試一個系統(tǒng)分派資源的簡單模擬程序，觀測到了死鎖產(chǎn)生的條件，并使用適當?shù)乃惴?，有效的預(yù)防和防止死鎖的發(fā)生。雖然操作系統(tǒng)是此前學的，再接觸時遺忘了許多，不過通過老師的講解，同學的協(xié)助，自己也仔細地看了這次課程設(shè)計的試驗指引，撿回了許多東西，對于銀行家算法的設(shè)計、編寫的思緒變得清楚。通過幾天重復(fù)的閱讀試驗指引，仔細的思考出現(xiàn)的問題，重復(fù)推敲、測試與修改，終于能完滿的完成課程設(shè)計任務(wù)。課程設(shè)計的時間雖然不長，但帶了給我知識，也帶給了我戰(zhàn)勝困難、完成任務(wù)的歡樂。希望以后有更多的機會接觸此類的課程設(shè)計。附：程序清單#defineN100#include<stdio.h>intT[N];intS[N];/*各類資源總數(shù)*/intp[N];/*剩余資源數(shù)*/charC[N];intR[N][N];/*已分派矩陣*/intQ[N][N];/*尚需分派矩陣*/intMAX[N][N];/*最大需求矩陣*/intcheck();intjudge();main(){intsum,i,j,n,m;printf("請輸入進程總數(shù)：");scanf("%d",&m);printf("請輸入資源總類數(shù)：");scanf("%d",&n);printf("請輸入每類資源總數(shù)：");for(j=0;j<n;j++){scanf("%d",&S[j]);}printf("請輸入已分派資源矩陣：\n");for(i=0;i<m;i++){for(j=0;j<n;j++)scanf("%d",&R[i][j]);/*已分派矩陣*/}printf("請輸入最大需求資源矩陣：\n");for(i=0;i<m;i++){for(j=0;j<n;j++)scanf("%d",&MAX[i][j]);/*最大需求矩陣*/}printf("尚需分派資源矩陣為：\n");printf("進程名");for(j=0;j<n;j++)printf("R%d\t",j+1);printf("\n");for(i=0;i<m;i++){printf("T%d\t",i+1);for(j=0;j<n;j++){Q[i][j]=MAX[i][j]-R[i][j];printf("%d\t",Q[i][j]);/*尚需分派矩陣*/}printf("\n");}check(m,n);judge(m,n);}intcheck(intm,intn)/*安全檢查函數(shù)*/{inti,j,k,l=0;for(j=0;j<n;j++){p[j]=S[j];for(i=0;i<m;i++)p[j]=p[j]-R[i][j];}for(i=0;i<m;i++)C[i]='F';for(i=0;i<m;i++){if(C[i]=='T')continue;else{for(j=0;j<n;j++){if(p[j]<Q[i][j])break;}if(j==n){C[i]='T';for(k=0;k<n;k++)p[k]+=R[i][k];T[l++]=i;i-=1; }elsecontinue;if(l==m){printf("系統(tǒng)是安全的\n");printf("安全序列是：\n");for(i=0;i<l;i++){printf("T%d",T[i]+1);if(i!=l-1)printf("-->"); }printf("\n");return1;}}}}intjudge(intm,intn)/*進程祈求函數(shù)*/{inti,j,t;intRequest[N][N];charch;while(1){printf("輸入要申請的資源的進程號(1~%d):",m);scanf("%d",&t);printf("輸入進程所祈求的各資源的數(shù)量:");for(j=0;j<n;j++)scanf("%d",&Request[t-1][j]);for(j=0;j<n;j++) {if(Request[t-1][j]>Q[t-1][j]) {printf("你輸入的祈求數(shù)超出進程的需求量!\n");return0; }if(Request[t-1][j]>p[j]) {printf("你輸入的祈求數(shù)超出系統(tǒng)有的資源數(shù)!\n");return0; } }for(j=0;j<n;j++) {p[j]-=Request[t-1][j];R[t-1][j]+=Request[t-1][j];Q[t-1][j]-=Request[t-1][j]; }if(check)printf("同意分派祈求!\n");else {printf("你的祈求被拒絕!\n");for(j=0;j<n;j++) {p[j]+=Request[t-1][j];R[t-1][j]-=Request[t-1][j];Q[t-1][j]+=Request[t-1][j]; }for(i=0;i<m;i++)C[i]='F';printf("你還想再次祈求分派嗎？是請按y/Y，否請按n/N，再確定\n");while(1) {ch=getch()