1、銀行家算法1. 課程設(shè)計(jì)的目的了解多道程序系統(tǒng)中，多個(gè)進(jìn)程并發(fā)執(zhí)行的資源分配，及死鎖的產(chǎn)生原因、必要條件和處理死鎖的基本方法，掌握預(yù)防死鎖的方法，系統(tǒng)安全狀態(tài)的基本概念，了解銀行家算法，及資源在進(jìn)程并發(fā)執(zhí)行中的資源分配策略，并且理解死鎖避免在當(dāng)前計(jì)算機(jī)系統(tǒng)不常使用的原因。根據(jù)設(shè)計(jì)題目的要求，充分地分析和理解題目，敘述系統(tǒng)的要求，明確程序要求實(shí)現(xiàn)的功能以及限制條件。明白自己需要用代碼實(shí)現(xiàn)的功能，清楚編寫每部分代碼的目的，做到有的放矢，有條理不遺漏的用代碼實(shí)現(xiàn)銀行家算法。2.設(shè)計(jì)方案論證2.1題目描述銀行家算法是一種最有代表性的避免死鎖的算法。在多道程序系統(tǒng)中，多個(gè)進(jìn)程的并發(fā)執(zhí)行來(lái)改善系統(tǒng)的資源利

2、用率，提高系統(tǒng)的吞吐量，但可能發(fā)生一種危險(xiǎn)死鎖。所謂死鎖(Deadlock)，是指多個(gè)進(jìn)程在運(yùn)行過(guò)程中因爭(zhēng)奪資源而造成的一種僵局（DeadlyEmbrace），當(dāng)進(jìn)程處于這種狀態(tài)時(shí)，若無(wú)外力作用，他們都無(wú)法在向前推進(jìn)。要預(yù)防死鎖，有摒棄“請(qǐng)求和保持”條件，摒棄“不剝奪”條件，摒棄“環(huán)路等待”條件等方法。但是，在預(yù)防死鎖的幾種方法之中，都施加了較強(qiáng)的限制條件；而在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，便可避免死鎖的發(fā)生。要解釋銀行家算法，必須先解釋操作系統(tǒng)安全狀態(tài)和不安全狀態(tài)。安全狀態(tài)是指系統(tǒng)能按照某種進(jìn)程順序P1,P

