銀行家演算法 : java實作(基于課本)
屬性
需要在構造方法中傳入的
- 整型Resources , 用于表名可用資源種類數量, 共有幾種資源
- 整型Process, 用于表名行程數量, 共有幾個行程
- 整型陣列Available, 用于表名每類可用資源的數量
- 整形矩陣Max, 用于表名每個行程所需的總的資源量
- 整型矩陣Allocation, 用于表示每個行程目前已經擁有的每類資源資源的資源數量
其他屬性
- 整形矩陣Need, 用于表示每個行程目前需要的每類資源資源的資源數量
- Available2, Allocation2, Need2, 分別時以上三個資料結構的備份, 用于安全性檢測, 不破環原資料結構
- 整型陣列work, 用于表示目前可用的資源數(在檢測安全性時使用)
- 布爾陣列finish, 安全性檢測時每一個行程完成后, 對應的索引改為true
方法
public
- BankerAlgorithm() 構造方法
- Algorithm() 銀行家演算法
- UpdateResources() 更新資料的演算法
private
- setNeed() 構造Need矩陣的方法
- reSetNeed() 重繪需求矩陣的方法
- reCopying() 復制備份的方法
- rebuild() 用于初始化work和finish的方法
- reFinish() 用于重繪work和finish陣列的方法
- able() 用于判斷work中的值夠不夠減的方法
- isSecurity() 用于判斷請求是不是安全的方法
- findThePath() 如果安全,用于排列出一個安全組合的方法
大體執行流程
傳入引數呼叫構造方法后, 使用銀行家演算法Algorithm(), 傳入請求引數(那個行程申請什么資源多少)
Algorithm()呼叫setNeed()建立Need矩陣, 經過兩部初始判斷后呼叫isSecurity()方法判斷請求是否安全,
isSecurity()建立work和finish, 通過判斷后回傳布林值給Algorithm(), 如果安全就呼叫findThePath()找到安全組合, 并輸出
測驗類中可選擇更新資料, 也可選擇不更新資料UpdateResources()
需要注意
所有的屬性貌似在物件創建之初先于構造方法創建,
也就是說如果屬性陣列的大小由其他數值屬性(需要被構造方法賦值)來確定時,
因為在構造方法賦值前,所使用的初始數值為0, 所以就是說屬性陣列大小為零,
所以任何此類陣列屬性都可由動態陣列代替(ArrayList/LinkedList).
代碼
演算法類
import java.util.ArrayList;
public class BankerAlgorithm {
public int Resources; //資源數量
public int Process; //行程數量
public int[] Available; //可用資源向量
public int[][] Max; //最大需求矩陣
public int[][] Allocation; //分配矩陣
public BankerAlgorithm(int Resources, int Process, int[] Available, int[][] Max, int[][] Allocation){
//構造方法
this.Process = Process;
this.Resources = Resources;
this.Allocation = Allocation;
this.Max = Max;
this.Available = Available;
}
/**
* 所有的屬性貌似在物件創建之初先于構造方法創建,
* 也就是說如果屬性陣列的大小由其他數值屬性(需要被構造方法賦值)來確定時,
* 因為在構造方法賦值前,所使用的初始數值為0,所以就是說屬性陣列大小為零
* 所以任何此類陣列屬性都可由動態陣列代替(ArrayList/LinkedList)
* */
private final ArrayList<ArrayList<Integer>> Need = new ArrayList<>();
private void setNeed(){
for(int i=0;i<Process;i++){
Need.add(i,new ArrayList<>());
for(int j=0;j<Resources;j++){
Need.get(i).add(j,(Max[i][j] - Allocation[i][j]));
}
}
}
private void reSetNeed(){
Need.clear();
setNeed();
}
//Available Allocation Need的備份
private final ArrayList<Integer> Available2 = new ArrayList<>();
private final ArrayList<ArrayList<Integer>> Allocation2 = new ArrayList<>();
private final ArrayList<ArrayList<Integer>> Need2 = new ArrayList<>();
private void reCopying(){ //用于復制備份
Available2.clear();
Allocation2.clear();
Need2.clear();
for(int i=0;i<Process;i++){
Allocation2.add(i,new ArrayList<>());
Need2.add(i,new ArrayList<>());
for(int j=0;j<Resources;j++){
Allocation2.get(i).add(j,Allocation[i][j]);
Need2.get(i).add(j,Need.get(i).get(j));
}
}
for(int i=0;i<Resources;i++){
Available2.add(i,Available[i]);
}
}
public void Algorithm(int i, int[] Request){ //行程i向系統提出資源請求
reSetNeed();
boolean f = true; //要求量小于需求量
for(int j=0;j<Resources;j++){
if (Request[j] > Need.get(i).get(j)) {
f = false;
break;
}
}
if(f){
boolean f2 = true; //要求量小于剩余量
for(int j=0;j<Resources;j++){
if (Request[j] > Available[j]) {
f2 = false;
break;
}
}
if(f2){
reCopying();
for(int j=0;j<Resources;j++){
Available2.set(j,Available2.get(j)-Request[j]);
Allocation2.get(i).set(j,(Allocation2.get(i).get(j)+Request[j]));
Need2.get(i).set(j,(Need2.get(i).get(j)-Request[j]));
}
if(isSecurity()){
ArrayList<Integer> path = findThePath();
for(int p:path)
System.out.print("p"+p+" ");
}else {
System.out.println("此請求不安全!");
}
}else
System.out.println("請求不通過: 請求資源數量大于現有資源量!");
}else
System.out.println("請求不通過: 申請資源數量大于自身所需!");
}
//work和finish
private final ArrayList<Integer> work = new ArrayList<>();
private final ArrayList<Boolean> finish = new ArrayList<>();
private void rebuild(){ //用于初始化work和finish
for(int i=0;i<Resources;i++){
work.add(Available2.get(i));
}
for(int i=0;i<Process;i++)
finish.add(false);
}
private void reFinish(){ //用于重繪work和finish陣列
work.clear();
for(int i=0;i<Resources;i++){
work.add(Available2.get(i));
}
finish.clear();
for(int i=0;i<Process;i++)
finish.add(false);
}
private boolean able(int i){ //用于判斷work中的值夠不夠減
boolean f = true;
for(int j=0;j<Resources;j++){
if (work.get(j) < Need2.get(i).get(j)) {
f = false;
break;
}
}
return f;
}
private boolean isSecurity(){ //用于判斷是不是安全
rebuild();
boolean flag = false;
for(int n=0;n<Process;n++) {
if(!flag) {
flag = true;
for (int i = 0; i < Process; i++) {
if (able(i) && !finish.get(i)) {
for (int j = 0; j < Resources; j++) {
work.set(j,work.get(j)+Allocation2.get(i).get(j));
Allocation2.get(i).set(j,0);
}
finish.set(i,true);
}
}
for (int i = 0; i < Process; i++) {
if (!finish.get(i)) {
flag = false;
break;
}
}
}
}
return flag;
}
private ArrayList<Integer> findThePath(){ //用于排列出一個安全組合
reCopying();
rebuild();
reFinish();
ArrayList<Integer> Path = new ArrayList<>();
boolean flag = false;
for(int n=0;n<Process;n++) {
if(!flag) {
flag = true;
for (int i = 0; i < Process; i++) {
if (able(i) && !finish.get(i)) {
for (int j = 0; j < Resources; j++) {
work.set(j,work.get(j)+Allocation2.get(i).get(j));
Allocation2.get(i).set(j,0);
}
finish.set(i,true);
Path.add(i);
}
}
for (int i = 0; i < Process; i++) {
if (!finish.get(i)) {
flag = false;
break;
}
}
}
}
return Path;
}
public void UpdateResources(int n, int[] Request){ //執行操作, 并更新資料
if(isSecurity()) {
for (int i = 0; i < Resources; i++) {
Available[i] = Available[i] - Request[i];
Allocation[n][i] = Allocation[n][i] + Request[i];
Need.get(n).set(i, Need.get(n).get(i) - Request[i]);
}
}
}
}
測驗類(兩個測驗案例)
public class Test {
public static void test1(){
int Resources = 3;
int Process = 5;
int[] Available = new int[]{3,3,2};
int[][] Max = new int[Process][Resources];
int[][] Allocation = new int[Process][Resources];
int[] max = new int[]{
7,5,3,3,2,2,9,0,2,2,2,2,4,3,3
};
int[] allocation = new int[]{
0,1,0,2,0,0,3,0,2,2,1,1,0,0,2
};
for(int i=0;i<Process;i++){
for(int j=0;j<Resources;j++){
Max[i][j] = max[i*Resources+j];
Allocation[i][j] = allocation[i*Resources+j];
}
}
BankerAlgorithm banker = new BankerAlgorithm(Resources,Process,Available,Max,Allocation);
int[] request1 = new int[]{1,0,2};
//P1發出請求Request(1,0,2)，執行銀行家演算法
banker.Algorithm(1,request1);
banker.UpdateResources(1,request1);
System.out.println();
int[] request2 = new int[]{3,3,0};
banker.Algorithm(4,request2);
banker.UpdateResources(1,request1);
}
public static void test2(){
int Resources = 3;
int Process = 5;
int[] Available = new int[]{2,1,0};
int[][] Max = new int[Process][Resources];
int[][] Allocation = new int[Process][Resources];
int[] max = new int[]{
7,5,3,3,2,2,9,0,2,2,2,2,4,3,3
};
int[] allocation = new int[]{
0,3,0,3,0,2,3,0,2,2,1,1,0,0,2
};
for(int i=0;i<Process;i++){
for(int j=0;j<Resources;j++){
Max[i][j] = max[i*Resources+j];
Allocation[i][j] = allocation[i*Resources+j];
}
}
BankerAlgorithm banker = new BankerAlgorithm(Resources,Process,Available,Max,Allocation);
int[] request0 = new int[]{0,2,0};
banker.Algorithm(0,request0);
}
public static void main(String[] args) {
test1();
System.out.println();
test2();
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/278804.html
標籤：其他