複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/銀行家算法/1679781
複製
複製成功

銀行家算法

鎖定
銀行家算法（Banker's Algorithm）是一個避免死鎖（Deadlock）的著名算法，是由艾茲格·迪傑斯特拉在1965年為T.H.E系統設計的一種避免死鎖產生的算法。它以銀行借貸系統的分配策略為基礎，判斷並保證系統的安全運行。 [1] 
中文名
銀行家算法
外文名
Banker's Algorithm
適用領域
操作系統
發明者
艾茲格·迪傑斯特拉

目錄

  1. 1 背景簡介
  2. 2 安全狀態
  3. 3 不安全狀態
  1. 4 數據結構
  2. 5 算法原理
  3. 6 算法實現
  1. ▪ 初始化
  2. ▪ 銀行家算法
  3. ▪ 安全性檢查算法

銀行家算法背景簡介

在銀行中，客户申請貸款的數量是有限的，每個客户在第一次申請貸款時要聲明完成該項目所需的最大資金量，在滿足所有貸款要求時，客户應及時歸還。銀行家在客户申請的貸款數量不超過自己擁有的最大值時，都應儘量滿足客户的需要。在這樣的描述中，銀行家就好比操作系統，資金就是資源，客户就相當於要申請資源的進程。
銀行家算法 銀行家算法
銀行家算法是一種最有代表性的避免死鎖的算法。在避免死鎖方法中允許進程動態地申請資源，但系統在進行資源分配之前，應先計算此次分配資源的安全性，若分配不會導致系統進入不安全狀態，則分配，否則等待。為實現銀行家算法，系統必須設置若干數據結構。
要解釋銀行家算法，必須先解釋操作系統安全狀態和不安全狀態。
安全序列是指一個進程序列{P1，…，Pn}是安全的，即對於每一個進程Pi(1≤i≤n），它以後尚需要的資源量不超過系統當前剩餘資源量與所有進程Pj (j < i )當前佔有資源量之和。

銀行家算法安全狀態

如果存在一個由系統中所有進程構成的安全序列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;
GOTO 2
(4)如所有的進程Finish= true，則表示安全；否則系統不安全。
銀行家算法流程圖
算法（C語言實現）
#include<STRING.H>
#include<stdio.h>
#include<stdlib.h>
#include<CONIO.H>/*用到了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();
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("類別:ABC\n");
printf("");
for(j=0;j<N;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())
{
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("資源類別:ABC\n");
printf("資源數目:");
for(j=0;j<N;j++)
{
printf("%d",AVAILABLE[j]);
}
printf("\n");
printf("\n");
printf("各進程還需要的資源量:\n");
printf("******Need******\n");
printf("資源類別:ABC\n");
for(i=0;i<M;i++)
{
printf("");
printf("%d",i);
printf("號進程:");
for(j=0;j<N;j++)
{
printf("%d",NEED[i][j]);
}
printf("\n");
}
printf("\n");
printf("各進程已經得到的資源量:\n");
printf("***Allocation***\n");
printf("資源類別:ABC\n");
for(i=0;i<M;i++)
{
printf("");
printf("%d",i);
printf("號進程:");
/*printf(":\n");*/
for(j=0;j<N;j++)
{
printf("%d",ALLOCATION[i][j]);
}
printf("\n");
}
printf("\n");
}
/*系統對進程請求響應，資源向量改變*/
voidchangdata(intk)
{
intj;
for(j=0;j<N;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<N;j++)
{
AVAILABLE[j]=AVAILABLE[j]+Request[j];
ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j];
NEED[k][j]=NEED[k][j]+Request[j];
}
}
/*安全性檢查函數*/
intchkerr()//在假定分配資源的情況下檢查系統的安全性
{
intWORK[N],FINISH[M],temp[M];//temp[]用來記錄進程安全執行的順序
inti,j,m,k=0,count;
for(i=0;i<M;i++)
FINISH[i]=FALSE;
for(j=0;j<N;j++)
WORK[j]=AVAILABLE[j];//把可利用資源數賦給WORK[]
for(i=0;i<M;i++)
{
count=0;
for(j=0;j<N;j++)
if(FINISH[i]==FALSE&&NEED[i][j]<=WORK[j])
count++;
if(count==N)//當進程各類資源都滿足NEED<=WORK時
{
for(m=0;m<N;m++)
WORK[m]=WORK[m]+ALLOCATION[i][m];
FINISH[i]=TRUE;
temp[k]=i;//記錄下滿足條件的進程
k++;
i=-1;
}
}
for(i=0;i<M;i++)
if(FINISH[i]==FALSE)
{
printf("系統不安全!!!本次資源申請不成功!!!\n");
return1;
}
printf("\n");
printf("經安全性檢查，系統安全，本次分配成功。\n");
printf("\n");
printf("本次安全序列：");
for(i=0;i<M;i++)//打印安全系統的進程調用順序
{
printf("進程");
printf("%d",temp[i]);
if(i<M-1)
printf("->");
}
printf("\n");
return0;
}
參考資料
  • 1.    《操作系統概念（Operating System Concepts）》