교착 상태 회피 - 은행원 알고리즘 (Banker's Algorithm)

교착 상태 회피 - 은행원 알고리즘 (Banker's Algorithm)

자원 요청 시 시스템이 안전 상태를 유지하는지 검사하여 데드락을 사전에 회피하는 알고리즘으로, 각 프로세스의 최대 자원 요구량을 사전에 파악하여 안전한 순서를 보장

목적: 데드락 회피, 안전 상태 유지, 자원 효율 활용

특징: 보수적, 안전 상태 검사, 최대 요구량 사전 파악, 안전 순서 존재

용어

• •Available: 현재 가용 자원
• •Max: 각 프로세스 최대 요구량
• •Allocation: 현재 할당량
• •Need: 추가 필요량(Max - Allocation)

안전 상태(Safe State): 모든 프로세스가 완료될 수 있는 순서(안전 순서)가 존재

안전 순서(Safe Sequence): 각 프로세스의 Need ≤ Available + 이전 프로세스 반환 자원

알고리즘

안전 상태 검사(Safety Algorithm): ① Work = Available ② Finish[i] = false ③ Need[i] ≤ Work인 프로세스 찾기 → Work += Allocation[i], Finish[i] = true → ④ 모든 Finish[i] = true면 안전

예시: P0(0,1,0), P1(2,0,0), P2(3,0,2), P3(2,1,1), P4(0,0,2) 자원, Available(3,3,2) → 안전 순서: P1→P3→P4→P2→P0

장점: 데드락 회피, 안전 보장, 자원 활용

단점: 보수적(자원 활용도 낮음), 최대 요구량 사전 파악 어려움, 계산 오버헤드(O(m×n²))

적용사례: 데이터베이스 트랜잭션, 임베디드 시스템, 이론적 연구

비교: 은행원(회피/보수적) vs 탐지·복구(실용적) vs 예방(비효율)

연관: 데드락, 안전 상태, 자원 할당, 회피