은행가 알고리즘은 운영체제에서 교착 상태(Deadlock)를 예방하기 위해 사용하는 대표적인 알고리즘입니다. 마치 은행이 대출 신청을 승인하기 전에 고객의 신용도와 상환 능력을 종합적으로 고려하여 파산 위험을 관리하는 것처럼, 은행가 알고리즘은 각 프로세스가 필요로 하는 자원을 미리 파악하고, 자원 할당이 시스템 전체의 교착 상태를 유발하지 않는지를 검사하여 안전한 자원 할당을 보장합니다.
은행가 알고리즘의 기본 개념
은행가 알고리즘은 다음과 같은 정보들을 기반으로 동작합니다.
- 프로세스(Process): 시스템 내에서 실행되는 작업 단위입니다.
- 자원(Resource): 프로세스가 작업을 수행하기 위해 필요한 CPU, 메모리, 입출력 장치 등과 같은 유한한 자원입니다.
- 최대 필요 자원(Maximum Need): 각 프로세스가 작업을 완료하기 위해 필요한 자원의 최대량입니다.
- 현재 할당된 자원(Currently Allocated): 각 프로세스에게 현재 할당된 자원의 양입니다.
- 가용 자원(Available): 시스템 내에서 현재 사용 가능한 자원의 총량입니다.
은행가 알고리즘의 핵심은 '안전 상태(Safe State)'를 유지하는 것입니다. 안전 상태란, 시스템 내의 모든 프로세스가 자신에게 할당된 자원을 모두 사용한 후에도, 다른 프로세스가 작업을 완료할 수 있는 자원 할당 순서가 적어도 하나 이상 존재하는 상태를 의미합니다. 만약 어떤 프로세스에게도 자원을 할당할 수 없는 상태가 된다면, 그 상태는 '안전하지 않은 상태(Unsafe State)'이며, 이 상태에서는 교착 상태가 발생할 가능성이 높습니다.
은행가 알고리즘의 동작 과정
프로세스가 새로운 자원을 요청하면, 은행가 알고리즘은 다음과 같은 단계를 거쳐 자원 할당 여부를 결정합니다.
- 요청 유효성 검사: 프로세스의 자원 요청량이 해당 프로세스가 미래에 필요로 할 최대 자원량을 초과하지 않는지 확인합니다. 초과한다면 오류로 처리합니다.
- 가용 자원과 비교: 요청된 자원량이 현재 시스템에 가용 가능한 자원량보다 적거나 같은지 확인합니다. 만약 가용 자원보다 많다면, 해당 프로세스는 기다려야 합니다.
- 가상 할당: 요청된 자원을 해당 프로세스에 가상으로 할당합니다. 즉, 가용 자원에서 요청량을 빼고, 해당 프로세스의 현재 할당된 자원량을 늘립니다.
- 안전성 검사: 가상 할당 후, 시스템이 '안전 상태'를 유지하는지 검사합니다. 이를 위해 '안전 알고리즘'이 사용됩니다.
- 안전 알고리즘: 현재 시스템 상태에서, 작업을 완료할 수 있는 프로세스를 찾아냅니다. 해당 프로세스가 작업을 완료하면, 할당되었던 자원을 시스템에 반환한다고 가정하고, 이 과정을 모든 프로세스가 완료될 때까지 반복합니다. 만약 모든 프로세스가 작업을 완료할 수 있다면, 시스템은 안전 상태입니다.
- 결정: 만약 가상 할당 후에도 시스템이 안전 상태를 유지한다면, 요청된 자원을 실제로 할당합니다. 그렇지 않다면, 해당 프로세스는 자원을 할당받지 못하고 기다려야 합니다.
은행가 알고리즘 예시
간단한 예시를 통해 은행가 알고리즘을 이해해 봅시다. 시스템에 3개의 프로세스 P0, P1, P2와 2개의 자원 타입 R1, R2가 있다고 가정합니다.
- 가용 자원 (Available): R1 = 1, R2 = 1
- 최대 필요 자원 (Maximum Need):
- P0: R1=2, R2=1
- P1: R1=1, R2=2
- P2: R1=3, R2=2
- 현재 할당된 자원 (Currently Allocated):
- P0: R1=1, R2=0
- P1: R1=0, R2=1
- P2: R1=0, R2=0
이때, 각 프로세스의 미래에 필요한 자원 (Need) 은 최대 필요 자원에서 현재 할당된 자원을 뺀 값입니다.
- P0 Need: R1=1, R2=1
- P1 Need: R1=1, R2=1
- P2 Need: R1=3, R2=2
이제 P0가 R1=1, R2=1을 추가로 요청했다고 가정해 봅시다.
-
요청 유효성 검사: P0의 요청량 (R1=1, R2=1)은 P0의 최대 필요량 (R1=1, R2=1)을 초과하지 않습니다. 유효합니다.
-
가용 자원과 비교: 요청량 (R1=1, R2=1)은 가용 자원 (R1=1, R2=1)보다 많지 않습니다. 할당 가능성이 있습니다.
-
가상 할당: 가용 자원에서 요청량을 빼면 (R1=1-1=0, R2=1-1=0) 남는 가용 자원은 0이 됩니다. P0에 가상으로 할당하면 P0의 현재 할당량은 (R1=1+1=2, R2=0+1=1)이 됩니다.
-
안전성 검사: 가상 할당 후 시스템 상태는 다음과 같습니다.
- Available: R1=0, R2=0
- P0: Need = R1=0, R2=0 (작업 완료)
- P1: Need = R1=1, R2=1
- P2: Need = R1=3, R2=2
이 상태에서 작업을 완료할 수 있는 프로세스가 있을까요?
- P0은 이미 Need가 0이므로 작업을 완료할 수 있습니다. P0이 완료되면 자원을 반환한다고 가정하면, Available은 (R1=0, R2=0) 그대로입니다.
- 이제 P1을 봅시다. P1의 Need는 (R1=1, R2=1)입니다. 현재 Available (R1=0, R2=0)으로는 P1의 작업을 완료할 수 없습니다.
- P2도 마찬가지입니다. P2의 Need는 (R1=3, R2=2)이며, Available (R1=0, R2=0)으로는 완료할 수 없습니다.
모든 프로세스가 작업을 완료할 수 있는 순서를 찾지 못했으므로, 이 가상 할당은 시스템을 '안전하지 않은 상태'로 만듭니다.
-
결정: 따라서 P0의 자원 요청 (R1=1, R2=1)은 거부됩니다. P0은 가용 자원이 충분해질 때까지 기다려야 합니다.
만약 P0가 R1=0, R2=1만 요청했다면 어떻게 될까요?
- 유효성 검사 및 가용 자원 비교 통과.
- 가상 할당: Available = (R1=1, R2=0), P0 Allocated = (R1=1, R2=1)
- 안전성 검사:
- Available: R1=1, R2=0
- P0 Need: R1=0, R2=0 (완료 가능)
- P1 Need: R1=1, R2=1
- P2 Need: R1=3, R2=2
- P0 완료 후 Available = (R1=1, R2=0).
- P1의 Need (R1=1, R2=1)은 Available (R1=1, R2=0)으로 완료할 수 없습니다.
- P2의 Need (R1=3, R2=2)도 완료할 수 없습니다.
- 이 경우에도 안전한 순서를 찾지 못하므로, P0의 요청은 거부됩니다.
은행가 알고리즘의 장단점
장점:
- 교착 상태를 효과적으로 예방할 수 있습니다.
- 시스템의 안정성을 높여줍니다.
단점:
- 각 프로세스의 최대 필요 자원을 미리 정확히 알아야 하는데, 이는 실제 시스템에서 예측하기 어려운 경우가 많습니다.
- 모든 프로세스의 최대 필요 자원을 미리 파악하고 안전성 검사를 수행해야 하므로, 시스템의 전반적인 처리량이 감소할 수 있습니다.
- 자원 할당 시마다 안전성 검사를 수행해야 하므로 오버헤드가 발생합니다.
은행가 알고리즘은 교착 상태를 방지하는 강력한 방법이지만, 그 복잡성과 요구사항 때문에 실제 시스템에서는 다른 교착 상태 처리 기법(탐지 및 복구 등)과 함께 사용되거나, 더 가벼운 예방 기법이 선호되기도 합니다.