這裡參考了:
http://mp.weixin.qq.com/s?__biz= ... 6oZ#wechat_redirect
http://blog.sina.com.cn/s/blog_7a4d0df90100zr6x.html
并針對Java實作需要對内容進行了修改。
銀行家算法(Banker’s Algorithm)是一個避免死鎖(Deadlock)的著名算法,由艾茲格·迪傑斯特拉在1965年為T.H.E系統設計的一種避免死鎖産生的算法。它以銀行借貸系統的配置設定政策為基礎,判斷并保證系統的安全運作。我們可以把作業系統看作是銀行家,作業系統管理的資源相當于銀行家管理的資金,程序向作業系統請求配置設定資源相當于使用者向銀行家貸款。
為保證資金的安全,銀行家規定:
(1) 當一個顧客對資金的最大需求量不超過銀行家現有的資金時就可接納該顧客;
(2) 顧客可以分期貸款,但貸款的總數不能超過最大需求量;
(3) 當銀行家現有的資金不能滿足顧客尚需的貸款數額時,對顧客的貸款可推遲支付,但總能使顧客在有限的時間裡得到貸款;
(4) 當顧客得到所需的全部資金後,一定能在有限的時間裡歸還所有的資金。
銀行家算法資料結構:
包括以下三個過程:
下面逐一簡紹這三個過程:
一、初始化Init() 流程圖:
由使用者輸入資料, 分别對 AVAILABLE , MAX , ALLOCATION , NEED 指派。
二、安全性檢查Safe() 流程圖:
步驟:
1.設定兩個工作向量 Work=AVAILABLE; FINISH
2.從程序集合中找到一個滿足下述條件的程序,FINISH ==false; NEED <= Work;
如找到,執行(3);否則,執行(4)
3.設程序獲得資源,可順利執行,直至完成,進而釋放資源。
Work += ALLOCATION; Finish=true;GOTO 2
4.如所有的程序Finish= true,則表示安全;否則系統不安全。
作業系統安全狀态和不安全狀态:
1.安全序列是指一個程序式列{P1,…,Pn}是安全的,如果對于每一個程序Pi(1≤i≤n),它以後尚 需要的資源量不超過系統目前剩餘資源量與所有程序Pj (j < i )目前占有資源量之和。
2.如果存在一個由系統中所有程序構成的安全序列P1,…,Pn,則系統處于安全狀态。安全狀态 一定是沒有死鎖發生。
3.如果不存在一個安全序列, 不安全狀态不一定導緻死鎖。
4.安全是指系統能找到一個序列使得所有資源得到配置設定。
三、銀行家算法Bank() 流程
1.在避免死鎖的方法中,所施加的限制條件較弱,有可能獲得令人滿意的系統性能。在該方法中把系統的狀态分為安全狀态和不安全狀态,隻要能使系統始終都處于安全狀态,便可以避免發生死鎖。
2.銀行家算法的基本思想是配置設定資源之前, 判斷系統是否是安全的; 若是, 才配置設定。它是最具有代表性的避免死鎖的算法。
3.設程序cusneed 提出請求REQUEST ,則銀行家算法按如下規則進行判斷。
(1) 如果REQUEST[cusneed] <= NEED[cusneed] ,則轉(2) ;否則,出錯。
(2) 如果REQUEST[cusneed] <= AVAILABLE[cusneed] 則轉(3);否則,出錯。
(3) 系統試探配置設定資源,修改相關資料:
AVAILABLE -= REQUEST [cusneed];
ALLOCATION[cusneed] += REQUEST[cusneed];
NEED[cusneed] -= REQUEST[cusneed];
(4) 系統執行安全性檢查,如安全,則配置設定成立;否則試探險性配置設定廢棄,系統恢複原狀。
具體的Java實作代碼如下:
package bankerTest;
import java.util.Scanner;
public class BankerClass {
int[] Available = {10, 8, 7};
int[][] Max = new int[3][3];
int[][] Alloction = 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 BankerClass() {
// Max={{6,3,2},{5,6,1},{2,3,2}};
}
public void setSystemVariable(){//設定各初始系統變量,并判斷是否處于安全狀态。
setMax();
setAlloction();
printSystemVariable();
SecurityAlgorithm();
}
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[j] = in.nextInt();
}
}
}
public void setAlloction() {//設定已配置設定矩陣Alloction
System.out.println("請設定請各程序配置設定矩陣Alloction:");
for (int i = 0; i < 3; i++) {
System.out.println("晴輸入程序P" + i + "的配置設定資源量:");
for (int j = 0; j < 3; j++) {
Alloction[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++) {
Available = Available - Alloction[j];
}
}
for (int i = 0; i < 3; i++) {//設定Need矩陣
for (int j = 0; j < 3; j++) {
Need[j] = Max[j] - Alloction[j];
}
}
}
public void printSystemVariable(){
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[j]+" ");
}
System.out.print("| ");
for(int j=0;j<3;j++){
System.out.print(Alloction[j]+" ");
}
System.out.print("| ");
for(int j=0;j<3;j++){
System.out.print(Need[j]+" ");
}
System.out.print("| ");
if(i==0){
for(int j=0;j<3;j++){
System.out.print(Available[j]+" ");
}
}
System.out.println();
}
}
public void setRequest() {//設定請求資源量Request
System.out.println("請輸入請求資源的程序編号:");
num= in.nextInt();//設定全局變量程序編号num
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]) {//判斷Request是否小于Need
if (Request[num][0] <= Available[0] && Request[num][1] <= Available[1] && Request[num][2] <= Available[2]) {//判斷Request是否小于Alloction
for (int i = 0; i < 3; i++) {
Available -= Request[num];
Alloction[num] += Request[num];
Need[num] -= Request[num];
}
} else {
System.out.println("目前沒有足夠的資源可配置設定,程序P" + num + "需等待。");
T=false;
}
} else {
System.out.println("程序P" + num + "請求已經超出最大需求量Need.");
T=false;
}
if(T==true){
printSystemVariable();
System.out.println("現在進入安全算法:");
SecurityAlgorithm();
}
}
public void SecurityAlgorithm() {//安全算法
boolean[] Finish = {false, false, false};//初始化Finish
int count = 0;//完成程序數
int circle=0;//循環圈數
int[] S=new int[3];//安全序列
for (int i = 0; i < 3; i++) {//設定工作向量
Work = Available;
}
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==false&&Need[0]<=Work[0]&&Need[1]<=Work[1]&&Need[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]+=Alloction[j];
}
Finish=true;//當目前程序能滿足時
S[count]=i;//設定目前序列排号
count++;//滿足程序數加1
for(int j=0;j<3;j++){
System.out.print(Alloction[j]+" ");
}
System.out.print("| ");
for(int j=0;j<3;j++){
System.out.print(Need[j]+" ");
}
System.out.print("| ");
for(int j=0;j<3;j++){
System.out.print(Work[j]+" ");
}
System.out.println();
}
}
circle++;//循環圈數加1
if(count==3){//判斷是否滿足所有程序需要
System.out.print("此時存在一個安全序列:");
for (int i = 0; i<3;i++){//輸出安全序列
System.out.print("P"+S+" ");
}
System.out.println("故目前可配置設定!");
break;//跳出循環
}
if(count<circle){//判斷完成程序數是否小于循環圈數
count=5;
System.out.println("目前系統處于不安全狀态,故不存在安全序列。");
break;//跳出循環
}
}
}
}
package bankerTest;
import java.util.Scanner;
public class TestBankerClass {
public static void main(String[] args) {
// TODO code application logic here
boolean Choose = true;
String C;
Scanner in = new Scanner(System.in);
BankerClass T = new BankerClass();
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;
}
}
}
}
運作結果如下:
這是一個三個程序,初始系統可用三類資源為{10,8,7}的銀行家算法:
請設定各程序的最大需求矩陣Max:
請輸入程序P0的最大資源需求量:
8 7 5
請輸入程序P1的最大資源需求量:
5 2 5
請輸入程序P2的最大資源需求量:
6 6 2
請設定請各程序配置設定矩陣Alloction:
晴輸入程序P0的配置設定資源量:
3 2 0
晴輸入程序P1的配置設定資源量:
2 0 2
晴輸入程序P2的配置設定資源量:
1 3 2
Available=Available-Alloction.
Need=Max-Alloction.
此時資源配置設定量如下:
程序 Max Alloction Need Available
P0 8 7 5 | 3 2 0 | 5 5 5 | 4 3 3
P1 5 2 5 | 2 0 2 | 3 2 3 |
P2 6 6 2 | 1 3 2 | 5 3 0 |
程序 Work Alloction Need Work+Alloction
P1 4 3 3 | 2 0 2 | 3 2 3 | 6 3 5
P2 6 3 5 | 1 3 2 | 5 3 0 | 7 6 7
P0 7 6 7 | 3 2 0 | 5 5 5 | 10 8 7
此時存在一個安全序列:P1 P2 P0 故目前可配置設定!
請輸入請求資源的程序編号:
請輸入請求各資源的數量:
1 0 0
即程序P0對各資源請求Request:(1,0,0).
此時資源配置設定量如下:
程序 Max Alloction Need Available
P0 8 7 5 | 4 2 0 | 4 5 5 | 3 3 3
P1 5 2 5 | 2 0 2 | 3 2 3 |
P2 6 6 2 | 1 3 2 | 5 3 0 |
現在進入安全算法:
程序 Work Alloction Need Work+Alloction
P1 3 3 3 | 2 0 2 | 3 2 3 | 5 3 5
P2 5 3 5 | 1 3 2 | 5 3 0 | 6 6 7
P0 6 6 7 | 4 2 0 | 4 5 5 | 10 8 7
此時存在一個安全序列:P1 P2 P0 故目前可配置設定!
您是否還要進行請求:y/n?
y
請輸入請求資源的程序編号:
2
請輸入請求各資源的數量:
0 1 0
即程序P2對各資源請求Request:(0,1,0).
此時資源配置設定量如下:
程序 Max Alloction Need Available
P0 8 7 5 | 4 2 0 | 4 5 5 | 3 2 3
P1 5 2 5 | 2 0 2 | 3 2 3 |
P2 6 6 2 | 1 4 2 | 5 2 0 |
現在進入安全算法:
程序 Work Alloction Need Work+Alloction
P1 3 2 3 | 2 0 2 | 3 2 3 | 5 2 5
P2 5 2 5 | 1 4 2 | 5 2 0 | 6 6 7
P0 6 6 7 | 4 2 0 | 4 5 5 | 10 8 7
此時存在一個安全序列:P1 P2 P0 故目前可配置設定!
您是否還要進行請求:y/n?
n
————————————————
版權聲明:本文為CSDN部落客「還我瓶邪」的原創文章,遵循 CC 4.0 BY-SA 版權協定,轉載請附上原文出處連結及本聲明。
原文連結:https://blog.csdn.net/u014634576/article/details/52600826