??????银行家算法（Banker's Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。
本次优化了动态规划问题，使得整个程序具有可扩展性。同时也有优化了输出显示问题，用到了System.out.print(String.format("%4.4s",i));
银行家算法：数据结构：
n=线程数量，m=资源类型数量
Max(总需求量)：n x m矩阵
Available(剩余资源量):长度为m的向量
Allocation(已分配资源量):n x m矩阵
Need(未来所需资源量)：n x m矩阵
1.Work和Finish分别是长度为m和n的向量初始化
Work = Available? ? ?
Finish[i]? = false (对于线程的初始化)
2.如何寻找可执行的线程T?
(a)Finish[i]=false? (表明当前进程未完成)? ? ? ?
(b)Need[i]<Work? (表明当前进程可满足)
?如果没有找到满足条件的线程Ti，证明系统是不安全的，转4。如果找到，则转3
3.Work=Work+Allocation[i]? ? ? ? ?
Finish[i]=true?(此时该进程被满足，转2，继续寻找下一个进程直到所有进程都为true为止)
4.如果所有系统Ti满足Finish[i] ==ture,则系统处于安全状态，否则就处于不安全状态
银行家算法：
初始化: Request[i] 线程Ti的资源请求向量? ? ? ? ? ? ? ?
Request[j] 线程Ti的资源请求Rj的实例
循环：? ?
1.如果Request[i]<=Need[i],则转到步骤2，否则拒绝资源的申请，因为其线程已经超过其最大需求? ?
2.如果Request[i]<=Available,则转到步骤3，否则线程Ti必须等待，因为资源无法满足需求
3.通过安全状态判断来确定是否分配资源给线程Ti,生成一个需要判断状态是否安全的资源分配环境
此时：
Available = Available - Request? ? ? ? ?
Allocation[i]=Allocation[i]+Request? ? ? ?
Need[i]=Need[i]-Request? ? ?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
调用安全状态判断:
如果返回结果是安全，则将资源分配给线程Ti ，否则系统会拒绝Ti的资源请求? ?? ? ? ? ? ?
例题1:
假定系统有R1,R2,R3这3类资源：
| R1 | R2 | R3 |
| 9 | 3 | 6 |
最大需求矩阵A：
| A | R1 | R2 | R3 |
| T1 | 3 | 2 | 2 |
| T2 | 6 | 1 | 3 |
| T3 | 3 | 1 | 4 |
| T4 | 4 | 2 | 2 |
已分配资源矩阵B：
| B | R1 | R2 | R3 |
| T1 | 1 | 0 | 0 |
| T2 | 6 | 1 | 2 |
| T3 | 2 | 1 | 1 |
| T4 | 0 | 0 | 2 |
当前资源需要矩阵C = A - B:
| C | R1 | R2 | R3 |
| T1 | 2 | 2 | 2 |
| T2 | 0 | 0 | 1 |
| T3 | 1 | 0 | 3 |
| T4 | 4 | 2 | 0 |
当前剩余资源向量V=R-A:
| R1 | R2 | R3 |
| 0 | 1 | 1 |
判断当前剩余资源量能否满足某个进程的需求量，通过对比我们可知，初始阶段只有线程T2可以满足，此时系统分配给T2所需要的资源，利用完之后并把T2的原有资源收回
此时系统可用资源为：
| R1 | R2 | R3 |
| 6 | 2 | 3 |
当前资源需要矩阵C ：
| C | R1 | R2 | R3 |
| T1 | 2 | 2 | 2 |
| T2 | 0 | 0 | 0 |
| T3 | 1 | 0 | 3 |
| T4 | 4 | 2 | 0 |
此时剩余资源可以满足任意的剩下三个线程，例如，我们先满足进程T1
此时系统可用资源为：
| R1 | R2 | R3 |
| 7 | 2 | 3 |
当前资源需要矩阵C ：
| C | R1 | R2 | R3 |
| T1 | 0 | 0 | 0 |
| T2 | 0 | 0 | 0 |
| T3 | 1 | 0 | 3 |
| T4 | 4 | 2 | 0 |
以此类推.........我们就可以得到顺序为 T2-T1-T3-T4的安全进程。
例题2：
此时系统可用资源为：
| R1 | R2 | R3 |
| 9 | 3 | 6 |
最大需求矩阵A：
| A | R1 | R2 | R3 |
| T1 | 3 | 2 | 2 |
| T2 | 6 | 1 | 3 |
| T3 | 3 | 1 | 4 |
| T4 | 4 | 2 | 2 |
已分配资源矩阵B：
| B | R1 | R2 | R3 |
| T1 | 2 | 0 | 1 |
| T2 | 5 | 1 | 1 |
| T3 | 2 | 1 | 1 |
| T4 | 0 | 0 | 2 |
当前资源需要矩阵C ：
| C | R1 | R2 | R3 |
| T1 | 1 | 2 | 1 |
| T2 | 1 | 0 | 2 |
| T3 | 1 | 0 | 3 |
| T4 | 4 | 2 | 0 |
此时系统可用资源为：
| R1 | R2 | R3 |
| 0 | 1 | 1 |
通过对比可以发现，此时系统资源无法满足任意一个进程Ti，所以无法找到当前资源够所有线程未来的资源需要，所以是不安全的。
Java代码实现：
import java.util.Scanner;
Scanner in = new Scanner(System.in);
int number=in.nextInt();
int member=in.nextInt();
int[] Available = new int[member]; //进程可以支配的资源
int[][] MaxDemand = new int[number][member]; //进程最大所拥有的资源
int[][] Allocation = new int[number][member]; //各个进程已有的资源
int[][] Need = new int[number][member]; //各进程的需求的资源量
int[][] Request = new int[number][member]; //各个进程申请的资源
int[] Work = new int[member]; //Work = Allocation+Need
int num = 0; //进程序列号
public BankerAlorithm(){}
public BankerAlorithm(int number,int member){
super();
this.member = member;
this.number = number;
} 输入各进程最大资源所需矩阵Max
public void SetMaxDemand(){ //输入各进程所需的最大需求矩阵
System.out.println("请设置各进程的最大需求矩阵");
for(int i =0;i<number;i++){
System.out.println("请输入进程P"+i+"最大的资源需求量：");
for(int j = 0;j<member;j++){
MaxDemand[i][j]=in.nextInt();
}
}
} 输入各进程已分配资源矩阵Allocation以及计算需求资源矩阵
public void SetAllocation(){ //输入可分配资源
System.out.println("请设置各进程分配矩阵：");
for(int i = 0;i<number;i++){
System.out.println("请输入进程P"+i+"的分配资源：");
for(int j = 0;j<member;j++){
Allocation[i][j] = in.nextInt();
}
}
System.out.println("剩余可用资源=可用资源-已分配资源");
System.out.println("需求=最大需求-已分配资源");
for(int i = 0;i<number;i++){ //系统剩余的资源
for(int j=0;j<member;j++){
Available[i] = Available[i]-Allocation[j][i];
}
}
for (int i = 0; i<number; i++){//输入各进程所需矩阵
for (int j = 0; j<member; j++){
Need[i][j] = MaxDemand[i][j] - Allocation[i][j];
}
}
}打印视图
public void Print(){ //打印视图
System.out.println("此时的资源分配量如下：");
System.out.println("进程 "+" Max "+" Alloction "+" Need "+" Available ");
for(int i = 0;i<number;i++){
System.out.print("P"+i+" ");
for(int j = 0;j<member;j++){
System.out.print(String.format("%4.4s",MaxDemand[i][j]));
}
System.out.print("|");
System.out.print(" ");
for(int j = 0;j<member;j++){
System.out.print(String.format("%4.4s",Allocation[i][j]));
}
System.out.print("|");
System.out.print(" ");
for(int j = 0;j<member;j++){
System.out.print(String.format("%4.4s",Need[i][j]));
}
System.out.print("| ");
System.out.print(" ");
if(i==0){
for(int j=0;j<member;j++){
System.out.print(String.format("%4.4s",Available[j]));
}
}
System.out.println();
}
}输入各进程请求资源的矩阵Request
public void SetRequest(){ //设置进程需求资源量
System.out.println("请输入请求资源的进程序列号：");
num = in.nextInt();
System.out.println("请输入请求各资源的数量：");
for(int i = 0;i<3;i++){
Request[num][i] = in.nextInt();
}
System.out.println("即进程P"+num+"对各资源的请求:（"+Request[num][0]+"，"+Request[num][1]+"，"+Request[num][2]);
BankerAlgorithmT();
} 银行家调度算法：
public void BankerAlgorithmT(){
boolean Flag = true;
boolean Just1 = false;
//判断申请资源是否小于所需资源以及系统可用资源
for(int i = 0;i<member;i++){
if(Request[num][i]<=Need[num][i]){
Just1 = true;
}
else{
break;
}
}
if(Just1==true){
boolean Just2 = false;
for(int i = 0;i<member;i++){
if(Request[num][i]<=Available[i]){
Just2 = true;
}
else{
break;
}
}
if(Just2==true){
for(int i =0;i<member;i++){
Available[i] -=Request[num][i]; //更新剩余资源
Allocation[num][i] += Request[num][i]; //更新已分配资源
Need[num][i] -= Request[num][i];
}
}
else{
System.out.println("当前没有足够的资源可分配，进程P"+num+"需要等待");
Flag = false;
}
}
else{
System.out.println("进程P" + num + "请求已经超出最大需求量Need，请求失败！");
Flag = false;
}
if(Flag==true){
Print();
SecurityAlgorithm();
}
}安全算法：
public void SecurityAlgorithm(){ //银行家安全算法
boolean[] Finish = new boolean[number]; //初始化进程
for(int i = 0;i<number;i++){
Finish[i] = false;
}
int count = 0;
int cyclenumbers = 0;
int[] S = new int[number+1];
for(int i = 0;i<member;i++){
Work[i] = Available[i];
}
boolean T = true;
boolean T1 = false;
boolean T2 = false;
while(count<number){
if(T){
System.out.println("进程 "+" Work "+" Allocation "+" Need "+" Work+Allocation");
T = false;
}
for(int i =0;i<number;i++){
if(Finish[i]==false){
T1 = true;
}
for(int j =0;j<member;j++){
if(Need[i][j]<=Work[j]){
T2 = true;
}
else{
T2 = false;
}
}
if(T1&&T2){
System.out.print("P"+i+" ");
for(int k =0;k<member;k++){
System.out.print(Work[k]+" ");
}
System.out.print("| ");
for (int j = 0; j<member;j++){
Work[j]+=Allocation[i][j];
}
Finish[i]=true; //表示当前进程已完成
S[count]=i; //存入当前能够完成的任务进程序列号
count++;
if(count==number){ //进程数量和完成数量相同
break;
}
for(int j=0;j<member;j++){
System.out.print(Allocation[i][j]+" ");
}
System.out.print("| ");
for(int j=0;j<member;j++){
System.out.print(Need[i][j]+" ");
}
System.out.print("| ");
for(int j=0;j<member;j++){
System.out.print(Work[j]+" ");
}
System.out.println();
}
else{
}
}
cyclenumbers++;
if(count==number){ //进程数量和完成数量相同
System.out.print("此时存在一个安全序列：");
System.out.print("此时存在一个安全序列：");
for (int i = 0; i<number;i++){//输出安全序列
System.out.print("P"+S[i]+" ");
}
System.out.println("故当前可分配！");
break;//跳出循环
}
if(count<cyclenumbers){
count= number;
System.out.println("当前系统处于不安全状态，故不存在安全序列。");
break;
}
}
下面是运行效果图：
?
最后附赠完整代码：
import java.util.Scanner;
public class BankerAlorithm {
Scanner in = new Scanner(System.in);
int number=in.nextInt();
int member=in.nextInt();
int[] Available = new int[member]; //进程可以支配的资源
int[][] MaxDemand = new int[number][member]; //进程最大所拥有的资源
int[][] Allocation = new int[number][member]; //各个进程已有的资源
int[][] Need = new int[number][member]; //各进程的需求的资源量
int[][] Request = new int[number][member]; //各个进程申请的资源
int[] Work = new int[member]; //Work = Allocation+Need
int num = 0; //进程序列号
public BankerAlorithm(){}
public BankerAlorithm(int number,int member){
super();
this.member = member;
this.number = number;
}
public void TotalOput(){
SetMaxDemand();
SetAllocation();
Print();
SecurityAlgorithm();
}
public void SetMaxDemand(){ //输入各进程所需的最大需求矩阵
System.out.println("请设置各进程的最大需求矩阵");
for(int i =0;i<number;i++){
System.out.println("请输入进程P"+i+"最大的资源需求量：");
for(int j = 0;j<member;j++){
MaxDemand[i][j]=in.nextInt();
}
}
}
public void SetAllocation(){ //输入可分配资源
System.out.println("请设置各进程分配矩阵：");
for(int i = 0;i<number;i++){
System.out.println("请输入进程P"+i+"的分配资源：");
for(int j = 0;j<member;j++){
Allocation[i][j] = in.nextInt();
}
}
System.out.println("剩余可用资源=可用资源-已分配资源");
System.out.println("需求=最大需求-已分配资源");
for(int i = 0;i<member;i++){ //系统剩余的资源
for(int j=0;j<number;j++){
Available[i] = Available[i]-Allocation[j][i];
}
}
for (int i = 0; i<number; i++) {//输入各进程所需矩阵
for (int j = 0; j<member; j++) {
Need[i][j] = MaxDemand[i][j] - Allocation[i][j];
}
}
}
public void Print(){ //打印视图
System.out.println("此时的资源分配量如下：");
System.out.println("进程 "+" Max "+" Alloction "+" Need "+" Available ");
for(int i = 0;i<number;i++){
System.out.print("P"+i+" ");
for(int j = 0;j<member;j++){
System.out.print(String.format("%4.4s",MaxDemand[i][j]));
}
System.out.print("|");
System.out.print(" ");
for(int j = 0;j<member;j++){
System.out.print(String.format("%4.4s",Allocation[i][j]));
}
System.out.print("|");
System.out.print(" ");
for(int j = 0;j<member;j++){
System.out.print(String.format("%4.4s",Need[i][j]));
}
System.out.print("| ");
System.out.print(" ");
if(i==0){
for(int j=0;j<member;j++){
System.out.print(String.format("%4.4s",Available[j]));
}
}
System.out.println();
}
}
public void SetRequest(){ //设置进程需求资源量
System.out.println("请输入请求资源的进程序列号：");
num = in.nextInt();
if(num<number){
System.out.println("请输入请求各资源的数量：");
for(int i = 0;i<number;i++){
Request[num][i] = in.nextInt();
}
System.out.println("即进程P"+num+"对各资源的请求:（"+Request[num][0]+"，"+Request[num][1]+"，"+Request[num][2]);
BankerAlgorithmT();
}
else{
System.out.println("输入错误！超过最大进程数量"+number);
}
}
public void BankerAlgorithmT(){
boolean Flag = true;
boolean Just1 = false;
//判断申请资源是否小于所需资源以及系统可用资源
for(int i = 0;i<member;i++){
if(Request[num][i]<=Need[num][i]){
Just1 = true;
}
else{
break;
}
}
if(Just1==true){
boolean Just2 = false;
for(int i = 0;i<member;i++){
if(Request[num][i]<=Available[i]){
Just2 = true;
}
else{
break;
}
}
if(Just2==true){
for(int i =0;i<member;i++){
Available[i] -=Request[num][i]; //更新剩余资源
Allocation[num][i] += Request[num][i]; //更新已分配资源
Need[num][i] -= Request[num][i];
}
}
else{
System.out.println("当前没有足够的资源可分配，进程P"+num+"需要等待");
Flag = false;
}
}
else{
System.out.println("进程P" + num + "请求已经超出最大需求量Need，请求失败！");
Flag = false;
}
if(Flag==true){
Print();
SecurityAlgorithm();
}
}
public void SecurityAlgorithm(){ //银行家安全算法
boolean[] Finish = new boolean[number]; //初始化进程
for(int i = 0;i<number;i++){
Finish[i] = false;
}
int count = 0;
int cyclenumbers = 0;
int[] S = new int[number+1];
for(int i = 0;i<member;i++){
Work[i] = Available[i];
}
boolean T = true;
boolean T1 = false;
boolean T2 = false;
while(count<number){
if(T){
System.out.println("进程 "+" Work "+" Allocation "+" Need "+" Work+Allocation");
T = false;
}
for(int i =0;i<number;i++){
if(Finish[i]==false){
T1 = true;
}
for(int j =0;j<member;j++){
if(Need[i][j]<=Work[j]){
T2 = true;
}
else{
T2 = false;
}
}
if(T1&&T2){
System.out.print("P"+i+" ");
for(int k =0;k<member;k++){
System.out.print(Work[k]+" ");
}
System.out.print("| ");
for (int j = 0; j<member;j++){
Work[j]+=Allocation[i][j];
}
Finish[i]=true; //表示当前进程已完成
S[count]=i; //存入当前能够完成的任务进程序列号
count++;
if(count==number){ //进程数量和完成数量相同
break;
}
for(int j=0;j<member;j++){
System.out.print(Allocation[i][j]+" ");
}
System.out.print("| ");
for(int j=0;j<member;j++){
System.out.print(Need[i][j]+" ");
}
System.out.print("| ");
for(int j=0;j<member;j++){
System.out.print(Work[j]+" ");
}
System.out.println();
}
else{
}
}
cyclenumbers++;
if(count==number){ //进程数量和完成数量相同
System.out.print("此时存在一个安全序列：");
System.out.print("此时存在一个安全序列：");
for (int i = 0; i<number;i++){//输出安全序列
System.out.print("P"+S[i]+" ");
}
System.out.println("故当前可分配！");
break;//跳出循环
}
if(count<cyclenumbers){
count= number;
System.out.println("当前系统处于不安全状态，故不存在安全序列。");
break;
}
}
}
}
import java.util.Scanner;
public class BankerAlorithmTest {
private static Scanner in;
public static void main(String[] args) {
// TODO 自动生成的方法存根
boolean choose = true;
String S;
in = new Scanner(System.in);
System.out.println("请输入线程个数和资源种类个数:");
BankerAlorithm Test1 = new BankerAlorithm();
System.out.println("请输入资源个数:");
for(int i =0;i<Test1.member;i++){
Test1.Available[i] = in.nextInt();
}
Test1.TotalOput();
while (choose == true) {
Test1.SetRequest();
System.out.println("您是否还要进行请求：1/2?");
S = in.nextLine();
if (S=="n") {
choose = false;
}
}
}
}