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 = 0i <typei++)
resource[i] = rand.nextInt(10) + 80
System.out.print("Resource:")
for(int i = 0i <typei++)
System.out.print(" " + resource[i])
System.out.println("")
for(int i = 0i <bank.lengthi++)
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 = 0i <typei++) {
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 = 0i <typei++) {
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 = 0i <typei++) {
resource[i] += allocation[i]
need[i] = allocation[i] = max[i] = 0
}
}
}
private void printer() {
//打印当前资源信息
System.out.print(getName() + " Max:")
for(int i = 0i <typei++)
System.out.print(" " + max[i])
System.out.print(" Allocation:")
for(int i = 0i <typei++)
System.out.print(" " + allocation[i])
System.out.print(" Need:")
for(int i = 0i <typei++)
System.out.print(" " + need[i])
System.out.print(" Available:")
for(int i = 0i <typei++)
System.out.print(" " + resource[i])
System.out.println("")
}
private boolean askFor() {
//随机产生申请资源量并检测是否超标
boolean canAsk = false
for(int i = 0i <typei++) {
request[i] = rand.nextInt(20)
//防止申请量超过所需量
if(request[i] >need[i])
request[i] = need[i]
}
for(int i = 0i <typei++) //防止随机申请资源全为0
if(request[i] >0)
canAsk = true
synchronized(resource) {
//锁住可供资源检查是否超标
for(int i = 0i <typei++) {
if(request[i] >resource[i])
//如果申请资源超过可供资源则等待一段时间后重新申请
return false
}
}
return canAsk
}
private void tryRequest() {
//创建副本尝试分配请求
synchronized(resource) {
for(int i = 0i <typei++)
//依然要防止请求量超出范围
if(request[i] >resource[i])
return
for(int i = 0i <typei++) {
//复制资源量并减去需求量到一个副本上
copyResource[i] = resource[i]
copyResource[i] -= request[i]
}
System.out.print(getName() + " ask for:")
for(int i = 0i <typei++)
System.out.print(" " + request[i])
System.out.println("")
if(checkSafe() == true) {
//如果检查安全则将副本值赋给资源量并修改占有量和需求量
for(int i = 0i <typei++) {
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 = 0i <bank.lengthi++) {
for(int j = typej <type*2j++) {
table[i][j] = bank[i].need[j%type]
}
for(int j = type*2j <type*3j++) {
table[i][j] = bank[i].allocation[j%type]
}
}
//冒泡排序按需求资源从小到大排
for(int i = 0i <bank.lengthi++) {
for(int j = ij <bank.length-1j++) {
sort(j, 4)
}
}
//进行此时刻的安全性检查
for(int i = 0i <typei++) {
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 = 1j <bank.length-1j++) {
for(int k = 0k <typek++) {
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 = typei <type*2i++) {
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 = 0i <typei++) {
if(need[i] != 0) {
finish = false
break
}
}
return finish
}
}
public static void main(String[] args) {
ThreadTest t = new ThreadTest()
//后台线程，设定程序运行多长时间后自动结束
new Timeout(30000, "---Stop!!!---")
}
}
什么是银行家算法：银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。
要解释银行家算法，必须先解释 *** 作系统安全状态和不安全状态。
安全序列是指一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j <i )当前占有资源量之和。
安全状态
如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。
不安全状态
不存在一个安全序列。不安全状态不一定导致死锁。
原理：
我们可以把 *** 作系统看作是银行家， *** 作系统管理的资源相当于银行家管理的资金，进程向 *** 作系统请求分配资源相当于用户向银行家贷款。
为保证资金的安全,银行家规定:
(1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客
(2) 顾客可以分歧贷款,但贷款的总数不能超过最大需求量
(3) 当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款
(4) 当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金.
*** 作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。
程序举例：
已知进程{P0,P1,P2,P3,P4}，有三类系统资源A、B、C的数量分别为10、5、7，在T0时刻的资源
（1）若进程P1请求资源，发出请求向量Request1（1，0，2），编写程序用银行家算法判断系统能否将资源分配给它；
（2）若进程P2提出请求Request(0，1，0)，用银行家算法程序验证系统能否将资源分配给它。
程序代码：
P1进程提出的请求，可以分配。
P2进程不能分配，因为请求的B类资源超过了它的最大值。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 50
void main()
{
unsigned int Available[MAXSIZE] //可利用资源向量
unsigned int Max[MAXSIZE][MAXSIZE] //最大需求矩阵
unsigned int Allocation[MAXSIZE][MAXSIZE]//已分配矩阵
unsigned int Need[MAXSIZE][MAXSIZE] //需求矩阵
unsigned int Request[MAXSIZE] //请求向量
unsigned int Work[MAXSIZE]//工作向量
bool Finish[MAXSIZE] //是否有足够资源分配给进程,使之运行完成
unsigned int SafeSequence[MAXSIZE] //安全序列
int i,j
int p//请求资源的进程的下标
int temp = 0 //安全序列下标
int total = 0
int N
int M
printf("请输入进程数N=")
scanf("%d",&N)
printf("请输入资源种类数M=")
scanf("%d",&M)
//用户输入数据,初始化Available数组
printf("初始化可用资源数组:\n")
for(i=0i<Mi++)
{
printf("\t%c类资源:",65+i)
scanf("%d",&Available[i])
}
//用户输入数据,初始化Max数组
printf("初始化最大需求数组:\n")
for(i=0i<Ni++)
{
printf("\tP%d进程最大需要\n",i)
for(j=0j<Mj++)
{
printf("\t\t%c类资源:",65+j)
scanf("%d",&Max[i][j])
}
}
//用户输入数据,初始化Allocation数组
printf("初始化已分配资源数组:\n")
for(i=0i<Ni++)
{
printf("\tP%d进程已分配\n",i)
for(j=0j<Mj++)
{
printf("\t\t%c类资源:",65+j)
scanf("%d",&Allocation[i][j])
}
}
//初始化Need数组
for(i=0i<Ni++)
for(j=0j<Mj++)
{
Need[i][j] = Max[i][j] - Allocation[i][j]
}
//进程发出资源请求后检查
do
{
printf("资源请求:\n")
printf("\t输入请求资源的进程下标:")
scanf("%d",&p)
printf("\t进程P%d请求\n",p)
//初始化请求向量
for(i=0i<Mi++)
{
printf("\t\t%c类资源:",65+i)
scanf("%d",&Request[i])
}
for(i=0i<Mi++) //检查Request <= Need ?
if(Request[i] >Need[p][i])
{
printf("\t请求的%c类资源数超过它所宣布的最大值!\n",65+i)
break
}
if(i == M) //通过上层检查,继续检查Request <= Available ?
{
for(i=0i<Mi++)
if(Request[i] >Available[i])
{
printf("\t尚无足够%c类资源,P%d须等待!\n",65+i,p)
break
}
}
if(i == M) //尝试分配
{
for(i=0i<Mi++)
{
Available[i] -= Request[i]
Allocation[p][i] += Request[i]
Need[p][i] -= Request[i]
}
}
}while(i<M)
//初始化Work,Finish向量
for(i=0i<Mi++)
{
Work[i] = Available[i]
}
for(i=0i<Ni++)
{
Finish[i] = false
}
//安全性算法
do
{
total = temp
for(i=0i<Ni++)
{
if(Finish[i] == false)
{
for(j=0j<Mj++)
if(Need[i][j] >Work[j])
{
break
}
if(j == M) //各类资源都满足Need <= Work
{
for(j=0j<Mj++)
{
Work[j] += Allocation[i][j]//释放资源
}
Finish[i] = true
SafeSequence[temp++] = i //加入安全序列
}
}
}
}while(total != temp) //所有进程检查一遍之后，如果安全序列有变化，则进行下一轮
//否则说明所有的Finish都为true,或者因没有安全序列退出循环
if(temp == N)
{
printf("安全序列:")
for(temp=0temp<Ntemp++)
{
printf("P%d ",SafeSequence[temp])
}
}
else
{
printf("系统处于不安全状态!不能分配!\n")
}
getchar()
getchar()
}
这个程序还行，输入有点麻烦，我自己编写的是用文件输入系统描述信息的，但是缺少说明，怕你搞不明白。希望对你有所帮助！
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）