3、2,，Pn（稱P1,P2,，Pn 序列為安全序列），來(lái)為每個(gè)進(jìn)程Pi分配其所需資源，直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求，使每個(gè)進(jìn)程都可以順利完成。安全狀態(tài)一定沒(méi)有死鎖發(fā)生。如果系統(tǒng)無(wú)法找到這樣一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)。安全序列：一個(gè)進(jìn)程序列P1，Pn是安全的，如果對(duì)于每一個(gè)進(jìn)程Pi(1in），它以后尚需要的資源量不超過(guò)系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程Pj (j < i )當(dāng)前占有資源量之和，則稱此進(jìn)程序列P1,P2,，Pn是安全的，稱作安全序列。銀行家算法：我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請(qǐng)求分配資源相當(dāng)于用戶向銀行家貸款。操

4、作系統(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)程已占用的資源數(shù)與本次申請(qǐng)的資源數(shù)之和是否超過(guò)了該進(jìn)程對(duì)資源的最大需求量。若超過(guò)則拒絕分配資源，若沒(méi)有超過(guò)則再測(cè)試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請(qǐng)量分配資源，否則也要推遲分配。2.2設(shè)計(jì)思路算法思路先對(duì)用戶提出的請(qǐng)求進(jìn)行合法性檢查，即檢查請(qǐng)求是否大于需要的，是否大于可利用的。若請(qǐng)求合法，則進(jìn)行預(yù)分配，對(duì)分配后的狀態(tài)調(diào)用安全性算法進(jìn)行檢查。若安全

5、，則分配；若不安全，則拒絕申請(qǐng)，恢復(fù)到原來(lái)的狀態(tài)，拒絕申請(qǐng)。銀行家算法中的數(shù)據(jù)結(jié)構(gòu)（1）可利用資源向量Available。這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。如果Available j= K，則表示系統(tǒng)中現(xiàn)有R類資源K個(gè)（2）最大需求矩陣Max。這是一個(gè)n*m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Maxi,j=K，則表示進(jìn)程i需要R類資源的數(shù)目為K。（3）分配矩陣Allocation。這也是一個(gè)n*m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的

6、資源數(shù)。如果Allocation i,j=K，則表示進(jìn)程i當(dāng)前已分得R類資源的數(shù)目為K。（4）需求矩陣Need。這也是一個(gè)n*m的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果Need i,j=K，則表示進(jìn)程i還需要R類資源K個(gè)，才能完成其任務(wù)。上述矩陣存在關(guān)系：Needi,j= Maxi,jAllocationi,j2.2.3銀行家算法設(shè)Requesti是進(jìn)程Pi的請(qǐng)求向量，Requesti=K表示進(jìn)程Pi需要K個(gè)j類資源。Pi發(fā)出資源請(qǐng)求后，按下列步驟進(jìn)行檢查：（1）如果requestijneedi,j，轉(zhuǎn)向步驟（2）；否則認(rèn)為錯(cuò)誤，所需要的資源數(shù)已超過(guò)它所宣布的最大值。（2）如果requ

7、estijavailablej，轉(zhuǎn)向步驟（3）；否則，表示尚無(wú)足夠資源，Pi需等待。（3）系統(tǒng)嘗試將資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：Availablej：=Availablej-Requestij；Allocationi,j：=Allocationi,j+ Requestij；Needi,j：=Needi,j- Requestij；（4）執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否出于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，已完成本次分配；否則，將本次試探分配作廢，恢復(fù)原來(lái)的資源分配狀態(tài)，讓Pi等待。2.1.4安全性檢查算法（1）設(shè)置兩個(gè)向量：工作向量work：表示系統(tǒng)可

8、提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，執(zhí)行安全性算法開(kāi)始時(shí)work：=available。finish標(biāo)志：表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。初始化finishi:=false;有足夠資源分配給進(jìn)程時(shí)，令finishi：=true。（2）從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程finishi=false; Needi,jworkj;找到執(zhí)行步驟（3），否則執(zhí)行步驟（4）。（3）當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行： Workj：=worki+allocationi,j； Finishi：=true； Go to step ；（4）如果所有

9、進(jìn)程的finishi=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。2.3設(shè)計(jì)方法2.3.1基本要求（1）可以輸入某系統(tǒng)的資源以及T0時(shí)刻進(jìn)程對(duì)資源的占用及需求情況的表項(xiàng)，以及T0時(shí)刻系統(tǒng)的可利用資源數(shù)。（2）對(duì)T0時(shí)刻的進(jìn)行安全性檢測(cè)，即檢測(cè)在T0時(shí)刻該狀態(tài)是否安全。（3）進(jìn)程申請(qǐng)資源，用銀行家算法對(duì)其進(jìn)行檢測(cè)，分為以下三種情況：A. 所申請(qǐng)的資源大于其所需資源，提示分配不合理不予分配并返回。B所申請(qǐng)的資源未大于其所需資源，但大于系統(tǒng)此時(shí)的可利用資源，提示分配不合理不予分配并返回。 C. 所申請(qǐng)的資源未大于其所需資源，亦未大于系統(tǒng)此時(shí)的可利用資源，預(yù)分配并進(jìn)行安全性檢查：

10、a. 預(yù)分配后系統(tǒng)是安全的，將該進(jìn)程所申請(qǐng)的資源予以實(shí)際分配并打印后返回。 b. 與分配后系統(tǒng)進(jìn)入不安全狀態(tài)，提示系統(tǒng)不安全并返回。（4）對(duì)輸入進(jìn)行檢查，即若輸入不符合條件，應(yīng)當(dāng)報(bào)錯(cuò)并返回重新輸入。2.3.2流程圖：（1）銀行家算法，如圖1所示。輸入進(jìn)程號(hào)初始化Request數(shù)組REQUESTcusneedi>NEEDcusneedi REQUESTcusneedi>AVAILABLEiYN試分配changdata()NSafe()Put()輸出內(nèi)容 Y圖1銀行家算法流程圖（2）安全性算法，如圖2所示。初始化work數(shù)組，使Workj=Availablej; Finishi=fal

11、seFinishi=true Y NNeedij>Workj Y Napply+;appy=N Y YFinishi=trueWorkm+=Allocationimtempk=i;k+l=mY不安全Availablei=Availablei+Requesti;Allocationnumi=Allocationnumi-RequestjNeednumi=Neednumi+Requesti; N輸出安全序列Return trueMaxnumi=Allocationnumi; Allocationnumi=0; Availablei = Availablei + Allocationnumi;

12、圖2安全性算法流程圖2.3.3調(diào)試結(jié)果（1）資源分配情況，如圖3所示。圖3資源分配情況（2）安全判斷，如圖4所示。圖4安全判斷（3）為1分配資源，如圖5所示。圖5為1分配資源（4）為4分配資源，如圖6所示。圖6為4分配資源（5）為0分配資源，如圖7所示。圖7為0分配資源3.設(shè)計(jì)體會(huì)通過(guò)本次課程設(shè)計(jì)，我收獲很多，首先我對(duì)十大算法之一的銀行家算法有了清楚的認(rèn)識(shí)，認(rèn)真分析了進(jìn)程產(chǎn)生死鎖的原因，了解為什么要進(jìn)行死鎖的避免，掌握銀行家算法的數(shù)據(jù)結(jié)構(gòu)，了解了算法的執(zhí)行過(guò)程，加深了對(duì)銀行家算法的理解。其次，我對(duì)編程有了個(gè)清楚的認(rèn)識(shí)，編程就是將先現(xiàn)實(shí)中的規(guī)律模擬成電腦能運(yùn)行的程序，方便我們的工作和學(xué)習(xí)生活。最

13、后，我也清楚認(rèn)識(shí)到理論聯(lián)系實(shí)際重要性，動(dòng)手操作能力和編程邏輯思維能力的提高的重要性，對(duì)自己所編寫的程序要學(xué)會(huì)調(diào)試，不斷改進(jìn)，向更加全面的方向考慮，同時(shí)也要考慮程序的可行性和健壯性?？偠灾?，我在編寫程序方面有了更加深入的認(rèn)識(shí)。不同的算法可以實(shí)現(xiàn)相同的功能，這是我從本次實(shí)驗(yàn)中深深體會(huì)到的，因而在今后的學(xué)習(xí)中遇到問(wèn)題我會(huì)嘗試著用的不同的方法來(lái)解決，有時(shí)候換個(gè)角度可以很方便的解決問(wèn)題課程設(shè)計(jì)是我們對(duì)專業(yè)課程知識(shí)綜合應(yīng)用的實(shí)踐訓(xùn)練，只有認(rèn)真的進(jìn)行課程設(shè)計(jì)，學(xué)會(huì)腳踏實(shí)地認(rèn)真思考學(xué)習(xí)，課程設(shè)計(jì)是培養(yǎng)我們綜合運(yùn)用所學(xué)知識(shí)，發(fā)現(xiàn)、提出、分析和解決實(shí)際問(wèn)題、鍛煉實(shí)踐能力的重要環(huán)節(jié),是對(duì)我們實(shí)際能力的考察過(guò)程。4

14、.參考文獻(xiàn)1 湯小丹，梁紅兵，哲鳳屏，湯子瀛.計(jì)算機(jī)操作系統(tǒng).M 西安：西安電子科技大學(xué)出版社，2007. 150-2202 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu). M 北京：清華大學(xué)出版社，2006. 14-993 趙莉，楊國(guó)梁，孫喁喁，徐飛.Java程序設(shè)計(jì)教程. M 西安：西安科技大學(xué)出版社，2009.25-994劉璟等.高級(jí)語(yǔ)言C+程序設(shè)計(jì).M西安電子科技大學(xué)出版社,2009.66-102附錄#include<iostream.h>#include<string.h>#define False 0#define True 1char name50=0;/資源名稱int Ma

