银行家算法(java实现)

引言

银行家算法是一种避免进程发生死锁的算法。

死锁的定义：
如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么改组进程是死锁的(Deadlock)
在死锁避免方法中，把系统的状态分为安全状态和不安全状态。
安全状态和不安全状态：
是指系统能按某种进程推进顺序$\left ( P_{1},P_{2}, ...,P_{n}\right )$ 为每个进程$P_{i}$分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。并称$\left ( P_{1},P_{2}, ...,P_{n}\right )$为安全序列。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。

银行家算法中的数据结构

银行家算法中有四个数据结构：

• 最大需求向量(Max)：是一个长度为m的数组，它定义了系统中每个进程对第m类资源的最大需求
• 已分配向量(Allocation)：是一个长度为m的数组，它定义了系统中每个进程对每一类资源分配给进程的资源数量。
• 需求向量(Need)：是一个长度为m的数组，用以表示进程还需要的各类资源数量
• 可利用资源向量(Available)：是一个长度为m的数组，其中每一个值代表可以当前可利用的资源数目。

上述数据中有这样的关系：Need = Max - Allocation

银行家算法

史上最详细的步骤^_^

• 【步骤一】创建进程数组PCB[n] (代表n个进程)
• 【步骤二】输入并初始化每个进程PCB[i]的Max数组、Allocation数组
• 【步骤三】利用Max数组和Allocation数组计算出Need数组
• 【步骤四】输入Available数组
• 【步骤五】为每个PCB添加完成状态变量Finish(0-未完成，1-完成)，得到Finish数组(全部初始化为0)
• 【步骤六】初始化表示安全状态变量Safe_Status = 0(0-不安全，1-安全)
• 【步骤七】循环进行资源分配：
• WHILE(SUM(Finish) < n):
• Safe_Status = 0
• FOR i = 1 TO n
• IF PCB[i]中Need的每个值 <= Avaliable的每个值 AND PCB[i].Finish == 0
• PCB[i].Finish = 1
• 将该进程PCB[i]加入安全序列队列
• Available = Available + PCB[i].Need
• Safe_Status = 1
• END IF
• END FOR
• IF Safe_Status == 0
• BREAK
• END IF
• END WHILE
• 【步骤八】判断系统是否安全：
• IF (SUM(Finish == n))
• 该系统安全
• END IF
• 【步骤九】输出安全序列队列

用Java实现银行家算法

Proc.java

表示进程信息的进程类

public class Proc {
	char name;
	int max_res[];
	int alloc_res[];
	int need_res[];
	boolean finish_status = false;

	public Proc(char name , int max[], int alloc[], int need[]) {
		// TODO Auto-generated constructor stub
		this.name = name;
		this.max_res = max;
		this.alloc_res = alloc;
		this.need_res = need;
		this.finish_status = false;
	}

	public void setName(char name) {
		this.name = name;
	}

	public char getName() {
		return name;
	}

	public void setMax_res(int max_res[]) {
		this.max_res = max_res;
	}

	public int[] getMax_res() {
		return max_res;
	}

	public void setAlloc_res(int alloc_res[]) {
		this.alloc_res = alloc_res;
	}

	public int[] getAlloc_res() {
		return alloc_res;
	}

	public void setNeed_res(int need_res[]) {
		this.need_res = need_res;
	}

	public int[] getNeed_res() {
		return need_res;
	}
}

BankRR.java

银行家算法和程序入口所在的类

import java.util.Scanner;

public class BankRR
{
	int pcb_nums;  // 进程数量
	int res_nums;  // 资源种类数量
	Proc pcbs[];   // 进程数组
	int max[];     // 最大需求资源向量
	int alloc[];   // 拥有资源数向量
	int need[];    // 还需要资源数向量
	int ava[];     // 可用资源数向量
	char safe_seq[];  // 安全序列数组
	boolean safe_stauts = false;  // 安全序列

