銀行家算法（Banker's Algorithm）是一個(gè)避免死鎖（Deadlock）的著名算法，是由艾茲格·迪杰斯特拉在1965年為T.H.E系統(tǒng)設(shè)計(jì)的一種避免死鎖產(chǎn)生的算法。它以銀行借貸系統(tǒng)的分配策略為基礎(chǔ)，判斷并保證系統(tǒng)的安全運(yùn)行。
背景簡介
在銀行中，客戶申請(qǐng)貸款的數(shù)量是有限的，每個(gè)客戶在第一次申請(qǐng)貸款時(shí)要聲明完成該項(xiàng)目所需的最大資金量，在滿足所有貸款要求時(shí)，客戶應(yīng)及時(shí)歸還。銀行家在客戶申請(qǐng)的貸款數(shù)量不超過自己擁有的最大值時(shí)，都應(yīng)盡量滿足客戶的需要。在這樣的描述中，銀行家就好比操作系統(tǒng)，資金就是資源，客戶就相當(dāng)于要申請(qǐng)資源的進(jìn)程。
銀行家算法是一種最有代表性的避免死鎖的算法。在避免死鎖方法中允許進(jìn)程動(dòng)態(tài)地申請(qǐng)資源，但系
統(tǒng)在進(jìn)行資源分配之前，應(yīng)先計(jì)算此次分配資源的安全性，若分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則分配，否則等待。為實(shí)現(xiàn)銀行家算法，系統(tǒng)必須設(shè)置若干數(shù)據(jù)結(jié)構(gòu)。
要解釋銀行家算法，必須先解釋操作系統(tǒng)安全狀態(tài)和不安全狀態(tài)。
安全序列是指一個(gè)進(jìn)程序列{P1，…，Pn}是安全的，即對(duì)于每一個(gè)進(jìn)程Pi(1≤i≤n），它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程Pj (j < i )當(dāng)前占有資源量之和。
安全狀態(tài)
如果存在一個(gè)由系統(tǒng)中所有進(jìn)程構(gòu)成的安全序列P1，…，Pn，則系統(tǒng)處于安全狀態(tài)。安全狀態(tài)一定是沒有死鎖發(fā)生。
不安全狀態(tài)
不存在一個(gè)安全序列。不安全狀態(tài)不一定導(dǎo)致死鎖。
數(shù)據(jù)結(jié)構(gòu)
1）可利用資源向量Available
是個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目。如果Available[j]=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個(gè)。
2）最大需求矩陣Max
這是一個(gè)n×m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Max[i,j]=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。
3）分配矩陣Allocation
這也是一個(gè)n×m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocation[i,j]=K，則表示進(jìn)程i當(dāng)前已分得Rj類資源的 數(shù)目為K。
4）需求矩陣Need。
這也是一個(gè)n×m的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果Need[i,j]=K，則表示進(jìn)程i還需要Rj類資源K個(gè)，方能完成其任務(wù)。
Need[i,j]=Max[i,j]-Allocation[i,j]
算法原理
我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請(qǐng)求分配資源相當(dāng)于用戶向銀行家貸款。
為保證資金的安全，銀行家規(guī)定：
(1) 當(dāng)一個(gè)顧客對(duì)資金的最大需求量不超過銀行家現(xiàn)有的資金時(shí)就可接納該顧客；
(2) 顧客可以分期貸款，但貸款的總數(shù)不能超過最大需求量；
(3) 當(dāng)銀行家現(xiàn)有的資金不能滿足顧客尚需的貸款數(shù)額時(shí)，對(duì)顧客的貸款可推遲支付，但總能使顧客在有限的時(shí)間里得到貸款；
(4) 當(dāng)顧客得到所需的全部資金后，一定能在有限的時(shí)間里歸還所有的資金.
操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請(qǐng)資源時(shí)，要測試該進(jìn)程對(duì)資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請(qǐng)量分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請(qǐng)資源時(shí)，先測試該進(jìn)程本次申請(qǐng)的資源數(shù)是否超過了該資源所剩余的總量。若超過則拒絕分配資源，若能滿足則按當(dāng)前的申請(qǐng)量分配資源，否則也要推遲分配。
算法實(shí)現(xiàn)
初始化
由用戶輸入數(shù)據(jù)，分別對(duì)可利用資源向量矩陣AVAILABLE、最大需求矩陣MAX、分配矩陣ALLOCATION、需求矩陣NEED賦值。
銀行家算法
在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)，便可以避免發(fā)生死鎖。
銀行家算法的基本思想是分配資源之前，判斷系統(tǒng)是否是安全的；若是，才分配。它是最具有代表性的避免死鎖的算法。
設(shè)進(jìn)程cusneed提出請(qǐng)求REQUEST[i]，則銀行家算法按如下規(guī)則進(jìn)行判斷。
(1)如果REQUEST[cusneed][i]<=NEED[cusneed][i]，則轉(zhuǎn)（2)；否則，出錯(cuò)。
(2)如果REQUEST [cusneed] [i]<= AVAILABLE[i]，則轉(zhuǎn)（3)；否則，出錯(cuò)。
(3)系統(tǒng)試探分配資源，修改相關(guān)數(shù)據(jù)：
AVAILABLE[i]-=REQUEST[cusneed][i];
ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];
NEED[cusneed][i]-=REQUEST[cusneed][i];
(4)系統(tǒng)執(zhí)行安全性檢查，如安全，則分配成立；否則試探險(xiǎn)性分配作廢，系統(tǒng)恢復(fù)原狀，進(jìn)程等待。
安全性檢查算法
（1)設(shè)置兩個(gè)工作向量Work=AVAILABLE;FINISH
(2)從進(jìn)程集合中找到一個(gè)滿足下述條件的進(jìn)程，
FINISH==false;
NEED<=Work;
如找到，執(zhí)行（3)；否則，執(zhí)行（4)
(3)設(shè)進(jìn)程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。
Work=Work+ALLOCATION;
Finish=true;
goto2
(4)如所有的進(jìn)程Finish=true，則表示安全；否則系統(tǒng)不安全。
銀行家算法流程圖
算法（c語言實(shí)現(xiàn)）
#include
#include
#include
#include /*用到了getch()*/
#define M 5 /*進(jìn)程數(shù)*/
#define N 3 /*資源數(shù)*/
#define FALSE 0
#define TRUE 1
/*M個(gè)進(jìn)程對(duì)N類資源最大資源需求量*/
int MAX[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};
/*系統(tǒng)可用資源數(shù)*/
int AVAILABLE[N]={10,5,7};
/*M個(gè)進(jìn)程已分配到的N類數(shù)量*/
int ALLOCATION[M][N]={{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0}};
/*M個(gè)進(jìn)程已經(jīng)得到N類資源的資源量 */
int NEED[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};
/*M個(gè)進(jìn)程還需要N類資源的資源量*/
int Request[N]={0,0,0};
void main()
{
int i=0,j=0;
char flag;
void showdata();
void changdata(int);
void rstordata(int);
int chkerr(int);
showdata();
enter:{
printf("請(qǐng)輸入需申請(qǐng)資源的進(jìn)程號(hào)(從0到");
printf("%d",M-1);
printf("):");
scanf("%d",&i);
}
if(i<0||i>=M)
{
printf("輸入的進(jìn)程號(hào)不存在，重新輸入!\n");
goto enter;
}
err:{
printf("請(qǐng)輸入進(jìn)程");
printf("%d",i);
printf("申請(qǐng)的資源數(shù)\n");
printf("類別: A B C\n");
printf(" ");
for (j=0;j
{
scanf("%d",&Request[j]);
if(Request[j]>NEED[i][j])
{
printf("%d",i);
printf("號(hào)進(jìn)程");
printf("申請(qǐng)的資源數(shù) > 進(jìn)程");
printf("%d",i);
printf("還需要");
printf("%d",j);
printf("類資源的資源量！申請(qǐng)不合理，出錯(cuò)！請(qǐng)重新選擇!\n");
goto err;
}
else
{
if(Request[j]>AVAILABLE[j])
{
printf("進(jìn)程");
printf("%d",i);
printf("申請(qǐng)的資源數(shù)大于系統(tǒng)可用");
printf("%d",j);
printf("類資源的資源量！申請(qǐng)不合理，出錯(cuò)！請(qǐng)重新選擇!\n");
goto err;
}
}
}
}
changdata(i);
if(chkerr(i))
{
rstordata(i);
showdata();
}
else
showdata();
printf("\n");
printf("按'y'或'Y'鍵繼續(xù)，否則退出\n");
flag=getch();
if (flag=='y'||flag=='Y')
{
goto enter;
}
else
{
exit(0);
}
}
/*顯示數(shù)組*/
void showdata()
{
int i,j;
printf("系統(tǒng)可用資源向量:\n");
printf("***Available***\n");
printf("資源類別: A B C\n");
printf("資源數(shù)目:");
for (j=0;j
{
printf("%d ",AVAILABLE[j]);
}
printf("\n");
printf("\n");
printf("各進(jìn)程還需要的資源量:\n");
printf("******Need******\n");
printf("資源類別: A B C\n");
for (i=0;i
{
printf(" ");
printf("%d",i);
printf("號(hào)進(jìn)程:");
for (j=0;j
{
printf(" %d ",NEED[i][j]);
}
printf("\n");
}
printf("\n");
printf("各進(jìn)程已經(jīng)得到的資源量: \n");
printf("***Allocation***\n");
printf("資源類別: A B C\n");
for (i=0;i
{
printf(" ");
printf("%d",i);
printf("號(hào)進(jìn)程:");
/*printf(":\n");*/
for (j=0;j
{
printf(" %d ",ALLOCATION[i][j]);
}
printf("\n");
}
printf("\n");
}
/*系統(tǒng)對(duì)進(jìn)程請(qǐng)求響應(yīng)，資源向量改變*/
void changdata(int k)
{
int j;
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];
}
}
/*資源向量改變*/
void rstordata(int k)
{
int j;
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];
}
}
/*安全性檢查函數(shù)*/
int chkerr(int s)
{
int WORK,FINISH[M],temp[M];
int i,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("系統(tǒng)不安全! 本次資源申請(qǐng)不成功!\n");
printf("\n");
return 1;
}
}
printf("\n");
printf("經(jīng)安全性檢查，系統(tǒng)安全，本次分配成功。\n");
printf("\n");
printf(" 本次安全序列：\n");
printf("進(jìn)程依次為");
for(i=0;i
{
printf("%d",temp[i]);
printf(" -> ");
}
printf("\n");
return 0;
}
參考資料 >