銀行家算法短小版

1、1簡介銀行家算法是一種最有代表性的避免死鎖的算法。在避免死鎖方法中允許進(jìn)程動態(tài)地申請資源，但系   銀行家算法統(tǒng)在進(jìn)行資源分配之前，應(yīng)先計算此次分配資源的安全性，若分配不會導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則分配，否則等待。為實現(xiàn)銀行家算法，系統(tǒng)必須設(shè)置若干數(shù)據(jù)結(jié)構(gòu)。要解釋銀行家算法，必須先解釋操作系統(tǒng)安全狀態(tài)和不安全狀態(tài)。安全序列是指一個進(jìn)程序列p1，pn是安全的，即對于每一個進(jìn)程pi(1in），它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程pj (j < i )當(dāng)前占有資源量之和。安全狀態(tài)如果存在一個由系統(tǒng)中所有進(jìn)程構(gòu)成的安全序列p1，pn，則系統(tǒng)處于安全狀態(tài)。安全

2、狀態(tài)一定是沒有死鎖發(fā)生。不安全狀態(tài)不存在一個安全序列。不安全狀態(tài)不一定導(dǎo)致死鎖。2數(shù)據(jù)結(jié)構(gòu)1）可利用資源向量available是個含有m個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目。如果availablej=k，則表示系統(tǒng)中現(xiàn)有rj類資源k個。2）最大需求矩陣max這是一個n×m的矩陣，它定義了系統(tǒng)中n個進(jìn)程中的每一個進(jìn)程對m類資源的最大需求。如果maxi,j=k，則表示進(jìn)程i需要rj類資源的最大數(shù)目為k。3）分配矩陣allocation這也是一個n×m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果allocationi,j=k，則表示進(jìn)程i當(dāng)

3、前已分得rj類資源的 數(shù)目為k。4）需求矩陣need。這也是一個n×m的矩陣，用以表示每一個進(jìn)程尚需的各類資源數(shù)。如果needi,j=k，則表示進(jìn)程i還需要rj類資源k個，方能完成其任務(wù)。needi,j=maxi,j-allocationi,j3算法原理我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請求分配資源相當(dāng)于用戶向銀行家貸款。為保證資金的安全，銀行家規(guī)定：(1) 當(dāng)一個顧客對資金的最大需求量不超過銀行家現(xiàn)有的資金時就可接納該顧客；(2) 顧客可以分期貸款，但貸款的總數(shù)不能超過最大需求量；(3) 當(dāng)銀行家現(xiàn)有的資金不能滿足顧客尚需的貸款

4、數(shù)額時，對顧客的貸款可推遲支付，但總能使顧客在有限的時間里得到貸款；(4) 當(dāng)顧客得到所需的全部資金后，一定能在有限的時間里歸還所有的資金.操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請資源時，要測試該進(jìn)程對資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請量分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請資源時，先測試該進(jìn)程本次申請的資源數(shù)是否超過了該資源所剩余的總量。若超過則拒絕分配資源，若能滿足則按當(dāng)前的申請量分配資源，否則也要推遲分配。4算法實現(xiàn)初始化由用戶輸入數(shù)據(jù)，分別對可利用資源向量矩陣available、最大需求矩陣max、分配矩陣allocat

5、ion、需求矩陣need賦值。銀行家算法在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)，便可以避免發(fā)生死鎖。銀行家算法的基本思想是分配資源之前，判斷系統(tǒng)是否是安全的；若是，才分配。它是最具有代表性的避免死鎖的算法。設(shè)進(jìn)程cusneed提出請求request i，則銀行家算法按如下規(guī)則進(jìn)行判斷。(1)如果request cusneed i<= needcusneedi，則轉(zhuǎn)（2)；否則，出錯。(2)如果request cusneed i<= availablecusneedi，則轉(zhuǎn)

6、（3)；否則，出錯。(3)系統(tǒng)試探分配資源，修改相關(guān)數(shù)據(jù)：availablei-=requestcusneedi;allocationcusneedi+=requestcusneedi;needcusneedi-=requestcusneedi;(4)系統(tǒng)執(zhí)行安全性檢查，如安全，則分配成立；否則試探險性分配作廢，系統(tǒng)恢復(fù)原狀，進(jìn)程等待。安全性檢查算法（1)設(shè)置兩個工作向量work=available;finish(2)從進(jìn)程集合中找到一個滿足下述條件的進(jìn)程，finish=false;need<=work;如找到，執(zhí)行（3)；否則，執(zhí)行（4)(3)設(shè)進(jìn)程獲得資源，可順利執(zhí)行，直至完成，從而

