实验2 银行家算法（2学时）

一、实验目的

理解银行家算法，掌握进程安全性检查的方法及资源分配的方法。

二、实验内容

    编写程序实现银行家算法，并验证程序的正确性。

  三、实验要求

    编制模拟银行家算法的程序，并以下面给出的例子验证所编写的程序的正确性。

例子：某系统有A、B、C、D 4类资源共5个进程（P0、P1、P2、P3、P4）共享，各进程对资源的需求和分配情况如下表所示。

现在系统中A、B、C、D 4类资源分别还剩1、5、2、0个，请按银行家算法回答下列问题：

（1）现在系统是否处于安全状态？

（2）如果现在进程P1提出需求（0、4、2、0）个资源的请求，系统能否满足它的请求？

package 操作系统实验二_银行家算法;

import java.util.Scanner;

public class Bank {
	Scanner in = new Scanner(System.in);
	int progressNum; 
	int typeNum; 
	int[] Ssum;

	int[][] Max;
	int[][] Allocation;
	int[][] Need;
	int[] Available; 
	int[] Work;
	boolean[] Finish = new boolean[50];
	
	public Bank() {
		start();

	}

	public void start() {
		System.out
				.println("***********************************************************");
		System.out
				.println("                       欢迎使用银行家算法");
		System.out
				.println("                      150511308       徐天骄                               ");
		System.out
				.println("***********************************************************");
		System.out.println("请选择操作：\n\t1.开始使用\n\t2.退出");
		int a;
		a = in.nextInt();
		if (a == 1) {
			input();
		} else {
			quit();
			
		}
	}

	public void input() {
		System.out.println("请输入进程个数：");
		this.progressNum = in.nextInt();
		System.out.println("请输入资源种类数:");
		this.typeNum = in.nextInt();
		this.Ssum = getSsum();
		this.Max = getMax();
		this.Allocation = getAllocation();
		this.Need = getNeed();
		this.Available = getAvailable(progressNum, typeNum);
		System.out.println("该时刻的资源分配表：");
		output();
		this.Check_Safe(Available);
		this.Ask_Distribution(false);
	}

	public int[] getSsum() {
		Ssum = new int[typeNum];
		System.out.println("请输入各类资源总数:");
		for (int i = 0; i < typeNum; i++) {
			Ssum[i] = in.nextInt();
		}
		return Ssum;
	}

	public int[][] getMax() {
		Max = new int[progressNum][typeNum];
		System.out.println("请输入最大需求矩阵:");
		for (int i = 0; i < progressNum; i++) {
			for (int j = 0; j < typeNum; j++) {
				Max[i][j] = in.nextInt();
			}
		}
		return Max;
	}

	public int[][] getAllocation() {
		Allocation = new int[progressNum][typeNum];
		System.out.println("请输入已分配资源情况矩阵");
		for (int i = 0; i < progressNum; i++) {
			for (int j = 0; j < typeNum; j++) {
				Allocation[i][j] = in.nextInt();
			}
		}
		return Allocation;
	}

	public int[][] getNeed() {
		Need = new int[progressNum][typeNum];
		for (int i = 0; i < progressNum; i++) {
			for (int j = 0; j < typeNum; j++) {
				Need[i][j] = Max[i][j] - Allocation[i][j];
				
			}
		}
		return Need;
	}

	public int[] getAvailable(int x, int y) {
		Available = new int[typeNum];
		Available = Ssum;
		System.out.println("进程的可用资源Available为：");
		for (int j = 0; j < typeNum; j++) {
			for (int i = 0; i < progressNum; i++) {
				Available[j] = Available[j] - Allocation[i][j];
			}
			System.out.print(Available[j] + " ");
		}
		System.out.println("");
		return Available;
	}

	public void setFinish(int x) {
		for (int i = 0; i < progressNum; i++) {
			Finish[i] = false;
		}
	}

	public boolean Check_Safe(int avail[]) {
		boolean boo = false;
		int k[] = new int[progressNum];
		int a = 0;
		Work = new int[typeNum];
		for (int i = 0; i < avail.length; i++) {
			Work[i] = avail[i];
		}

		setFinish(progressNum);
		for (int s = 0; s < progressNum; s++) {

			for (int i = 0; i < progressNum; i++) {
				if (Finish[i] == false) {

					for (int j = 0; j < typeNum; j++) {
						if (Need[i][j] <= Work[j]) {
							if (j + 1 == typeNum) {
								Finish[i] = true;
								k[a] = i;
								a++;
								for (int m = 0; m < typeNum; m++) {
									Work[m] = Work[m] + Allocation[i][m];
								}

							} else {
								continue;
							}

						} else {
							break;
						}
					}

				} else {
					continue;
				}
			}
		}
		if (a == progressNum) {
			System.out.println("此刻系统处于安全状态，存在安全序列为：");

			for (int i = 0; i < progressNum; i++) {
				System.out.print("P" + k[i] + "\t");
			}
			System.out.println("");
			boo = true;

		} else {
			System.out.println("此时系统处于非安全状态");
			choice();
			boo = false;
		}
		return boo;

	}

