银行家

import java.util.*;

class ThreadTest {
static int type = 4, num = 10; //定义资源数目和线程数目
static int[] resource = new int[type]; //系统资源总数
//static int[] copyResource = new int[type]; //副本
static Random rand = new Random();
static Bank[] bank = new Bank[num]; //线程组
Bank temp = new Bank();

public void init() {
//初始化组中每个线程，随机填充系统资源总数
for(int i = 0; i < type; i++)
resource[i] = rand.nextInt(10) + 80;
System.out.print( Resource: );
for(int i = 0; i < type; i++)
System.out.print( + resource[i]);
System.out.println( );
for(int i = 0; i < bank.length; i++)
bank[i] = new Bank( # + i);
}
public ThreadTest4() {
init();
}

class Bank extends Thread {
//银行家算法避免死锁
public int[]
max = new int[type], //总共需求量
need = new int[type], //尚需资源量
allocation = new int[type]; //已分配量
private int[]
request = new int[type], //申请资源量
copyResource = new int[type]; //资源副本
private boolean isFinish = false; //线程是否完成
int[][] table = new int[bank.length][type*4]; //二维资源分配表

private void init() {
// 随机填充总共、尚需、已分配量
synchronized(resource) {
for(int i = 0; i < type; i++) {
max[i] = rand.nextInt(5) + 10;
need[i] = rand.nextInt(10);
allocation[i] = max[i] - need[i];
resource[i] -= allocation[i]; //从系统资源中减去已分配的
}
printer();
for(int i = 0; i < type; i++) {
if(resource[i] < 0) {
//若出现已分配量超出系统资源总数的错误则退出
System.out.println( The summation of Threads allocations is out of range! );
System.exit(1);
}
}
}
}

public Bank(String s) {
setName(s);
init();
start();
}
public Bank() {
//none
}

public void run() {
try {
sleep(rand.nextInt(2000));
}
catch(InterruptedException e) {
throw new RuntimeException(e);
}
while(true) {
//程序没有完成时一直不断申请资源
if(askFor() == false) {
try {
sleep(1000);
}
catch(InterruptedException e) {
throw new RuntimeException(e);
}
}
else
tryRequest();
if(noNeed() == true)
break;
}
//休眠一段时间模拟程序运行
try {
sleep(1000);
}
catch(InterruptedException e) {
throw new RuntimeException(e);
}
System.out.println(getName() + finish! );
synchronized(resource) {
//运行结束释放占有资源
for(int i = 0; i < type; i++) {
resource[i] += allocation[i];
need[i] = allocation[i] = max[i] = 0;
}
}
}

private void printer() {
//打印当前资源信息
System.out.print(getName() + Max: );
for(int i = 0; i < type; i++)
System.out.print( + max[i]);
System.out.print( Allocation: );
for(int i = 0; i < type; i++)
System.out.print( + allocation[i]);
System.out.print( Need: );
for(int i = 0; i < type; i++)
System.out.print( + need[i]);
System.out.print( Available: );
for(int i = 0; i < type; i++)
System.out.print( + resource[i]);
System.out.println( );
}
private boolean askFor() {
//随机产生申请资源量并检测是否超标
boolean canAsk = false;
for(int i = 0; i < type; i++) {
request[i] = rand.nextInt(20);
//防止申请量超过所需量
if(request[i] > need[i])
request[i] = need[i];
}
for(int i = 0; i < type; i++) //防止随机申请资源全为0
if(request[i] > 0)
canAsk = true;
synchronized(resource) {
//锁住可供资源检查是否超标
for(int i = 0; i < type; i++) {
if(request[i] > resource[i])
//如果申请资源超过可供资源则等待一段时间后重新申请
return false;
}
}
return canAsk;
}
private void tryRequest() {
//创建副本尝试分配请求
synchronized(resource) {
for(int i = 0; i < type; i++)
//依然要防止请求量超出范围
if(request[i] > resource[i])
return;
for(int i = 0; i < type; i++) {
//复制资源量并减去需求量到一个副本上
copyResource[i] = resource[i];
copyResource[i] -= request[i];
}
System.out.print(getName() + ask for: );
for(int i = 0; i < type; i++)
System.out.print( + request[i]);
System.out.println( );
if(checkSafe() == true) {
//如果检查安全则将副本值赋给资源量并修改占有量和需求量
for(int i = 0; i < type; i++) {
resource[i] = copyResource[i];
allocation[i] += request[i];
need[i] -= request[i];
}
System.out.println(getName() + request succeed! );
}
else
System.out.println(getName() + request fail! );
}
}
private boolean checkSafe() {
//银行家算法检查安全性
synchronized(bank) {
//将线程资源信息放入二维资源分配表检查安全性，0~type可用资源／type~type*2所需资源／type*2~type*3占有资源／type*3~-1可用+占用资源
for(int i = 0; i < bank.length; i++) {
for(int j = type; j < type*2; j++) {
table[i][j] = bank[i].need[j%type];
}
for(int j = type*2; j < type*3; j++) {
table[i][j] = bank[i].allocation[j%type];
}
}
//冒泡排序按需求资源从小到大排
for(int i = 0; i < bank.length; i++) {
for(int j = i; j < bank.length-1; j++) {
sort(j, 4);
}
}
//进行此时刻的安全性检查
for(int i = 0; i < type; i++) {
table[0][i] = copyResource[i];
table[0][i+type*3] = table[0][i] + table[0][i+type*2];
if(table[0][i+type*3] < table[1][i+type])
return false;
}
for(int j = 1; j < bank.length-1; j++) {
for(int k = 0; k < type; k++) {
table[j][k] = table[j-1][k+type*3];
table[j][k+type*3] = table[j][k] + table[j][k+type*2];
if(table[j][k+type*3] < table[j+1][k+type])
return false;
}
}
}
return true;
}
private void sort(int j, int k) {
//递归冒泡排序
int tempNum;
if(table[j][k] > table[j+1][k]) {
for(int i = type; i < type*2; i++) {
tempNum = table[j][i];
table[j][i] = table[j+1][i];
table[j+1][i] = tempNum;
}
/*temp = bank[j];
bank[j] = bank[j+1];
bank[j+1] = temp;*/
}
else if(table[j][k] == table[j+1][k] && k < type*2) //此资源量相同时递归下一个资源量排序并且防止超出范围
sort(j, k+1);
}
private boolean noNeed() {
//是否还需要资源
boolean finish = true;
for(int i = 0; i < type; i++) {
if(need[i] != 0) {
finish = false;
break;
}
}
return finish;
}
}

public static void main(String[] args) {
ThreadTest t = new ThreadTest();
//后台线程，设定程序运行多长时间后自动结束
new Timeout(30000, ---Stop!!!--- );
}
}