死鎖相關(guān)算法設計報告

1、w操作系統(tǒng)課程設計報告題目：死鎖相關(guān)算法院班 姓 學系：信息學院級：信管11-2名:土裕辰號：1101051024指導教師： 趙華一、概述本次設計的程序主要功能是實現(xiàn)銀行家算法、安全性算法、死鎖檢測算法，并根據(jù) 輸入的數(shù)據(jù)和相應的調(diào)度算法計算每個進程的調(diào)度結(jié)果，根據(jù)輸入的數(shù)據(jù)，判斷系統(tǒng)安 全狀態(tài)，判斷進程的資源請求是否可以被滿足，判定系統(tǒng)是否為死鎖狀態(tài)，然后輸出各 種判定結(jié)果(是否安全、安全序列、是否死鎖、是否允許分配)。本程序根據(jù)當前進程對資源的占用和未分配資源的數(shù)量，判斷當前系統(tǒng)是否處于安 全狀態(tài)，判定當前狀態(tài)下進程對資源的請求是否能夠被滿足，然后判斷當前系統(tǒng)是否產(chǎn) 牛死鎖，這給進程的運行

2、提供了較寬松的環(huán)境，有利于進程的并發(fā)執(zhí)行。通過對銀行家 算法，安全性算法和死鎖檢測算法的模擬，加深了對這三種算法的理解，更好地掌握了 死鎖預防和檢測的方法。二、設計的基本概念和原理(1) 安全性算法安全狀態(tài)：指系統(tǒng)能按某種進程順序(pl, p2,，pn)(稱vpl, p2,，pn > 序列為安全序列)，來為每個進程pi分配其所需資源，直至滿足每個進程對資源的最大 需求，使每個進程都可順利地完成。如果系統(tǒng)無法找到這樣一個安全序列，則稱系統(tǒng)處 于不安全狀態(tài)。(2) 銀行家算法銀行家算法把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當于銀行家管理的資 金，進程向操作系統(tǒng)請求分配資源相當于用戶向銀

3、行家貸款。為保證資金的安全，銀行家規(guī)定： 當一個顧客對資金的最大需求量不超過銀行家現(xiàn)有的資金時就可接納該顧客； 顧客可以分期貸款，但貸款的總數(shù)不能超過最大需求量； 當銀行家現(xiàn)有的資金不能滿足顧客尚需的貸款數(shù)額時，對顧客的貸款可推遲支 付，但總能使顧客在有限的時間里得到貸款； 當顧客得到所需的全部資金后，一定能在有限的時間里歸還所有的資金.操作系統(tǒng)按照銀行家制定的規(guī)則為進程分配資源，當進程首次申請資源時，要測試 該進程對資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當前的 中請量分配資源，否則就推遲分配。當進程在執(zhí)行中繼續(xù)中請資源時，先測試該進程本 次審請的資源數(shù)是否超過了該資源

4、所剩余的總量。若超過則拒絕分配資源，若能滿足則 按當前的申請量分配資源，否則也要推遲分配。(3) 死鎖檢測算法 在資源分配圖中，找岀一個既不阻塞又非獨立的進程結(jié)點pio在順利地情況下，pi 可獲得所需資源而繼續(xù)運行，直至運行完畢，再釋放其所占有的全部資源，這相當于消 去pi所有的請求邊和分配邊，使之成為孤立的結(jié)點。 重復上述過程，在進行一系列的簡化后，若能消去圖屮所有的邊，使所有的進程結(jié) 點都成為孤立結(jié)點，則稱該圖是可簡化的；若不能通過任何進程使該圖完全簡化，則稱 該圖是不可完全簡化的。 當且僅當某狀態(tài)的資源分配圖是不可完全簡化時，此狀態(tài)為死鎖狀態(tài)。三、總體設計本程序才用了結(jié)構(gòu)化程序設計方法，

5、將程序進行了模塊化劃分。首先定義兒種算法 中的數(shù)據(jù)結(jié)構(gòu)，用數(shù)組來存放資源。用用戶輸入的數(shù)據(jù)來初始化相關(guān)數(shù)組，以此來表示 不同種類、不同進程請求的資源數(shù)量。首先調(diào)用安全性算法檢測當前系統(tǒng)是否處于安全 狀態(tài)。然后用戶輸入請求向量，調(diào)用銀行家算法判斷是否允許分配。本程序包括以下三個模塊：（1）預定義模塊定義程序所用到的頭文件并定義了進程數(shù)量和臨界資源的種類。（2）主程序模塊包括以下五個步驟 輸入當前系統(tǒng)狀態(tài) 調(diào)用安全性算法檢測系統(tǒng)是否處于安全狀態(tài)。若安全執(zhí)行步驟，否則退出程序。 輸入請求向量 調(diào)用銀行家算法對資源矩陣進行假定修改 調(diào)用安全性算法判斷上述假定修改后系統(tǒng)是否安全，若安全系統(tǒng)允許分配，否則