15、x5050=0;/進(jìn)程所需各類資源的最大需求int Allocation5050=0;/系統(tǒng)已分配資源int Need5050=0;/進(jìn)程需求資源int Available50=0;/系統(tǒng)可用資源向量int Request50=0;/進(jìn)程請(qǐng)求資源向量int Work50=0;/存放系統(tǒng)可提供進(jìn)程繼續(xù)運(yùn)行所需各類資源數(shù)目int temp50=0;/存放安全序列int b50=0;/系統(tǒng)各類資源總數(shù)int M=50;/進(jìn)程的最大數(shù)目為50int N=50;/資源的最大數(shù)目為50void display() int i,j,number,m,n;char ming;int a50=0;cout<

16、;<"請(qǐng)輸入系統(tǒng)中資源的種類:"cin>>n;N=n;for(i=0;i<n;i+) cout<<"資源"<<i+1<<"的名稱和數(shù)量:"cin>>ming>>number;namei=ming;bi=number;cout<<"請(qǐng)輸入進(jìn)程的數(shù)量:"cin>>m;M=m;cout<<"請(qǐng)輸入各進(jìn)程的最大需求("<<m<<"*"<

17、<n<<"矩陣)Max:"<<endl;for(i=0;i<m;i+)for(j=0;j<n;j+)cin>>Maxij;cout<<"請(qǐng)輸入各進(jìn)程的已分配("<<m<<"*"<<n<<"矩陣)Allocation:"<<endl;for(i=0;i<m;i+)for(j=0;j<n;j+)cin>>Allocationij;Needij=Maxij-Allocati

