threadtest.java

java语言银行家算法的简单实现

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!!!---"); 
} 
}