死锁避免设计思想
当进程请求资源时，对进程发出的每一个系统能够满足的自愿申请进行动态检查，并根据检查结果决定是否分配资源。
制约关系
- 假设进程P和Q同时请求同一个资源，资源总数为M。Q的最大需求量为B，P的最大需求量为A
- 当已经分配情况的交点处于OXO2Y时，P或Q都能满足
- 当已经分配情况的交点处于O2O3AX时，能够满足P不能满足Q
- 当处于BO1O3Y时，能够满足Q不能满足P
- 当进入O1O2O3时，任意进程都不能满足，认为绝对发生死锁，这是需要避免的
安全状态与安全序列
- 安全状态：系统中存在一个由所有进程构成的安全序列
- 安全序列：一个进程序列{P1,…Pn}，对于每一个进程，它以后还需要的资源量不超过西戎当前剩余资源量与所有进程Pj(j< i)当前占有资源量（考虑之前的进程占有完后会释放）之和。
典型实现方式（银行家算法）
思路：先假定分配好的情况，再判断是否安全
- 初始化
n: 系统进程数量 m: 资源类数量 Available ARRAY[1..m] of integer //可用资源 Max: ARRAY[1..n, 1..m] of integer //各进程对各类资源最大需求 Allocation: ARRAY[1..n, 1..m] of integer //当前资源分配情况 Request: ARRAY[1..n, 1..m] of integer //各进程请求情况 - 假定分配好的状态(以下为简记，只考虑一类资源)
1. 若Request[i] <= Need[i] 转2. 否则报错 2. 若Request[i] <= Available 转3. 否则等待 3. 假设系统分配了资源。则有新状态 Avaliable -= Request[i] Allocation[i] += Request[i]; Need[i] -= Request[i] - 安全性检查
Work: ARRAY[1..m] of integer //当前剩余资源 Finish: ARRAY[1..n] of Boolean //检查进程是否成功 1. Work = Available; Finish = false 2. 寻找进程i，满足 a. Finish[i] == false b. Need[i] <= Work 若不存在，则转4 3. Work += Work + Allocation; Finish[i]=true; //模拟Pj释放资源 4. 若对所有i，Finish[i]==true,则安全，否则不安全
Java实现
import java.util.Scanner;
public class Banker {
final static int NUM_RESOURCES = 100;
final static int NUM_Thread = 100;
int[] Avaliable = {10, 8, 7};
int[][] Max = new int[3][3];
int[][] Allocation = new int[3][3];
int[][] Need = new int[3][3];
int[][] Request = new int[3][3];
int[] Work = new int[3];
int num = 0;//进程编号
Scanner in = new Scanner(System.in);
public Banker(){}
public void setSystemVariable(){//设置各初始系统变量，并判断是否处于安全状态。
setMax();
setAllocation();
printSystemStatus();
testSafe();
}
public void setMax() {//设置Max矩阵
System.out.println("请设置各进程的最大需求矩阵Max：");
for (int i = 0; i < 3; i++) {
System.out.println("请输入进程P" + i + "的最大资源需求量：");
for (int j = 0; j < 3; j++) {
Max[i][j] = in.nextInt();
}
}
}
public void setAllocation() {
System.out.println("请设置各进程分配矩阵Alloction：");
for (int i = 0; i < 3; i++) {
System.out.println("请输入进程P" + i + "的分配资源量：");
for (int j = 0; j < 3; j++) {
Allocation[i][j] = in.nextInt();
}
}
System.out.println("Available=Available-Alloction.");
System.out.println("Need=Max-Alloction.");
for (int i = 0; i < 3; i++) {//设置Alloction矩阵
for (int j = 0; j < 3; j++) {
Avaliable[i] = Avaliable[i] - Allocation[j][i];
}
}
for (int i = 0; i < 3; i++) {//设置Need矩阵
for (int j = 0; j < 3; j++) {
Need[i][j] = Max[i][j] - Allocation[i][j];
}
}
}
public void printSystemStatus() {
System.out.println("此时资源分配量如下：");
System.out.println("进程 "+" Max "+" Alloction "+" Need "+" Available ");
for(int i=0;i<3;i++) {
System.out.print("P" + i + " ");
for(int j=0;j<3;j++) {
System.out.print(Max[i][j] + " ");
}
System.out.print("| ");
for(int j=0;j<3;j++) {
System.out.print(Allocation[i][j] + " ");
}
System.out.print("| ");
for(int j=0;j<3;j++) {
System.out.print(Need[i][j] + " ");
}
System.out.print("| ");
if(i==0) {
for(int j=0;j<3;j++) {
System.out.print(Avaliable[j] + " ");
}
}
System.out.println();
}
}
public void setRequest() {
System.out.println("输入进程编号");
num = in.nextInt();
System.out.println("输入请求资源");
for(int j=0;j<3;j++) {
Request[num][j] = in.nextInt();
}
System.out.println("即进程P" + num + "对各资源请求Request：(" + Request[num][0] + "," + Request[num][1] + "," + Request[num][2] + ").");
BankerAlgorithm();
}
public void BankerAlgorithm() {
boolean T = true;
if(Request[num][0] <= Need[num][0] && Request[num][1] <= Need[num][1] && Request[num][2] <= Need[num][2]) {
if(Request[num][0] <= Avaliable[0] && Request[num][1] <= Avaliable[1] && Request[num][2] <= Avaliable[2]) {
for(int i=0;i<3;i++) {
Avaliable[i] -= Request[num][i];
Allocation[num][i] += Request[num][i];
Need[num][i] -= Request[num][i];
}
} else {
System.out.println("当前没有足够资源");
T = false;
}
} else {
System.out.println("请求超出最大需求量");
T = false;
}
if(T==true) {
printSystemStatus();
System.out.println("进入安全检测");
testSafe();
}
}
public void testSafe() {
boolean[] Finish = {false, false, false};//初始化Finish
int count = 0;//完成进程数
int circle=0;//循环圈数
int[] S = new int[3];//安全序列
Work = Avaliable.clone();
boolean flag = true;
while(count < 3) {
if(flag) {
System.out.println("进程 "+" Work "+" Alloction "+" Need "+" Work+Alloction ");
flag = false;
}
for(int i=0;i<3;i++) {
if (Finish[i]==false&&Need[i][0]<=Work[0]&&Need[i][1]<=Work[1]&&Need[i][2]<=Work[2]) {//判断条件
System.out.print("P"+i+" ");
for (int k = 0; k < 3; k++){
System.out.print(Work[k]+" ");
}
System.out.print("| ");
for (int j = 0; j<3;j++){
Work[j] += Allocation[i][j]; //尝试归还
}
Finish[i]=true;//当当前进程能满足时
S[count]=i;//设置当前序列排号
count++;//满足进程数加1
for(int j=0;j<3;j++){
System.out.print(Allocation[i][j]+" ");
}
System.out.print("| ");
for(int j=0;j<3;j++){
System.out.print(Need[i][j]+" ");
}
System.out.print("| ");
for(int j=0;j<3;j++){
System.out.print(Work[j]+" ");
}
System.out.println();
}
}
circle++;
if(count==3) {
System.out.println("安全序列存在");
for (int i = 0; i<3;i++){//输出安全序列
System.out.print("P"+S[i]+" ");
}
System.out.println("故当前可分配！");
break;//跳出循环
}
if(count<circle){//判断完成进程数是否小于循环圈数
count=5;
System.out.println("当前系统处于不安全状态，故不存在安全序列。");
break;//跳出循环
}
}
}
public static void main(String[] args) {
// TODO code application logic here
boolean Choose = true;
String C;
Scanner in = new Scanner(System.in);
Banker T = new Banker();
System.out.println("这是一个三个进程，初始系统可用三类资源为{10,8,7}的银行家算法：");
T.setSystemVariable();
while (Choose == true) {
T.setRequest();
System.out.println("您是否还要进行请求：y/n?");
C = in.nextLine();
if (C.endsWith("n")) {
Choose = false;
}
}
}
}
测试结果
参考资料
- 《操作系统》——北大陈向群
- <a href=https://blog.csdn.net/u014634576/article/details/52600826>银行家算法Java实现</a>
