銀行家算法 os課程設(shè)計(jì)-文庫(kù)吧
2025-05-18 11:28 本頁(yè)面
【正文】 列{P1，…，Pn}是安全的，如果對(duì)于每一個(gè)進(jìn)程Pi(1≤i≤n），它以后尚需要的資源量不超過(guò)系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程Pj (j i )當(dāng)前占有資源量之和。雖然并非所有的不安全狀態(tài)都會(huì)產(chǎn)生死鎖狀態(tài)，但當(dāng)系統(tǒng)進(jìn)入不安全狀態(tài)后，便可能進(jìn)而進(jìn)入死鎖狀態(tài)；反之，只要系統(tǒng)處于安全狀態(tài)，系統(tǒng)便可避免進(jìn)入死鎖狀態(tài)。因此，避免死鎖的實(shí)質(zhì)在于，如何使系統(tǒng)不進(jìn)入不安全狀態(tài)，銀行家算法就是用來(lái)判斷某種情況會(huì)不會(huì)進(jìn)入不安全狀態(tài)。 先對(duì)用戶提出的請(qǐng)求進(jìn)行合法性檢查，即檢查請(qǐng)求的是不大于需要的，是否不大于可利用的。若請(qǐng)求合法，則進(jìn)行試分配。最后對(duì)試分配后的狀態(tài)調(diào)用安全性檢查算法進(jìn)行安全性檢查。若安全，則分配，否則，不分配，恢復(fù)原來(lái)狀態(tài)，拒絕申請(qǐng)。 1）主要數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)(1) 最大需求矩陣Max[][]：這是一個(gè)n*m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Max[i，j]=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。(2) 已分配矩陣Allocation[][]：這也是一個(gè)n*m的矩陣，它定義了系統(tǒng)中每一類資源 當(dāng)前已分配給沒一進(jìn)程的資源數(shù)。如果Allocation[i，j]=K，則表示 進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。(3) 仍需求矩陣Need[][]=Max[][]Allocation[][]：這也是一個(gè)n*m的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果Need[i,j]=K，則表示進(jìn)程i還需要Rj類資源K個(gè)，方能完成其任務(wù)。(4) 可利用資源向量Available[]：這是一個(gè)含有m個(gè) 元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。Available[j]=K，則表示系統(tǒng)中現(xiàn)有Rj 類資源K個(gè)。申請(qǐng)各類資源向量Request[](5) 工作向量 work[]：：表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，執(zhí)行安全性算法開始時(shí)work：=available；(6) Finish[]：表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。初始化finish[i]:=false。有足夠資源分配給進(jìn)程時(shí)，令finish[i]：=true。2）銀行家算法步驟（1）如果Requesti＜o(jì)r =Need,則轉(zhuǎn)向步驟(2)；否則，認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過(guò)它所宣布的最大值。（2）如果Request＜o(jì)r=Available,則轉(zhuǎn)向步驟（3）；否則，表示系統(tǒng)中尚無(wú)足夠的資源，進(jìn)程必須等待。（3）系統(tǒng)試探把要求的資源分配給進(jìn)程Pi,并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Available=AvailableRequest[i]。 Allocation=Allocation+Request。 Need=NeedRequest。(4)系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。3）安全性算法步驟（1）設(shè)置兩個(gè)向量①工作向量Work。它表示系統(tǒng)可提供進(jìn)程繼續(xù)運(yùn)行所需要的各類資源數(shù)目，執(zhí)行安全算法開始時(shí)，Work=Allocation。②布爾向量Finish。它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成，開始時(shí)先做Finish[i]=false，當(dāng)有足夠資源分配給進(jìn)程時(shí)，令Finish[i]=true。（2）從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程：①Finish[i]=false②Needor=Work如找到，執(zhí)行步驟（3）；否則，執(zhí)行步驟（4）。（3）當(dāng)進(jìn)程P獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：Work=Work+Allocation。Finish[i]=true。 轉(zhuǎn)向步驟（2）。（4） 如果所有進(jìn)程的Finish[i]=true,則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。5. 設(shè)計(jì)實(shí)現(xiàn)過(guò)程1）算法整體設(shè)計(jì)與調(diào)用 主函數(shù)int main()，首先判定T0時(shí)刻的安全性，利用安全性算法int chkerr(int s) ，void changdata(int k) ，void rstordata(int k) 函數(shù)對(duì)T0時(shí)刻的資源分配情況進(jìn)行分析，判斷T0時(shí)是否存在一個(gè)安全序列，若不存在則直接顯示不安全，若存在，則輸入每個(gè)進(jìn)程號(hào)，接著有進(jìn)程申請(qǐng)資源，輸入所申請(qǐng)的資源，調(diào)用int chkerr()函數(shù)求安全序列，如果可以求出安全序列，則說(shuō)明分配后系統(tǒng)不會(huì)進(jìn)入不安全狀態(tài)，正式將資源分配給申請(qǐng)資源的進(jìn)程，最后用changdata(n)。rstordata(n)函數(shù)輸出分配資源后每個(gè)進(jìn)程的信息。如果求不出安全序列，說(shuō)明分配后系統(tǒng)會(huì)處于不安全狀態(tài)，則不能將資源分配給該進(jìn)程，讓其等待，系統(tǒng)恢復(fù)原始狀態(tài)。如果申請(qǐng)資源的數(shù)量不滿足條件，則讓該進(jìn)程等待。繼續(xù)判斷其他申請(qǐng)資源的進(jìn)程。 （1） if(Request[j]NEED[n][j]) 、if(Request[j]AVAILABLE[j]) 用來(lái)判斷是否可以進(jìn)行試分配，如果判斷結(jié)果為真，說(shuō)明申請(qǐng)資源的進(jìn)程申請(qǐng)的資源數(shù)目不滿足Request []=need[]或Request []=available[]條件，不能為該進(jìn)程進(jìn)行試分配，如果判斷結(jié)果為0，說(shuō)明可以進(jìn)行試分配。 （2）int chkerr()：這個(gè)函數(shù)用來(lái)求安全序列，首先初始化 WORK=AVAILABLE[j]。 ，然后當(dāng)iM時(shí)循環(huán)找滿足條件 FINISH[i]==FALSEamp。amp。NEED[i][j]=WORK的進(jìn)程，表示進(jìn)程可以順利執(zhí)行則WORK=WORK+ALLOCATION[i][j]。再繼續(xù)找下一個(gè)滿足條件的進(jìn)程。如果單循環(huán)結(jié)束時(shí)每個(gè)進(jìn)程的Finish[i]都等于1，則說(shuō)明可以找到安全序列，返回1，如果不是每個(gè)Finish[i]都等于TRUE，則說(shuō)明找不到一個(gè)安全序列，返回i=0；2）程序流程圖：開始初始化 讀入初始化狀態(tài)時(shí)的資源分配表
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1