18、onij;if(Needij<0)cout<<"您輸入的第"<<i+1<<"個(gè)進(jìn)程所擁有的第"<<j+1<<"個(gè)資源數(shù)錯(cuò)誤,請(qǐng)重新輸入:"<<endl;j-;continue;cout<<"目前可用的資源:"<<endl;for(i=0;i<N;i+)cout<<namei<<" "cout<<endl;for (j=0;j<N;j+)for(i=

19、0;i<M;i+)aj+=Allocationij;Availablej=bj-aj;for(i=0;i<N;i+)cout<<Availablei<<" "/輸出分配資源cout<<endl;void print()/顯示資源分配情況int i,j;cout<<" Max Allocation Need"<<endl;cout<<"進(jìn)程名 "for(j=0;j<3;j+)for(i=0;i<N;i+)cout<<namei&l

20、t;<" "cout<<" "cout<<endl;for(i=0;i<M;i+)cout<<" "<<i<<" "for(j=0;j<N;j+)cout<<Maxij<<" "cout<<" "for(j=0;j<N;j+)cout<<Allocationij<<" "cout<<" &qu

21、ot;for(j=0;j<N;j+)cout<<Needij<<" "cout<<endl;int changdata(int i)/進(jìn)行資源分配 int j;for (j=0;j<M;j+) Availablej=Availablej-Requestj; Allocationij=Allocationij+Requestj; Needij=Needij-Requestj;return 1;int safe(int num,int M,int N)/安全性算法對(duì)系統(tǒng)進(jìn)行分析int i,j,k=0,m,apply,Finish5

22、=0;int flag;int flag1;for(j=0;j<M;j+) Workj=Availablej; for(flag=0;flag<M;flag+)for(i=0;i<M;i+)apply=0;for(j=0;j<N;j+)if (Finishi=False&&Needij<=Workj) apply+;if(apply=N)for(m=0;m<N;m+)Workm=Workm+Allocationim;/變分配數(shù)Finishi=True;tempk=i;k+;for(i=0;i<M;i+)if(Finishi=False)

23、cout<<"系統(tǒng)不安全"<<endl;/不成功系統(tǒng)不安全for(i = 0;i<N;i+) Availablei=Availablei+Requesti;Allocationnumi=Allocationnumi-Requesti; Neednumi=Neednumi+Requesti; return -1; cout<<"系統(tǒng)是安全的!"<<endl;/如果安全，輸出成功 cout<<"分配的序列:"for(i=0;i<M;i+)/輸出運(yùn)行進(jìn)程數(shù)組cout&l

24、t;<tempi;if(i<M-1) cout<<"->"cout<<endl;for(i = 0;i<N;i+)if(Maxnumi = Allocationnumi) flag1 = 1; elseflag1 = 0;break;if(flag1 = 1)for(i=0;i<N;i+)Availablei = Availablei + Allocationnumi;Allocationnumi = 0;return 0;void bank(int M,int N)/銀行家算法對(duì)申請(qǐng)資源對(duì)進(jìn)行判定char ch; int i=0,j=0; ch='y'cout<<"請(qǐng)輸入要求分配的資源進(jìn)程號(hào)(0-&