操作系統(tǒng)-銀行家算法

1、操作系統(tǒng)課程設(shè)計 銀行家算法第一章 引言1.1 課程設(shè)計目地：操作系統(tǒng)是計算機系統(tǒng)的核心系統(tǒng)軟件，它負(fù)責(zé)控制和管理整個系統(tǒng)的資源并組織用戶協(xié)調(diào)使用這些資源，使計算機高效的工作。課程設(shè)計的目的是綜合應(yīng)用學(xué)生所學(xué)知識，通過實驗環(huán)節(jié)，加深學(xué)生對操作系統(tǒng)基本原理和工作過程的理解，提高學(xué)生獨立分析問題、解決問題的能力，增強學(xué)生的動手能力。第二章 銀行家算法描述 2.1 銀行家算法簡介：銀行家算法是一種最有代表性的避免死鎖的算法。在避免死鎖方法中允許進程動態(tài)地申請資源，但系統(tǒng)在進行資源分配之前，應(yīng)先計算此次分配資源的安全性，若分配不會導(dǎo)致系統(tǒng)進入不安全狀態(tài)，則分配，否則等待。要解釋銀行家算法，必須先解釋操

2、作系統(tǒng)安全狀態(tài)和不安全狀態(tài)。安全狀態(tài)：如果存在一個由系統(tǒng)中所有進程構(gòu)成的安全序列P1，Pn，則系統(tǒng)處于安全狀態(tài)。安全狀態(tài)一定是沒有死鎖發(fā)生。不安全狀態(tài):不存在一個安全序列。不安全狀態(tài)不一定導(dǎo)致死鎖。那么什么是安全序列呢？安全序列：一個進程序列P1，Pn是安全的，如果對于每一個進程Pi(1in），它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與所有進程Pj (j i )當(dāng)前占有資源量之和。2.2銀行家算法描述：我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進程向操作系統(tǒng)請求分配資源相當(dāng)于用戶向銀行家貸款。操作系統(tǒng)按照銀行家制定的規(guī)則為進程分配資源，當(dāng)進程首次申請資源時，

3、要測試該進程對資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請量分配資源，否則就推遲分配。當(dāng)進程在執(zhí)行中繼續(xù)申請資源時，先測試該進程已占用的資源數(shù)與本次申請的資源數(shù)之和是否超過了該進程對資源的最大需求量。若超過則拒絕分配資源，若沒有超過則再測試系統(tǒng)現(xiàn)存的資源能否滿足該進程尚需的最大資源量，若能滿足則按當(dāng)前的申請量分配資源，否則也要推遲分配。2.3銀行家算法原理2.3.1銀行家算法的思路 先對用戶提出的請求進行合法性檢查，即檢查請求的是不大于需要的，是否不大于可利用的。若請求合法，則進行試分配。最后對試分配后的狀態(tài)調(diào)用安全性檢查算法進行安全性檢查。若安全，則分配，否則，不

4、分配，恢復(fù)原來狀態(tài)，拒絕申請。2.3.2 銀行家算法中用到的主要數(shù)據(jù)結(jié)構(gòu)可利用資源向量 int Availablej j為資源的種類。最大需求矩陣 int Maxij i為進程的數(shù)量。分配矩陣 int Allocationij 需求矩陣 int needij= Maxij- Allocationij申請各類資源數(shù)量 int Request ij i進程申請j資源的數(shù)量工作向量 int Workx int Finishy 2.3.3 銀行家算法bank()進程i發(fā)出請求申請k個j資源，Request ij=k (1)檢查申請量是否不大于需求量：Request ij=needi,j,若條件不符重新

5、輸入，不允許申請大于需求量。(2)檢查申請量是否小于系統(tǒng)中的可利用資源數(shù)量：Request ij=availablei,j，若條件不符就申請失敗，阻塞該進程，用goto語句跳轉(zhuǎn)到重新申請資源。(3)若以上兩個條件都滿足，則系統(tǒng)試探著將資源分配給申請的進程，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：Availablei,j= Availablei,j- Request ij；Allocationij= Allocationij+ Request ij；needij= needij- Request ij；(4)試分配后，執(zhí)行安全性檢查，調(diào)用safe()函數(shù)檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)。若安全，才正式

6、將資源分配給進程；否則本次試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓該進程等待。(5)用dowhile 循環(huán)語句實現(xiàn)輸入字符y/n判斷是否繼續(xù)進行資源申請。2.3.4安全性檢查算法（safe()函數(shù)）(1)設(shè)置兩個向量：工作向量Work，它表示系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目，在執(zhí)行安全性算法開始時，Work= Available。Finish，它表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。開始時先做Finishi=0；當(dāng)有足夠的資源分配給進程時，再令Finishi=1。(2)在進程中查找符合以下條件的進程：條件1：Finishi=0；條件2：needij=Workj若找到，則執(zhí)

