banker's algorothm
銀行家算法是針對避免死鎖問題的經典算法
其算法以銀行借貸為基礎，判斷并且保證系統的安全運作
介紹銀行家算法需要先介紹三個概念：
1：安全序列：指一個程序式列{1、2、3、... n}，對于每一個程序來說，都有他之後所需的資源量不超過系統目前剩餘的資源量與該程序目前所占據資源量之和。
2、安全狀态
系統中所有程序可以構成一個安全序列，則可以稱該系統處于安全狀态，安全狀态是一定沒有死鎖發生的。
3、不安全狀态
系統中不存在一個安全序列。不安全狀态不一定發生死鎖。
算法描述（資料結構）
系統可利用資源向量：available
定義一個含有m個向量的數組，表示系統可以利用的各類（m類）資源的總數，比如available[2]=10;表示第二類資源的總數為10個；
最大需求矩陣MAX
這是一個n*m的一個數組，表示系統中n個程序對于各類資源的最大需求，如MAX[1,2]=10；表示下标為1的程序需要第二類資源10個；
配置設定矩陣allocation
這也是一個n*m的矩陣，表示系統中各個程序已經配置設定的各類資源；如allocation[1,2]=5;表示下标為1的程序已經配置設定第二類資源5個。
需求矩陣need
同樣，這個也是一個n*m的矩陣，表示各個程序目前尚需各類資源的數目，比如need[1,2]=3;
表示下标為1的程序還需要第二類資源3個。Need[n,m]=MAX[n,m]-allocation[n,m];
安全算法的檢測
舉個栗子（反正不是闆個栗子）
系統中存在A,B,C 3個程序，記憶體資源最大需求分别為70,60,50；記憶體資源總量為100，若目前配置設定資源分别是40,20,10；則在初始時刻各資源表示如下表：
| Max | Allocation | Need | Residue | |
| A | 70 | 30 | 30 | 30 |
| B | 60 | 20 | 40 | |
| C | 50 | 10 | 10 |
可見安全序列存在，為A->B->C或者為A->C->B
若這個時候C資源請求配置設定10個資源，系統會假定配置設定給C，然後檢測系統安全性
| Max | Allocation | Need | Residue | |
| A | 70 | 30 | 30 | 20 |
| B | 60 | 20 | 40 | |
| C | 50 | 20 | 30 |
則目前剩餘資源不能滿足任何一個程序，不存在安全序列，則系統醜拒C的請求
以下是源碼部分，源碼主體架構來自于百度百科，但經過驗證發現，該源碼存在嚴重bug，即當程序獲得所有資源之後，并不會釋放該資源，以下源碼已修正該bug，（哎，百度啊）
以下部分均為代碼，開發環境VS2008，開發語言C。
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<conio.h> //
#define process 5 //define process number
#define resource 3 //define resource category number
#define false 0
#define true 1
#define runing 0 //process execution status
#define over 1 int max[process][resource]={{8,5,4},{1,4,2},{7,0,3},{2,2,2},{4,4,3}};
int available[resource]={12,6,7};
int allocation[process][resource]={{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0}};
int need[process][resource]={{8,5,4},{1,4,2},{7,0,3},{2,2,2},{4,4,3}};
int request[resource]={0,0,0};
//
void showdata();
void changdata(int);
void rstordata(int);
void process_over();
int chkerr();
void main() //main function
{
int i=0,j=0;
char flag; showdata();//show message about Initialzed
enter:
{
printf("請輸入需申請資源的程序号（從0到");
printf("%d",process-1);
printf("）:");
scanf("%d",&i);
}
if(i<0||i>=process)
{
printf("輸入的程序号不存在，重新輸入!\n");
goto enter;
}
err:
{
printf("請輸入程序");
printf("%d",i);
printf("申請的資源數\n");
printf("類别:ABC\n");
printf("");
for(j=0;j<resource;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");
goto err;
}
else
{
if(request[j]>available[j])
{
printf("程序");
printf("%d",i);
printf("申請的資源數大于系統可用");
printf("%d",j);
printf("類資源的資源量!申請不合理，出錯!請重新選擇!\n");
goto err;
}
}
}
}
changdata(i);
if(chkerr())
{
rstordata(i);
showdata();
}
else
{
process_over(i);
showdata();
}
printf("\n");
printf("按'y'或'Y'鍵繼續,否則退出\n");
flag=getch();
if(flag=='y'||flag=='Y')
{
goto enter;
}
else
{
exit(0);
}
}
void showdata()
{
int i,j;
printf("系統可用資源向量:\n");
printf("***Available***\n");
printf("資源類别:A B C\n");
printf("資源數目:");
for(j=0;j<resource;j++)
{
printf("%d ",available[j]);
}
printf("\n");
printf("\n");
printf("各程序還需要的資源量:\n");
printf("******Need******\n");
printf("資源類别:A B C\n");
for(i=0;i<process;i++)
{
printf("");
printf("%d",i);
printf("号程序:");
for(j=0;j<resource;j++)
{
printf("%d ",need[i][j]);
}
printf("\n");
}
printf("\n");
printf("各程序已經得到的資源量:\n");
printf("***Allocation***\n");
printf("資源類别:A B C\n");
for(i=0;i<process;i++)
{
printf("");
printf("%d",i);
printf("号程序:");
for(j=0;j<resource;j++)
{
printf("%d ",allocation[i][j]);
}
printf("\n");
}
printf("\n");
}
void changdata(int k)
{
int j;
for(j=0;j<resource;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<resource;j++)
{
available[j]=available[j]+request[j];
allocation[k][j]=allocation[k][j]-request[j];
need[k][j]=need[k][j]+request[j];
}
}
int chkerr()
{
int WORK[resource],FINISH[process],temp[process];//temp[]:process execution sequence
int i,j,m,k=0,count;
for(i=0;i<process;i++)
FINISH[i]=false;
for(j=0;j<resource;j++)
WORK[j]=available[j];
for(i=0;i<process;i++)
{
count=0;
for(j=0;j<resource;j++)
if(FINISH[i]==false&&need[i][j]<=WORK[j])
count++;
if(count==resource)//All process:need<=work
{
for(m=0;m<resource;m++)
WORK[m]=WORK[m]+allocation[i][m];
FINISH[i]=true;
temp[k]=i;
k++;
i=-1;
}
}
for(i=0;i<process;i++)
if(FINISH[i]==false)
{
printf("系統不安全!!!本次資源申請不成功!!!\n");
return 1;
}
printf("\n");
printf("經安全性檢查，系統安全，本次配置設定成功。\n");
printf("\n");
printf("本次安全序列：");
for(i=0;i<process;i++)//display safety execution sequence
{
printf("程序");
printf("%d",temp[i]);
if(i<process-1)
printf("->");
}
printf("\n");
return 0;
}
void process_over(int k)
{
int j;
int flag=over;
for(j=0;j<resource;j++)
{
if(need[k][j]!=0)
flag=runing;
}
if(flag==over)
{
printf("程序");
printf("%d",k);
printf("已獲得所有資源，執行完畢，釋放所占用資源\n");
for(j=0;j<resource;j++)
{
available[j]=available[j]+allocation[k][j];
need[k][j]=allocation[k][j];
allocation[k][j]=0;
}
}
};
以下為該代碼執行後效果截圖：
以上為對于銀行家算法學習整理心得，若有錯誤，望指正！ Thanks for your reading！