死锁避免程序设计-银行家算法
...大约 16 分钟
死锁避免程序设计-银行家算法
算法介绍
试利用银行家算法对死锁避免算法进行模拟，确保系统在冬天申请资源的同时，永远不会陷入不安全状态。
具体要求如下：
（1）程序中进程数量、资源种类数在程序运行时由用户输入；
（2）程序中的资源状态表结构根据输入的进程数量、资源种类数由程序动态生成；
（3）资源状态表中的数量既可以通过随机函数自动产生，也可以由用户手工输入；
（4）程序首先判断系统是否安全，然后在系统安全的前提下，由用户手动完成资源申请，其方法是：先输入或选择进程，然后输入该进程的资源申请要求；
（5）针对用户输入的资源申请，系统应视情况不同给出如下四种执行结果：
1）显示“资源申请不合理”；
2）显示“资源申请超过最大可用资源数，资源不够分配”；
3）显示“找不到安全序列，进程资源申请不予满足”；
4）先显示所找到的安全序列，进而告知用户资源已被分配，并同步修改资源状态表中相关数据。
算法设计说明
银行家算法设计原理分析
针对资源申请进行两个判断：
// 请求资源与需求量、提供量进行校验
request<=Need
request<=Available
分析：
判断当前某进程向系统请求的各类资源的资源数是否小于或等于该进程的尚需要资源数
判断当前某进程向系统请求的各类资源的资源数是否小于或等于当前系统可提供的资源数
如果满足a中条件，则对该进程进行“假装分配资源”，完成三个变量值的修改
当前系统可提供的各类资源量减少：Available = Available – request
当前进程的各类资源的剩余需求量减少：Need = Need – request
当前进程对各类资源的占有量增加：Allocation = Allocation + request
完成“假装分配”操作，进入安全性检测算法，检测对应的安全序列
- 先定义两个工作向量Work,finish,并为其赋初值
Work = Available ; finish = false ;
Work表示当前系统剩余的各类资源的资源数量，其相当于Available
finish用以表示当前系统是否有足够的资源分配给该进程，如果有则为true，反之为false
进行判断：Need <= Work ?
判断当前进程的尚需要资源数是否小于或等于当前系统可提供的资源数目
如果满足条件则执行两个操作：
当前进程释放资源：Work = Work + Allocation
状态标志置为true：finish = true
以此类推，按照一定的次序依次查找分析（执行b）
当所有的进程都遍历完毕，则遍历所有进程对应的状态标识finish，若所有的finish标志都为true，则说明该序列是安全序列，反之则不是。（若新状态不安全，则所对应的进程必须恢复之前的资源分配状态并等待下一个进程的request）
如若安全性检测成功则可输出其对应的安全序列并真正将申请的资源数分配给该进程，反之，则回退到资源分配前的状态（修改三个变量值），继续检验下一个进程的申请结果。
当前系统可提供的各类资源量复原：Available = Available + request
当前进程的各类资源的剩余需求量复原：Need = Need + request
当前进程对各类资源的占有量复原：Allocation = Allocation - request
代码设计思路
ResourceState.java:资源状态：资源状态表相关属性定义
BankerAlgorithmDemo.java:银行家算法实现(银行家算法、安全性检测)，处理资源表状态
BankerAlgorithmDemoTest.java：测试主类，用于控制台交互
ResourceState.java
/**
* 1.资源状态：资源状态表相关属性定义
*/
class ResourceState {
// 进程数
private int processNum;
// 资源类型数
private int resourceNum;
// i类进程对j类资源的最大需求量
private int max[][];
//i类进程对j类资源的占有量
private int allocation[][];
//当前系统资源的可分配量（剩余量）
private int available[];
//i类进程对j类资源的尚需求量（剩余需求量 =max[][]-allocation[][]）
private int need[][];
// 变量初始化构造方法实现
ResourceState(int processNum,int resourceNum,int max[][], int allocation[][], int available[], int need[][]) {
this.processNum = processNum;
this.resourceNum = resourceNum;
// 需要初始化的有四个部分：max、allocation、available、need
this.max = max;
this.allocation = allocation;
this.available = available;
this.need = need;
}
// 构造方法
ResourceState(ResourceState rs) {
this.max = rs.max;
this.allocation = rs.allocation;
this.available = rs.available;
this.need = rs.need;
}
// 状态表打印数据输出
public void showData() {
//打印当前时刻各个进程对各类资源的数据
System.out.println("Process \t\t\t\tmax \t\t\tAlloc \t\t\tAvail \t\t\tneed");
for (int i = 0; i < this.processNum ; i++) {
System.out.print("P" + i + ":\t\t\t\t\t\t");
for(int j=0;j<this.resourceNum;j++){
System.out.print(this.max[i][j] + " ");
}
System.out.print("\t\t\t");
for(int j=0;j<this.resourceNum;j++){
System.out.print(this.allocation[i][j] + " ");
}
System.out.print("\t\t\t");
for(int j=0;j<this.resourceNum;j++){
System.out.print(this.available[j] + " ");
}
System.out.print("\t\t\t");
for(int j=0;j<this.resourceNum;j++){
System.out.print(this.need[i][j] + " ");
}
System.out.println(); //换行
}
}
public int[][] getMax() {
return max;
}
public void setMax(int[][] max) {
this.max = max;
}
public int[][] getAllocation() {
return allocation;
}
public void setAllocation(int[][] allocation) {
this.allocation = allocation;
}
public int[] getAvailable() {
return available;
}
public void setAvailable(int[] available) {
this.available = available;
}
public int[][] getNeed() {
return need;
}
public void setNeed(int[][] need) {
this.need = need;
}
public int getProcessNum() {
return processNum;
}
public void setProcessNum(int processNum) {
this.processNum = processNum;
}
public int getResourceNum() {
return resourceNum;
}
public void setResourceNum(int resourceNum) {
this.resourceNum = resourceNum;
}
}
BankerAlgorithmDemo.java
/**
* 银行家算法实现
*/
public class BankerAlgorithmDemo {
/**
* 2.银行家算法实现
* @param rs 资源状态
* @param p 对应进程序号
* @param request request数组对应资源请求量
*/
public void callBankerAlgorithm(ResourceState rs, int p, int request[]) {
// 定义布尔变量，查看request是否满足银行家算法要求
boolean validFlag = false;// 初始化状态为false
//2.1 先进行判断 ：request<need && request<available
for (int j = 0; j < rs.getResourceNum(); j++) {
// 比较每个进程对每类资源的请求量是否小于需求量
if (request[j] > rs.getNeed()[p][j]) {
System.out.println("资源申请不合理");
return;
}
// 比较每个进程对每类资源的请求量是否小于当前系统可提供的资源数目
if (request[j] > rs.getAvailable()[j]) {
System.out.println("资源申请超过最大可用资源数，资源不够分配");
return;
} else {
validFlag = true; //满足条件则将状态置为true
}
}
// 循环比较完毕，满足条件则执行“假装分配操作”
if (validFlag) {
this.proMalloc(rs,p, request);
System.out.println("输出“模拟分配”后的资源数据如下：");
rs.showData();
System.out.println("提示：银行家算法调用完毕，现进入安全性检测");
// 进入下一步的安全性检测
if (this.safety(rs)) {
System.out.println("\n安全性检测完毕，允许分配，且安全序列表示如上述所示");
} else {
System.out.println("\n安全性检测失败，允许资源分配，但可能会引发死锁状态！");
this.rollback(rs,p, request); //调用回溯算法实现状态复原
}
}
}
// 试探性分配数据
private void proMalloc(ResourceState rs,int p, int request[]) {
for (int j = 0; j < rs.getResourceNum(); j++) {
// 系统可用资源量减少
rs.getAvailable()[j] -= request[j];
// 当前进程对某类资源的剩余资源量减少
rs.getNeed()[p][j] -= request[j];
// 当前进程对某类资源的占有量增加
rs.getAllocation()[p][j] += request[j];
}
}
// 回溯算法实现
private void rollback(ResourceState rs,int p, int request[]) {
for (int j = 0; j < rs.getResourceNum(); j++) {
// 系统可用资源量复原
rs.getAvailable()[j] -= request[j];
// 当前进程对某类资源的剩余资源量复原
rs.getNeed()[p][j] -= request[j];
// 当前进程对某类资源的占有量复原
rs.getAllocation()[p][j] += request[j];
}
}
/**
* 3.安全性算法实现
*
* @return
*/
public boolean safety(ResourceState rs) { // work:当前系统资源的工作量，用于safety算法（与available[]相关联），将当前系统各类资源的剩余量传给work
int work[] = rs.getAvailable();
// 当前该类进程的安全性状态
boolean finish[] = new boolean[rs.getProcessNum()];
for (int k = 0; k < rs.getProcessNum(); k++) {
// 每个状态初始化安全状态都为false
finish[k] = false;
}
for (int i = 0; i < rs.getProcessNum(); i++) {
// 安全性状态为true说明已经遍历过，不需要再重复遍历
if (!finish[i]) {
// 若当前每个进程对各类资源的需求量都小于当前系统各类资源的剩余量
boolean validFlag = true;
for(int j=0;j<rs.getResourceNum();j++){
// 若出现不满足条件则设置validFlag为false并跳出循环
if(rs.getNeed()[i][j] > work[j]){
validFlag = false;
break;
}
}
// 校验validFlag状态，满足条件则释放资源，修改该进程的安全性状态
if(validFlag){
// 为了查看过程修改这个available,但实际是不能修改这个内容，只能借助Work工作向量实现 work[2] += rs.getAllocation()[i][2];
//this.available[0]+=this.allocation[i][0];
for(int j=0;j<rs.getResourceNum();j++){
work[j] += rs.getAllocation()[i][j];
}
finish[i] = true;
// 打印当前的进程序号，记录安全序列
System.out.print("P" + i + "--->");
// 重新回到起点进行检测（从p0-pi依次进行分析）
i = -1;
//System.out.println(this.available[0]+" "+this.available[1]+" "+this.available[2]);
}
}
}
// 判断每个状态是否为true，即判断每个进程是否处于安全性状态
for (int a = 0; a < rs.getProcessNum(); a++) {
// 若出现false值则说明不满足安全性校验
if (!finish[a]) {
return false;
}
}
return true;
}
}
BankerAlgorithmDemoTest.java
public class BankerAlgorithmDemoTest {
/**
* 自定义方法初始化资源状态表参数
*/
private static ResourceState initResourceStateAuto(int processNum, int resourceNum) {
// 下述为根据用户输入选择，测试银行家算法
int max[][] = new int[processNum][resourceNum];
int allocation[][] = new int[processNum][resourceNum];
int available[] = new int[processNum];
// need初始化（剩余需求量 =max[][]-allocation[][]）
int need[][] = new int[processNum][resourceNum];
for (int i = 0; i < processNum; i++) {
for (int j = 0; j < resourceNum; j++) {
need[i][j] = max[i][j] - allocation[i][j];
}
}
// 初始化状态表
ResourceState rs = new ResourceState(processNum, resourceNum, max, allocation, available, need);
// 打印参数
rs.showData();
return rs;
}
/**
* 自定义方法初始化资源状态表参数(系统自动生成参数)：
* 考虑参数随机生成具备不确定性，此处考虑调整为自定义参数设定
*/
private static ResourceState initResourceStateParamAuto(ResourceState rs) {
// 待完善（随机数据生成）
Scanner sc = new Scanner(System.in);
int max[][] = new int[rs.getProcessNum()][rs.getResourceNum()];
rs.setMax(max);
int allocation[][] = new int[rs.getProcessNum()][rs.getResourceNum()];
rs.setAllocation(allocation);
int available[] = new int[rs.getResourceNum()];
rs.setAvailable(available);
// 更新need
int need[][] = new int[rs.getProcessNum()][rs.getResourceNum()];
for (int i = 0; i < rs.getProcessNum(); i++) {
for (int j = 0; j < rs.getResourceNum(); j++) {
need[i][j] = rs.getMax()[i][j] - rs.getAllocation()[i][j];
}
}
rs.setNeed(need);
// 显示T0状态下各类资源的相关数据
System.out.println("显示T0状态下各类资源的相关数据如下");
rs.showData();
return rs;
}
/**
* 自定义方法初始化资源状态表参数(人工输入)
*/
private static ResourceState initResourceStateParamManual(ResourceState rs) {
Scanner sc = new Scanner(System.in);
System.out.println("请按照进程顺序输入Max（各进程对每类资源的最大需求量）：");
for (int i = 0; i < rs.getProcessNum(); i++) {
System.out.print("请输入第P" + i + "个进程对应的max值：");
// 定义字符串数组用以接收数据
String[] st = sc.next().split("-");
for (int j=0;j<rs.getResourceNum();j++) { // 强制类型转化
rs.getMax()[i][j] = Integer.valueOf(st[j]);
}
}
System.out.println("请按照进程顺序输入allocation（各进程对每类资源当前的占有量）：");
for (int i = 0; i < rs.getProcessNum(); i++) {
System.out.print("请输入第P" + i + "个进程对应的allocation值");
String[] st = sc.next().split("-"); //定义字符数组用以接收数据
for (int j=0;j<rs.getResourceNum();j++) {
rs.getAllocation()[i][j] = Integer.valueOf(st[j]);
}
}
System.out.println("请依次输入available（当前系统的各类资源的剩余量）：");
String[] st = sc.next().split("-"); // 定义字符数组用以接收数据
for (int j=0;j<rs.getResourceNum();j++) {
rs.getAvailable()[j]=Integer.valueOf(st[j]);
}
// 更新need
int need[][] = new int[rs.getProcessNum()][rs.getResourceNum()];
for (int i = 0; i < rs.getProcessNum(); i++) {
for (int j = 0; j < rs.getResourceNum(); j++) {
need[i][j] = rs.getMax()[i][j] - rs.getAllocation()[i][j];
}
}
rs.setNeed(need);
// 显示T0状态下各类资源的相关数据
System.out.println("显示T0状态下各类资源的相关数据如下");
rs.showData();
return rs;
}
public static void main(String[] args) {
// 下述为根据用户输入选择，测试银行家算法
int request[] = null;
Scanner sc = new Scanner(System.in);
/**
* 1.请求用户输入自定义进程数量、资源种类(用于初始化各类数组)
*/
System.out.print("请输入自定义进程数量:");
int processNum = sc.nextInt();
System.out.print("\n请输入自定义资源种类:");
int resourceNum = sc.nextInt();
/**
* 2.根据指定参数动态初始化资源状态表，打印状态表信息
*/
ResourceState rs = initResourceStateAuto(processNum, resourceNum);
/**
* 3.根据用户选择处理资源状态表数据
* 资源状态表数量可随机生成或者通过用户手工输入
*/
System.out.println("请选择操作（进行资源状态表数量初始化）：1.随机函数生成；2.手动输入");
int chooseNum = sc.nextInt();
switch (chooseNum) {
case 1: {
// rs = initResourceStateParamAuto(rs);
System.out.println("随机初始化数据");
break;
}
case 2: {
// 手动输入初始化参数
rs = initResourceStateParamManual(rs);
break;
}
default: {
System.err.println("无效操作！");
}
}
// 循环操作选择
int choose = 0;
/**
* 4.进程操作
*/
System.out.println("请输入所要操作的进程序号（起始值从0开始）:");
int p = sc.nextInt();
System.out.println("请依次输入该进程申请的各类资源数据:");
// 定义字符数组用以接收数据
String[] st1 = sc.next().split("-");
//将字符数组强制转化为int型数组(定义int型数组，用以接收char型数组)
int req[] = new int[rs.getResourceNum()];
int r = 0;
for (String s : st1) {
int m = Integer.parseInt(s);
req[r] = m;
r++;
}
request = req;
// 创建一个银行家测试对象bad
BankerAlgorithmDemo bad = new BankerAlgorithmDemo();
// 调用银行家算法进行测试
bad.callBankerAlgorithm(rs, p, request);
System.out.println("调用银行家算法和安全性算法后各资源的数据显示如下（成功/终断）");
rs.showData();
System.out.println("是否还要进行下一次资源分配？ 1.继续下一次资源分配 2.退出程序");
choose = sc.nextInt();
while (choose == 1) {
// 重新开辟空间保存原来的对象，用以进行下一步操作
// ResourceState newRs = new ResourceState(rs);
System.out.println("请开始进行下一次资源分配... ...");
System.out.println("请输入所要操作的进程序号（起始值从0开始）:");
int operProcessTag = sc.nextInt();
System.out.println("请依次输入该进程申请的各类资源数据:");
// 定义字符数组用以接收数据
String[] st2 = sc.next().split("-");
for (int i=0;i<rs.getResourceNum();i++) {
request[i] = Integer.parseInt(st2[i]);
}
System.out.println("显示T0状态下各类资源的相关数据如下");
rs.showData();
// 调用银行家算法进行测试
bad.callBankerAlgorithm(rs, operProcessTag, request);
System.out.println("调用银行家算法和安全性算法后各资源的数据显示如下（成功/终断）");
rs.showData();
System.out.println("是否还要进行下一次资源分配？ 1.继续下一次资源分配 2.退出程序");
choose = sc.nextInt();
}
}
}
结果分析
（1）程序中进程数量、资源种类数在程序运行时由用户输入；
程序运行时通过用户输入自定义进程数量和资源种类初始化参数
int processNum = sc.nextInt();
int resourceNum = sc.nextInt();
（2）程序中的资源状态表结构根据输入的进程数量、资源种类数由程序动态生成；
// 调用自定义方法根据用户输入的参数初始化状态表信息
ResourceState rs = initResourceStateAuto(processNum, resourceNum);
（3）资源状态表中的数量既可以通过随机函数自动产生，也可以由用户手工输入；
switch (chooseNum) {
case 1: {
// 随机生成函数
rs = initResourceStateParamAuto(rs);
break;
}
case 2: {
// 手动输入初始化参数
rs = initResourceStateParamManual(rs);
break;
}
default: {
System.err.println("无效操作！");
}
}
// 此处为了校验算法的正确性下述内容通过手动指定参数进行处理，以验证不同的情况（参数配置后续结合不同的情况进行处理分析）
（4）程序首先判断系统是否安全，然后在系统安全的前提下，由用户手动完成资源申请，其方法是：先输入或选择进程，然后输入该进程的资源申请要求；
结合银行家算法实现思路说明，用户手动输入配置信息模拟资源申请操作（此处设定输入进程号进行控制指定进程、及根据资源种类配置其对应的申请数），随后调用银行家算法校验request与need、available的关系
校验通过则进行假装分配并执行安全性检测，如果安全性检测通过则允许分配，若不通过则进行状态回溯
// 银行家算法实现
public void callBankerAlgorithm(ResourceState rs, int p, int request[]) {
// 定义布尔变量，查看request是否满足银行家算法要求
boolean validFlag = false;// 初始化状态为false
//2.1 先进行判断 ：request<need && request<available
for (int j = 0; j < 3; j++) {
// 比较每个进程对每类资源的请求量是否小于需求量
if (request[j] > rs.getNeed()[p][j]) {
System.out.println("request请求资源量不满足“request<need”的要求！");
return;
}
// 比较每个进程对每类资源的请求量是否小于当前系统可提供的资源数目
if (request[j] > rs.getAvailable()[j]) {
System.out.println("request请求资源量不满足“request<available”的要求！");
return;
} else {
validFlag = true; //满足条件则将状态置为true
}
}
// 循环比较完毕，满足条件则执行“假装分配操作”
if (validFlag) {
this.proMalloc(rs,p, request);
System.out.println("输出“假装分配”后的资源数据如下：");
rs.showData();
System.out.println("提示：银行家算法调用完毕，现进入安全性检测");
// 进入下一步的安全性检测
if (this.safety(rs)) {
System.out.println("\n安全性检测完毕，允许分配，且安全序列表示如上述所示");
} else {
System.out.println("\n安全性检测失败，允许资源分配，但可能会引发死锁状态！");
this.rollback(rs,p, request); //调用回溯算法实现状态复原
}
}
}
（5）针对用户输入的资源申请，系统应视情况不同给出如下四种执行结果：
结合用户输入的资源申请，此处模拟操作检验相应的操作结果，验证银行家算法的执行
输入针对每个进程对应的资源种类的数值配置以分隔符“-”进行切割，展示如下数据
1）显示“资源申请不合理”；
该情况的出现是针对进程对每类资源的请求量大于需求量的时候
2）显示“资源申请超过最大可用资源数，资源不够分配”；
该情况的出现是针对进程对每类资源的请求量是否大于当前系统可提供的资源数目
3）显示“找不到安全序列，进程资源申请不予满足”；
通过了下述校验
request<=Need
request<=Available
进行模拟分配，随后调用安全行检测算法获取关联的安全序列，若找不到符合条件的安全序列则做出相应反馈
4）先显示所找到的安全序列，进而告知用户资源已被分配，并同步修改资源状态表中相关数据
校验通过，并进行安全性检测，进行资源分配，修改状态表数据
Powered by Waline v3.1.3