银行家算法代码
简介：本文为大家奉献银行家算法的java代码实现，拿去吧，我的算法思路就是深度优先遍历（DFS），对深度优先遍历不熟悉的，可以看看我的这篇博客。
银行家算法：银行家算法（Banker's Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。
/*银行家算法 Banker Algorithm*/
/*算法思路：dfs（深度优先遍历）*/
import java.util.*;
public class Main{
static class Process{ // 每个进程的情况
public Resources max;
public Resources allocation;
public Resources need;
public Process() {
// TODO Auto-generated constructor stub
}
public Process(Resources max, Resources allocation, Resources need)
{
this.max = max;
this.allocation = allocation;
this.need = need;
}
}
static class Resources // 这里以三个资源为例子
{
int A, B, C;
public Resources(int A, int B, int C) {
this.A = A;
this.B = B;
this.C = C;
//System.out.println("RE" + this.A + " " + this.B + " " + this.C);
}
void showAll() // 查看当前的资源的占比情况 调试用的
{
System.out.println("A:" + A + " " + "B:" + B + " " + "C:" + C);
}
}
static List<Process> pset = new ArrayList<Process>(); // 存放每个进程的情况
static List<Integer> v = new ArrayList<Integer>(); // 存放最后的安全序列的
static int N = 110; // 资源的最大个数的限制
static boolean [] st = new boolean[N]; // dfs的辅助数组
static int n;
static Resources available; // 把可用的资源定义为全局数组 方便修改
static int cnt = 0; // 存放最后的结果数
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.print("输入进程数：");
n = in.nextInt(); // 进程的数量
int a, b, c;
int i = 0;
int t = n;
while(t -- > 0)
{
System.out.println("输入进程P" + i + "的Max:");
System.out.print("A:");
a = in.nextInt();
System.out.print("B:");
b = in.nextInt();
System.out.print("C:");
c = in.nextInt();
i ++;
Resources max = new Resources(a, b, c);
System.out.println("输入Allocation:");
System.out.print("A:");
a = in.nextInt();
System.out.print("B:");
b = in.nextInt();
System.out.print("C:");
c = in.nextInt();
Resources allocation = new Resources(a, b, c);
pset.add(new Process(max, allocation, Sub(max, allocation)));
}
System.out.println("输入Available:");
System.out.print("A:");
a = in.nextInt();
System.out.print("B:");
b = in.nextInt();
System.out.print("C:");
c = in.nextInt();
available = new Resources(a, b, c);
if (n == 0) return;
dfs(0);
if (cnt == 0) System.out.println("没有安全序列");
System.out.println("安全序列的数量：" + cnt);
}
static Resources Sub(Resources r1, Resources r2) // 计算两个资源集合相减的结果
{
Resources r = new Resources(r1.A - r2.A, r1.B - r2.B, r1.C - r2.C);
// System.out.println("Sub");
// r.showAll();
return r;
}
static Resources Add(Resources r1, Resources r2) // 两个资源集合相加
{
Resources r = new Resources(r1.A + r2.A, r1.B + r2.B, r1.C + r2.C);
// System.out.println("Add:");
// r.showAll();
return r;
}
static boolean CP(Resources r1, Resources r2) // 对两个资源集合进行比较 r1 <= r2返回true
{
boolean flag = false;
if (r1.A <= r2.A && r1.B <= r2.B && r1.C <= r2.C) flag = true;
// if (flag == false)
// {
// System.out.println("r1 ");
// r1.showAll();
// System.out.println("r2 ");
// r2.showAll();
// }
return flag;
}
// 深度优先遍历的模板
static void dfs(int u)
{
if (u == n)
{
cnt ++;
for (Integer it : v) // 打印结果
{
System.out.print("P" + it + " ");
}
System.out.println();
return;
}
for (int i = 0; i < n; ++ i)
{
Resources t1 = pset.get(i).need;
Resources t2 = pset.get(i).allocation;
if (!st[i] && CP(t1, available)) // 如果当前的这个进程的need小于available而且没有被访问过
{
st[i] = true;
available = Add(t2, available);
v.add(i);
dfs(u + 1);
available = Sub(available, t2);
st[i] = false;
v.remove(v.size() - 1);
}
}
}
}运行结果：
输入进程数：5
输入进程P0的Max:
A:7
B:5
C:3
输入Allocation:
A:0
B:1
C:0
输入进程P1的Max:
A:3
B:2
C:2
输入Allocation:
A:2
B:0
C:0
输入进程P2的Max:
A:9
B:0
C:2
输入Allocation:
A:3
B:0
C:2
输入进程P3的Max:
A:2
B:2
C:2
输入Allocation:
A:2
B:1
C:1
输入进程P4的Max:
A:4
B:3
C:3
输入Allocation:
A:0
B:0
C:2
输入Available:
A:3
B:3
C:2
P1 P3 P0 P2 P4
P1 P3 P0 P4 P2
P1 P3 P2 P0 P4
P1 P3 P2 P4 P0
P1 P3 P4 P0 P2
P1 P3 P4 P2 P0
P1 P4 P3 P0 P2
P1 P4 P3 P2 P0
P3 P1 P0 P2 P4
P3 P1 P0 P4 P2
P3 P1 P2 P0 P4
P3 P1 P2 P4 P0
P3 P1 P4 P0 P2
P3 P1 P4 P2 P0
P3 P4 P1 P0 P2
P3 P4 P1 P2 P0
安全序列的数量：16