6、不 允許。（3）其他函數(shù)模塊定義安全性算法、銀行家算法和死鎖檢測算法。程序流程圖：開始系統(tǒng)足否安仝輸入訶求 向廿4苗川銀行家算法不允許分配資n源 v詁求趨過靈上譏？詁霖副過呵利用？mi允許分配資源結(jié)束!1!i、詳細設計每個模塊的代碼及分析如下:1、預定義模塊#include "stdafx.h"#include <iostream>#define m 3 資源類數(shù)#define n 5 進程個數(shù)2、主程序模塊int main(int argc, char * argv)int availablem,maxn ml, allocationn m,neednl m,

7、requestn m;/available可用資源向量 max最大需求矩陣 allocation分配矩陣need需求矩陣requestij進程i請求資源j的數(shù)量int i,j,p,flag,bank;/bank表示調(diào)用銀行家算法的返回值，為1表示分配完成，為0表 示未分配；flag二 1;輸入相關(guān)數(shù)據(jù)n«endl;cout«h死鎖相關(guān)算法cout«"請輸入數(shù)據(jù)：” vvendl;cout«endl«"輸入最大需求矩陣:*'«endl; for(i=0;i<n;i+) for(j=0;j<m;j+

8、) cin»maxij;cout«"輸入分配矩陣："vvendl;for(i=0;i<n;i+)for(j=0；jvm;j+) cin»allocationfij;cout«h輸入需求矩陣:"«endl;for(i=0;i<n;i+)for(j=0;j<m;j+)cin»needi|j;cout«"輸入可利用資源向量:"«endl;for(i=0;i<m;i+)cin»availablei;判斷當前系統(tǒng)是否安全safealg(ava

9、ilable,max,allocation,need,flag);if(flag= 1)/如果當前系統(tǒng)安全可以輸入請求向量cout«"輸入請求向量:n«endl;cout«"進程："«endl;cin»p;cout«n輸入«tn«p«n進程” vv”請求資源的數(shù)量n«endl;for(j=0;j<m;j+)cin»requestp j;else/否則提示用戶，退出程序cout«"無法分配資源"«endl;ret

10、urn 0;調(diào)用銀行家算法，對當前請求進行假定修改bank=banker( available,allocation,need,request,p);if(bank=0)return 0;/判斷是否安全，flag=l表示分配后系統(tǒng)處于安全狀態(tài)，flag=o表示分配后系統(tǒng) 不安全safealg( available,max, allocation,need,flag);if(flag=0)cout«"系統(tǒng)不分配資源"«endl;elsecout«"系統(tǒng)允許分配資源"«endl;3、其它函數(shù)模塊void safealg

11、(int avail,int maxm,int allocm,int needm,int &flag)/安全性算法 /avail可用資源向量 max最大需求矩陣 alloc分配矩陣 need需求矩陣flag引用用于標記是否安全int i,j,k,flagsafe,flagneed,count;int workm,finishn,safen;/work工作向量finish表示系統(tǒng)是否有足夠資源是進 程執(zhí)行完成safe存放安全序列count 二 0;for(j=0;j<m;j+)/ 將 avail 賦值給 workwork j =a vail j;for(i=0;i<n;i卄)

12、將所有finish全部置為0finishi=0;for(k=0;k<n;k+)for(i=0;i<n;i+)flagneed=l;for(j=0;j<m;j+) / 找到 need 小于等于 work 的進程 flagneed=l 表示 找到 flagneed=0表示未找到if(needij>workj)flagneed=0;break;if(flagneed=l&&finishi=0)找到need小于等于work的進程后 若此進 程的finish為0,則分配資源，進程執(zhí)行結(jié)束冋收資源。finishi=l;safecount+=i; 將進程放入安全序列數(shù)