7、釋放資源。work=work+allocation;finish=true;goto 2(4)如所有的進(jìn)程finish= true，則表示安全；否則系統(tǒng)不安全。銀行家算法流程圖算法（c語言實現(xiàn)）#include <string.h>#include <stdio.h>#include <stdlib.h>#include <conio.h> /*用到了getch()*/#define m 5 /*進(jìn)程數(shù)*/#define n 3 /*資源數(shù)*/#define false 0#define true 1/*m個進(jìn)程對n類資源最大資源需求量*/int

8、 maxmn=7,5,3,3,2,2,9,0,2,2,2,2,4,3,3;/*系統(tǒng)可用資源數(shù)*/int availablen=15,10,13;/*m個進(jìn)程對n類資源最大資源需求量*/int allocationmn=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0;/*m個進(jìn)程已經(jīng)得到n類資源的資源量 */int needmn=7,5,3,3,2,2,9,0,2,2,2,2,4,3,3;/*m個進(jìn)程還需要n類資源的資源量*/int requestn=0,0,0;void main()int i=0,j=0;char flag;void showdata();void changda

9、ta(int);void rstordata(int);int chkerr(int);showdata();enter:printf("請輸入需申請資源的進(jìn)程號（從0到");printf("%d",m-1);printf("）:");scanf("%d",&i);if(i<0|i>=m)printf("輸入的進(jìn)程號不存在，重新輸入!n");goto enter;err:printf("請輸入進(jìn)程");printf("%d",i);pr

10、intf("申請的資源數(shù)n");printf("類別: a b cn");printf(" ");for (j=0;j<n;j+)scanf("%d",&requestj);if(requestj>needij)printf("%d",i);printf("號進(jìn)程");printf("申請的資源數(shù) > 進(jìn)程");printf("%d",i);printf("還需要");printf(&quo

11、t;%d",j);printf("類資源的資源量!申請不合理，出錯!請重新選擇!n");goto err;elseif(requestj>availablej)printf("進(jìn)程");printf("%d",i);printf("申請的資源數(shù)大于系統(tǒng)可用");printf("%d",j);printf("類資源的資源量!申請不合理，出錯!請重新選擇!n");goto err;changdata(i);if(chkerr(i)rstordata(i);show

12、data();elseshowdata();printf("n");printf("按'y'或'y'鍵繼續(xù),否則退出n");flag=getch();if (flag='y'|flag='y')goto enter;elseexit(0);/*顯示數(shù)組*/void showdata()int i,j;printf("系統(tǒng)可用資源向量:n");printf("*available*n");printf("資源類別: a b cn");

13、printf("資源數(shù)目:");for (j=0;j<n;j+)printf("%d ",availablej);printf("n");printf("n");printf("各進(jìn)程還需要的資源量:n");printf("*need*n");printf("資源類別: a b cn");for (i=0;i<m;i+)printf(" ");printf("%d",i);printf("號進(jìn)程

14、:");for (j=0;j<n;j+)printf(" %d ",needij);printf("n");printf("n");printf("各進(jìn)程已經(jīng)得到的資源量: n");printf("*allocation*n");printf("資源類別: a b cn");for (i=0;i<m;i+)printf(" ");printf("%d",i);printf("號進(jìn)程:");/*p

15、rintf(":n");*/for (j=0;j<n;j+)printf(" %d ",allocationij);printf("n");printf("n");/*系統(tǒng)對進(jìn)程請求響應(yīng)，資源向量改變*/void changdata(int k)int j;for (j=0;j<n;j+)availablej=availablej-requestj;allocationkj=allocationkj+requestj;needkj=needkj-requestj;/*資源向量改變*/void rstor

16、data(int k)int j;for (j=0;j<n;j+)availablej=availablej+requestj;allocationkj=allocationkj-requestj;needkj=needkj+requestj;/*安全性檢查函數(shù)*/int chkerr(int s)int work,finishm,tempm;int i,j,k=0;for(i=0;i<m;i+)finishi=false;for(j=0;j<n;j+)work=availablej;i=s;while(i<m)if (finishi=false&&needij<=work)work=work+allocationij;finishi=true;tempk=i;k+;i=0;elsei+;for(i=0;i<m;i+)if(finishi=false)printf("n");printf("系統(tǒng)不安全! 本次資源申請不成功!n");printf("n&q