7、行步驟(3)否則，執(zhí)行步驟(4)(3)當(dāng)進程獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：Workj= Workj+ Allocationij；Finishi=1；goto step 2；(4)如果所有的Finishi=1都滿足，則表示系統(tǒng)處于安全狀態(tài)，否則，處于不安全狀態(tài)。第三章 銀行家算法流程圖3.1 系統(tǒng)主要過程流程圖3.2銀行家算法流程圖3.3、安全性算法流程圖第四章源程序結(jié)構(gòu)分析4.1 程序結(jié)構(gòu)4.1.1初始化chushihua()：用于程序開始進行初始化輸入數(shù)據(jù)：進程數(shù)量、資源種類、各種資源可利用數(shù)量、各進程的各種資源已分配數(shù)量、各進程對各類資源最大需求數(shù)等。

8、4.1.2當(dāng)前安全性檢查safe()：用于判斷當(dāng)前狀態(tài)安全性，根據(jù)不同地方的調(diào)用提示處理不同。4.1.2 銀行家算法bank()：進行銀行家算法模擬實現(xiàn)的模塊，調(diào)用其他各個模塊進行銀行家算法模擬過程。4.1.4 顯示當(dāng)前狀態(tài)show()：顯示當(dāng)前資源分配詳細(xì)情況，包括：各種資源的總數(shù)量(all)、系統(tǒng)目前各種資源可用的數(shù)量、各進程已經(jīng)得到的資源數(shù)量、各進程還需要的資源量。4.1.5主程序main() 逐個調(diào)用初始化、顯示狀態(tài)、安全性檢查、銀行家算法函數(shù)，使程序有序的進行。4.2 數(shù)據(jù)結(jié)構(gòu)程序使用的全局變量：const int x=10，y=10； /定義常量int Availablex; /各

9、種資源可利用的數(shù)量int Allocationyy; /各進程當(dāng)前已分配的資源數(shù)量int Maxyy; /各進程對各類資源的最大需求數(shù)int Needyy; /還需求矩陣int Requestx; /申請各類資源的數(shù)量int Workx; /工作向量，表系統(tǒng)可提供給進程運行所需各類資源數(shù)量int Finishy; /表系統(tǒng)是否有足夠的資源分配給進程，0為否，1為是int py; /存儲安全序列int i,j; /全局變量，主要用于循環(huán)語句中int n,m; /n為進程的數(shù)量,m為資源種類數(shù)int l=0,counter=0;4.3 函數(shù)聲明void chushihua(); /系統(tǒng)初始化函數(shù)v

10、oid safe(); /安全性算法函數(shù)void bank(); /銀行家算法函數(shù)void show (); /輸出當(dāng)前資源分配情況4.4 主函數(shù)main()int main() cout /顯示程序開始提示信息 chushihua(); /初始化函數(shù)調(diào)用coutendlendl; showdata(); /輸出初始化后的狀態(tài) /=判斷當(dāng)前狀態(tài)的安全性= safe(); /安全性算法函數(shù)調(diào)用 if (ln) coutn當(dāng)前狀態(tài)不安全，無法申請,程序退出!endl; coutendl; system(pause); sign(); /調(diào)用簽名函數(shù) return 0; / break; else

11、int i; /局部變量 l=0;coutn安全的狀態(tài)!endl; cout安全序列為: ; coutendl進程(p0); /輸出安全序列，考慮顯示格式，先輸出第一個 for (i=1; in; i+) cout進程(pi); for (i=0; in; i+) Finishi=0; /所有進程置為未分配狀態(tài) coutendlendl; bank(); /銀行家算法函數(shù)調(diào)用return 0; 第五章 銀行家算法代碼實現(xiàn)5.1 源程序代碼：#include #include #include using namespace std; #define TRUE 1 /定義 TRUE =1#def

