1.数据结构
- 可利用的资源向量Available：一个含有m个元素的数组，其中每一个元素代表一类可利拥的资源数目，其初始值是系统中所配置的该类全部可用资源数目，其数值随该类资源的分配改变而改变。如果Available[j]=K，则表示系统中现有Rj类资源K个。
- 最大需求矩阵Max：一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。
- 分配矩阵Allocation：一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的数目为K。
- 需求矩阵Need：一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个方能完成其任务。
Need[i,j]=Max[i,j]-Allocation[i,j]
2.银行家算法
在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配资源之前，判断系统是否是安全的；若是，才分配。它是最具有代表性的避免死锁的算法。
设进程cusneed提出请求REQUEST [i]，则银行家算法按如下规则进行判断。
(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，则转（2)；否则，出错。
(2)如果REQUEST [cusneed] [i]<= AVAILABLE[i]，则转（3)；否则，等待。
(3)系统试探分配资源，修改相关数据：
AVAILABLE[i]-=REQUEST[cusneed][i];
ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];
NEED[cusneed][i]-=REQUEST[cusneed][i];
(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。
3.安全性算法
(1)设置两个工作向量Work=AVAILABLE;FINISH
(2)从进程集合中找到一个满足下述条件的进程，
FINISH==false;
NEED<=Work;
如找到，执行（3)；否则，执行（4)
(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。
Work=Work+ALLOCATION;
Finish=true;
GOTO 2
(4)如所有的进程Finish= true，则表示安全；否则系统不安全。
主要代码：
安全性检测：
public void allocation(){
flag_i.clear();
for (int i = 0; i < this.processes_Size ; i++) {
Finish[i] = false;
}
for (int i = 0; i < this.Resources_Size ; i++) {
Work[0][i] = AvailableTmp[0][i];
}
int count = 0;
int flag = 0; //flag_i中的个数
while (count < this.processes_Size){
for (int i = 0; i < this.processes_Size ; i++) {
if(flag_i.contains(i)){
continue;
}else {
int k = 0;
while (k < this.Resources_Size){
if(NeedTmp[i][k] <= Work[count][k] && (this.Finish[count]==false)){
k++;
}else {
k = this.Resources_Size+1;
}
}
if(k == this.Resources_Size){
flag_i.add(i);
flag++;
break; //每次添加一个
}
}
}
//
//每走一遍for循环应该找到一个，才能往下执行
if((count+1) == flag){
for (int i = 0; i < this.Resources_Size; i++) {
Work_All[count][i] = Work[count][i] + AllocationTmp[(int) flag_i.get(count)][i];
}
this.Finish[count] = true;
count++;
//赋值
for (int i = 0; i < this.Resources_Size; i++) {
Work[count][i] = Work_All[count - 1][i];
}
}
else {
count++;
System.out.println("第"+count+"次安全性检测失败！");
break;
}
if(Finish[count-1] == false){
break;
}
}
//跳出循环如果有进程数个值，说明每个进程都能满足，将试分配的值真实分配
if(flag_i.size() == this.processes_Size){
for (int i = 0; i < this.processes_Size; i++) {
for (int j = 0; j < this.Resources_Size ; j++) {
Allocation[i][j] =AllocationTmp[i][j];
Need[i][j] = NeedTmp[i][j];
}
}
for (int i = 0; i < this.Resources_Size; i++) {
Available[0][i] = AvailableTmp[0][i];
}
showResult();
System.out.println("*********************************");
show();
}else {
if(flag_i.size() == 0){
System.out.println("不满足任何进程的需求！");
System.out.println("无安全序列！");
System.out.println("******************************");
show();
}else {
System.out.println("无安全序列！");
System.out.println("*****************************");
show();
}
}
}
银行家分配部分：
private void requset() {
copy();
System.out.println("请输入要请求资源的进程号：");
String name = scanner.next();
int putInto = -1; //判断输入的是几号进程
for (int i = 0; i < this.processes_Size; i++) {
if (name.equals(processes[i])){
putInto = i;
}
}
//如果输入的在进程序列内不存在
if(putInto == -1){
System.out.println("非法输入！");
return;
}
System.out.println();
System.out.println("请输入再次申请的资源大小：");
int[] num = new int[this.Resources_Size]; //输入的request值
for (int i = 0; i < this.Resources_Size; i++) {
num[i] = scanner.nextInt();
}
int k = 0;
for (int i = 0; i < this.Resources_Size; i++) {
if ((num[i] <= Need[putInto][i]) && (num[i] <= Available[0][i])) {
k++;
} else {
if((num[i] > Need[putInto][i])) {
System.out.println("申请大于需要的进程！");
System.out.println("***************************");
show();
return;
}
if(num[i] > Available[0][i]){
System.out.println("资源不足！");
System.out.println("***************************");
show();
return;
}
}
}
//跳出说明满足要求尝试分配资源
if(k == this.Resources_Size){
for (int j = 0; j < this.Resources_Size; j++) {
NeedTmp[putInto][j] = NeedTmp[putInto][j] - num[j];
AllocationTmp[putInto][j] = AllocationTmp[putInto][j] + num[j];
AvailableTmp[0][j] = AvailableTmp[0][j] - num[j];
}
}
allocation();
}
但是遇到的问题是，当满足银行家算法但是不满足安全性算法时，怎么将银行家预分配的再次还给初始分配前的值，最终采用临时的副本数组，每次安全性算法都是对副本操作，当满足时，才将原数组改变，然后将其输出，当然还有当一个就是一个进程的所需要的资源已经全部得到，此时应该将其删除序列表，并且将其拿到的资源全部还给系统，以便于其他进程的申请。
删除进程（已经获取到了全部所需要的资源）：
private void resReturn(){
int count = 0;
int num = 0;
while (count < processes_Size) {
for (int i = 0; i < this.Resources_Size; i++) {
if (Need[count][i] == 0){
num++;
}
}
if(num == Resources_Size){
for (int i = 0; i < this.Resources_Size ; i++) {
Available[0][i] = Allocation[count][i]+Available[0][i];
}
for (int i = 0; i < this.processes_Size; i++) {
for (int j = 0; j < this.Resources_Size; j++) {
if(i < count){
Need[i][j] = Need[i][j];
Allocation[i][j] = Allocation[i][j];
processes[i] = processes[i];
}else {
Need[i][j] = Need[i+1][j];
Allocation[i][j] = Allocation[i+1][j];
processes[i] = processes[i+1];
}
}
}
processes_Size--;
}
num = 0;
count++;
}
}
测试用例：
申请资源结果：
完整代码如下：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.Scanner;
public class Dijkstra {
private int[][] Max; //资源最大需求
private int[][] Allocation; //已经分配的资源
private int[][] Need; //需要的资源
private int[][] Available; //剩余的资源
private int[][] Work; //执行资源
private int[][] Work_All; //目前剩余的资源
private boolean[] Finish; //是否安全
private ArrayList flag_i; //存入满足当前需求的资源序号
private Scanner scanner;
private String[] processes; //进程
private resource[] resources; //资源
private int MAX_Vaue = 20; //最大的资源以及进程数
private int processes_Size; //真实进程个数
private int Resources_Size; //真实资源个数
//副本数据
private int[][] AllocationTmp; //已经分配的资源
private int[][] NeedTmp; //需要的资源
private int[][] AvailableTmp; //剩余的资源
private String[] processesTmp; //进程
class resource{
String resourceName; //资源名
int resourceSize; //资源大小
public resource(String name,int size){
resourceName = name;
resourceSize = size;
}
}
/**
* 初始化
*/
public Dijkstra(){
this.Max = new int[MAX_Vaue][MAX_Vaue];
this.Allocation = new int[MAX_Vaue][MAX_Vaue];
this.Need = new int[MAX_Vaue][MAX_Vaue];
this.Available = new int[1][MAX_Vaue];
this.Work = new int[MAX_Vaue][MAX_Vaue];
this.Work_All = new int[MAX_Vaue][MAX_Vaue];
this.Finish = new boolean[MAX_Vaue];
this.processes = new String[MAX_Vaue];
this.resources = new resource[MAX_Vaue];
this.scanner = new Scanner(System.in);
this.flag_i = new ArrayList();
//副本
this.AllocationTmp = new int[MAX_Vaue][MAX_Vaue];
this.NeedTmp = new int[MAX_Vaue][MAX_Vaue];
this.AvailableTmp = new int[MAX_Vaue][MAX_Vaue];
this.processesTmp = new String[MAX_Vaue];
}
public static void main(String[] args) {
Dijkstra dijkstra = new Dijkstra();
dijkstra.control();
}
/**
* 选择功能
*/
private void control() {
System.out.println("欢迎来到本系统");
for (;;) {
System.out.println("=============================");
System.out.println("请选择：");
System.out.println("1.初始化系统");
System.out.println("2.再次请求分配");
System.out.println("3.添加资源");
System.out.println("4.添加进程");
System.out.println("0.退出程序");
System.out.println("============================");
int sc = scanner.nextInt();
switch (sc) {
case 1:
start();
break;
case 2:
requset();
break;
case 3:
addResource();
break;
case 4:
addProce();
break;
case 0:
return;
default:
System.out.println("无效输入！");
break;
}
}
}
/**
* 添加进程
*/
private void addProce() {
System.out.println("请输入进程名：");
String name = scanner.next();
this.processesTmp[processes_Size++] = name;
System.out.println("请输入进程已经获取的各资源大小：");
int a = 0;
while (a < Resources_Size){
int num = scanner.nextInt();
AllocationTmp[processes_Size-1][a] = num;
a++;
}
System.out.println("请输入该进程还需要的各资源大小：");
int b = 0;
while (b < Resources_Size){
int num = scanner.nextInt();
NeedTmp[processes_Size-1][b] = num;
b++;
}
for (int i = 0; i < processes_Size ; i++) {
for (int j = 0; j < Resources_Size; j++) {
if(AllocationTmp[processes_Size-1][j] > Available[0][j] ){ //如果添加的进程的某项已经分的资源大于剩余的资源，直接不可以分配
System.out.println("无效的进程输入！");
processes_Size--;
return;
}
else {
//否则将该进程写入
for (int k = 0; k < this.processes_Size; k++) {
for (int p = 0; p < this.Resources_Size ; p++) {
Allocation[k][p] =AllocationTmp[k][p];
Need[k][p] = NeedTmp[k][p];
}
}
for (int k = 0; k < this.Resources_Size; k++) {
Available[0][k] = AvailableTmp[0][k];
}
for (int k = 0; k < this.processes_Size ; k++) {
processes[k] = processesTmp[k];
}
}
}
}
calculate();
}
/**
* 添加资源
*/
private void addResource() {
System.out.println("请输入要添加的个数：");
int number = scanner.nextInt();
while (number > 0) {
System.out.println("请输入资源名：");
String resouname = scanner.next();
System.out.println("请输入资源大小：");
int size = scanner.nextInt();
this.resources[this.Resources_Size++] = new resource(resouname, size);
number--;
}
calculate();
}
/**
* 初始化
*/
private void start() {
System.out.println("请输入进程个数：");
int proceNum = scanner.nextInt();
System.out.println("请输入进程名：");
while (processes_Size < proceNum){
String proceName = scanner.next();
this.processes[processes_Size++] = proceName;
}
System.out.println("请输入资源个数：");
int resouNum = scanner.nextInt();
System.out.println("请输入资源名以及资源的总大小：");
while (Resources_Size < resouNum){
String resouName = scanner.next();
int size = scanner.nextInt();
this.resources[Resources_Size++] = new resource(resouName,size);
}
System.out.println("请输入目前的分配情况：");
for (int i = 0; i < this.processes_Size ; i++) {
for (int j = 0; j < this.Resources_Size ; j++) {
int sc = scanner.nextInt();
Allocation[i][j] = sc;
}
}
System.out.println("请输入目前的需要情况：");
for (int i = 0; i < this.processes_Size ; i++) {
for (int j = 0; j < this.Resources_Size ; j++) {
int sc = scanner.nextInt();
Need[i][j] = sc;
}
}
calculate();
}
/**
* 计算当前的资源分配表
*/
private void calculate(){
for (int i = 0; i < this.processes_Size ; i++) {
for (int j = 0; j < this.Resources_Size ; j++) {
Max[i][j] = Allocation[i][j] + Need[i][j];
}
}
//求每个进程分出去的总和
int[] resour_sun = new int[this.Resources_Size]; //每个进程分出去的总和数组
int tmp = 0;
while (tmp < this.Resources_Size) {
for (int i = 0; i < this.processes_Size; i++) {
resour_sun[tmp] += Allocation[i][tmp];
}
tmp++;
}
//求出Avaiable
for (int i = 0; i < this.Resources_Size; i++) {
Available[0][i] = resources[i].resourceSize - resour_sun[i];
}
copy();
allocation();
}
/**
* 给副本赋值
*/
private void copy(){
//给副本赋值
for (int i = 0; i < this.processes_Size; i++) {
for (int j = 0; j < this.Resources_Size ; j++) {
AllocationTmp[i][j] =Allocation[i][j];
NeedTmp[i][j] = Need[i][j];
}
}
for (int i = 0; i < this.Resources_Size; i++) {
AvailableTmp[0][i] = Available[0][i];
}
for (int i = 0; i < this.processes_Size ; i++) {
processesTmp[i] = processes[i];
}
}
/**
* 展示初始化结果
*/
private void show() {
resReturn();
System.out.println("当前资源情况：");
System.out.println("进程名"+" Max "+" Allocation "+" Need "+" Available ");
int tmp = 0;
while (tmp < 4) {
System.out.print(" ");
for (int i = 0; i < this.Resources_Size; i++) {
System.out.print(resources[i].resourceName + " ");
}
tmp++;
}
System.out.println();
for (int i = 0; i < this.processes_Size; i++) {
System.out.print(processes[i]+" ");
for (int j = 0; j < this.Resources_Size; j++) {
System.out.print(Max[i][j]+" ");
}
System.out.print(" ");
for (int j = 0; j < this.Resources_Size; j++) {
System.out.print(Allocation[i][j]+" ");
}
System.out.print(" ");
for (int j = 0; j < this.Resources_Size; j++){
System.out.print(Need[i][j]+" ");
}
System.out.print(" ");
if(i == 0) {
for (int j = 0; j < this.Resources_Size; j++) {
System.out.print(Available[0][j] + " ");
}
}
System.out.println();
}
System.out.println();
}
/**
* 判断是否可以分配（安全性的检测）
*/
public void allocation(){
flag_i.clear();
for (int i = 0; i < this.processes_Size ; i++) {
Finish[i] = false;
}
for (int i = 0; i < this.Resources_Size ; i++) {
Work[0][i] = AvailableTmp[0][i];
}
int count = 0;
int flag = 0; //flag_i中的个数
while (count < this.processes_Size){
for (int i = 0; i < this.processes_Size ; i++) {
if(flag_i.contains(i)){
continue;
}else {
int k = 0;
while (k < this.Resources_Size){
if(NeedTmp[i][k] <= Work[count][k] && (this.Finish[count]==false)){
k++;
}else {
k = this.Resources_Size+1;
}
}
if(k == this.Resources_Size){
flag_i.add(i);
flag++;
break; //每次添加一个
}
}
}
//
//每走一遍for循环应该找到一个，才能往下执行
if((count+1) == flag){
for (int i = 0; i < this.Resources_Size; i++) {
Work_All[count][i] = Work[count][i] + AllocationTmp[(int) flag_i.get(count)][i];
}
this.Finish[count] = true;
count++;
//赋值
for (int i = 0; i < this.Resources_Size; i++) {
Work[count][i] = Work_All[count - 1][i];
}
}
else {
count++;
System.out.println("第"+count+"次安全性检测失败！");
break;
}
if(Finish[count-1] == false){
break;
}
}
//跳出循环如果有进程数个值，说明每个进程都能满足，将试分配的值真实分配
if(flag_i.size() == this.processes_Size){
for (int i = 0; i < this.processes_Size; i++) {
for (int j = 0; j < this.Resources_Size ; j++) {
Allocation[i][j] =AllocationTmp[i][j];
Need[i][j] = NeedTmp[i][j];
}
}
for (int i = 0; i < this.Resources_Size; i++) {
Available[0][i] = AvailableTmp[0][i];
}
show();
System.out.println("*********************************");
showResult();
}else {
if(flag_i.size() == 0){
System.out.println("不满足任何进程的需求！");
System.out.println("无安全序列！");
System.out.println("******************************");
show();
}else {
System.out.println("无安全序列！");
System.out.println("*****************************");
show();
}
}
}
/**
* 展示分配后的结果
*/
private void showResult() {
System.out.println("当前时刻的安全性：");
System.out.println("进程名"+" work "+" Allocation "+" Need "+" Work+All "+" Finish ");
int tmp = 0;
while (tmp < 4) {
System.out.print(" ");
for (int i = 0; i < this.Resources_Size; i++) {
System.out.print(resources[i].resourceName + " ");
}
tmp++;
}
System.out.println();
for (int i = 0; i < this.processes_Size; i++) {
System.out.print(processes[(int)flag_i.get(i)]+" ");
for (int j = 0; j < this.Resources_Size; j++) {
System.out.print(Work[i][j]+" ");
}
System.out.print(" ");
for (int j = 0; j < this.Resources_Size; j++) {
System.out.print(Allocation[(int)flag_i.get(i)][j]+" ");
}
System.out.print(" ");
for (int j = 0; j < this.Resources_Size; j++){
System.out.print(Need[(int)flag_i.get(i)][j]+" ");
}
System.out.print(" ");
for (int j = 0; j < this.Resources_Size; j++){
System.out.print(Work_All[i][j]+" ");
}
System.out.print(" ");
System.out.print(" "+Finish[i]+" ");
System.out.println();
}
//迭代遍历安全序列
System.out.println();
Iterator<Integer> iterator = flag_i.iterator();
System.out.println("存在安全序列为：");
while (iterator.hasNext()) {
int num = iterator.next();
if(processes[num] !=null) {
System.out.print(processes[num] + " ");
}
}
System.out.println();
}
/**
* 申请资源
*/
private void requset() {
copy();
System.out.println("请输入要请求资源的进程号：");
String name = scanner.next();
int putInto = -1; //判断输入的是几号进程
for (int i = 0; i < this.processes_Size; i++) {
if (name.equals(processes[i])){
putInto = i;
}
}
//如果输入的在进程序列内不存在
if(putInto == -1){
System.out.println("非法输入！");
return;
}
System.out.println();
System.out.println("请输入再次申请的资源大小：");
int[] num = new int[this.Resources_Size]; //输入的request值
for (int i = 0; i < this.Resources_Size; i++) {
num[i] = scanner.nextInt();
}
int k = 0;
for (int i = 0; i < this.Resources_Size; i++) {
if ((num[i] <= Need[putInto][i]) && (num[i] <= Available[0][i])) {
k++;
} else {
if((num[i] > Need[putInto][i])) {
System.out.println("申请大于需要的进程！");
System.out.println("***************************");
show();
return;
}
if(num[i] > Available[0][i]){
System.out.println("资源不足！");
System.out.println("***************************");
show();
return;
}
}
}
//跳出说明满足要求尝试分配资源
if(k == this.Resources_Size){
for (int j = 0; j < this.Resources_Size; j++) {
NeedTmp[putInto][j] = NeedTmp[putInto][j] - num[j];
AllocationTmp[putInto][j] = AllocationTmp[putInto][j] + num[j];
AvailableTmp[0][j] = AvailableTmp[0][j] - num[j];
}
}
allocation();
}
/**
* 删除进程(如果某个资源申请后的need 为0)
*/
private void resReturn(){
int count = 0;
int num = 0;
while (count < processes_Size) {
for (int i = 0; i < this.Resources_Size; i++) {
if (Need[count][i] == 0){
num++;
}
}
if(num == Resources_Size){
for (int i = 0; i < this.Resources_Size ; i++) {
Available[0][i] = Allocation[count][i]+Available[0][i];
}
for (int i = 0; i < this.processes_Size; i++) {
for (int j = 0; j < this.Resources_Size; j++) {
if(i < count){
Need[i][j] = Need[i][j];
Allocation[i][j] = Allocation[i][j];
processes[i] = processes[i];
}else {
Need[i][j] = Need[i+1][j];
Allocation[i][j] = Allocation[i+1][j];
processes[i] = processes[i+1];
}
}
}
processes_Size--;
}
num = 0;
count++;
}
}
}
