threadtest.java

银行家算法

package bankpackage;

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