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

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

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

4、源，若能滿足則按當(dāng)前的申請(qǐng)量分配資源，否則也要推遲分配。（3）死鎖檢測(cè)算法 在資源分配圖中，找出一個(gè)既不阻塞又非獨(dú)立的進(jìn)程結(jié)點(diǎn)Pi。在順利地情況下，Pi可獲得所需資源而繼續(xù)運(yùn)行，直至運(yùn)行完畢，再釋放其所占有的全部資源，這相當(dāng)于消去Pi所有的請(qǐng)求邊和分配邊，使之成為孤立的結(jié)點(diǎn)。 重復(fù)上述過程，在進(jìn)行一系列的簡(jiǎn)化后，若能消去圖中所有的邊，使所有的進(jìn)程結(jié)點(diǎn)都成為孤立結(jié)點(diǎn)，則稱該圖是可簡(jiǎn)化的；若不能通過任何進(jìn)程使該圖完全簡(jiǎn)化，則稱該圖是不可完全簡(jiǎn)化的。 當(dāng)且僅當(dāng)某狀態(tài)的資源分配圖是不可完全簡(jiǎn)化時(shí)，此狀態(tài)為死鎖狀態(tài)。三、總體設(shè)計(jì)本程序才用了結(jié)構(gòu)化程序設(shè)計(jì)方法，將程序進(jìn)行了模塊化劃分。首先定義幾種算法中的

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

6、行家算法和死鎖檢測(cè)算法。程序流程圖：四、詳細(xì)設(shè)計(jì)每個(gè)模塊的代碼及分析如下：1、 預(yù)定義模塊#include "stdafx.h"#include <iostream>#define m 3 /資源類數(shù)#define n 5 /進(jìn)程個(gè)數(shù)2、 主程序模塊int main(int argc, char* argv)int Availablem,Maxnm,Allocationnm,Neednm,Requestnm;/Available可用資源向量 Max最大需求矩陣 Allocation分配矩陣 Need需求矩陣 Requestij 進(jìn)程i請(qǐng)求資源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<<" 請(qǐng)輸入數(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;/判斷當(dāng)前系統(tǒng)是否安全Safealg(Available,Max,Allocati

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

10、e/ 否則提示用戶，退出程序 cout<<"無法分配資源"<<endl;return 0;/調(diào)用銀行家算法,對(duì)當(dāng)前請(qǐng)求進(jìn)行假定修改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引用用于標(biāo)記是否安全 int i,j,k,flagSafe,flagNeed,count;int Workm,Finishn,safen;/Work工作向量 Finish表示系統(tǒng)是否有足夠資源是進(jìn)程執(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的進(jìn)程 flagNeed=1 表示找到 flagNeed=0表示未找到 if(needij>Workj) flagNeed=0; break; if(flagNeed=1&&Finishi=0)/ 找到Need小于等于Work的

13、進(jìn)程后 若此進(jìn)程的Finish為0，則分配資源，進(jìn)程執(zhí)行結(jié)束回收資源。 Finishi=1; safecount+=i; /將進(jìn)程放入安全序列數(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<<"當(dāng)前系統(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請(qǐng)求向量 p第p個(gè)進(jìn)程請(qǐng)求分配資源 int j; for(j=0;

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

16、加上請(qǐng)求數(shù)量needpj-=reqpj;/需求數(shù)量減少請(qǐng)求數(shù)量 cout<<endl<<endl<<"若滿足請(qǐng)求，" return 1；五、測(cè)試與數(shù)據(jù)分析假定系統(tǒng)中有五個(gè)進(jìn)程P0，P1,P2，P3,P4和三類資源A，B，C，各種資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況如下圖所示資源情況進(jìn)程 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ù)輸入進(jìn)程，調(diào)用安全性算法判斷T0時(shí)刻系統(tǒng)是否安全，若安全，輸出安全序列，執(zhí)行（2）步；否則，退出程序。（2） P1請(qǐng)求資源：P1發(fā)出請(qǐng)求向量Reques1（1,0,2），系統(tǒng)調(diào)用銀行家算法進(jìn)行檢查和修改，然后調(diào)用安全性算法，判斷此時(shí)系統(tǒng)是否安全。若安全，輸出安全序列，允許分配資源；否則，不允許分配，退出程序。（3） P4請(qǐng)求資源：P4發(fā)出請(qǐng)求向量Request4（3,3,0），統(tǒng)調(diào)用銀行家算法進(jìn)行檢查和修改，然后調(diào)用安全性算法，判斷此時(shí)系統(tǒng)是否安全。若安全，輸出安全序列，允許分配資源；否則，不允許分配，退出程序。六、完成的情況、簡(jiǎn)要的

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