1、操作系統(tǒng)課程設(shè)計報告題目： 死鎖相關(guān)算法院系：信息學(xué)院班級：信管11-2姓名：王裕辰學(xué)號：1101051024指導(dǎo)教師： 趙 華 一、 概述本次設(shè)計的程序主要功能是實現(xiàn)銀行家算法、安全性算法、死鎖檢測算法，并根據(jù)輸入的數(shù)據(jù)和相應(yīng)的調(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í)行。通過對銀行家算法，安全性算法和死鎖檢測算法的模擬，加深了對這三種算法的理解，更好地掌握了死鎖預(yù)防和檢測的方法。二、設(shè)計的基本概念和原理（1）安全性算法安全狀態(tài)：指系統(tǒng)能按某種進程順序（P1，P2，Pn）（稱< P1，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é)點Pi。在順利地情況下，Pi可獲得所需資源而繼續(xù)運行，直至運行完畢，再釋放其所占有的全部資源，這相當于消去Pi所有的請求邊和分配邊，使之成為孤立的結(jié)點。 重復(fù)上述過程，在進行一系列的簡化后，若能消去圖中所有的邊，使所有的進程結(jié)點都成為孤立結(jié)點，則稱該圖是可簡化的；若不能通過任何進程使該圖完全簡化，則稱該圖是不可完全簡化的。 當且僅當某狀態(tài)的資源分配圖是不可完全簡化時，此狀態(tài)為死鎖狀態(tài)。三、總體設(shè)計本程序才用了結(jié)構(gòu)化程序設(shè)計方法，將程序進行了模塊化劃分。首先定義幾種算法中的

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

6、行家算法和死鎖檢測算法。程序流程圖：四、詳細設(shè)計每個模塊的代碼及分析如下：1、 預(yù)定義模塊#include "stdafx.h"#include <iostream>#define m 3 /資源類數(shù)#define n 5 /進程個數(shù)2、 主程序模塊int main(int argc, char* argv)int Availablem,Maxnm,Allocationnm,Neednm,Requestnm;/Available可用資源向量 Max最大需求矩陣 Allocation分配矩陣 Need需求矩陣 Requestij 進程i請求資源j的數(shù)量int i,

7、j,P,flag,bank;/bank表示調(diào)用銀行家算法的返回值，為1表示分配完成，為0表示未分配;flag=1;/輸入相關(guān)數(shù)據(jù) cout<<" 死鎖相關(guān)算法 "<<endl;cout<<" 請輸入數(shù)據(jù)："<<endl; cout<<endl<<"輸入最大需求矩陣："<<endl;for(i=0;i<n;i+)for(j=0;j<m;j+)cin>>Maxij; cout<<"輸入分配矩陣："&l

8、t;<endl; for(i=0;i<n;i+)for(j=0;j<m;j+)cin>>Allocationij;cout<<"輸入需求矩陣："<<endl; for(i=0;i<n;i+)for(j=0;j<m;j+)cin>>Needij; cout<<"輸入可利用資源向量："<<endl;for(i=0;i<m;i+)cin>>Availablei;/判斷當前系統(tǒng)是否安全Safealg(Available,Max,Allocati

9、on,Need,flag); if(flag=1)/如果當前系統(tǒng)安全可以輸入請求向量cout<<"輸入請求向量："<<endl;cout<<"進程："<<endl;cin>>P;cout<<"輸入"<<"P"<<P<<"進程"<<"請求資源的數(shù)量"<<endl;for(j=0;j<m;j+) cin>>RequestPj;els

10、e/ 否則提示用戶，退出程序 cout<<"無法分配資源"<<endl;return 0;/調(diào)用銀行家算法,對當前請求進行假定修改bank=Banker(Available,Allocation,Need,Request,P); if(bank=0)return 0;/判斷是否安全，flag=1表示分配后系統(tǒng)處于安全狀態(tài)，flag=0表示分配后系統(tǒng)不安全 Safealg(Available,Max,Allocation,Need,flag); if(flag=0)cout<<"系統(tǒng)不分配資源"<<endl;

