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