[ 운영체제 ] Banker's Algorithm

데드락 해결 방법 중 회피(Avoidance)를 다루다가 Banker's Algorithm 내용이 길어져서 따로 정리한다. Banker's Algorithm은 자원의 인스턴스 개수가 두 개 이상일 때 사용할 수 있는 회피 방법이다. 이 알고리즘에서 사용하는 자료구조는 아래와 같고, 이는 이미 알고 있다는 가정 하에 시작한다.

 

int n = number of Processes
int m = number of Resource Types

int Available[m] = 각 Resource Type 별로 이용 가능한 instance 개수
// Available[j] = k, R_j의 인스턴스 개수가 k 개라는 뜻

int Max[n][m] = 각 프로세스의(n) 자원별(m) 최대 요구 인스턴스 수
// Max[i][j] = k, P_i는 R_j의 인스턴스를 최대 k개 요구할 수 있다

int Allocation[n][m] = 현재 각 프로세스에 할당되어 있는 자원별 인스턴스 수
// Allocation[i][j] = k, P_i는 현재 R_j의 인스턴스를 k개 할당받음

int Need[n][m] = 각 프로세스가 실행 종료를 위해 필요로 하는 자원별 인스턴스 수
// Need[i][j] = k, P_i는 실행 종료까지 R_j의 인스턴스 k개를 할당받아야 함
// Need[i][j] = Max[i][j] - Allocation[i][j]

 

위 정보는 알고 있다는 가정 하에 시작하는 것을 명심하자. Banker's Algorithm의 큰 흐름은 아래와 같다. 

 

1. Resource-Request Algorithm → 요청 이후가 Safe State면 요청 수락, 아니면 기각.

1번을 계속 반복. Safety Algorithm은 Safe Sequence가 있는지 확인하는 알고리즘으로, 1번에서 요청 이후가 Safe State인지 판별할 때 쓰인다. 

 

위 흐름을 그대로 따라가면 된다. 각 알고리즘의 상세 내용은 곧 다룬다. 먼저 큰 흐름만 이해하자.

 

용어가 약간 헷갈릴 수 있는데, Resource-Request Algorithm이 Banker's Algorithm이라고 생각하면 된다. 따라서 앞으로 두 알고리즘은 같은 것으로 이해하면 된다. Safety Algorithm은 Banker's Algorithm 안에서 사용되는 알고리즘이기 때문에, Safety Algorithm에 대한 이해가 선행되어 있어야 한다. Safety Algorithm의 단계는 아래와 같다. 

 

1. Need_i <= Available 인 프로세스를 찾는다. 즉, 가용 자원으로 작업을 완료할 수 있는 프로세스 P_i 를 찾는다.
2. P_i  작업을 완료시키고, P_i 가 해제한 자원을 Available에 더해준다. 

모든 프로세스가 작업을 완료할 때까지 1-2 번을 계속 반복한다.
작업이 완료되지 않은 프로세스가 있으면 해당 시스템은 Unsafe State.

 

예제로 한 번 풀어보면 정말 쉽다. 따라서 Safety Algorithm은 예제 풀이를 먼저 하고 수도 코드를 다루겠다.

Safety Algorithm 예제

프로세스의 개수 = 5 (P0 ~ P4)
자원 타입의 개수 = 3 (R_A, R_B, R_C)

R_A의 인스턴스 수 = 10
R_B의 인스턴스 수 = 5
R_C의 인스턴스 수 = 7

문제 : 초기값이 아래와 같다고 할 때, 이 시스템의 Safe Sequence는?

참고!! 문제의 Work 배열은 Available 배열에 해당함.

 

Snapshot at time T_0

 

먼저, 문제에는 Need 배열이 따로 주어지지 않았기 때문에 주어진 값으로 도출해내야 한다. 위에서 Need 배열은 Max - Allocation 값과 일치한다고 했다. 따라서 Need 배열을 적어주면 아래와 같다. 

 

Need 배열 추가

 

이 상태에서 safety Algorithm을 그대로 적용하면 된다. 먼저 현재 가용 자원으로 Need를 충족하는 프로세스를 살펴보자. 작업을 완료할 수 있는 프로세스는 P_1과 P_3이다. P_1을 먼저 완료 시키면, P_1은 자원을 해제할 것이고 그 결과 Work 배열은 원래 값에서 A만 2 증가할 것이다. 그 이유는 Need 만큼은 어차피 할당 후 돌려받기 때문에 제로섬이고, 새로 들어오는 인스턴스는 원래 P_1이 보유중인 A 인스턴스 2개 뿐이기 때문이다. P_1이 완료된 후의 모습은 아래와 같다. 

 

P_1 종료 후 모습

 

같은 원리로 P_3 → P_4 → P_0 → P_2 순서로 프로세스를 완료하면 정상적으로 수행됨을 알 수 있을 것이다. 이는 직접 해보기를 바란다.

 

그럼 이제 Safety Algorithm을 수도 코드로 살펴보자. Safety Algorithm은 아까 말했듯이 Safe Sequence가 있는지 판단하는 알고리즘이다. 따라서 반환값은 boolean 값이다.

Safety Algorithm

n = 프로세스 개수
m = 자원 타입 개수

1. Work[m], Finish[n]
--- 초기화
--- Work[m] = Available[m]
--- Finish[i] = false (i = 0, 1, 2, ..., n-1)

2. 아래 두 조건을 만족하는 i 탐색
--- a) Finish[i] == false // 아직 덜 끝난 프로세스 찾음
--- b) Need_i <= Work // 가용 자원으로 P_i 끝낼 수 있는지 검사
-- i를 찾을 수 없으면 4번으로, i를 찾았으면 3번으로

3. 
- Work = Work + Allocation_i // P_i 완료시키고 자원 받음
- Finish[i] = true // P_i 완료 처리
- 2번으로

4. 
- if 모든 i에 대해 Finish[i] == true 면, 시스템은 Safe State
- else Unsafe State

 

위에서 수작업으로 풀었던 예제와 비교해서 보기를 바란다. 만약 예제를 잘 풀었으면 Safety Algorithm은 어렵지 않게 이해할 수 있을 것이다. 이제 거의 끝났다. 마지막으로 Resource-Request Algorithm만 알아보면 된다. 이 알고리즘이 진짜 Banker's Algorithm이다. 

Resource-Request Algorithm for Process  P_i

알고리즘을 설명하기 전에 이 알고리즘의 목적이 무엇인지 정확하게 알고 가자. 이 알고리즘의 목적은 요청 이후에 Safe State를 유지하는 것이다. 만약에 요청 이후가 Unsafe State라면 이전 상태로 롤백한다. 

 

Request = P_i의 request 배열
Request_i[j] = k // P_i 가 R_j의 인스턴스 k 개를 요청

1. 
- if Request_i <= Need_i, 2번으로 이동 // 요청 가능하기 때문
- else, 프로세스가 최대 요구치를 넘겼으므로 에러 호출

2. 
- if Request_i <= Available, 3번으로 이동 // 요청 가능하기 때문
- else, P_i는 대기

3. 값 갱신
- Available = Available - Request_i
- Allocation_i = Allocation_i + Request_i
- Need_i = Need_i - Request_i
--- if Safe, P_i에게 자원 할당 // 그대로 진행, Safety Algorithm 사용
--- else, P_i는 대기, 이전 resource state(위에 갱신값) 복구 // 롤백

 

 

 

뭔가 어려워 보이지만 알고보면 별거 없다. 이해가 안 되면 반복해서 읽어보기를 바란다. 예제를 활용하면 빨리 이해할 수 있을 것이다.