Banker's 알고리즘으로 안전 상태를 검사하는 방법

자원을 배분하기 전에 끝까지 완료될 수 있는지 확인한다

Banker's 알고리즘은 Dijkstra가 제안한 교착상태 회피 기법으로, 운영체제가 자원 요청을 받았을 때 해당 자원을 배분한 뒤에도 시스템이 안전 상태로 남는지를 먼저 확인한다. 은행이 대출을 승인한 뒤에도 모든 고객의 요구를 감당할 수 있는지 따지는 방식처럼, 모든 프로세스가 어떤 순서로든 완료할 수 있다면 요청을 수락하고 그렇지 않으면 할당하지 않는다.

이 방식은 교착상태를 예방하는 기법과 달리 실행 중인 자원 요청을 대상으로 판단한다. 탐지처럼 교착상태가 발생한 뒤 처리하는 것도 아니며, 교착상태를 무시하는 Ostrich Algorithm과도 다르다.

⤢✕

안전 순서가 있으면 안전 상태다

안전 상태는 모든 프로세스가 순차적으로 필요한 자원을 받고 종료할 수 있는 상태다. 이때 가능한 실행 순서를 안전 순서라고 하며, <P1, P2, P3, ..., Pn>처럼 나타낸다.

안전 순서에서는 각 프로세스 Pi가 필요한 자원을 얻어 종료하고, 반환한 자원이 다음 프로세스의 실행에 쓰일 수 있다. 조건은 다음과 같이 표현할 수 있다.

Need_i ≤ Available + Σ(Allocation_j), j < i

반대로 안전 순서를 찾지 못하면 불안전 상태다. 불안전 상태가 곧 교착상태를 의미하는 것은 아니지만, 이후 추가 자원 요청에서 교착상태가 발생할 수 있다.

⤢✕

안전성 판단에 쓰는 상태값

Banker's 알고리즘은 사용 가능한 자원, 프로세스별 최대 요구량, 현재 할당량, 그리고 남은 요구량을 함께 관리한다.

Available은 현재 줄 수 있는 자원이다

각 자원 유형별로 아직 할당되지 않은 수량을 나타낸다.

Available[j] = k

여기서 j는 자원 유형(Resource Type)이고 k는 사용 가능한 j 자원의 개수다.

Available = [3, 2, 2]

이 값은 자원 A가 3개, 자원 B가 2개, 자원 C가 2개 사용 가능하다는 뜻이다.

Max는 프로세스가 요구할 수 있는 상한이다

Max는 프로세스가 작업을 마칠 때까지 필요로 할 수 있는 자원의 최대 수량이다.

Max[i, j] = k

i는 프로세스 번호, j는 자원 유형, k는 프로세스 i가 필요로 하는 j 자원의 최대 개수다.

        A  B  C
P0:     7  5  3
P1:     3  2  2
P2:     9  0  2

Allocation은 이미 배분된 자원이다

현재 각 프로세스에 할당된 자원 수량은 Allocation에 기록한다.

Allocation[i, j] = k

i는 프로세스 번호, j는 자원 유형, k는 프로세스 i에 현재 할당된 j 자원의 개수다.

        A  B  C
P0:     0  1  0
P1:     2  0  0
P2:     3  0  2

Need는 작업을 마치기 위해 남은 요구량이다

Need는 최대 요구량에서 현재 할당량을 뺀 값이다.

Need[i, j] = Max[i, j] - Allocation[i, j]

프로세스 i가 종료하려면 추가로 필요한 j 자원의 개수를 의미한다.

Need = Max - Allocation

        A  B  C
P0:     7  4  3  (7-0, 5-1, 3-0)
P1:     1  2  2  (3-2, 2-0, 2-0)
P2:     6  0  0  (9-3, 0-0, 2-2)

⤢✕

요청을 가상으로 배분한 뒤 되돌릴 수 있게 한다

자원 요청은 먼저 프로세스의 최대 요구 범위를 넘지 않는지 확인한다. Request_i ≤ Need_i가 성립하지 않으면 최대 요구량을 초과한 요청이므로 에러로 처리한다.

그다음 Request_i ≤ Available인지 검사한다. 사용 가능한 자원이 부족하면 요청은 대기한다. 두 조건을 통과하면 실제 배분 전에 다음처럼 가상 할당을 수행한다.

Available = Available - Request_i
Allocation_i = Allocation_i + Request_i
Need_i = Need_i - Request_i

가상 할당 상태에서 안전성 검사를 실행한다. 안전 상태라면 할당을 유지하고, 불안전 상태라면 값을 롤백한 뒤 요청을 대기시킨다.

