[정보처리기사] 은행가 알고리즘(Banker's Algorithm)

4과목: 프로그래밍 언어활용

 

https://eduon.com/itembank/subjectlist/132

 

은행가 알고리즘(Banker's Algorithm)은 교착상태에 빠질 가능성이 있는지 판단하기 위해 샹태를 '안전상태(safe state)' 와 '불안정상태(unsafe state)' 로 나눠 판단합니다. 

 

교착상태란?

 

교착상태(deadlock)는 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 의미합니다. 

 

예를들어 좁을 길을 지나는 두 대의 자동차가 서로 길을 막고 비켜 주지 않는 상황을 상상해 봅시다. 한 대의 자동차의 양보 없이는 공유된 좁은 길을 두 대 모두 지나가는 방법이 없을 것입니다. 

 

여기서 두 대의 자동차를 프로세스로 좁은 길(받대편으로 건너가려고 하는 상황)을 공유 자원으로 생각한다면 두 개의 프로세스가 선점하고 있는 자신의 자원은 양보하지 않은채 상대방 쪽 (좁은 길의 건너편) 자원을 요구하는 상황이라고 생각하면 될것 같습니다. 

 

교착상태 조건

 

교착상태 조건은 다음 4가지 조건을 동시에 필요 충분 조건으로 만족해야 합니다.

 

• 상호 배제(Mutual Exclusion): 적어도 하나의 자원은 반드시 비 공유 되는 상태에서 하나의 프로세스가 점유한다. 
• 점유와 대기(Hold and Wait): 적어도 하나의 자원을 점유하면서, 다른 프로세스에 의해 점유된 다른 자원을 요구하고 할당받기를 기다린다.
• 비 선점(No Preemption): 작업의 수행이 끝날 때까지 해당자원을 반환하지 않는다.
• 환형대기(Circular Wait): 각 프로세스는 환형 내의 이전 프로세스가 요청하는 자원을 점유하고 요청한다.

 

 교착상태 해결방안

 

교착상태 해결방안은 총 4종류로 교착상태 예방, 회피, 탐지, 복구가 있습니다.

오늘 다룰 주제인 은행가 알고리즘은 교착상태 회피 방법으로, 데드락 가능성이 있는지 없는지 운영체제가 검사하고 가능성이 없을 경우에만 자원을 할당함으로써 문제 발생을 피하는 방법입니다. 

 

 

출처: https://jhnyang.tistory.com/102