	public void Ask_Distribution(boolean b) {
		int a = 0;
		int a0=0;
		int a1 = 0;
		boolean bo = false;
		for (int i = 0; i < typeNum; i++) {
			Work[i] = Available[i];
		}

		System.out.println("请输入请求分配的进程编号：");
		int m = in.nextInt();
		System.out.println("请输入请求的各资源数");
		int dis[] = new int[typeNum];
		for (int i = 0; i < typeNum; i++) {
			dis[i] = in.nextInt();
		}
		for (int i = 0; i < typeNum; i++) {
			if (dis[i] <= Need[m][i]) {
				a++;
				continue;

			} else {
				System.out.println("出错！！！请求资源数大于需求资源数!");
				choice();
				break;
			}
		}
		if (a == typeNum) {
			for (int i = 0; i < typeNum; i++) {
				if (dis[i] <= Work[i]) {
					a0=a0+1;
					if(a0==typeNum){
						for (int j = 0; j < dis.length; j++) {
							Work[j] = Work[j] - dis[j];
							Allocation[m][j] = Allocation[m][j] + dis[j];
							Need[m][j] = Need[m][j] - dis[j];
						}
						bo = Check_Safe(Work);
					}
					continue;
				} else {
					System.out.println("出错！！！请求资源数大于可用资源数!");
					choice();
					break;
				}
			}
		}

		
		if (bo) {
			for (int i = 0; i < typeNum; i++) {
				Available[i] = Available[i]-dis[i];
				if (Allocation[m][i] == Max[m][i]) {
					a1 = a1 + 1;
				}
				while (a1 == typeNum) {
					System.out.println("(进程P"+m+"对资源的最大需求已满足，对其占有资源进行回收)");
					for (int j = 0; j <typeNum; j++) {
						Available[j] = Available[j] + Allocation[m][j];
					}
					break;

				}

			}
			System.out.println("因此可以满足" + m + "进程的请求，分配后的各种变量值更新为:");
			output();
			choice();
			
		}else{
			for (int i = 0; i < dis.length; i++) {
				Work[i] = Work[i] + dis[i];
				Allocation[m][i] = Allocation[m][i] - dis[i];
				Need[m][i] = Need[m][i] + dis[i];
			}
		}
	}

	public void output() {

		System.out.println(" 进程     max\t\tallocation\t  need\t\tavailable");
		System.out.print("P0  ");
		for (int i = 0; i < typeNum; i++) {
			System.out.print(Max[0][i] + "   ");
		}
		System.out.print(" 	");
		for (int i = 0; i < typeNum; i++) {
			System.out.print(Allocation[0][i] + "   ");
		}
		System.out.print(" 	");
		for (int i = 0; i < typeNum; i++) {
			System.out.print(Need[0][i] + "   ");
		}
		System.out.print(" 	");
		for (int i = 0; i < typeNum; i++) {
			System.out.print(Available[i] + "   ");
		}
		System.out.println();
		for (int i = 1; i < progressNum; i++) {
			System.out.print("P" + i + "  ");
			for (int j = 0; j < typeNum; j++) {
				System.out.print(Max[i][j] + "   ");
			}
			System.out.print(" 	");
			for (int j = 0; j < typeNum; j++) {
				System.out.print(Allocation[i][j] + "   ");
			}
			System.out.print(" 	");
			for (int j = 0; j < typeNum; j++) {
				System.out.print(Need[i][j] + "   ");
			}

			System.out.println();
		}

	}

	public void choice() {
		System.out.println("*****************************************");
		System.out.println("“Y”选择再次输入\n“N”返回银行家算法初始位置");
		System.out.println("****************************************");
		String str = in.next();
		if (str.equals("y")) {
			Ask_Distribution(false);
		} else {
			new Bank();
		}
	}
	
	public void quit() {
		System.out.println("您确定要退出吗?请选择“Y”/“N”");
		String a = in.next();
		if (a.equals("Y")) {
			System.out.println("**************感谢您的使用！**************");

		} else {
			start();
		}
	}
	
	public static void main(String[] args) {
		Bank yh = new Bank();
	}
}