은행 가 알고리즘

글 목록

은행 가 알고리즘

데이터 구조

은행 가 알고리즘

안전성 알고리즘

안전 상태
시스템 이 특정한 프로 세 스 추진 순서에 따라 모든 프로 세 스 Pi 에 필요 한 자원 을 분배 하고 모든 프로 세 스 가 자원 에 대한 최대 수 요 를 만족 시 킬 때 까지 모든 프로 세 스 가 순조롭게 실 행 될 수 있 도록 하 는 것 을 말한다.이 프로 세 스 추진 순 서 를 보안 시퀀스 라 고 합 니 다.
이러한 안전 서열 을 찾 지 못 하면 시스템 은 안전 하지 않 은 상태 에 있다.
잠 금 을 피 하 는 해결 방식 은 시스템 이 자원 분 배 를 할 때 시스템 이 안전 하지 않 은 상태 에 들 어가 지 않도록 하 는 것 이다.
은행 가 알고리즘
한 은행 가 는 그의 고정 자금 을 몇 명의 고객 에 게 빌려 서 이런 고객 들 이 자금 에 대한 최대 수 요 를 만족 시 킨 후에 거래 를 완성 하고 빌 린 자금 을 은행 가 에 게 돌려 줄 수 있 도록 했다.모든 고객 이 몇 번 의 대출 을 받는다 고 가정 하면 모든 고객 은 자신 이 요구 하 는 최대 자금 의 양 을 미리 설명 하고 매번 에 일부 자금 의 신청 을 한다.만약 에 은행 가가 고객 이 자금 에 대한 최대 수 요 량 을 만족 시 키 면 이 고객 은 자금 운영 이 완 료 된 후에 제 한 된 시간 안에 모든 자금 을 은행 가 에 게 돌려 준다.과정 은 다음 과 같다.

고객 의 차관 조작 은 모든 조작 이 완 료 될 때 까지 이 순서 로 진행 된다.

은행 가 는 고객 의 대출 조작 을 판단 하여 안전성 을 확인한다

안전 하 다 면 빌려 주 고 그렇지 않 으 면 잠시 빌려 주지 않 는 다.

데이터 구조
(1) 이용 가능 한 자원 벡터
m 개의 요 소 를 포함 하 는 배열 입 니 다. 모든 요 소 는 하나의 자원 의 수량 을 대표 합 니 다. Availbale [j] = k 대표 시스템 에 현재 Rj 류 자원 k 개가 있 습 니 다.그 수 치 는 이러한 자원 의 분배 와 회수 에 따라 동태 적 으로 변 할 것 이다.
(2) 최대 수요 매트릭스 Max
n×m 의 행렬 은 시스템 n 개 프로 세 스 의 모든 프로 세 스 가 m 류 자원 에 대한 최대 수 요 를 정의 합 니 다.Max[i][j] = k 프로 세 스 i 가 Rj 류 자원 을 필요 로 하 는 최대 수 는 k 개 임 을 나타 낸다.이게 움 직 이지 않 게 조심 하 세 요.
(3) 분배 매트릭스 할당
n×m 의 행렬 은 시스템 의 모든 프로 세 스 가 분 배 된 특정한 자원 의 수량 을 정의 합 니 다.Allocation[i][j] = k i 프로 세 스 가 Rj 류 자원 의 수량 을 k 로 분 배 했 음 을 나타 낸다.
(4) 수요 매트릭스 Need
n×m 의 행렬 은 모든 프로 세 스 가 필요 로 하 는 각종 자원 수 를 나타 낸다.Need[i][j] = k 프로 세 스 i 는 Rj 류 자원 k 개가 있어 야 실행 할 수 있 음 을 나타 낸다.
위의 행렬 사이 에 이런 관계 가 존재 한 다 는 것 이 분명 하 다. Need[i][j] = Max[i][j] - Allocation[i][j]은행 가 알고리즘
Request 가 프로 세 스 를 대표 하 는 요청 벡터 를 가정 하면 Request[i][j] = k 프로 세 스 Pi 가 os 에 k 개의 Rj 류 자원 을 신청 하 는 것 을 나타 낸다.프로 세 스 가 요청 을 보 낸 후 os 는 아래 절차 에 따라 검 사 를 진행 합 니 다.
(1) 만약 Request[i][j] <= Need[i][j] 에 (2) 로 전환 하지 않 으 면 자원 신청 이 잘못 되 었 다 고 생각 합 니 다. 신청 한 자원 이 선언 한 최대 치 를 넘 었 기 때 문 입 니 다.
(2) 만약 Request[i][j] <= Available[j] 자원 이 충분 하 게 분배 된다 면 * * (3) * * 로 전환 합 니 다. 그렇지 않 으 면 프로 세 스 를 기다 리 게 합 니 다.
(3) 시스템 은 자원 을 프로 세 스 Pi 에 배분 하고 데이터 구조의 값 을 수정 합 니 다.Available[j] = Available[j] - Request[i][j] ; Allocation[i][j] = Allocation[i][j] + Request[i][j] ; Need[i][j] = Need[i][j] - Request[i][j] ;
(4) 시스템 이 안전성 알고리즘 을 실행 하고 이번 자원 배분 후 시스템 이 안전 상태 에 있 는 지 확인한다.안전 해야만 자원 을 프로 세 스 Pi 에 정식으로 분배 할 수 있 습 니 다. 안전 하지 않 습 니 다. 이번 탐색 을 폐기 하고 원래 의 자원 분배 상 태 를 회복 하 며 프로 세 스 Pi 가 기다 리 고 있 습 니 다.
보안 알고리즘
(1) 벡터 두 개 설정

작업 벡터 Work 는 시스템 이 제공 할 수 있 는 각종 자원 수 를 나타 내 고 초기 화 시 Work = Available

벡터 Finish 를 완성 하면 시스템 이 특정한 프로 세 스에 충분 한 자원 을 배분 하여 실행 이 완료 되 었 는 지 를 나타 낸다.시작 할 때 Finish [i] = false;

(2) 프로 세 스 집합 에서 실행 가능 한 프로 세 스 를 찾 아 다음 조건 을 만족 시 킵 니 다.Finish[i] = false ; Need[i][] < Work[]
찾 을 수 있다 면, 실행 절차 * (3), 그렇지 않 으 면 실행 (4) * * *
(3) 프로 세 스 Pi 가 자원 을 획득 하면 실행 이 완료 되 고 자원 을 방출 할 수 있 습 니 다.Work = Work + Allocation[i] ; Finish[i] = true ;
돌아 가기 * * (2) * 계속 찾기
(4) 모든 프로 세 스 가 Finish = true 를 만족 시 키 면 시스템 이 안전 상태 에 있 고 잠 금 이 발생 하지 않 습 니 다.
그렇지 않 으 면 시스템 이 안전 하지 않 은 상태 에 처 해 있다.