	public void bank_init()
	{
		// A sample
		/*   Max   Alloc  Need   Avai
		 - a 7 5 3, 0 1 0, 7 4 3, 3 3 2
		 - b 3 2 2, 2 0 0, 1 2 2
		 - c 9 0 2, 3 0 2, 6 0 0
		 - d 2 2 2, 2 1 1, 0 1 1
		 - e 4 3 3, 0 0 2, 4 3 1
		 */
		@SuppressWarnings("resource")
		Scanner in = new Scanner(System.in);
		System.out.println("一共有几个进程：");
		pcb_nums = in.nextInt();
		System.out.println("一共有几个资源");
		res_nums = in.nextInt();
		pcbs = new Proc[pcb_nums];  // 创建进程数组
		ava = new int[res_nums];     // 可用资源
		safe_seq = new char[pcb_nums];  // 安全序列
		for (int i = 0; i < pcbs.length; i++)
		{
			max = new int[res_nums];     // 最大资源
			alloc = new int[res_nums];   // 拥有资源
			need = new int[res_nums];    // 需要资源
			System.out.println("-----------------------");
			System.out.println("输入第" + (i+1) + "个进程信息(名字-最大资源-拥有资源)");
			System.out.println("名字：");
			char name = in.next().charAt(0);
			System.out.println("最大资源：");
			for (int j = 0; j < res_nums; j++)
			{
				max[j] = in.nextInt();
			}
			System.out.println("拥有资源：");
			for (int j = 0; j < res_nums; j++)
			{
				alloc[j] = in.nextInt();
			}
			for (int j = 0; j < res_nums; j++)
			{
				need[j] = max[j] - alloc[j];
			}
			pcbs[i] = new Proc(name, max, alloc, need);
		}
		System.out.println("---可用资源---：");
		for (int j = 0; j < res_nums; j++)
		{
			ava[j] = in.nextInt();
		}
	}

	public void algori()
	{
		int safe_count = 0;
		while(safe_count != pcb_nums)
		{
			for (int i = 0; i < pcb_nums; i++)
			{
				if (pcbs[i].finish_status == false) // 判断该pcb是否完成
				{
					for (int j = 0; j < res_nums; j++)
					{
						int now_res = pcbs[i].getNeed_res()[j];
						if (now_res <= ava[j])
						{
							pcbs[i].finish_status = true;
						}
						else
						{
							pcbs[i].finish_status = false;
							break;
						}
					}

					if (pcbs[i].finish_status) // 如果该pcb可以完成，则完成后回收资源
					{
						for (int j = 0; j < res_nums; j++)
						{
							ava[j] += pcbs[i].getNeed_res()[j];
						}
						safe_seq[safe_count] = pcbs[i].getName();
						safe_count++;
					}
				}
			}
			for (int i = 0; i < pcb_nums; i++)
			{
				if (pcbs[i].finish_status)
				{
					safe_stauts = true;
					break;
				}
				else
				{
					safe_stauts = false;
				}
			}
			if (!safe_stauts) {
				break;
			}
		}
		if (safe_stauts) {
			System.out.println("该系统安全，安全序列为：");
			for (int i = 0; i < pcb_nums; i++) {
				System.out.print(safe_seq[i]+" ");
			}
		}
		else {
			System.out.println("该系统不安全");
		}
	}
	public static void main(String[] args)
	{
		BankRR test = new BankRR();
		test.bank_init();
		test.algori();
	}
}

运行示例

进程样例如下：

运行结果：

一共有几个进程：
5
一共有几个资源
3
-----------------------
输入第1个进程信息(名字-最大资源-拥有资源)
名字：
a
最大资源：
7 5 3
拥有资源：
0 1 0
-----------------------
输入第2个进程信息(名字-最大资源-拥有资源)
名字：
b
最大资源：
3 2 2
拥有资源：
2 0 0
-----------------------
输入第3个进程信息(名字-最大资源-拥有资源)
名字：
c
最大资源：
9 0 2
拥有资源：
3 0 2
-----------------------
输入第4个进程信息(名字-最大资源-拥有资源)
名字：
d
最大资源：
2 2 2
拥有资源：
2 1 1
-----------------------
输入第5个进程信息(名字-最大资源-拥有资源)
名字：
e
最大资源：
4 3 3
拥有资源：
0 0 2
---可用资源---：
3 3 2
该系统安全，安全序列为：
b d e a c