银行家算法(Java版)附测试数据
package banker;import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;/*** @author lele* @title 银行家算法* @date 2020-10-31*/public class BankerAlgorithm {private Integer processNumber;//进程数量private Integer resourceTypeNumber;//资源类型数量private List<Process> processes;//所有进程集合private List<Resource> resources;//所有资源集合/*** @param processNumber 进程数量* @param resourceTypeNumber 资源类型数量* @param initResourceAvailable 资源初始值* @param initProcessMax 进程对各类资源的最大需求量* @param initProcessAllocation 当前时刻进程对各类资源的占有量*/public BankerAlgorithm(Integer processNumber, Integer resourceTypeNumber, List<Integer> initResourceAvailable,List<List<Integer>> initProcessMax, List<List<Integer>> initProcessAllocation) {this.processNumber = processNumber;this.resourceTypeNumber = resourceTypeNumber;Process.resourceTypeNumber = this.resourceTypeNumber;resources = new ArrayList<>(resourceTypeNumber);//创建资源集合processes = new ArrayList<>(processNumber);//创建进程集合//初始化各类资源for (int i = 0; i < resourceTypeNumber; i++) {resources.add(new Resource(initResourceAvailable.get(i)));}//初始化各个进程信息for (int i = 0; i < processNumber; i++) {processes.add(new Process(initProcessMax.get(i), initProcessAllocation.get(i)));}}/*** 第i号进程对各类资源提出的资源请求** @param i 进程编号* @param requestParam 对各类资源请求的数目* @return 返回是否可以请求成功*/public boolean request(Integer i, List<Integer> requestParam) {Process process = processes.get(i);boolean flag = true;//判断当前资源请求数量是否大于该进程宣布的资源请求数量for (int j = 0; j < resourceTypeNumber; j++) {if (requestParam.get(j) > process.need.get(j)) {flag = false;break;}}if (flag) {//判断各类资源是否能够满足请求的资源数目for (int j = 0; j < resourceTypeNumber; j++) {if (requestParam.get(j) > resources.get(j).available) {flag = false;break;}}if (flag) {//试图将资源分配给该进程,修改相关数据值for (int j = 0; j < resourceTypeNumber; j++) {resources.get(j).available -= requestParam.get(j);process.allocation.set(j, process.allocation.get(j) + requestParam.get(j));process.need.set(j, process.need.get(j) - requestParam.get(j));}//安全性算法检验if (isSafety()) {//若安全,则正式分配System.out.println("安全,可正式分配");return true;} else {//若不安全,则回滚数据for (int j = 0; j < resourceTypeNumber; j++) {resources.get(j).available += requestParam.get(j);process.allocation.set(j, process.allocation.get(j) - requestParam.get(j));process.need.set(j, process.need.get(j) + requestParam.get(j));}System.out.println("进入不安全状态,不分配资源!");return false;}} else {System.out.println("尚无足够资源,需等待...");return flag;}} else {System.out.println("错误:需要的资源已经超过了宣布的最大值!");return flag;}}/*** 安全性算法检查** @return 返回安全性结果*/public boolean isSafety() {//初始化当前工作向量workArrayList<Integer> work = new ArrayList<>(resourceTypeNumber);for (Resource resource : resources) {work.add(resource.available);}//初始化finish为falseArrayList<Boolean> finish = new ArrayList<>(processNumber);for (int i = 0; i < processNumber; i++) {finish.add(false);}//用于对所有循环的遍历,若在一次遍历中所有进程都不满足要求,则遍历结束boolean repeat;//遍历每个进程do {repeat = false;for (int i = 0; i < processes.size(); i++) {Process process = processes.get(i);if (finish.get(i) == false) {//判断当前进程是否满足:根据当前各类资源的数量,是否可以完成自己的需求,即needboolean flag = true;for (int j = 0; j < resourceTypeNumber; j++) {if (process.need.get(j) > work.get(j)) {flag = false;break;}}//若满足需求,则该进程则归还给系统自己所占有的全部资源if (flag) {for (int j = 0; j < resourceTypeNumber; j++) {work.set(j, process.allocation.get(j) + work.get(j));finish.set(i, true);}System.out.println("进程编号:" + i);repeat = true;}}}} while (repeat);boolean flag = true;for (Boolean f : finish) {if (f == false) {flag = false;break;}}return flag;}public static void main(String[] args) {Scanner in = new Scanner(System.in);System.out.println("process number");Integer processNumber = in.nextInt();System.out.println("resourceTypeNumber number");Integer resourceTypeNumber = in.nextInt();//输入各类资源数量List<Integer> initResourceAvailable = new ArrayList<>();for (int i = 0; i < resourceTypeNumber; i++) {initResourceAvailable.add(in.nextInt());}List<List<Integer>> initProcessMax = new ArrayList<>();List<Integer> max;//输入各个进程对各类资源的最大需求量for (int i = 0; i < processNumber; i++) {max = new ArrayList<>();for (int j = 0; j < resourceTypeNumber; j++) {max.add(in.nextInt());}initProcessMax.add(max);}List<List<Integer>> initProcessAllocation = new ArrayList<>();//输入各个进程对各类资源当前的占有量List<Integer> allocation;for (int i = 0; i < processNumber; i++) {allocation = new ArrayList<>();for (int j = 0; j < resourceTypeNumber; j++) {allocation.add(in.nextInt());}initProcessAllocation.add(allocation);}//初始化BankerAlgorithm bankerAlgorithm = new BankerAlgorithm(processNumber, resourceTypeNumber, initResourceAvailable, initProcessMax, initProcessAllocation);//模拟书上例题System.out.println("T0时刻:" + bankerAlgorithm.isSafety());ArrayList<Integer> requestParam = new ArrayList<>();requestParam.add(1);requestParam.add(0);requestParam.add(2);System.out.println("P1请求资源:" + bankerAlgorithm.request(1, requestParam));requestParam.clear();requestParam.add(3);requestParam.add(3);requestParam.add(0);System.out.println("P4请求资源:" + bankerAlgorithm.request(4, requestParam));requestParam.clear();requestParam.add(0);requestParam.add(2);requestParam.add(0);System.out.println("P0请求资源:" + bankerAlgorithm.request(0, requestParam));//模拟练习题最后一道/*System.out.println(bankerAlgorithm.isSafety());ArrayList<Integer> requestParam = new ArrayList<>();requestParam.add(1);requestParam.add(2);requestParam.add(2);requestParam.add(2);System.out.println(bankerAlgorithm.request(2,requestParam));*/}
}//进程类
class Process {//每个进程所持有的资源类别数量相等public static Integer resourceTypeNumber;//资源类别数量public List<Integer> max;//对各类资源的最大需求数目public List<Integer> allocation;//进程已经分配到的各类资源的数目public List<Integer> need = new ArrayList<>(resourceTypeNumber);//进程需要的各类资源的数目public Process(List<Integer> max, List<Integer> allocation) {this.max = max;this.allocation = allocation;for (int i = 0; i < resourceTypeNumber; i++) {need.add(max.get(i) - allocation.get(i));}}
}//资源类
class Resource {public Integer available;//资源的空闲数目//初始化资源空闲数public Resource(Integer available) {this.available = available;}
}/*
模拟书上例题数据
process number
5
resourceTypeNumber number
4
1
6
2
2
0
0
4
4
2
7
5
0
3
6
10
10
0
9
8
4
0
6
6
10
0
0
3
2
1
0
0
0
1
3
5
4
0
3
3
2
0
0
1
4
*//*
模拟练习题最后一道process number
5
resourceTypeNumber number
3
3
3
2
7
5
3
3
2
2
9
0
2
2
2
2
4
3
3
0
1
0
2
0
0
3
0
2
2
1
1
0
0
2
*/
发布评论