banker’s algorithm

은행원 알고리즘(Banker’s Algorithm)은 교착 상태(Deadlock)를 방지하는 자원 할당 알고리즘입니다. 이름은 은행의 대출 방식에서 유래되었는데, 은행이 고객에게 대출을 해줄 때 남아 있는 자원을 충분히 보유하고 있는지 확인하듯이, 이 알고리즘은 프로세스에 자원을 할당할 때 시스템이 안정 상태(Safe State)를 유지할 수 있는지 판단하는 방식으로 작동합니다.

1. 개념

   • 목적: 프로세스에 자원을 할당하기 전에 시스템이 안전 상태에 있는지 확인하여, 자원 할당으로 인해 교착 상태가 발생할 가능성이 있으면 할당을 거부합니다.
   • 안전 상태(Safe State): 현재 자원을 할당해도 모든 프로세스가 필요한 자원을 최종적으로 사용할 수 있는 상태입니다. 안전 상태에서는 교착 상태가 발생하지 않습니다.

2. 작동 원리

은행원 알고리즘은 시스템에 남은 자원이 모든 프로세스가 필요로 하는 최종 자원 요구량을 충족할 수 있을 때만 자원을 할당합니다. 이를 위해 각 프로세스와 자원에 대한 최대 요구량(Maximum Requirement), 현재 할당량(Allocation), 잔여 자원(Available)을 확인하며, 아래의 절차를 따릅니다.
1. 요청 확인: 프로세스가 자원을 요청할 때, 요청한 자원이 현재 시스템의 잔여 자원보다 적거나 같은지 확인합니다. 그렇지 않다면 요청을 거부합니다.
2. 가상 할당: 요청한 자원을 가상으로 할당한 후, 시스템이 안전 상태인지 확인합니다.
3. 안전성 검사: 자원을 할당한 상태에서, 모든 프로세스가 최종적으로 자원을 해제할 수 있는지 안전 상태를 검사합니다. 이 과정에서, 필요 시 프로세스가 차례대로 자원을 해제하며 순환적으로 자원이 모든 프로세스에게 제공 가능한지를 확인합니다.
4. 자원 할당/거부: 안전 상태로 확인되면 자원을 실제로 할당합니다. 그렇지 않으면 요청을 거부하고 해당 프로세스는 대기 상태로 들어갑니다.

3. 예제 시나리오

   • 예를 들어, 5개의 프로세스와 3개의 자원이 있는 시스템을 생각해 봅시다.
   • 각 프로세스는 자신이 필요한 최대 자원 요구량과 현재 할당된 자원 수를 시스템에 전달합니다.
   • 특정 프로세스가 자원을 요청할 때 은행원 알고리즘은 가상으로 자원을 할당한 상태를 시뮬레이션하여 시스템이 안정 상태에 머무를 수 있는지 확인합니다.
   • 안정 상태라면 자원을 할당하고, 그렇지 않다면 요청을 거부하여 대기 상태로 둡니다.

4. 장단점

   • 장점: 교착 상태를 예방하며, 시스템이 안정 상태에 머무를 수 있도록 자원을 관리합니다.
   • 단점: 시스템의 자원 요구량을 미리 알고 있어야 하므로, 자원 요구량이 일정하지 않은 상황에서는 구현이 어렵습니다. 또한, 자원 요청과 안전 상태 확인에 많은 계산이 필요하므로 계산량이 큰 시스템에서는 비효율적일 수 있습니다.

요약

은행원 알고리즘은 프로세스에 자원을 할당할 때 시스템이 교착 상태에 빠지지 않도록 안정 상태를 확인하여 자원을 할당하거나 거부하는 기법입니다.