은행가 알고리즘

은행가 알고리즘이란

은행가 알고리즘은 교착상태를 회피하는 대표 알고리즘이다.

프로세스가 자원을 요청할 때마다 할당 후에도 안전한지 미리 따져 본다.

안전하면 할당하고, 위험하면 요청을 보류한다.

자료구조

은행가 알고리즘은 Max, Allocation, Need, Available 네 가지 값으로 동작한다.

Need는 Max에서 Allocation을 뺀 값이라 따로 입력하지 않고 계산한다.

Available은 전체 자원에서 모든 Allocation의 합을 뺀 남은 양이다.

안전 상태 판정

안전성 검사는 Need가 Available 이하인 프로세스를 골라 실행시킨다.

그 프로세스가 끝나면 보유 자원을 모두 반납하므로 Available에 더한다.

모든 프로세스가 이 순서로 끝나면 안전 상태이고, 이 순서가 안전 순서열이다.

자원 요청 처리

자원 요청이 들어오면 먼저 두 가지 조건을 확인한다.

요청량이 Need 이하인지 보고, 그다음 현재 Available 이하인지 본다.

두 조건을 통과하면 가상으로 할당해 안전성 검사를 한다. 불안전하면 가상 할당을 취소하고 대기시킨다.

계산 예제

총 자원이 12개이고 할당 합계가 5+2+2=9개이므로 Available은 3개다.

P1은 Need 2가 Available 3 이하라 먼저 실행된다. 반납 후 Available은 5개가 된다.

이어서 P0, P2가 차례로 실행되어 Available이 12개로 돌아오므로 안전 상태다.

예방과 회피 구분

헷갈리기 쉬운 점은 예방과 회피를 섞는 것이다.

예방은 네 가지 조건 중 하나를 구조적으로 없애고, 회피는 할당할 때마다 안전 상태를 검사한다.

은행가 알고리즘의 한계는 프로세스가 최대 요구량을 미리 선언해야 한다는 점이다.

정리

은행가 알고리즘은 자원 할당 전에 안전 상태를 검사해 교착상태를 회피한다.

Need는 Max에서 Allocation을 뺀 값이다. 안전 순서열이 있으면 할당하고 없으면 대기한다.

시험에서는 정의, 자료구조, 안전성 검사 절차가 자주 나온다.