13、組中for(j=0;j<m;j+)work|j+=allocij;flagsafe=l; 判斷是否為安全狀態(tài)flagsafe為1表示安全，為0表示不安全 for(i=0;i<n;i+)if(finishi=o)flagsafe=o;coutvv”當前系統(tǒng)處于不安全狀態(tài)n«endl;break;if(flagsafe=l)cout«"安全序列為：h«endl;for(i=0;i<count;i+) cout«',p,«safei«h n;cout«endl«"系統(tǒng)處于安全

14、狀態(tài)h«endl;flag=flagsafe;int banker(int avail,int allocm,int needm,int reqm,int p)/ 銀行家算法/ avail可用資源數(shù) alloc分配矩陣need需求矩陣req請求向量p第p個進程請 求分配資源intj;for(j二0;jvm;j+) /判斷請求向量是否大于第p個進程的需求矩陣if(reqpj>needpj)cout«h請求資源數(shù)己經(jīng)超過最大值"«endl;return 0;for(j=0;jvm；j+)判斷請求向量是否大于可用資源數(shù)if(reqpfj>avail

15、j)coutvv”沒有足夠資源，進程需等待”vvendl;return 0;for(j=0;j<m;j+) /進行修改availj-=reqpfjl; 可用資源數(shù)減去請求數(shù)量alloc p j +=reqp j ;/已分配資源數(shù)量加上請求數(shù)量need p j -=req p j ;/需求數(shù)量減少請求數(shù)量cout«endl«endl«"若滿足請求，”;return 1；五、測試與數(shù)據(jù)分析假定系統(tǒng)中有五個進程po, p1,p2, p3,p4和三類資源a, b, c,各種資源的數(shù) 量分別為10、5、7,在t0時刻的資源分配情況如下圖所示maxalloca

16、tionneedavailableabcabcabcabcp0753010743332pl322200122p2902302600p3222211011p4433002431(1) 將上述矩陣中的數(shù)據(jù)輸入進程，調(diào)用安全性算法判斷t0時刻系統(tǒng)是否安全，若 安全，輸岀安全序列，執(zhí)行(2)步；否則，退岀程序。(2) p1請求資源：p1發(fā)出請求向量requesl (1,0,2),系統(tǒng)調(diào)用銀行家算法進行檢查 和修改，然后調(diào)用安全性算法，判斷此時系統(tǒng)是否安全。若安全，輸出安全序列， 允許分配資源；否則，不允許分配，退岀程序。(3) p4請求資源：p4發(fā)出請求向量request (3,3,0),統(tǒng)調(diào)用銀行家

17、算法進行檢查和 修改，然后調(diào)用安全性算法，判斷此時系統(tǒng)是否安全。若安全，輸出安全序列, 允許分配資源；否則，不允許分配，退出程序。六、完成的情況、簡要的使用說明本程序經(jīng)過了調(diào)試，能夠正常運行，并能夠得到止確的結(jié)果。但使用時應注意以下 兒個問題：1、程序運行開始是必須按照規(guī)定的形式輸入max, allocation, need,和available 矩陣。2、程序屮的進程數(shù)和資源數(shù)被定義為常量，用戶無法在程序屮設定當前系統(tǒng)中的 進程數(shù)和資源數(shù)，但可以在代碼中進行修改。3、只要用戶輸入某時刻的資源分配情況，程序都會自動檢查當前系統(tǒng)是否安全。 進程請求資源時，需要先輸入進程號在輸入請求向量。七、結(jié)果

18、分析運行程序時出現(xiàn)下圖，提示用戶輸入相關(guān)數(shù)據(jù)按照五測試與數(shù)據(jù)分析中的數(shù)據(jù)輸入程序，程序自動調(diào)用安全性算法判斷當前是否安全, 輸出結(jié)果如下圖所示輸入進程1, 請求向量（1,0,2）調(diào)用銀行家算法對數(shù)據(jù)進行修改，再次調(diào)用安全性算 法檢查，判斷是否分配資源。 c:userswycdesktop0s;ji8i5ttbankerdebugbanker.exee安全序列為：p1 p3 p4 p0 p2系統(tǒng)處于安全狀態(tài)蠕入誦隸向量：進程1輸入p1進程請求資源的數(shù)1 6 2安全斤列為：p1 p3 p4 po p2系統(tǒng)處于安全狀態(tài)系統(tǒng)允許分配資源press any key to continue輸入進程4, 請求向量（3,3,0）調(diào)用銀行家算法對數(shù)據(jù)進行修改，再次調(diào)用安全性算 法檢查，