背景簡介
在銀行中，客戶申請貸款的數量是有限的，每個客戶在第一次申請貸款時要聲明完成該項目所需的最大資金量，在滿足所有貸款要求時，客戶應及時歸還。銀行家在客戶申請的貸款數量不超過自己擁有的最大值時，都應盡量滿足客戶的需要。在這樣的描述中，銀行家就好比操作系統，資金就是資源，客戶就相當于要申請資源的進程。
銀行家算法是一種最有代表性的避免死鎖的算法。在避免死鎖方法中允許進程動态地申請資源，但系
統在進行資源分配之前，應先計算此次分配資源的安全性，若分配不會導緻系統進入不安全狀态，則分配，否則等待。為實現銀行家算法，系統必須設置若幹數據結構。
要解釋銀行家算法，必須先解釋操作系統安全狀态和不安全狀态。
安全序列是指一個進程序列{P1，…，Pn}是安全的，即對于每一個進程Pi(1≤i≤n），它以後尚需要的資源量不超過系統當前剩餘資源量與所有進程Pj(j
安全狀态
如果存在一個由系統中所有進程構成的安全序列P1，…，Pn，則系統處于安全狀态。安全狀态一定是沒有死鎖發生。
不安全狀态
不存在一個安全序列。不安全狀态不一定導緻死鎖。
數據結構
1）可利用資源向量Available
是個含有m個元素的數組，其中的每一個元素代表一類可利用的資源數目。如果Available[j]=K，則表示系統中現有Rj類資源K個。
2）最大需求矩陣Max
這是一個n×m的矩陣，它定義了系統中n個進程中的每一個進程對m類資源的最大需求。如果Max[i,j]=K，則表示進程i需要Rj類資源的最大數目為K。
3）分配矩陣Allocation
這也是一個n×m的矩陣，它定義了系統中每一類資源當前已分配給每一進程的資源數。如果Allocation[i,j]=K，則表示進程i當前已分得Rj類資源的數目為K。
4）需求矩陣Need。
這也是一個n×m的矩陣，用以表示每一個進程尚需的各類資源數。如果Need[i,j]=K，則表示進程i還需要Rj類資源K個，方能完成其任務。
Need[i,j]=Max[i,j]-Allocation[i,j]
算法原理
我們可以把操作系統看作是銀行家，操作系統管理的資源相當于銀行家管理的資金，進程向操作系統請求分配資源相當于用戶向銀行家貸款。
為保證資金的安全，銀行家規定：
(1)當一個顧客對資金的最大需求量不超過銀行家現有的資金時就可接納該顧客；
(2)顧客可以分期貸款，但貸款的總數不能超過最大需求量；
(3)當銀行家現有的資金不能滿足顧客尚需的貸款數額時，對顧客的貸款可推遲支付，但總能使顧客在有限的時間裡得到貸款；
(4)當顧客得到所需的全部資金後，一定能在有限的時間裡歸還所有的資金.
操作系統按照銀行家制定的規則為進程分配資源，當進程首次申請資源時，要測試該進程對資源的最大需求量，如果系統現存的資源可以滿足它的最大需求量則按當前的申請量分配資源，否則就推遲分配。當進程在執行中繼續申請資源時，先測試該進程本次申請的資源數是否超過了該資源所剩餘的總量。若超過則拒絕分配資源，若能滿足則按當前的申請量分配資源，否則也要推遲分配。
算法實現
初始化
由用戶輸入數據，分别對可利用資源向量矩陣AVAILABLE、最大需求矩陣MAX、分配矩陣ALLOCATION、需求矩陣NEED賦值。
銀行家算法
在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統性能。在該方法中把系統的狀态分為安全狀态和不安全狀态，隻要能使系統始終都處于安全狀态，便可以避免發生死鎖。
銀行家算法的基本思想是分配資源之前，判斷系統是否是安全的；若是，才分配。它是最具有代表性的避免死鎖的算法。
設進程cusneed提出請求REQUEST[i]，則銀行家算法按如下規則進行判斷。
(1)如果REQUEST[cusneed][i]<=NEED[cusneed][i]，則轉（2)；否則，出錯。
(2)如果REQUEST[cusneed][i]<=AVAILABLE[i]，則轉（3)；否則，出錯。
(3)系統試探分配資源，修改相關數據：
AVAILABLE[i]-=REQUEST[cusneed][i];
ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];
NEED[cusneed][i]-=REQUEST[cusneed][i];
(4)系統執行安全性檢查，如安全，則分配成立；否則試探險性分配作廢，系統恢複原狀，進程等待。
安全性檢查算法
（1)設置兩個工作向量Work=AVAILABLE;FINISH
(2)從進程集合中找到一個滿足下述條件的進程，
FINISH==false;
NEED<=Work;
如找到，執行（3)；否則，執行（4)
(3)設進程獲得資源，可順利執行，直至完成，從而釋放資源。
Work=Work+ALLOCATION;
Finish=true;
GOTO2
(4)如所有的進程Finish=true，則表示安全；否則系統不安全。
銀行家算法流程圖
算法（C語言實現）
#include
#include
#include
#include/*用到了getch()*/
#defineM5/*進程數*/
#defineN3/*資源數*/
#defineFALSE0
#defineTRUE1
/*M個進程對N類資源最大資源需求量*/
intMAX[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};
/*系統可用資源數*/
intAVAILABLE[N]={10,5,7};
/*M個進程已分配到的N類數量*/
intALLOCATION[M][N]={{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0}};
/*M個進程已經得到N類資源的資源量*/
intNEED[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};
/*M個進程還需要N類資源的資源量*/
intRequest[N]={0,0,0};
voidmain()
{
inti=0,j=0;
charflag;
voidshowdata();
voidchangdata(int);
voidrstordata(int);
intchkerr(int);
showdata();
enter:{
printf("請輸入需申請資源的進程号(從0到");
printf("%d",M-1);
printf("):");
scanf("%d",&i);
}
if(i<0||i>=M)
{
printf("輸入的進程号不存在，重新輸入!n");
gotoenter;
}
err:{
printf("請輸入進程");
printf("%d",i);
printf("申請的資源數n");
printf("類别:ABCn");
printf("");
for(j=0;j
{
scanf("%d",&Request[j]);
if(Request[j]>NEED[i][j])
{
printf("%d",i);
printf("号進程");
printf("申請的資源數>進程");
printf("%d",i);
printf("還需要");
printf("%d",j);
printf("類資源的資源量!申請不合理，出錯!請重新選擇!n");
gotoerr;
}
else
{
if(Request[j]>AVAILABLE[j])
{
printf("進程");
printf("%d",i);
printf("申請的資源數大于系統可用");
printf("%d",j);
printf("類資源的資源量!申請不合理，出錯!請重新選擇!n");
gotoerr;
}
}
}
}
changdata(i);
if(chkerr(i))
{
rstordata(i);
showdata();
}
else
showdata();
printf("n");
printf("按'y'或'Y'鍵繼續,否則退出n");
flag=getch();
if(flag=='y'||flag=='Y')
{
gotoenter;
}
else
{
exit(0);
}
}
/*顯示數組*/
voidshowdata()
{
inti,j;
printf("系統可用資源向量:n");
printf("***Available***n");
printf("資源類别:ABCn");
printf("資源數目:");
for(j=0;j
{
printf("%d",AVAILABLE[j]);
}
printf("n");
printf("n");
printf("各進程還需要的資源量:n");
printf("******Need******n");
printf("資源類别:ABCn");
for(i=0;i
{
printf("");
printf("%d",i);
printf("号進程:");
for(j=0;j
{
printf("%d",NEED[i][j]);
}
printf("n");
}
printf("n");
printf("各進程已經得到的資源量:n");
printf("***Allocation***n");
printf("資源類别:ABCn");
for(i=0;i
{
printf("");
printf("%d",i);
printf("号進程:");
/*printf(":n");*/
for(j=0;j
{
printf("%d",ALLOCATION[i][j]);
}
printf("n");
}
printf("n");
}
/*系統對進程請求響應，資源向量改變*/
voidchangdata(intk)
{
intj;
for(j=0;j
{
AVAILABLE[j]=AVAILABLE[j]-Request[j];
ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j];
NEED[k][j]=NEED[k][j]-Request[j];
}
}
/*資源向量改變*/
voidrstordata(intk)
{
intj;
for(j=0;j
{
AVAILABLE[j]=AVAILABLE[j]+Request[j];
ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j];
NEED[k][j]=NEED[k][j]+Request[j];
}
}
/*安全性檢查函數*/
intchkerr(ints)
{
intWORK,FINISH[M],temp[M];
inti,j,k=0;
for(i=0;i
for(j=0;j
{
WORK=AVAILABLE[j];
i=s;
while(i
{
if(FINISH[i]==FALSE&&NEED[i][j]<=WORK)
{
WORK=WORK+ALLOCATION[i][j];
FINISH[i]=TRUE;
temp[k]=i;
k++;
i=0;
}
else
{
i++;
}
}
for(i=0;i
if(FINISH[i]==FALSE)
{
printf("n");
printf("系統不安全!本次資源申請不成功!n");
printf("n");
return1;
}
}
printf("n");
printf("經安全性檢查，系統安全，本次分配成功。n");
printf("n");
printf("本次安全序列：n");
printf("進程依次為");
for(i=0;i
{
printf("%d",temp[i]);
printf("->");
}
printf("n");
return0;
}
