은행 가 알고리즘 (자바 구현)
24841 단어 문 제 를 풀다
은행 가 알고리즘 (Banker 's Algorithm) 은 잠 금 (Deadlock) 을 피 하 는 유명한 알고리즘 으로 에 즈 그 디 제 스 트 라 가 1965 년 에 T. H. E 시스템 을 위해 디자인 한 잠 금 발생 을 피 하 는 알고리즘 이다.그것 은 은행 대출 시스템 의 분배 전략 을 바탕 으로 시스템 의 안전 운행 을 판단 하고 확보한다.우 리 는 운영 체 제 를 은행 가로 볼 수 있다. 운영 체제 관리의 자원 은 은행 가 관리의 자금 에 해당 하고 프로 세 스 가 운영 체제 에 자원 분 배 를 요청 하 는 것 은 사용자 가 은행 가 에 게 대출 하 는 것 과 같다.자금 의 안전 을 확보 하기 위해 은행 가 는 (1) 한 고객 이 자금 에 대한 최대 수 요 량 이 은행 가 기 존의 자금 을 초과 하지 않 을 때 이 고객 을 받 아들 일 수 있다 고 규정 했다.(2) 고객 은 분할 대출 을 할 수 있 지만 대출 의 총 수 요 량 은 최대 수 요 량 을 초과 할 수 없다.(3) 은행 가 기 존의 자금 이 고객 이 필요 로 하 는 대출 액 수 를 만족 시 키 지 못 할 때 고객 의 대출 은 지불 을 연기 할 수 있 지만 고객 으로 하여 금 제 한 된 시간 에 대출 을 받 게 한다.(4) 고객 이 필요 한 모든 자금 을 받 은 후에 반드시 제 한 된 시간 안에 모든 자금 을 돌려 줄 수 있다.
은행 가 알고리즘 데이터 구조:
다음 과 같은 세 가지 과정 을 포함한다. 
다음은 이 세 가지 과정 을 요약 합 니 다. 첫째, Init () 프로 세 스 도 를 초기 화 합 니 다. 사용자 가 데 이 터 를 입력 하고 각각 AVAILABLE, MAX, ALLOCATION, NEED 에 값 을 부여 합 니 다.
2. 안전성 검사 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. 안전 이란 시스템 이 하나의 서열 을 찾 아 모든 자원 을 분배 하 는 것 을 말 합 니 다.
3. 은행 가 알고리즘 Bank ()절차 1. 잠 금 을 피 하 는 방법 에서 가 하 는 제한 조건 이 약 하고 만 족 스 러 운 시스템 성능 을 얻 을 수 있 습 니 다. 이 방법 에서 시스템 의 상 태 를 안전 상태 와 안전 하지 않 은 상태 로 나 누 어 시스템 이 항상 안전 상태 에 있 으 면 생사 의 자 물 쇠 를 피 할 수 있 습 니 다. 2. 은행 가 알고리즘 의 기본 사상 은 자원 을 분배 하기 전에 시스템 이 맞 는 지 판단 하 는 것 입 니 다.안전 합 니 다. 만약 에 분배 합 니 다. 이것 은 가장 대표 적 인 잠 금 을 피 하 는 알고리즘 입 니 다. 3. 프로 세 스 cusneed 가 request [i] 를 요청 하면 은행 가 알고리즘 은 다음 과 같은 규칙 에 따라 판단 합 니 다.; 그렇지 않 으 면 오류 가 발생 합 니 다. (3) 시스템 에서 자원 배분 을 탐색 하고 관련 데 이 터 를 수정 합 니 다. AVAILABLE [i] - = request [cusneed] [i]; ALLOCATION [cusneed] [i] + = request [cusneed] [i]; NEED [cusneed] [i] - = request [cusneed] [i]; (4) 시스템 이 안전성 검 사 를 수행 하고 안전 하면 분배 가 성립 됩 니 다. 그렇지 않 으 면 탐험 적 분 배 를 폐기 하고 시스템 을 원상 태 로 복원 합 니 다.
구체 적 인 자바 구현 코드 는 다음 과 같 습 니 다.
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[i][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[i][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[i] = Available[i] - Alloction[j][i];
}
}
for (int i = 0; i < 3; i++) {//设置Need矩阵
for (int j = 0; j < 3; j++) {
Need[i][j] = Max[i][j] - Alloction[i][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[i][j]+" ");
}
System.out.print("| ");
for(int j=0;j<3;j++){
System.out.print(Alloction[i][j]+" ");
}
System.out.print("| ");
for(int j=0;j<3;j++){
System.out.print(Need[i][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[i] -= Request[num][i];
Alloction[num][i] += Request[num][i];
Need[num][i] -= Request[num][i];
}
} 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[i] = Available[i];
}
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[i]==false&&Need[i][0]<=Work[0]&&Need[i][1]<=Work[1]&&Need[i][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[i][j];
}
Finish[i]=true;//当当前进程能满足时
S[count]=i;//设置当前序列排号
count++;//满足进程数加1
for(int j=0;j<3;j++){
System.out.print(Alloction[i][j]+" ");
}
System.out.print("| ");
for(int j=0;j<3;j++){
System.out.print(Need[i][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[i]+" ");
}
System.out.println("故当前可分配！");
break;//跳出循环
}
if(count//判断完成进程数是否小于循环圈数
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, 25 프로 세 스 P2 의 최대 자원 수 요 량 을 입력 하 십시오.자 원 량: 202 맑 음 입력 프로 세 스 P2 의 배분 자 원 량: 1, 3, 2 Available = Available - Alloction. Need = Max - Alloction. 이때 자원 분 배 량 은 다음 과 같다.6 3 5 P2 6 3 5 | 1 3 2 | 5 3 0 | 7 6 7 P0 7 7 | 3 2 0 | 5 5 | 10 8 7 이 때 하나의 안전 서열 이 존재 합 니 다. P1 P2 P0 이 므 로 현재 분배 할 수 있 습 니 다! 요청 자원 의 프로 세 스 번 호 를 입력 하 십시오. 0 각 자원 을 요청 하 는 수량 을 입력 하 십시오. 1 0 즉 프로 세 스 P0 이 각 자원 에 대한 요청 Request: (1, 0, 0). 이때 자원 분 배 량 은 다음 과 같 습 니 다. 프로 세 스 Max Alluction Need Available P0 8 7 5 | 4 2 0 | 4 5 | 3 3 P1 5 5 | 2 2 | 3 2 3 | P2 6 2 | 1 3 2 | 5 3 0 | 현재 보안 알고리즘 에 들 어 갑 니 다.보안 시퀀스: P1 P2 P0 이 므 로 현재 할당 할 수 있 습 니 다. 요청 하 시 겠 습 니까? y/n? y 요청 자원 의 프로 세 스 번 호 를 입력 하 십시오. 2 요청 자원 의 수량 을 입력 하 십시오. 0, 10 즉 프로 세 스 P2 가 각 자원 에 대한 요청 Request: (0, 1, 0). 이때 자원 분 배 량 은 다음 과 같 습 니 다. 프로 세 스 Max Alluction Need Available P0 8 7 5 | 4 2 0 | 4 5 | 3 2 3 P1 5 5 | 2 2 | 3 2 3 | P2 6 2 | 1 4 2 | 5 20 | 현재 보안 알고리즘 에 들 어 갑 니 다. 프로 세 스 Work Alluction Need Work + Alluction P1 3 2 3 | 2 2 | 3 2 3 | 5 2 5 P2 5 25 | 1 4 2 | 5 2 2 0 | 6 7 P0 6 6 7 | 4 2 0 | 4 5 5 5 5 | 10 8 7 이때 존재 합 니 다.보안 시퀀스: P1 P2 P0 이 므 로 현재 할당 가능 합 니 다! 요청 하 시 겠 습 니까? y/n? n
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
LeetCode Java First 400 문제 풀이 - 032Longest Valid Parentheses Hard Given a string containing just the characters '(' and ')' , find the length of the ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