12、ine FALSE 0 /定義 FLASE=0void bank(vector,vectorvector ,vectorvector ,int ,int ); /聲明bank（應(yīng)行家算法）int safe(vector Available,vectorvector Need,vectorvector Allocation,int n,int m);/聲明safe（）安全性算法void init();/*主函數(shù)main()*/void main()init();int safe(vector Available,vectorvector Need,vectorvector Allocation,

13、int n,int m);/*初始化函數(shù)init()*/ 下面的是在dos命令下使用的程序void init()int m; /m資源類數(shù)int n; /進程數(shù)cout輸入資源類數(shù)m;vector Available(m); /動態(tài)申請數(shù)組Available可用資源向量 cout輸入各類資源總數(shù):endl;for (int i=0;im;i+)cout輸入RiAvailablei;coutn輸入進程數(shù)n;vectorvector Max(n, vector(m);cout輸入進程i的最大需求向量;for (int j=0;jm;j+)cout 輸入需要RjMaxij;while (MaxijA

14、vailablej)coutjMaxij;cout輸入已分配的Allocationendl;vectorvector Allocation(n, vector(m);vectorvector Need(n, vector(m);for ( i=0;in;i+)cout輸入為進程i的分配向量;for (int j=0;jm;j+)cout 輸入分配RjAllocationij;while(AllocationijMaxij)coutj+1Allocationij;Needij=Maxij-Allocationij;Availablej =Availablej-Allocationij;int s

15、afe(vector Available,vectorvector Need,vectorvector Allocation,int n,int m);cout此狀態(tài)安全!endl;bank(Available,Need,Allocation,n,m);/調(diào)用銀行家算法bank()函數(shù)/ 下面的是在文件中導(dǎo)入我們所需的信息/*/void init()int m; /m資源類數(shù)int n; /進程數(shù)cout輸入資源類數(shù)m;vector Available(m); /動態(tài)申請數(shù)組Available可用資源向量 cout輸入各類資源總數(shù):endl;FILE *fp;fp=fopen(Availabl

16、e.txt,r+);cout從Available.txt文件中讀入數(shù)據(jù)，并輸出endl;for(int i=0;im;i+)fscanf(fp,%d,&Availablei);coutAvailableit;fclose(fp);coutn輸入進程數(shù)n;vectorvector Max(n, vector(m);fp=fopen(Max.txt,r+);cout從Max.txt文件中讀入數(shù)據(jù)，并輸出endl;for(i=0;in;i+) for (int j=0;jm;j+)fscanf(fp,%d,&Maxij);coutMaxij ;coutendl;fclose(fp);cout輸入已分

17、配的Allocationendl;vectorvector Allocation(n, vector(m);vectorvector Need(n, vector(m);fp=fopen(Allocation.txt,r+);coutAllocation.txt從文件中讀入數(shù)據(jù)，并輸出endl;for(i=0;in;i+)for (int j=0;jm;j+)fscanf(fp,%d,&Allocationij);Needij=Maxij-Allocationij; /在初始化Max時，同時初始化Need數(shù)組Availablej =Availablej-Allocationij; /在初始化M

18、ax時，同時修改Available數(shù)組coutAllocationij ;coutendl;fclose(fp);int safe(vector Available,vectorvector Need,vectorvector Allocation,int n,int m);cout此狀態(tài)安全!endl;bank(Available,Need,Allocation,n,m);/調(diào)用銀行家算法bank()函數(shù)/*/*銀行家算法bank()函數(shù)*/void bank(vector Available,vectorvector Need,vectorvector Allocation,int n,i

19、nt m)vector Request(m);int all=0;/定義變量all，如果all=0，表示進程已經(jīng)運行完，如果all=1，表示還有進程沒有運行完for (int i=0;in;i+)for(int j=0;jm;j+)all +=Needij;if (0=all)cout所有進程已經(jīng)運行完，結(jié)束=1，表示還有進程沒有運行完/循環(huán)直至all0,即找到一個未運行完的進程cout任選一個進程作為當(dāng)前進程0-n-1jc;for (int j=0;jm;j+)all += Needjcj;if (0=all)cout此進程已經(jīng)運行，重新輸入endl;cout輸入該進程的請求向量endl;f

20、or (i=0;iRequesti;while(RequestiNeedjci|RequestiAvailablei)cout請求向量無法滿足endl;break; /系統(tǒng)試探著把資源分配給該進程/for (i=0;im;i+)Availablei=Availablei-Requesti;Allocationjci=Allocationjci+Requesti;Needjci=Needjci-Requesti;int bb=0;bb=safe(Available,Need,Allocation,n,m);/調(diào)用安全性算法，判斷此次資源分配后，系統(tǒng)是否處安全狀態(tài)if (1=bb)cout系統(tǒng)成功

21、分配資源endl;elsecout系統(tǒng)未能成分配資源,收回預(yù)分配資源endl;for (i=0;im;i+)Availablei=Availablei+Requesti;Allocationjci=Allocationjci-Requesti;Needjci=Needjci+Requesti;cout您還想再次請求分配嗎?是請按y/Y,否請按其它鍵again; if(again=y|again=Y) all=0;continue; break;/*安全性算法safe()函數(shù)*/int safe(vector Available,vectorvector Need,vectorvector Al

22、location,int n,int m)vector Work(m),Finish(n);/申請工作向量work，finishWork=Available;vector count(n); /記錄安全序列int len=-1; /記錄安全序列的進程個數(shù)，如果len=n，即表示所有的finish【i】=true，處于安全狀態(tài)for(int i=0;im;i+)Finishi=FALSE; for (i=0;in;i+) int needed=1;for (int j=0;jm;j+)if(Needij=Workj)needed=needed*TRUE;else needed=needed*FALSE;if (Finishi=FALSE)&needed=1)for (j=0;jm;j+)Workj=Workj+Allocatio