[운영체제] 만화로 알아보는 은행원 알고리즘(Banker's algorithm) (교착상태 회피 알고리즘)

교착상태 회피를 구현하는 방법 중 하나인 에츠허르 데이크스트라가 제시한 은행원 알고리즘(banker's algorithm)의 예시.

교착 상태는 프로세스가 서로 자원을 점유하려고 하는 과정에서 아래 네 가지 필요조건이 동시에 충족될 경우 발생합니다.

1. 상호 배제 : 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원입니다.
2. 비선점 : 한 프로세스가 사용하는 자원은 다른 프로세스가 빼앗을 수 없습니다.
3. 점유와 대기 : 프로세스는 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태입니다.
4. 원형 대기 : 점유와 대기를 하는 프로세스 간 사이클이 발생합니다.

교착상태가 발생할 경우 해결 방법은 세 가지입니다.

1. 예방
2. 회피
3. 검출과 회복

이 중 은행원 알고리즘은 교착상태 회피를 위한 알고리즘 중 하나로, 다익스트라 알고리즘으로 유명한 에츠허르 데이크스트라가 제시했습니다.

시스템 교착을 일으키지 않고 각 프로세스가 요구한 양 만큼의 자원을 할당해줄 수 있는 순서를 안전순서열이라고 하며, 안전순서열이 존재하는 상태를 안전상태, 존재하지 않는 상태를 불안전상태라고 합니다.

참고

• 쉽게 배우는 운영체제(조성호 저)
• https://jhnyang.tistory.com/102