반환 자원까지 반영해 완료 가능한 프로세스를 찾는다

안전성 검사는 현재 가용 자원을 Work에 복사하고, 각 프로세스의 완료 여부를 Finish로 관리하며 시작한다.

Work = Available
Finish[i] = false for all i

아직 완료되지 않았고 Need_i ≤ Work를 만족하는 프로세스를 찾는다. 해당 프로세스는 완료할 수 있으므로 할당받았던 자원을 Work에 반환한 것으로 처리한다.

Finish[i] == false이고 Need_i ≤ Work인 프로세스 i 찾기

찾으면:

Work = Work + Allocation_i
Finish[i] = true

찾지 못하면 종료

모든 Finish[i] == true이면 안전 상태이고, 일부 Finish[i] == false로 남으면 불안전 상태다.

⤢✕

상태 행렬에서 안전 순서를 찾는 예

다음은 사용 가능한 자원과 프로세스별 Allocation, Max, Need를 둔 초기 상태다.

Available = [3, 3, 2]

        Allocation    Max        Need
        A  B  C       A  B  C    A  B  C
P0:     0  1  0       7  5  3    7  4  3
P1:     2  0  0       3  2  2    1  2  2
P2:     3  0  2       9  0  2    6  0  0
P3:     2  1  1       2  2  2    0  1  1
P4:     0  0  2       4  3  3    4  3  1

Work에서 시작해 실행 가능한 프로세스를 고르고, 그 프로세스가 반환하는 자원을 다음 판단에 반영한다.

Work = [3, 3, 2]

순서:
1. P1: Need = [1,2,2] ≤ Work [3,3,2] → 실행 가능
   Work = [3,3,2] + [2,0,0] = [5,3,2]

2. P3: Need = [0,1,1] ≤ Work [5,3,2] → 실행 가능
   Work = [5,3,2] + [2,1,1] = [7,4,3]

3. P4: Need = [4,3,1] ≤ Work [7,4,3] → 실행 가능
   Work = [7,4,3] + [0,0,2] = [7,4,5]

4. P2: Need = [6,0,0] ≤ Work [7,4,5] → 실행 가능
   Work = [7,4,5] + [3,0,2] = [10,4,7]

5. P0: Need = [7,4,3] ≤ Work [10,4,7] → 실행 가능
   Work = [10,4,7] + [0,1,0] = [10,5,7]

안전 순서: <P1, P3, P4, P2, P0>
결과: 안전 상태

이 상태에서 P1이 [1,0,2]를 요청하면 가상 할당 후에도 안전 순서가 존재하므로 요청을 승인한다.

가상 할당:
Available = [3,3,2] - [1,0,2] = [2,3,0]
Allocation_P1 = [2,0,0] + [1,0,2] = [3,0,2]
Need_P1 = [1,2,2] - [1,0,2] = [0,2,0]

안전성 검사: 안전 순서 존재 → 할당 승인

안전성을 얻는 대신 감수하는 제약

Banker's 알고리즘은 자원 할당 단계에서 교착상태를 원천 차단하고 100% 안전성을 보장한다. 문제가 발생하기 전에 차단하므로 복구 비용이 없고 동작을 예측하기 쉽다.

반면 각 프로세스의 최대 자원 요구량을 미리 알아야 한다. 실제 요구량을 사전에 파악하기 어렵고, 동적 환경에서는 부적합할 수 있다. 과대 추정은 자원 낭비로 이어진다. 자원 수가 고정되어 있어 동적 자원 추가나 제거가 어렵다는 점도 제약이다.

또한 요청마다 안전성 검사를 수행하므로 프로세스 수가 많아질수록 느려질 수 있으며, 계산 복잡도는 O(m × n²)이다. 여기서 m은 자원 종류, n은 프로세스 수다. 실제 교착상태가 발생하지 않을 상황까지 거부할 수 있어 자원 활용률 저하와 병목 현상도 발생할 수 있다.

⤢✕

다른 교착상태 처리 방식과의 차이

구분	예방 (Prevention)	회피 (Avoidance)	탐지 (Detection)	무시 (Ignorance)
대표 기법	4가지 조건 제거	Banker's 알고리즘	Deadlock Detection Graph	Ostrich Algorithm
시점	설계 단계	실행 중	실행 중	발생 후
오버헤드	낮음	높음	중간	없음
자원 활용	낮음	중간	높음	높음
안전성	높음	높음	중간	낮음
적용	임베디드 시스템	중요 시스템	일반 시스템	데스크톱 OS