操作系统：基于Java的银行家算法（优化版）

​​​​​​银行家算法（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]

 如果没有找到满足条件的线程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类资源：

最大需求矩阵A：

已分配资源矩阵B：

当前资源需要矩阵C = A - B:

当前剩余资源向量V=R-A:

判断当前剩余资源量能否满足某个进程的需求量，通过对比我们可知，初始阶段只有线程T2可以满足，此时系统分配给T2所需要的资源，利用完之后并把T2的原有资源收回

此时系统可用资源为：

当前资源需要矩阵C ：

此时剩余资源可以满足任意的剩下三个线程，例如，我们先满足进程T1

此时系统可用资源为：

当前资源需要矩阵C ：

以此类推.........我们就可以得到顺序为 T2-T1-T3-T4的安全进程。

例题2：

此时系统可用资源为：

最大需求矩阵A：

已分配资源矩阵B：

当前资源需要矩阵C ：

此时系统可用资源为：

通过对比可以发现，此时系统资源无法满足任意一个进程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 
输入各进程已分配资源矩阵Allocation以及计算需求资源矩阵
 
		public void SetAllocation(){         //输入可分配资源
		System.out.println("请设置各进程分配矩阵：");
		for(int i = 0;i 
打印视图
 
	public void Print(){      //打印视图
		System.out.println("此时的资源分配量如下：");
		System.out.println("进程    "+"    Max    "+"    Alloction    "+"    Need    "+"         Available ");
		for(int i = 0;i 
输入各进程请求资源的矩阵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 
安全算法：
 
	public void SecurityAlgorithm(){ //银行家安全算法

		boolean[] Finish = new boolean[number]; //初始化进程
		for(int i = 0;i 
下面是运行效果图：
 
 
 
最后附赠完整代码：
 
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 
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