11、else cout<<"系統(tǒng)允許分配資源"<<endl;3、 其它函數(shù)模塊void Safealg(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;

12、 for(j=0;j<m;j+)/ 將avail賦值給WorkWorkj=availj;for(i=0;i<n;i+)/ 將所有Finish全部置為0Finishi=0;for(k=0;k<n;k+)for(i=0;i<n;i+) flagNeed=1; for(j=0;j<m;j+) / 找到Need小于等于Work的進程 flagNeed=1 表示找到 flagNeed=0表示未找到 if(needij>Workj) flagNeed=0; break; if(flagNeed=1&&Finishi=0)/ 找到Need小于等于Work的

13、進程后 若此進程的Finish為0，則分配資源，進程執(zhí)行結(jié)束回收資源。 Finishi=1; safecount+=i; /將進程放入安全序列數(shù)組中 for(j=0;j<m;j+) Workj+=allocij; flagSafe=1; /判斷是否為安全狀態(tài) flagsafe為1表示安全，為0表示不安全for(i=0;i<n;i+) if(Finishi=0) flagSafe=0;cout<<"當前系統(tǒng)處于不安全狀態(tài)"<<endl;break; if(flagSafe=1)cout<<"安全序列為： "&

14、lt;<endl; for(i=0;i<count;i+) cout<<"P"<<safei<<" " cout<<endl<<"系統(tǒng)處于安全狀態(tài)"<<endl;Flag=flagSafe;int Banker(int avail,int allocm,int needm,int reqm,int p)/ 銀行家算法 / avail可用資源數(shù) alloc分配矩陣 need需求矩陣 req請求向量 p第p個進程請求分配資源 int j; for(j=0;

15、j<m;j+) /判斷請求向量是否大于第p個進程的需求矩陣if(reqpj>needpj) cout<<"請求資源數(shù)已經(jīng)超過最大值"<<endl; return 0; for(j=0;j<m;j+)/判斷請求向量是否大于可用資源數(shù) if(reqpj>availj) cout<<"沒有足夠資源，進程需等待"<<endl;return 0;for(j=0;j<m;j+) /進行修改 availj-=reqpj; /可用資源數(shù)減去請求數(shù)量allocpj+=reqpj;/已分配資源數(shù)量

16、加上請求數(shù)量needpj-=reqpj;/需求數(shù)量減少請求數(shù)量 cout<<endl<<endl<<"若滿足請求，" return 1；五、測試與數(shù)據(jù)分析假定系統(tǒng)中有五個進程P0，P1,P2，P3,P4和三類資源A，B，C，各種資源的數(shù)量分別為10、5、7，在T0時刻的資源分配情況如下圖所示資源情況進程 MaxAllocationNeedAvailableA B CA B CA B CA B CP07 5 30 1 07 4 33 3 2P13 2 22 0 01 2 2P29 0 23 0 26 0 0P32 2 22 1 10 1 1

17、P44 3 30 0 24 3 1（1） 將上述矩陣中的數(shù)據(jù)輸入進程，調(diào)用安全性算法判斷T0時刻系統(tǒng)是否安全，若安全，輸出安全序列，執(zhí)行（2）步；否則，退出程序。（2） P1請求資源：P1發(fā)出請求向量Reques1（1,0,2），系統(tǒng)調(diào)用銀行家算法進行檢查和修改，然后調(diào)用安全性算法，判斷此時系統(tǒng)是否安全。若安全，輸出安全序列，允許分配資源；否則，不允許分配，退出程序。（3） P4請求資源：P4發(fā)出請求向量Request4（3,3,0），統(tǒng)調(diào)用銀行家算法進行檢查和修改，然后調(diào)用安全性算法，判斷此時系統(tǒng)是否安全。若安全，輸出安全序列，允許分配資源；否則，不允許分配，退出程序。六、完成的情況、簡要的

18、使用說明本程序經(jīng)過了調(diào)試，能夠正常運行，并能夠得到正確的結(jié)果。但使用時應(yīng)注意以下幾個問題：1、 程序運行開始是必須按照規(guī)定的形式輸入Max，Allocation，Need，和Available矩陣。2、 程序中的進程數(shù)和資源數(shù)被定義為常量，用戶無法在程序中設(shè)定當前系統(tǒng)中的進程數(shù)和資源數(shù)，但可以在代碼中進行修改。3、 只要用戶輸入某時刻的資源分配情況，程序都會自動檢查當前系統(tǒng)是否安全。進程請求資源時，需要先輸入進程號在輸入請求向量。七、結(jié)果分析運行程序時出現(xiàn)下圖，提示用戶輸入相關(guān)數(shù)據(jù)按照五測試與數(shù)據(jù)分析中的數(shù)據(jù)輸入程序，程序自動調(diào)用安全性算法判斷當前是否安全，輸出結(jié)果如下圖所示輸入進程1，請求向量（1,0,2）調(diào)用銀行家算法對數(shù)據(jù)進行修改，再次調(diào)用安全性算法檢查，判斷是否分配資源。輸入進程4，請求向量（3,3,0）調(diào)用銀行家算法對數(shù)據(jù)進行修改，再次